Optimal convergence rates for convex distributed optimization in networks
From MaRDI portal
(Redirected from Publication:5214253)
Abstract: In this work, we consider the distributed optimization of non-smooth convex functions using a network of computing units. We investigate this problem under two regularity assumptions: (1) the Lipschitz continuity of the global objective function, and (2) the Lipschitz continuity of local individual functions. Under the local regularity assumption, we provide the first optimal first-order decentralized algorithm called multi-step primal-dual (MSPD) and its corresponding optimal convergence rate. A notable aspect of this result is that, for non-smooth functions, while the dominant term of the error is in , the structure of the communication network only impacts a second-order term in , where is time. In other words, the error due to limits in communication resources decreases at a fast rate even in the case of non-strongly-convex objective functions. Under the global regularity assumption, we provide a simple yet efficient algorithm called distributed randomized smoothing (DRS) based on a local smoothing of the objective function, and show that DRS is within a multiplicative factor of the optimal convergence rate, where is the underlying dimension.
Recommendations
- A dual approach for optimal algorithms in distributed optimization over networks
- Distributed consensus-based multi-agent convex optimization via gradient tracking technique
- Communication-efficient algorithms for decentralized and stochastic optimization
- On convergence rate of distributed stochastic gradient algorithm for convex optimization with inequality constraints
- Primal-dual stochastic distributed algorithm for constrained convex optimization
Cites work
- \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
- A dual approach for optimal algorithms in distributed optimization over networks
- A first-order primal-dual algorithm for convex problems with applications to imaging
- Achieving Geometric Convergence for Distributed Optimization Over Time-Varying Graphs
- An Optimal Algorithm for Decentralized Finite-Sum Optimization
- Chebyshev acceleration of iterative refinement
- Communication-efficient algorithms for decentralized and stochastic optimization
- Communication-efficient sparse regression
- Convex optimization: algorithms and complexity
- Decentralized and parallel primal and dual accelerated methods for stochastic convex programming problems
- DEXTRA: A Fast Algorithm for Optimization Over Directed Graphs
- Distributed optimization and statistical learning via the alternating direction method of multipliers
- Distributed Optimization Over Time-Varying Directed Graphs
- Distributed Subgradient Methods for Multi-Agent Optimization
- DQM: Decentralized Quadratically Approximated Alternating Direction Method of Multipliers
- DSA: decentralized double stochastic averaging gradient algorithm
- Dual Averaging for Distributed Optimization: Convergence Analysis and Network Scaling
- EXTRA: an exact first-order algorithm for decentralized consensus optimization
- Fast Distributed Gradient Methods
- scientific article; zbMATH DE number 5454133 (Why is no real title available?)
- Introductory lectures on convex optimization. A basic course.
- Linear Convergence Rate of a Class of Distributed Augmented Lagrangian Algorithms
- Mirror Prox algorithm for multi-term composite minimization and semi-separable problems
- On the Linear Convergence of the ADMM in Decentralized Consensus Optimization
- Proximité et dualité dans un espace hilbertien
- Push–Pull Gradient Methods for Distributed Optimization in Networks
- Randomized smoothing for stochastic optimization
- Robust accelerated gradient methods for smooth strongly convex functions
- Stochastic Gradient-Push for Strongly Convex Functions on Time-Varying Directed Graphs
Cited in
(55)- Optimal distributed stochastic mirror descent for strongly convex optimization
- Convergence rate analysis of distributed optimization with projected subgradient algorithm
- Decentralized optimization over tree graphs
- Distributed optimization for degenerate loss functions arising from over-parameterization
- \(\mathcal{H}_\infty\) network optimization for edge consensus
- A regularized stochastic subgradient projection method for an optimal control problem in a stochastic partial differential equation
- On arbitrary compression for decentralized consensus and stochastic optimization over directed networks
- Distributed adaptive Newton methods with global superlinear convergence
- Exponential convergence of distributed primal-dual convex optimization algorithm without strong convexity
- Mass-spring-damper networks for distributed optimization in non-Euclidean spaces
- Communication-efficient algorithms for decentralized and stochastic optimization
- Distributed optimization over networks
- Distributed communication-sliding mirror-descent algorithm for nonsmooth resource allocation problem
- On the convergence of decentralized gradient descent
- On convergence rate of distributed stochastic gradient algorithm for convex optimization with inequality constraints
- Almost sure convergence of random projected proximal and subgradient algorithms for distributed nonsmooth convex optimization
- Accelerated gradient methods and dual decomposition in distributed model predictive control
- Swarming for faster convergence in stochastic optimization
- Distributed optimization with arbitrary local solvers
- Robust asynchronous stochastic gradient-push: asymptotically optimal and network-independent performance for strongly convex functions
- On the convergence of exact distributed generalisation and acceleration algorithm for convex optimisation
- scientific article; zbMATH DE number 7626754 (Why is no real title available?)
- Distributed Optimization Based on Gradient Tracking Revisited: Enhancing Convergence Rate via Surrogation
- Composite optimization for the resource allocation problem
- An iteratively regularized stochastic gradient method for estimating a random parameter in a stochastic PDE. A variational inequality approach
- scientific article; zbMATH DE number 7307473 (Why is no real title available?)
- Communication-Efficient Distributed Eigenspace Estimation
- An Optimal Algorithm for Decentralized Finite-Sum Optimization
- A distributed flexible delay-tolerant proximal gradient algorithm
- Asynchronous Broadcast-Based Convex Optimization Over a Network
- Dual Averaging for Distributed Optimization: Convergence Analysis and Network Scaling
- Push–Pull Gradient Methods for Distributed Optimization in Networks
- An accelerated communication-efficient primal-dual optimization framework for structured machine learning
- A dual approach for optimal algorithms in distributed optimization over networks
- Stochastic distributed learning with gradient quantization and double-variance reduction
- A stochastic averaging gradient algorithm with multi‐step communication for distributed optimization
- Non-smooth setting of stochastic decentralized convex optimization problem over time-varying graphs
- Optimal Methods for Convex Risk-Averse Distributed Optimization
- Graph Topology Invariant Gradient and Sampling Complexity for Decentralized and Stochastic Optimization
- Optimal data splitting in distributed optimization for machine learning
- On decentralized nonsmooth optimization
- scientific article; zbMATH DE number 7733441 (Why is no real title available?)
- Decentralized saddle-point problems with different constants of strong convexity and strong concavity
- Understanding a Class of Decentralized and Federated Optimization Algorithms: A Multirate Feedback Control Perspective
- Decentralized personalized federated learning: lower bounds and optimal algorithm for all personalization modes
- Localization and approximations for distributed non-convex optimization
- Towards accelerated rates for distributed optimization over time-varying networks
- Recent theoretical advances in decentralized distributed convex optimization
- Distributed zeroth-order optimization: convergence rates that match centralized counterpart
- Stochastic adversarial noise in the ``black box optimization problem
- Accelerated zero-order SGD method for solving the black box optimization problem under ``overparametrization condition
- Distributed accelerated gradient methods with restart under quadratic growth condition
- Decentralised convex optimisation with probability-proportional-to-size quantization
- Optimal and efficient algorithms for decentralized online convex optimization
- Exploiting agent symmetries for performance analysis of distributed optimization methods
This page was built for publication: Optimal convergence rates for convex distributed optimization in networks
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5214253)
