On the Global and Linear Convergence of the Generalized Alternating Direction Method of Multipliers

By Wei Deng, Wotao Yin. 2016

727 citations recorded by the source corpus.

Subfields: Aerospace Engineering, Computational Mechanics, Signal Processing

How researchers see this paper

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

In Aerospace Engineering

In Computational Mechanics

In Signal Processing

Citations in the corpus

Communication-Efficient Distributed Optimization using an Approximate Newton-type Method (2013, methodology): “A similar dependence occurs with other recently-proposed algorithms for distributed optimization (e.g. Yang, 2013; Mahajan et al., 2013; Dekel et al., 2012; Cotter et al., 2011; Duchi et al., 2012).”
Federated Optimization: Distributed Machine Learning for On-Device Intelligence (2016, methodology): “Another class of algorithms relevant for this work is Alternating Direction Method of Multipliers (ADMM) [14, 28].”
On the Linear Convergence of the ADMM in Decentralized Consensus Optimization (2013, methodology): “Also, we have with I 2 EN being a 2 EN × 2 EN identity matrix.”
Communication-Efficient Distributed Optimization of Self-Concordant Empirical Loss (2015, neutral): “(2) In machine learning applications, the probability distribution of z is usually unknown, and the SAA approach is referred as empirical risk minimization (ERM).”
Stochastic, Distributed and Federated Optimization for Machine Learning (2017, methodology): “An exception is the approach of Zhang, Lee and Shin [194], which is similar to our approach in spirit, albeit based on ADMM, in that they allow for the subproblems to be solved inexactly.”
Parallel Multi-Block ADMM with o(1 / k) Convergence (2013, neutral): “The analysis is based on bounding the error (cid:107) u k − u ∗ (cid:107) 2 G and estimating its decrease, motivated by the works [19, 8, 16]. where Proof .”
Tight global linear convergence rate bounds for Douglas–Rachford splitting (2015, background): “The works in [21, 22, 33] consider distributed formulations, while the works in [8, 11, 15, 28, 24, 31, 27, 17, 16, 1, 2] show global convergence rate bounds under various assumptions.”
Stochastic Variance Reduced Gradient Methods by Sampling Extra Data with Replacement (2017, methodology): “With an appropriately chosen value for σ, it is shown by Frostig et al. (2015) and Lin et al.”
Stochastic Dual Coordinate Ascent with Alternating Direction Method of Multipliers (2014, methodology): “As for batch settings, the linear convergence of batch ADMM has been shown by Deng and Yin (2012). However, their proof can not be directly applied to our stochastic setting.”
Partitioning Data on Features or Samples in Communication-Efficient Distributed Optimization? (2015, methodology): “buted algorithms have been proposed [1, 16, 12, 14, 8]. The main bottleneck in distributed computing –communication– was handled by many researches differently. Some work considered ADMM type methods [3, 6], another used block-coordinate type algorithms [8, 17, 7, 9], where they tried to solve the l”
Proximal Splitting Algorithms: A Tour of Recent Advances, with New Twists. (2020, methodology): “…linear operators We the following problem, generalizing The Generalized Chambolle–Pock algorithm (110) has appeared in the literature under diﬀerent names, like Alternating Proximal Gradient Method [86], Generalized Alternating Direction Method of Multipliers [87], or Preconditioned ADMM [88,89].”
Bregman Alternating Direction Method of Multipliers (2013, methodology): “Several problems have been beneﬁted from the linearization of quadratic term [8], e.g., when f is (cid:96) 1 loss function [16], and projection onto the unit simplex or (cid:96) 1 ball [9].”
Fast Alternating Direction Optimization Methods (2014, methodology): “Other analytical approaches can be used to prove convergence of {λk} (see, for example, [12]); however, we use the above techniques because they lend themselves to the analysis of an accelerated ADMM scheme.”
Linear Convergence Rate of a Class of Distributed Augmented Lagrangian Algorithms (2013, methodology): “Recently, [30], [31] show that the ADMM method converges globally linearly, for certain more general convex costs than ours.”
Unwrapping ADMM: Efficient Distributed Computing via Transpose Reduction (2015, background): “For example when f is strongly convex, accelerated ADMM obtains O (1 /k 2 ) convergence (Goldstein et al., 2014a), and if we further assume D has full row rank, R-linear convergence is possible (Deng & Yin, 2012).”
An introduction to continuous optimization for imaging (2016, background): “A generalization of the ADMM in the same flavour is considered in Deng and Yin (2016), and several convergence rates are derived in smooth cases.”
A General Analysis of the Convergence of ADMM (2015, positive): “As two examples, Giselsson & Boyd (2014) consider the case ε = 0 and Deng & Yin (2012) consider the case α = 1 and ε = 0 .”
On the linear convergence of the alternating direction method of multipliers (2012, neutral): “Under these and additional rank conditions on the constraint matrix E , some linear convergence rate results can be obtained for a subset of primal and dual variables in the ADMM algorithm (or its variant); see [5,11,23].”
A distributed block coordinate descent method for training $l_1$ regularized linear classifiers (2014, background): “Several variants of global convergence and rate of convergence (e.g., O( 1k )) results exist under different weak/strong convexity assumptions on the two terms of the objective function (Deng and Yin, 2012; Deng et al., 2013).”