Separable approximations and decomposition methods for the augmented Lagrangian

By Rachael Tappenden, Peter Richtárik, Burak Büke. 2013

42 citations recorded by the source corpus.

In this paper, we study decomposition methods based on separable approximations for minimizing the augmented Lagrangian. In particular, we study and compare the diagonal quadratic approximation method (DQAM) of Mulvey and Ruszczyński [A diagonal quadratic approximation method for large scale linear programs, Oper. Res. Lett. 12 (1992), pp. 205–215] and the parallel coordinate descent method (PCDM) of Richtárik and Takáč [Parallel coordinate descent methods for big data optimization. Technical report, November 2012. arXiv:1212.0873]. We show that the two methods are equivalent for feasibility problems up to the selection of a step-size parameter. Furthermore, we prove an improved complexity bound for PCDM under strong convexity, and show that this bound is at least 8(L′/L̄)(ω−1)2 times better than the best known bound for DQAM, where ω is the degree of partial separability and L’ and L̄ are the maximum and average of the block Lipschitz constants of the gradient of the quadratic penalty appearing in the augmented Lagrangian.

Subfields: Artificial Intelligence, Computational Mechanics, Numerical Analysis

How researchers see this paper

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

In Artificial Intelligence

In Computational Mechanics

In Numerical Analysis

Citations in the corpus

Distributed Coordinate Descent Method for Learning with Big Data (2013, background): “Methods of this type, in various settings, were studied by several authors, including Hsieh et al. (2008); Shalev-Shwartz & Tewari (2009); Nesterov (2012); Richt´arik & Tak´aˇc (2012c); Necoara et al. (2012); Tappenden et al. (2013b); Shalev-Shwartz & Zhang (2013b); Lu & Xiao (2013).”
Distributed optimization with arbitrary local solvers (2015, neutral): “See also [64].”
Stochastic, Distributed and Federated Optimization for Machine Learning (2017, background): “For previous work on randomized block coordinate descent we refer to the reader to [175] and [174].”
Stochastic Dual Coordinate Ascent with Adaptive Probabilities (2015, background): “Other related work includes (Nemirovski et al., 2009; Duchi et al., 2011; Agarwal & Bottou, 2014; Zhao et al., 2014a; Fountoulakis & Tappenden, 2014; Tappenden et al., 2014).”
Coordinate descent with arbitrary sampling I: algorithms and complexity† (2014, unknown): “We provide a complexity analysis of ALPHA, from which we deduce as a direct corollary complexity bounds for its many variants, all matching or improving best known bounds.”
SDNA: Stochastic Dual Newton Ascent for Empirical Risk Minimization (2015, background): “…based on running coordinate ascent in the dual such as those mentioned above and also (Richtárik & Takáč, 2014; 2012; Fercoq & Richtárik, 2013b; Tappenden et al., 2014; Richtárik & Takáč, 2013a;b; Fercoq & Richtárik, 2013a; Fercoq et al., 2014; Qu et al., 2014; Qu & Richtárik, 2014a)…”
On optimal probabilities in stochastic coordinate descent methods (2013, methodology): “The first assumption generalizes the ESO concept introduced in [21] and later used in [5,6,22,27,28] to nonuniform samplings.”
Parallel Direction Method of Multipliers (2014, methodology): “In [20], randomized block coordinate descent (RBCD) [16, 18] is used to solve (2) exactly, but leading to a double-loop algorithm along with the dual step.”
Quartz: Randomized Dual Coordinate Ascent with Arbitrary Sampling (2015, background): “Besides [23, 22], ESO inequalities were further studied in [30, 31, 7, 21, 6, 5, 12].”