Fast alternating linearization methods for minimizing the sum of two convex functions

By Donald Goldfarb, Shiqian Ma, Katya Scheinberg. 2009

282 citations recorded by the source corpus.

We present in this paper alternating linearization algorithms based on an alternating direction augmented Lagrangian approach for minimizing the sum of two convex functions. Our basic methods require at most \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${O(1/\epsilon)}$$\end{document} iterations to obtain an \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\epsilon}$$\end{document} -optimal solution, while our accelerated (i.e., fast) versions of them require at most \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${O(1/\sqrt{\epsilon})}$$\end{document} iterations, with little change in the computational effort required at each iteration. For both types of methods, we present one algorithm that requires both functions to be smooth with Lipschitz continuous gradients and one algorithm that needs only one of the functions to be so. Algorithms in this paper are Gauss-Seidel type methods, in contrast to the ones proposed by Goldfarb and Ma in (Fast multiple splitting algorithms for convex optimization, Columbia University, 2009) where the algorithms are Jacobi type methods. Numerical results are reported to support our theoretical conclusions and demonstrate the practical potential of our algorithms.

Subfields: Artificial Intelligence, Computational Mechanics, Numerical Analysis, Optimization & Training

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

In Optimization & Training

Citations in the corpus

Frank-Wolfe Splitting via Augmented Lagrangian Method (2018, methodology): “(2)An example of approximate minimization is taking one proximal gradient step, as used for example, in the Linearized ADMM algorithm (Goldfarb et al., 2013; Yang and Yuan, 2013).”
On the O(1=k) convergence of asynchronous distributed alternating Direction Method of Multipliers (2013, background): “Other recent works analyzed the rate of convergence of ADMM a nd other related algorithms under smoothness conditions on the objective function (see [8], [ 16], [17]).”
Information Bottleneck Domain Adaptation with Privileged Information for Visual Recognition (2016, methodology): “In this way, the minimization can be carried out with the Fast Alternating Linearization Method (FALM) [19].”
Flexible Clustered Multi-Task Learning by Learning Representative Tasks (2016, background): “For the second subproblem, the convergence property of ADMM for convex objective function with more than two block variables cannot be theoretically guaranteed as is generally accepted currently [22], [8].”
Generalized Convexity and Integral Inequalities (2015, background): “This double inequality is known as classical Hermite-Hadamard inequality.”
Camera-trap images segmentation using multi-layer robust principal component analysis (2017, methodology): “Active Subspace RPCA (AS-RPCA) [9]; Exact ALM (EALM), Inexact ALM (IALM), Partial APG (APG-PARTIAL) and APG [10]; Lagrangian Alternating Direction Method (LSADM) [11]; Non-Smooth Augmented Lagrangian v1 (NSA1) and Non-Smooth Augmented Lagrangian v2 (NSA2) [12]; Probabilistic Robust Matrix Factorizat”
Learning to Rank Using User Clicks and Visual Features for Image Retrieval (2015, methodology): “Then given a penalty parameter 1/μ, the corresponding augmented Lagrangian function [23] is given as”
Alternating direction augmented Lagrangian methods for semidefinite programming (2010, unknown): “This simple idea has been applied to many other problem classes, such as, variational inequality problems [16,17,37], linear programming [9], nonlinear convex optimization [1,7,13,14,20,21,28], maximal monotone operators [10] and nonsmooth 1 minimization arising from compressive sensing [30,35,36,40”
On the Global and Linear Convergence of the Generalized Alternating Direction Method of Multipliers (2016, methodology): “This rate is stronger than the sublinear rates such as O(1/k) and O(1/k(2)) and is given in terms of the solution error, which is stronger than those given in terms of the objective error in [19, 20, 23], the violation of optimality conditions in [21], and the solution relative change in [22].”
Adaptive Consensus ADMM for Distributed Optimization (2017, background): “…to have a O (1 /k ) convergence rate under mild conditions for convex problems (He & Yuan, 2012; 2015), while a O (1 /k 2 ) rate is possible when at least one of the functions is strongly convex or smooth (Goldfarb et al., 2013; Goldstein et al., 2014; Kadkhodaie et al., 2015; Tian & Yuan, 2016).”
Nuclear Norm Based Matrix Regression with Applications to Face Recognition with Occlusion and Illumination Changes (2014, methodology): “More recently, the Nesterov-type scheme was also applied to accelerate the alternating direction methods [46], [50].”
Towards an optimal stochastic alternating direction method of multipliers (2014, background): “Indeed, these benefits have also borne through in applications such large-scale lasso (Boyd et al., 2011), constrained image deblurring (Chan et al., 2013), and matrix completion (Goldfarb et al., 2012), to name a few.”
Randomized First-Order Methods for Saddle Point Optimization (2014, unknown): “exact penalty method [22]. When p = 2, a special augmented Lagrangian method, namely the alternating direction method of multipliers (ADMM) [11, 43, 29, 15, 12], has been intensively studied recently [3, 18, 19, 20, 41]. However, as shown by Chen et al. [7], a direction extension of ADMM does not ne”