Abstract: We study non-convex distributed optimization problems where a set of agents collaboratively solve a separable optimization problem that is distributed over a time-varying network. The existing methods to solve these problems rely on (at most) one time-scale algorithms, where each agent performs a diminishing or constant step-size gradient descent at the average estimate of the agents in the network. However, if possible at all, exchanging exact information, that is required to evaluate these average estimates, potentially introduces a massive communication overhead. Therefore, a reasonable practical assumption to be made is that agents only receive a rough approximation of the neighboring agents' information. To address this, we introduce and study a extit{two time-scale} decentralized algorithm with a broad class of extit{lossy} information sharing methods (that includes noisy, quantized, and/or compressed information sharing) over extit{time-varying} networks. In our method, one time-scale suppresses the (imperfect) incoming information from the neighboring agents, and one time-scale operates on local cost functions' gradients. We show that with a proper choices for the step-sizes' parameters, the algorithm achieves a convergence rate of for non-convex distributed optimization problems over time-varying networks, for any . Our simulation results support the theoretical results of the paper.
Recommendations
- Distributed nonconvex constrained optimization over time-varying digraphs
- Achieving Geometric Convergence for Distributed Optimization Over Time-Varying Graphs
- Inexact dual averaging method for distributed multi-agent optimization
- Distributed optimization methods for nonconvex problems with inequality constraints over time-varying networks
- Distributed subgradient-free stochastic optimization algorithm for nonsmooth convex functions over time-varying networks
Cites work
- An Online Convex Optimization Approach to Proactive Network Resource Allocation
- Constrained Consensus and Optimization in Multi-Agent Networks
- Convergence of Asynchronous Distributed Gradient Methods Over Stochastic Networks
- Convergence rate of linear two-time-scale stochastic approximation.
- Convex optimization: algorithms and complexity
- Diffusion Adaptation Strategies for Distributed Optimization and Learning Over Networks
- Distributed Consensus Algorithms in Sensor Networks With Imperfect Communication: Link Failures and Channel Noise
- Distributed nonconvex constrained optimization over time-varying digraphs
- Distributed Optimization Over Time-Varying Graphs With Imperfect Sharing of Information
- Distributed Subgradient Methods for Convex Optimization Over Random Networks
- Distributed Subgradient Methods for Multi-Agent Optimization
- Ergodic Stochastic Optimization Algorithms for Wireless Communication and Networking
- Ergodicity of Continuous-Time Distributed Averaging Dynamics: A Spanning Directed Rooted Tree Approach
- Fast Distributed Gradient Methods
- scientific article; zbMATH DE number 1324223 (Why is no real title available?)
- Non-Convex Distributed Optimization
- Nonlinear Two-Time-Scale Stochastic Approximation: Convergence and Finite-Time Performance
- On Distributed Averaging Algorithms and Quantization Effects
- On Endogenous Random Consensus and Averaging Dynamics
- On Nonconvex Decentralized Gradient Descent
- On the convergence of decentralized gradient descent
- Persuasion Bias, Social Influence, and Unidimensional Opinions
- Probability. Theory and examples.
- Product of Random Stochastic Matrices
- Quantization Design for Distributed Optimization
- Quantized consensus
- Quantized Consensus and Averaging on Gossip Digraphs
Cited in
(2)
This page was built for publication: DIMIX: Diminishing Mixing for Sloppy Agents
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6161307)
