Alternating Direction Method of Multipliers for Machine Learning (Hardcover)

· 제목 : Alternating Direction Method of Multipliers for Machine Learning (Hardcover) 
· 분류 : 외국도서 > 컴퓨터 > 인공지능(AI)
· ISBN : 9789811698392
· 쪽수 : 263쪽
· 출판일 : 2022-06-16

1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

1.1 Examples of Constrained Optimization Problems in Machine Learning  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

1.2 Sketch of Representative Works on ADMM . . . . . . . . . . . . . . . . . . . . . . 3

1.3 About the Book . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

2 Derivations of ADMM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

2.1 Lagrangian Viewpoint of ADMM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

2.1.1 Dual Ascent . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

2.1.2 Augmented Lagrangian Method . . . . . . . . . . . . . . . . . . . . . . . . . . 12

2.1.3 Alternating Direction Method of Multipliers . . . . . . . . . . . . . . . . 14

2.1.4 Relation to the Split Bregman Method . . . . . . . . . . . . . . . . . . . . . 15

2.2 Operator Splitting Viewpoint of ADMM . . . . . . . . . . . . . . . . . . . . . . . 17

2.2.1 Douglas-Rachford Splitting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

2.2.2 From DRS to ADMM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

3 ADMM for Deterministic and Convex Optimization . . . . . . . . . . . . . . . . . . . 21

3.1 Original ADMM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

3.1.1 Convergence Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

3.1.2 Sublinear Convergence Rate . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

3.1.3 Linear Convergence Rate . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

3.2 Bregman ADMM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

3.2.1 Sublinear Convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

3.2.2 Linear Convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

3.3 Accelerated Linearized ADMM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

3.3.1 Sublinear Convergence Rate . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

3.3.2 Linear Convergence Rate . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65

3.4 Special Case: Linearized Augmented Lagrangian Method and Its

Acceleration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72

3.5 Multi-block ADMM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74

3.5.1 Gaussian Back Substitution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75

3.5.2 Linearized ADMM with Parallel Splitting . . . . . . . . . . . . . . . . . . . 78

3.5.3 Combing the Serial and the Parallel Update Orders . . . . . . . . . . . . 80

3.6 The Constraint is Nonlinear . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81

References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86

4 ADMM for Nonconvex Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89

4.1 Multi-block Bregman ADMM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89

4.1.1 No Assumptions on the Linear Constraint but More

Assumptions on the Objectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94

4.2 Proximal ADMM with Exponential Averaging . . . . . . . . . . . . . . . . . . . 96

4.3 ADMM for Multilinearly Constrained Optimization . . . . . . . . . . . . . . 105

4.3.1 Nonnegative Matrix Factorization . . . . . . . . . . . . . . . . . . . . . . . . 106

4.3.2 Robust PCA. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .110

References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114

5 Stochastic ADMM. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115

5.1 Stochastic ADMM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116

5.2 Variance Reduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121

5.3 Momentum Acceleration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129

5.4 Non-convex Stochastic ADMM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153

5.4.1 Non-convex SADMM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153

5.4.2 SPIDER Acceleration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157

References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164

6 ADMM for Distributed Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167

6.1 Centralized Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167

6.1.1 ADMM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168

6.1.2 Linearized ADMM. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170

6.1.3 Accelerated Linearized ADMM . . . . . . . . . . . . . . . . . . . . . . . . . 171

6.2 Decentralized Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172

6.2.1 ADMM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173

6.2.2 Linearized ADMM. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178

6.2.3 Acceleration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179

6.3 Asynchronous Distributed ADMM . . . . . . . . . . . . . . . . . . . . . . . . . . . 181

6.3.1 Convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181

6.3.2 Linear Convergence Rate . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186

6.3.3 Randomized Asynchronous ADMM . . . . . . . . . . . . . . . . . . . . . 192

6.4 Nonconvex Distributed ADMM. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .199

6.5 ADMM with Generally Linearly Constraints . . . . . . . . . . . . . . . . . . . 199

References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 200

7 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203

7.1 Practical Issues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203

7.1.1 Stopping Criterion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203

7.1.2 Adaptive Penalty Parameters . . . . . . . . . . . . . . . . . . . . . . . . . . . . 204

References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205

8 Mathematical Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207

8.1 Notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207

8.2 Algebra and Probability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 208

8.3 Convex Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 210

8.4 Nonconvex Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215

References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215

Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217