Convergence analysis of alternating direction method of multipliers for a family of nonconvex problems

By Mingyi Hong, Zhi-Quan Tom Luo, Meisam Razaviyayn. 2014

990 citations recorded by the source corpus.

In this paper, we analyze the behavior of the alternating direction method of multipliers (ADMM), for solving a family of nonconvex problems. Our focus is given to the well-known consensus and sharing problems, both of which have wide applications in signal processing. We show that in the presence of nonconvex objective function, classical ADMM is able to reach the set of stationary solutions for these problems, if the stepsize is chosen large enough. An interesting consequence of our analysis is that the ADMM is convergent for a family of sharing problems, regardless of the number of blocks or the convexity of the objective function. Our analysis is broadly applicable to many ADMM variants involving proximal update rules and various flexible block selection rules.

Subfields: 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 Computational Mechanics

In Signal Processing

Citations in the corpus

Learning Privately over Distributed Features: An ADMM Sharing Approach (2019, methodology): “…theoretical convergence guarantees and iteration complexity results under the non-convex loss in a fully parallel setting, whereas previously, the convergence of ADMM sharing algorithm for non-convex losses is only known for the case of sequential (Gauss-Seidel) execution Hong et al. (2016).”
Federated Tensor Factorization for Computational Phenotyping (2017, methodology): “e optimization problem (5) is then solved via consensus alternating direction method of multipliers (ADMM) [2], which decomposes the original problem into sub-problems using auxiliary variables and ensures convergence to a stationary point even with nonconvex problem [15].”
L G ] 1 1 A pr 2 01 7 Federated Tensor Factorization for Computational Phenotyping (2018, methodology): “e optimization problem (5) is then solved via consensus alternating direction method of multipliers (ADMM) [2], which decomposes the original problem into sub-problems using auxiliary variables and ensures convergence to a stationary point even with nonconvex problem [15].”
Prox-PDA: The Proximal Primal-Dual Algorithm for Fast Distributed Nonconvex Optimization and Learning Over Networks (2017, methodology): “This observation suggests that in contrast to (Hong et al., 2014; Hajinezhad et al., 2016a) the augmented Lagrangian alone cannot serve as the potential function for Prox-PDA.”
Plug-and-Play ADMM for Image Restoration: Fixed-Point Convergence and Applications (2016, neutral): “(8) 2 Treatingṽ(k) as the “noisy” image, (8) minimizes the residue betweenṽ(k) and the “clean” imagev using the priorg(v).”
A Distributed, Asynchronous and Incremental Algorithm for Nonconvex Optimization: An ADMM Based Approach (2014, methodology): “We refer the readers to [43] for detailed arguments.”
Global Convergence of ADMM in Nonconvex Nonsmooth Optimization (2015, methodology): “[26] deals with the nonconvex separable objective functions for some specific Ai, which forms the sharing and consensus problem.”
Sparse Array Beampattern Synthesis via Alternating Direction Method of Multipliers (2018, background): “ADMM has also been applied to solve nonconvex problems, and the progress is continually made for the corresponding convergence analysis [30].”
Gradient Primal-Dual Algorithm Converges to Second-Order Stationary Solutions for Nonconvex Distributed Optimization (2018, methodology): “In particular, reference (Hong et al., 2016) develops non-convex ADMM based methods (with global sublinear convergence rate) for solving the global consensus problem (3).”
Distributed Non-Convex First-Order optimization and Information Processing: Lower Complexity Bounds and Rate Optimal Algorithms (2018, background): “However, no lower bound analysis has been developed for distributed non-convex problem (1); there are even not many algorithms that provide achievable rate bounds (except for the recent works [12]–[15]), not to mention any analysis on the tightness/sharpness of these upper bounds.”
NESTT: A Nonconvex Primal-Dual Splitting Method for Distributed and Stochastic Optimization (2016, methodology): “We define the optimality gap by adding to ‖∇̃L(w)‖(2) the size of the constraint violation [13]:”
Calculus of the Exponent of Kurdyka–Łojasiewicz Inequality and Its Applications to Linear Convergence of First-Order Methods (2016, positive): “One future research direction is to develop calculus rules for deducing the exponent of potential functions such as the augmented Lagrangian function Lβ(x, y, z) = f (x) + g(y) + zT (x − y) + β2 ‖x − y‖2 used in the convergence analysis of the alternating direction method of multiplier in a nonconve”
FedLoc: Federated Learning Framework for Data-Driven Cooperative Localization and Location Data Processing (2020, methodology): “Next, we continue to introduce a more recent proximal ADMM (short as pxADMM) scheme proposed in [91], which is capable of reducing the communication overhead and the computational time at the same time .”
Walkman: A Communication-Efficient Random-Walk Algorithm for Decentralized Optimization (2018, methodology): “We will use inequality (4) to show the sufficient descent of a Lyapunov function L, which was used in [33] and extended in [34].”
A Unified Algorithmic Framework for Block-Structured Optimization Involving Big Data: With applications in machine learning and signal processing (2015, background): “For extensions to nonconvex problems, see the recent work [90] and [91].”
Adversarial Robustness vs. Model Compression, or Both? (2019, background): “In this work, we use the ADMM approach due to its potential for all the pruning schemes and its compatibility with adversarial training, as shall be demonstrated in the later section.”
An introduction to continuous optimization for imaging (2016, background): “…conditions which guarantee convergence to a critical point (of the Lagrangian) are given in a few recent papers (Chartrand and Wohlberg 2013, Magnússon, Chathuranga Weeraddana, Rabbat and Fischione 2014, Hong et al. 2015, Wang, Yin and Zeng 2015), sometimes involving more than two blocks.”