Convergence Rate of Distributed ADMM Over Networks

DOI10.1109/TAC.2017.2677879MaRDI QIDQ4566904zbMATH OpenOpenAlexFDO

Authors Ali Makhdoumi, Asuman Ozdaglar

Publication date 27 June 2018

Published in IEEE Transactions on Automatic Control (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Convex programming (90C25) Programming involving graphs or networks (90C35)

Abstract: We propose a distributed algorithm based on Alternating Direction Method of Multipliers (ADMM) to minimize the sum of locally known convex functions using communication over a network. This optimization problem emerges in many applications in distributed machine learning and statistical estimation. We show that when functions are convex, both the objective function values and the feasibility violation converge with rate $O(frac1T)$, where $T$ is the number of iterations. We then show that if the functions are strongly convex and have Lipschitz continuous gradients, the sequence generated by our algorithm converges linearly to the optimal solution. In particular, an $epsilon$-optimal solution can be computed with $O(sqrtkapp{a}_{f}log(1/epsilon))$ iterations, where $kapp{a}_f$ is the condition number of the problem. Our analysis also highlights the effect of network structure on the convergence rate through maximum and minimum degree of nodes as well as the algebraic connectivity of the network.

Cited in

(26)

• Is ADMM always faster than average consensus?
• Distributed optimization over directed graphs with row stochasticity and constraint regularity
• Network-decentralised optimisation and control: an explicit saturated solution
• Distributed optimization with information-constrained population dynamics
• Augmented Lagrange algorithms for distributed optimization over multi-agent networks via edge-based method
• Decentralized optimization over tree graphs
• Distributed decision-coupled constrained optimization via proximal-tracking
• A novel bound on the convergence rate of ADMM for distributed optimization
• Tracking-ADMM for distributed constraint-coupled optimization
• Exponential convergence of distributed primal-dual convex optimization algorithm without strong convexity
• Communication-efficient algorithms for decentralized and stochastic optimization
• A distributed methodology for approximate uniform global minimum sharing
• Revisiting EXTRA for Smooth Distributed Optimization
• Solving Fused Penalty Estimation Problems via Block Splitting Algorithms
• Convergence testing on a distributed network of processors
• Distributed stochastic variance reduced gradient methods by sampling extra data with replacement
• Decentralized consensus algorithm with delayed and stochastic gradients
• Distributed subgradient-free stochastic optimization algorithm for nonsmooth convex functions over time-varying networks
• A local-minimization-free zero-gradient-sum algorithm for distributed optimization
• A divide-and-conquer algorithm for distributed optimization on networks
• Distributed event-triggered algorithm for unconstrained convex optimisation over weight-balanced directed networks
• A distributed parallel optimization algorithm via alternating direction method of multipliers
• Distributed gradient descent method with edge-based event-driven communication for non-convex optimization
• A first-order algorithm for decentralised min-max problems
• Decentralized bilevel optimization
• Barron space for graph convolutional neural networks

This page was built for publication: Convergence Rate of Distributed ADMM Over Networks

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