Linear Convergence Rate of a Class of Distributed Augmented Lagrangian Algorithms

By Dusan Jakovetic, José M. F. Moura, Joao Xavier. 2013

140 citations recorded by the source corpus.

We study distributed optimization where nodes cooperatively minimize the sum of their individual, locally known, convex costs fi(x)'s; x ϵ ℝd is global. Distributed augmented Lagrangian (AL) methods have good empirical performance on several signal processing and learning applications, but there is limited understanding of their convergence rates and how it depends on the underlying network. This paper establishes globally linear (geometric) convergence rates of a class of deterministic and randomized distributed AL methods, when the fi's are twice continuously differentiable and have a bounded Hessian. We give explicit dependence of the convergence rates on the underlying network parameters. Simulations illustrate our analytical findings.

Subfields: Computational Mechanics, Computer Networks and Communications

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

1. Mingyi Hong
2. Wotao Yin
3. Francis R. Bach
4. Qing Ling
5. Peter Richtárik
6. Haoran Sun
7. Kevin Scaman
8. Wei Shi

In Computer Networks and Communications

1. Wotao Yin
2. Wei Shi
3. Mingyi Hong
4. Qing Ling
5. Aryan Mokhtari
6. Gang Wu
7. Francis R. Bach
8. Kevin Scaman

Citations in the corpus

• DJAM: Distributed Jacobi Asynchronous Method for Learning Personal Models (2018, methodology): “They use techniques ranging from distributed (sub)gradient descent [4], [5] to more elaborate techniques such as EXTRA [6], distributed ADMM [7], [8], dual averaging [9], and distributed augmented Lagrangean [10].”
• EXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimization (2014, methodology): “The augmented Lagrangian based primal-dual methods have linear convergence under strong convexity and Lipschitz gradient assumptions [4,30] or under the positive-definite bounded Hessian assumption [12,13].”
• Optimal Algorithms for Non-Smooth Distributed Optimization in Networks (2018, background): “Many algorithms were proposed to solve the decentralized optimization of an average of functions (see for example [1, 11, 3, 4, 12, 2, 13, 5]), and a sheer amount of work was devoted to improving the convergence rate of these algorithms [5, 6].”
• Optimal Algorithms for Smooth and Strongly Convex Distributed Optimization in Networks (2017, methodology): “, 2015; Mokhtari & Ribeiro, 2016), augmented Lagrangians (Jakovetić et al., 2015), and more recent approaches (Nedich et al.”
• Distributed Non-Convex First-Order optimization and Information Processing: Lower Complexity Bounds and Rate Optimal Algorithms (2018, methodology): “Primal methods such as distributed subgradient (DSG) method [6], the EXTRA method [9], as well as primal-dual based methods such as distributed augmented Lagrangian method [11], Alternating Direction Method of Multipliers (ADMM) [12–15] have been proposed.”