Numerical methods for distributed stochastic compositional optimization problems with aggregative structure

Shengchao Zhao, Yongchao LiuOptim. Methods Softw 2025 · DOI

TL;DR

This paper introduces novel distributed algorithms (D-ASCGD and CD-ASCGD) for solving complex optimization problems where multiple agents collaborate over a network. These methods efficiently handle "compositional" objective functions (functions of functions) with an "aggregative" structure, achieving optimal convergence rates even with limited communication.

What Problem Does This Paper Address?

Many real-world problems, from machine learning to finance, involve optimizing a complex objective function that is a composition of multiple functions. When these optimizations are distributed across a network of agents, and each agent's contribution to the inner function is aggregated, the problem becomes a "distributed stochastic compositional optimization problem with aggregative structure." Traditional methods struggle with the communication overhead and the inherent complexity of these problems. This paper aims to develop efficient and scalable numerical methods for solving such problems in a decentralized manner.

Methods

The core of the proposed methods lies in combining several advanced techniques:

  • Hybrid Variance Reduction: To efficiently estimate the values and gradients of each agent's private "inner-level" function, the authors employ a hybrid variance reduction technique. This helps reduce the noise inherent in stochastic optimization.
  • Dynamic Average Consensus: To track the aggregated information of the inner-level function across the network, a dynamic average consensus mechanism is used. This allows agents to collectively agree on a value without a central coordinator.
  • Distributed Stochastic Gradient Descent (DSGD): The standard DSGD framework is adapted to incorporate the above techniques for the compositional and aggregative structure. This leads to the Distributed Aggregative Stochastic Compositional Gradient Descent (D-ASCGD) method.
  • Communication Compression: To further reduce communication costs, a compressed variant called Compressed Distributed Aggregative Stochastic Compositional Gradient Descent (CD-ASCGD) is proposed. This method uses techniques like quantization and sparsification to send less data over the network.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and simulated experiments.

Key Insights and Ideas

  • Bridging Compositionality and Aggregation: The paper successfully tackles the challenging combination of compositional objective functions and aggregative structures in a distributed setting, a problem that is less explored than simpler distributed optimization tasks.
  • Efficiency through Hybrid Techniques: The synergy between hybrid variance reduction and dynamic average consensus is crucial for achieving efficient information propagation and gradient estimation in a decentralized network.
  • Communication Compression for Scalability: The CD-ASCGD method demonstrates that significant communication savings can be achieved without sacrificing convergence speed, making the algorithms more practical for large-scale distributed systems.
  • Optimal Convergence Rates: Both D-ASCGD and CD-ASCGD achieve the optimal convergence rate of $O(1/\sqrt{K})$, which is a significant theoretical result for this class of problems.

Key Results

  • The proposed D-ASCGD algorithm achieves an optimal convergence rate of $O(1/\sqrt{K})$ for smooth objective functions.
  • The communication-compressed variant, CD-ASCGD, also maintains the optimal convergence rate of $O(1/\sqrt{K})$ while significantly reducing communication costs.
  • Simulated experiments on decentralized reinforcement learning problems verify the effectiveness of both D-ASCGD and CD-ASCGD, showing comparable or better performance than existing methods.

Limitations and Future Work

  • Assumptions: The theoretical analysis relies on several assumptions regarding the objective functions (e.g., Lipschitz continuity, bounded gradients) and network properties (e.g., strongly connected graph). Relaxing these assumptions could lead to more broadly applicable algorithms.
  • Hyperparameter Tuning: The performance of the algorithms can be sensitive to hyperparameter choices (step sizes, compression parameters), which might require careful tuning in practice.
  • Extension to Non-convex Problems: While the paper focuses on convex or smooth settings, extending these methods to more general non-convex compositional optimization problems would be a valuable future direction.
  • Real-world Applications: Further exploration of these algorithms in diverse real-world distributed learning scenarios would be beneficial to demonstrate their practical utility.

Summary updated

BibTeX
@article{zhao2025numerical,
  author = {Shengchao Zhao and Yongchao Liu},
  title = {{Numerical methods for distributed stochastic compositional optimization problems with aggregative structure}},
  journal = {Optim. Methods Softw.},
  year = {2025},
  doi = {10.1080/10556788.2024.2381214},
}
Figure