Numerical methods for distributed stochastic compositional optimization problems with aggregative structure

ABSTRACT

The paper studies the distributed stochastic compositional optimization problems over networks, where all the agents' inner-level function is the sum of each agent's private expectation function. Focusing on the aggregative structure of the inner-level function, we employ the hybrid variance reduction method to obtain the information on each agent's private expectation function, and apply the dynamic consensus mechanism to track the information on each agent's inner-level function. Then by combining with the standard distributed stochastic gradient descent method, we propose a distributed aggregative stochastic compositional gradient descent method. When the objective function is smooth, the proposed method achieves the convergence rate $\mathcal{O}\left(K^{-1/2}\right)$. We further combine the proposed method with the communication compression and propose the communication compressed variant distributed aggregative stochastic compositional gradient descent method. The compressed variant of the proposed method maintains the convergence rate $\mathcal{O}\left(K^{-1/2}\right)$. Simulated experiments on decentralized reinforcement learning verify the effectiveness of the proposed methods.

KEYWORDS:

• Distributed stochastic compositional optimization
• aggregative structure
• hybrid variance reduction technique
• dynamic consensus mechanism
• communication compression

2020 MATHEMATICS SUBJECT CLASSIFICATIONS:

• 68W15
• 62L20
• 90C15

Disclosure statement

No potential conflict of interest was reported by the author(s).

Notes

1 By the iterations of $y_{i,k}$, $z_{i,k}$ in Algorithm 1 and the definitions of ${\overline{y}}_k$ and ${\overline{z}}_k$, we have ${\overline{y}}_k=\frac{1}{n}\sum _{j=1}^n{G}_{j,k}$ and ${\overline{z}}_k=\frac{1}{n}\sum _{j=1}^n{\hat{G}}_{j,k}$

2 For any fixed K, $a_k$ is a constant dependent on K.

3 $\breve{a}$ is dependent on K.

4 $h\left(x\right)$ denotes the objective function of problem (42(42) $\underset{x\in {\mathbb{R}}^d}{min}\frac{1}{2|\mathcal{S}|}\sum _{s=1}^{|\mathcal{S}|}{({\varphi }_s^{⊺}x-\frac{1}{n}\sum _{j=1}^n{\mathbb{E}}_{s^{\mathrm{\prime }}}[r_{s,s^{\mathrm{\prime }}}^{\left(j\right)}+\gamma {\varphi }_{s^{\mathrm{\prime }}}^{⊺}x|s])}^2+\frac{\lambda }{2}\Vert x{\Vert }^2,$(42) ).

Additional information

Funding

The research is supported by the NSFC #11971090 and Fundamental Research Funds for the Central Universities DUT22LAB301.

Notes on contributors

Shengchao Zhao

Shengchao Zhao obtained his B.S. degree in Mathematics and Applied Mathematics from Qingdao University of Science and Technology, China, in 2017, and a Ph.D. Degree in Operations Research and Control Theory from Dalian University of Technology, in 2024. He is currently an assistant professor in the School of Mathematics, China University of Mining and Technology, Xuzhou, China. His research interests include stochastic programming and distributed optimization.

Yongchao Liu

Yongchao Liu obtained a B.S. Degree in Information and Computing Science from Dalian Maritime University, in 2005, and a Ph.D. Degree in Operations Research and Control Theory from Dalian University of Technology, in 2011. He was a postdoctoral associate at the University of Southampton, from 2014 to 2016. He is currently a professor in the School of Mathematical Sciences, Dalian University of Technology, Dalian, China. His research Interests include stochastic programming, distributed optimization, variational inequalities and games.