Distributed stochastic compositional optimization problems over directed networks

DOI10.1007/S10589-023-00512-0MaRDI QIDQ6179879zbMATH OpenOpenAlexFDO

Authors Shengchao Zhao, Yongchao Liu

Publication date 18 January 2024

Published in Computational Optimization and Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2203.11074

zbMATH Keywords

asymptotic normalitygradient trackingdirected communication networksdistributed stochastic compositional optimization

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Stochastic programming (90C15)

Abstract: We study the distributed stochastic compositional optimization problems over directed communication networks in which agents privately own a stochastic compositional objective function and collaborate to minimize the sum of all objective functions. We propose a distributed stochastic compositional gradient descent method, where the gradient tracking and the stochastic correction techniques are employed to adapt to the networks' directed structure and increase the accuracy of inner function estimation. When the objective function is smooth, the proposed method achieves the convergence rate $mathcalOleft(k^{-1/2}ight)$ and sample complexity $mathcalOleft(frac1epsilo{n}^{2}ight)$ for finding the ($epsilon$)-stationary point. When the objective function is strongly convex, the convergence rate is improved to $mathcalOleft(k^{-1}ight)$. Moreover, the asymptotic normality of Polyak-Ruppert averaged iterates of the proposed method is also presented. We demonstrate the empirical performance of the proposed method on model-agnostic meta-learning problem and logistic regression problem.

Recommendations

• A decentralized Nesterov gradient method for stochastic optimization over unbalanced directed networks
• On arbitrary compression for decentralized consensus and stochastic optimization over directed networks
• A stochastic averaging gradient algorithm with multi‐step communication for distributed optimization
• Stochastic compositional gradient descent: algorithms for minimizing compositions of expected-value functions
• Distributed stochastic gradient tracking methods

Cites work

• scientific article; zbMATH DE number 4015993 (Why is no real title available?)
• scientific article; zbMATH DE number 3761782 (Why is no real title available?)
• A Single Timescale Stochastic Approximation Method for Nested Stochastic Optimization
• A Stochastic Subgradient Method for Nonsmooth Nonconvex Multilevel Composition Optimization
• A Two-Timescale Stochastic Algorithm Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Critic
• Accelerating Stochastic Composition Optimization
• Acceleration of Stochastic Approximation by Averaging
• Asymptotic properties of dual averaging algorithm for constrained distributed stochastic optimization
• Asymptotic properties of primal-dual algorithm for distributed stochastic optimization over random networks with imperfect communications
• Fully asynchronous policy evaluation in distributed reinforcement learning over networks
• Harnessing Smoothness to Accelerate Distributed Optimization
• Multilevel composite stochastic optimization via nested variance reduction
• Multilevel stochastic gradient methods for nested composition optimization
• Non-negative matrices and Markov chains.
• On Asymptotic Normality in Stochastic Approximation
• On a Stochastic Approximation Method
• Performance of a Distributed Stochastic Approximation Algorithm
• Push–Pull Gradient Methods for Distributed Optimization in Networks
• Sample average approximation method for compound stochastic optimization problems
• Sample complexity of sample average approximation for conditional stochastic optimization
• Solving Stochastic Compositional Optimization is Nearly as Easy as Solving Stochastic Optimization
• Statistical estimation of composite risk functionals and risk optimization problems
• Stochastic compositional gradient descent: algorithms for minimizing compositions of expected-value functions
• Stochastic multilevel composition optimization algorithms with level-independent convergence rates

Cited in

(2)

• Numerical methods for distributed stochastic compositional optimization problems with aggregative structure
• A decentralized Nesterov gradient method for stochastic optimization over unbalanced directed networks

This page was built for publication: Distributed stochastic compositional optimization problems over directed networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6179879)