Alternating Direction Method of Multipliers for Machine Learning

Foreword
Foreword
Preface
Acknowledgments
About the Book
Contents
Acronyms
1 Introduction
	1.1 Examples of Constrained Optimization Problems in Machine Learning
	1.2 Sketch of Representative Works on ADMM
	References
2 Derivations of ADMM
	2.1 Lagrangian Viewpoint of ADMM
		2.1.1 Dual Ascent
		2.1.2 Augmented Lagrangian Method
		2.1.3 Alternating Direction Method of Multipliers
		2.1.4 Relation to the Split Bregman Method
	2.2 Operator Splitting Viewpoint of ADMM
		2.2.1 Douglas–Rachford splitting
		2.2.2 From DRS to ADMM
	References
3 ADMM for Deterministic and Convex Optimization
	3.1 Original ADMM
		3.1.1 Convergence Analysis
		3.1.2 Sublinear Convergence Rate
			3.1.2.1 Non-ergodic Convergence Rate
			3.1.2.2 Ergodic Convergence Rate
		3.1.3 Linear Convergence Rate
			3.1.3.1 Linear Convergence Under the Strong Convexity and Smoothness Assumption
			3.1.3.2 Linear Convergence Under the Error Bound Condition
	3.2 Bregman ADMM
		3.2.1 Sublinear Convergence
			3.2.1.1 Ergodic Convergence Rate
			3.2.1.2 Non-ergodic Convergence Rate
		3.2.2 Linear Convergence
	3.3 Accelerated Linearized ADMM
		3.3.1 Sublinear Convergence Rate
		3.3.2 Linear Convergence Rate
	3.4 Special Case: Linearized Augmented Lagrangian Method and Its Acceleration
	3.5 Multi-block ADMM
		3.5.1 Gaussian Back Substitution
		3.5.2 Prediction-Correction
		3.5.3 Linearized ADMM with Parallel Splitting
		3.5.4 Combining the Serial and the Parallel Update Orders
	3.6 Variational Inequality Perspective
		3.6.1 Unified Framework in Variational Inequality
		3.6.2 Unified Convergence Rate Analysis
	3.7 The Case of Nonlinear Constraints
	References
4 ADMM for Nonconvex Optimization
	4.1 Multi-block Bregman ADMM
		4.1.1 With More Assumptions on the Objectives
	4.2 Proximal ADMM with Exponential Averaging
	4.3 ADMM for Multilinearly Constrained Optimization
	References
5 ADMM for Stochastic Optimization
	5.1 Stochastic ADMM
	5.2 Variance Reduction
	5.3 Momentum Acceleration
	5.4 Nonconvex Stochastic ADMM and Its Acceleration
		5.4.1 Nonconvex SADMM
		5.4.2 SPIDER Acceleration
	References
6 ADMM for Distributed Optimization
	6.1 Centralized Optimization
		6.1.1 ADMM
		6.1.2 Linearized ADMM
		6.1.3 Accelerated Linearized ADMM
	6.2 Decentralized Optimization
		6.2.1 ADMM
			6.2.1.1 Convergence Analysis
		6.2.2 Linearized ADMM
		6.2.3 Accelerated Linearized ADMM
	6.3 Asynchronous Distributed ADMM
		6.3.1 Convergence
		6.3.2 Linear Convergence Rate
	6.4 Nonconvex Distributed ADMM
	6.5 ADMM with Generally Linear Constraints
	References
7 Practical Issues and Conclusions
	7.1 Practical Issues
		7.1.1 Stopping Criterion
		7.1.2 Choice of Penalty Parameters
		7.1.3 Avoiding Excessive Auxiliary Variables
		7.1.4 Solving Subproblems Inexactly
		7.1.5 Other Considerations
	7.2 Conclusions
	References
A Mathematical Preliminaries
	A.1 Notations
	A.2 Algebra and Probability
	A.3 Convex Analysis
	A.4 Nonconvex Analysis
	References
Index