Fast Alternating Direction Optimization Methods

By Tom Goldstein, Brendan O'Donoghue, Simon Setzer, Richard Baraniuk. SIAM Journal of Imaging Sciences, 2014

826 citations recorded by the source corpus.

Alternating direction methods are a common tool for general mathematical programming and optimization. These methods have become particularly important in the field of variational image processing, which frequently requires the minimization of nondifferentiable objectives. This paper considers accelerated (i.e., fast) variants of two common alternating direction methods: the alternating direction method of multipliers (ADMM) and the alternating minimization algorithm (AMA). The proposed acceleration is of the form first proposed by Nesterov for gradient descent methods. In the case that the objective function is strongly convex, global convergence bounds are provided for both classical and accelerated variants of the methods. Numerical examples are presented to demonstrate the superior performance of the fast methods for a wide variety of problems.

View Paper: https://www.semanticscholar.org/paper/b1dc0fa0edd9ccf77f6a3df48833f6e48fc40068

How researchers see this paper

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

Citations in the corpus

Optimal Parameter Selection for the Alternating Direction Method of Multipliers (ADMM): Quadratic Problems (2013, methodology): “We evaluate for four algorithms: the ADMM iterates in (31) with and without over-relaxation and the corresponding tuning rules developed in this paper, and the fast-ADMM iterates (40) with ρ = 1 as proposed by [27] and ρ = ρ of our paper.”
Efficient Accelerated Coordinate Descent Methods and Faster Algorithms for Solving Linear Systems (2013, background): “Just as the accelerated gradient descent method has improved the theoretical and empirical running time of various gradient descent algorithms [25], [15], we hope that ACDM will improve the running time of various algorithms for which coordinate descent based approaches have proven effective.”
Unwrapping ADMM: Efficient Distributed Computing via Transpose Reduction (2015, methodology): “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).”
Parallel Multi-Block ADMM with o(1 / k) Convergence (2013, unknown): “Its convergence rate has been actively studied; see [21, 19, 18, 13, 8, 20] and the references therein.”
Group-Based Alternating Direction Method of Multipliers for Distributed Linear Classification (2017, methodology): “The convergence analysis relies on the optimality of λi , which is similar to that in [42] in each iteration.”
Bregman Alternating Direction Method of Multipliers (2013, background): “For strongly convex functions, the dual objective of an accelerated version of ADMM can converge at a rate ofO(1/T (2)) [14].”
A distributed block coordinate descent method for training $l_1$ regularized linear classifiers (2014, methodology): “For ease of reference, we list the methods that we implemented and studied: (1)ADMM: accelerated alternating direction method of multipliers [9], (2)Hyd: Hydra [20], (3) GRock: GReedy coOrdinate-block [16], (4) FPA: Flexible Parallel Algorithm [7], (5) PCD: Parallel Coordinate Descent Newton method ”
Broad Learning System: An Effective and Efficient Incremental Learning System Without the Need for Deep Architecture (2018, background): “Moreover, it has been shown that many state-of-art algorithms for l1 norm involved problems could be derived by ADMM [50], such as FISTA.”
PhaseMax: Convex Phase Retrieval via Basis Pursuit (2016, methodology): “empirical success probability of PhaseMax in a noiseless and complex-valued scenario with measurement vectors taken independently and uniformly from the unit sphere. We use a custom ADMM-based solver [37] and declare success whenever the relative reconstruction error satisﬁes RRE = kx0 xk2 2 kx0k2 2”
Convergence analysis of alternating direction method of multipliers for a family of nonconvex problems (2014, background): “§Department of Electrical Engineering, Stanford University, Stanford, CA 94305 (meisamr@stanford.edu).”
Nuclear Norm Based Matrix Regression with Applications to Face Recognition with Occlusion and Illumination Changes (2014, methodology): “The authors of [45], [46] has showed that ADMM can achieve O 1=k ð Þ global convergence, where k is the number of iterations, under a strong convexity assumption.”
An introduction to continuous optimization for imaging (2016, background): “A first important contribution is by Goldstein et al. (2014), who discuss various cases, and in the case considered here propose a heuristic approach which might be more efficient in practice.”
On the Global and Linear Convergence of the Generalized Alternating Direction Method of Multipliers (2016, background): “The work [21] proves that the dual objective value of a modification to the ADM descends at O(1/k2) under the assumption that the objective functions are strongly convex (one of them being quadratic) and both subproblems are solved exactly.”
Convex Optimization for Big Data: Scalable, randomized, and parallel algorithms for big data analytics (2014, methodology): “For the former, we can update z k +1 inexactly by using a single step of the proximal gradient method, which leads to the method shown in Algorithm 4 which was motivated in [19] as a preconditioned variant of ADMM and then analyzed in [20] in a more general framework.”
A General Analysis of the Convergence of ADMM (2015, unknown): “Goldstein et al. (2012) propose an accelerated version of ADMM in the spirit of Nesterov, and prove a O (1 /k 2 ) convergence rate in the case where f and g are both strongly convex and g is quadratic.”
Plug-and-Play ADMM for Image Restoration: Fixed-Point Convergence and Applications (2016, methodology): “The adaptive update scheme is inspired from [40], which was originally used to accelerate ADMM algorithms for convex problems.”