Linear Convergence Rate of a Class of Distributed Augmented Lagrangian\n Algorithms

2013/07/09 by Dušan Jakovetić, José M. F. Moura, Jakovetic, Dusan +3 · 3 citations
Computer Science · Engineering · #Distributed Control Multi-Agent Systems #FOS: Computer and information sciences #Information Theory (cs.IT) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.1307.2482

openalex publication_date 2013/07/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We study distributed optimization where nodes cooperatively minimize the sum\nof their individual, locally known, convex costs f_i(x)'s, x \∈ mathbb\nR^d is global. Distributed augmented Lagrangian (AL) methods have good\nempirical performance on several signal processing and learning applications,\nbut there is limited understanding of their convergence rates and how it\ndepends on the underlying network. This paper establishes globally linear\n(geometric) convergence rates of a class of deterministic and randomized\ndistributed AL methods, when the f_i's are twice continuously differentiable\nand have a bounded Hessian. We give explicit dependence of the convergence\nrates on the underlying network parameters. Simulations illustrate our\nanalytical findings.\n

Cited by

• Exact Decentralized Optimization via Explicit ℓ₁ Consensus Penalties
• An Optimal Control Interpretation of Augmented Distributed Optimization Algorithms
• Distributed gradient methods under heavy-tailed communication noise

Related

• Complexity Certification of a Distributed Augmented Lagrangian Method
• A distributed augmented Lagrangian decomposition algorithm for constrained optimization
• Convergence Theory of Flexible ALADIN for Distributed Optimization
• An Asynchronous Distributed Proximal Gradient Method for Composite Convex Optimization
• Geometrical Convergence Rate for Distributed Optimization with Time-Varying Directed Graphs and Uncoordinated Step-Sizes