The direct extension of ADMM for multi-block convex minimization problems is not necessarily convergent

By Caihua Chen, Bingsheng He, Yinyu Ye, Xiaoming Yuan. 2014

771 citations recorded by the source corpus.

Subfields: Civil and Structural 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 Civil and Structural Engineering

In Computational Mechanics

In Signal Processing

Citations in the corpus

GADMM: Fast and Communication Efficient Framework for Distributed Machine Learning (2019, methodology): “However, this convergence rate is ensured only under the block size smaller than 3 (Chen et al., 2016), and its primal variables are sequentially updated, which is ill-suited for fast implementation.”
Multi-label Learning with Missing Labels Using Mixed Dependency Graphs (2018, background): “1 C2 C3 C4 C5 C6 Corel 5k [15] 260 138 37 98 99 5 ESP Game [40] 268 129 41 92 120 4 IAPRTC-12 [23] 291 179 36 132 98 4 MediaMill [35] 101 63 14 52 30 3 In terms of the convergence, as demonstrated in [9], the ADMM algorithm for multi-block (more than 2 blocks) convex optimization is not necessarily ”
Dykstra's Algorithm, ADMM, and Coordinate Descent: Connections, Insights, and Extensions (2017, background): “After all, both of these are multi-block ADMM approaches, and multi-block ADMM has subtle convergence behavior as studied, e.g., in Lin et al. (2015); Chen et al. (2016).”
Convergence analysis of alternating direction method of multipliers for a family of nonconvex problems (2014, neutral): “R ed is tr ib ut io n su bj ec t t o SI A M li ce ns e or c op yr ig ht ; s ee h ttp :// w w w .s ia m .o rg /jo ur Copyright © by SIAM.”
ADMM Based Privacy-Preserving Decentralized Optimization (2017, background): “In fact, as indicated in [47], a direct extension from twoblock to multi-block convex minimization is not necessarily convergent.”
Global Convergence of ADMM in Nonconvex Nonsmooth Optimization (2015, background): “In [11], their divergence example is minimize x1,x2,y 0 (35a)”
A Three-Operator Splitting Scheme and its Optimization Applications (2015, background): “Recently, it was shown that the direct extension of ADMM to three blocks does not converge [14].”
Parallel Direction Method of Multipliers (2014, methodology): “In some cases, it has been shown that ADMM might not converge for multiple blocks [7].”
On Full Jacobian Decomposition of the Augmented Lagrangian Method for Separable Convex Programming (2015, methodology): “Keywords: Convex programming, augmented Lagrangian method, Jacobian decomposition, contraction methods, convergence rate, operator splitting methods, assignment problem”
Sparse Representation for 3D Shape Estimation: A Convex Relaxation Approach (2015, background): “Note that there is no theoretical guarantee for the convergence of ADMM solving a multi-block problem as (33) [60], while the developed algorithm works well in practice.”
Randomized First-Order Methods for Saddle Point Optimization (2014, neutral): “show in [8] that a direct extension of ADMM does not necessarily converge for solving this type of problem whenever p ≥ 3.”
Q-GADMM: Quantized Group ADMM for Communication Efficient Decentralized Machine Learning (2019, positive): “It was shown in [45] that Gauss-Seidel ADMM [34] achieves the convergence rate o (1 /k ) .”
A simple algorithm for a class of nonsmooth convex-concave saddle-point problems (2015, background): “, [5] where even the convergence become an issue.”
Parallel Multi-Block ADMM with o(1 / k) Convergence (2013, positive): “By using this adaptive strategy, the resulting paramters { P i } are usually much smaller than those required by the condition (2.8), thereby leading to substantially faster convergence in practice.”