Accelerated Optimization for Machine Learning: First-Order Algorithms

Foreword by Michael I. Jordan
Foreword by Zongben Xu
Foreword by Zhi-Quan Luo
Preface
	References
Acknowledgements
Contents
About the Authors
Acronyms
1 Introduction
	1.1 Examples of Optimization Problems in Machine Learning
	1.2 First-Order Algorithm
	1.3 Sketch of Representative Works on Accelerated Algorithms
	1.4 About the Book
	References
2 Accelerated Algorithms for Unconstrained Convex Optimization
	2.1 Accelerated Gradient Method for Smooth Optimization
	2.2 Extension to Composite Optimization
		2.2.1 Nesterov's First Scheme
		2.2.2 Nesterov's Second Scheme
			2.2.2.1 A Primal-Dual Perspective
		2.2.3 Nesterov's Third Scheme
	2.3 Inexact Proximal and Gradient Computing
		2.3.1 Inexact Accelerated Gradient Descent
		2.3.2 Inexact Accelerated Proximal Point Method
	2.4 Restart
	2.5 Smoothing for Nonsmooth Optimization
	2.6 Higher Order Accelerated Method
	2.7 Explanation: A Variational Perspective
		2.7.1 Discretization
	References
3 Accelerated Algorithms for Constrained Convex Optimization
	3.1 Some Facts for the Case of Linear Equality Constraint
	3.2 Accelerated Penalty Method
		3.2.1 Generally Convex Objectives
		3.2.2 Strongly Convex Objectives
	3.3 Accelerated Lagrange Multiplier Method
		3.3.1 Recovering the Primal Solution
		3.3.2 Accelerated Augmented Lagrange Multiplier Method
	3.4 Alternating Direction Method of Multiplier and Its Non-ergodic Accelerated Variant
		3.4.1 Generally Convex and Nonsmooth Case
		3.4.2 Strongly Convex and Nonsmooth Case
		3.4.3 Generally Convex and Smooth Case
		3.4.4 Strongly Convex and Smooth Case
		3.4.5 Non-ergodic Convergence Rate
			3.4.5.1 Original ADMM
			3.4.5.2 ADMM with Extrapolation and Increasing Penalty Parameter
	3.5 Primal-Dual Method
		3.5.1 Case 1: μg=μh=0
		3.5.2 Case 2: μg>0, μh=0
		3.5.3 Case 3: μg=0, μh>0
		3.5.4 Case 4: μg>0, μh>0
	3.6 Faster Frank–Wolfe Algorithm
	References
4 Accelerated Algorithms for Nonconvex Optimization
	4.1 Proximal Gradient with Momentum
		4.1.1 Convergence Theorem
		4.1.2 Another Method: Monotone APG
	4.2 AGD Achieves Critical Points Quickly
		4.2.1 AGD as a Convexity Monitor
		4.2.2 Negative Curvature Descent
		4.2.3 Accelerating Nonconvex Optimization
	4.3 AGD Escapes Saddle Points Quickly
		4.3.1 Almost Convex Case
		4.3.2 Very Nonconvex Case
		4.3.3 AGD for Nonconvex Problems
			4.3.3.1 Locally Almost Convex → Globally Almost Convex
			4.3.3.2 Outer Iterations
			4.3.3.3 Inner Iterations
	References
5 Accelerated Stochastic Algorithms
	5.1 The Individually Convex Case
		5.1.1 Accelerated Stochastic Coordinate Descent
		5.1.2 Background for Variance Reduction Methods
		5.1.3 Accelerated Stochastic Variance Reduction Method
		5.1.4 Black-Box Acceleration
	5.2 The Individually Nonconvex Case
	5.3 The Nonconvex Case
		5.3.1 SPIDER
		5.3.2 Momentum Acceleration
	5.4 Constrained Problem
	5.5 The Infinite Case
	References
6 Accelerated Parallel Algorithms
	6.1 Accelerated Asynchronous Algorithms
		6.1.1 Asynchronous Accelerated Gradient Descent
		6.1.2 Asynchronous Accelerated Stochastic Coordinate Descent
	6.2 Accelerated Distributed Algorithms
		6.2.1 Centralized Topology
			6.2.1.1 Large Mini-Batch Algorithms
			6.2.1.2 Dual Communication-Efficient Methods
		6.2.2 Decentralized Topology
	References
7 Conclusions
	References
A Mathematical Preliminaries
	A.1 Notations
	A.2 Algebra and Probability
	A.3 Convex Analysis
	A.4 Nonconvex Analysis
	References
Index