Optimal distributed stochastic mirror descent for strongly convex optimization
From MaRDI portal
Publication:1640744
Abstract: In this paper we consider convergence rate problems for stochastic strongly-convex optimization in the non-Euclidean sense with a constraint set over a time-varying multi-agent network. We propose two efficient non-Euclidean stochastic subgradient descent algorithms based on the Bregman divergence as distance-measuring function rather than the Euclidean distances that were employed by the standard distributed stochastic projected subgradient algorithms. For distributed optimization of nonsmooth and strongly convex functions whose only stochastic subgradients are available, the first algorithm recovers the best previous known rate of O(ln(T)/T) (where T is the total number of iterations). The second algorithm is an epoch variant of the first algorithm that attains the optimal convergence rate of O(1/T), matching that of the best previously known centralized stochastic subgradient algorithm. Finally, we report some simulation results to illustrate the proposed algorithms.
Recommendations
- Stochastic mirror descent method for distributed multi-agent optimization
- Optimal convergence rates for convex distributed optimization in networks
- Distributed subgradient-free stochastic optimization algorithm for nonsmooth convex functions over time-varying networks
- Distributed stochastic subgradient projection algorithms for convex optimization
- On stochastic subgradient mirror-descent algorithm with weighted averaging
Cites work
- Beyond the regret minimization barrier: optimal algorithms for stochastic strongly-convex optimization
- Constrained Consensus and Optimization in Multi-Agent Networks
- Diffusion Adaptation Strategies for Distributed Optimization and Learning Over Networks
- Distributed Constrained Optimization by Consensus-Based Primal-Dual Perturbation Method
- Distributed convex optimization via continuous-time coordination algorithms with discrete-time communication
- Distributed multi-agent optimization subject to nonidentical constraints and communication delays
- Distributed Optimization Over Time-Varying Directed Graphs
- Distributed stochastic subgradient projection algorithms for convex optimization
- Distributed Subgradient Methods for Multi-Agent Optimization
- EXTRA: an exact first-order algorithm for decentralized consensus optimization
- Gossip Algorithms for Convex Consensus Optimization Over Networks
- Initialization-free distributed algorithms for optimal resource allocation with feasibility constraints and application to economic dispatch of power systems
- Mirror descent and nonlinear projected subgradient methods for convex optimization.
- On convergence rate of distributed stochastic gradient algorithm for convex optimization with inequality constraints
- On Distributed Convex Optimization Under Inequality and Equality Constraints
- Robust Stochastic Approximation Approach to Stochastic Programming
- Stochastic Gradient-Push for Strongly Convex Functions on Time-Varying Directed Graphs
- Understanding machine learning. From theory to algorithms
Cited in
(37)- Stochastic mirror descent method for distributed multi-agent optimization
- Distributed consensus-based multi-agent convex optimization via gradient tracking technique
- Continuous-time distributed optimization with strictly pseudoconvex objective functions
- Distributed online bandit optimization under random quantization
- Gradient-free distributed optimization with exact convergence
- Distributed heterogeneous multi-agent networks optimization with nonconvex velocity constraints
- Output feedback tracking control of a class of continuous-time nonlinear systems via adaptive dynamic programming approach
- Asynchronous impulsive control for consensus of second-order multi-agent networks
- \(\mathscr{L}_2 - \mathscr{L}_\infty\) consensus of stochastic delayed multi-agent systems with ADT switching interaction topologies
- Mass-spring-damper networks for distributed optimization in non-Euclidean spaces
- Distributed communication-sliding mirror-descent algorithm for nonsmooth resource allocation problem
- Deterministic and stochastic primal-dual subgradient algorithms for uniformly convex minimization
- Distributed Stochastic Optimization via Matrix Exponential Learning
- Ergodic mirror descent
- On stochastic subgradient mirror-descent algorithm with weighted averaging
- Distributed optimization of multi-integrator agent systems with mixed neighbor interactions
- Distributed mirror descent algorithm over unbalanced digraphs based on gradient weighting technique
- A stochastic averaging gradient algorithm with multi‐step communication for distributed optimization
- Distributed regularized online optimization using forward-backward splitting
- Distributed solving linear algebraic equations with switched fractional order dynamics
- Distributed delayed dual averaging for distributed optimization over time-varying digraphs
- A Fenchel dual gradient method enabling regularization for nonsmooth distributed optimization over time-varying networks
- No-regret learning for repeated non-cooperative games with lossy bandits
- Event-triggered primal-dual design with linear convergence for distributed nonstrongly convex optimization
- Distributed projection‐free algorithm for constrained aggregative optimization
- Distributed constrained optimization with periodic dynamic quantization
- Distributed constrained optimization for multi-agent networks with communication delays under time-varying topologies
- Stochastic mirror descent for convex optimization with consensus constraints
- Convergence rate bounds for the mirror descent method: IQCs, Popov criterion and Bregman divergence
- Decentralized online strongly convex optimization with general compressors and random disturbances
- Distributed cooperative optimization control for nonlinear multi-agent systems with event-triggered communication
- Decentralized stochastic subgradient projection optimization algorithms over random networks
- Distributed stochastic constrained optimization with constant step-sizes via saddle-point dynamics
- Distributed constrained optimization over unbalanced graphs and delayed gradient
- Distributedly solving network linear equations with event-based algorithms
- Linear convergence for distributed stochastic optimization with coupled inequality constraints
- Weighted \(\mathcal{H}_\infty\) consensus design for stochastic multi-agent systems subject to external disturbances and ADT switching topologies
This page was built for publication: Optimal distributed stochastic mirror descent for strongly convex optimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1640744)
