Linear Coupling: An Ultimate Unification of Gradient and Mirror Descent

By Zeyuan Allen-Zhu, Lorenzo Orecchia. 2014

309 citations recorded by the source corpus.

First-order methods play a central role in large-scale machine learning. Even though many variations exist, each suited to a particular problem, almost all such methods fundamentally rely on two types of algorithmic steps: gradient descent, which yields primal progress, and mirror descent, which yields dual progress. We observe that the performances of gradient and mirror descent are complementary, so that faster algorithms can be designed by LINEARLY COUPLING the two. We show how to reconstruct Nesterov's accelerated gradient methods using linear coupling, which gives a cleaner interpretation than Nesterov's original proofs. We also discuss the power of linear coupling by extending it to many other settings that Nesterov's methods cannot apply to.

Subfields: Artificial Intelligence

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

Citations in the corpus

How To Make the Gradients Small Stochastically: Even Faster Convex and Nonconvex SGD (2018, neutral): “Recall that starting from a point x0, if we perform T steps of gradient descent (GD) xt+1 = xt− 1 L∇f(xt), then it satisfies ∑T−1 t=0 ‖∇f(xt)‖(2) ≤ L(f(x0)− f(x∗)) (see for instance [7, 23]).”
Katyusha: the first direct acceleration of stochastic gradient methods (2016, methodology): “This should not be a big surprise because in accelerated full-gradient methods, the values τ1 and α also decrease (although with respect to k rather than s) when there is no strong convexity [8].”
Accelerated Mirror Descent in Continuous and Discrete Time (2015, methodology): “This algorithm is a generalization of Allen-Zhu and Orecchia’s interpretation of Nesterov’s method in [1], where x is a convex combination of a mirror descent update and a gradient descent update.”
On the Convergence of Nesterov's Accelerated Gradient Method in Stochastic Settings (2020, methodology): “Aybat et al. (2019) and Kulunchakov & Mairal (2019a) consider smooth stronglyconvex functions in a stochastic approximation model with gradients that are unbiased and have bounded variance, and they show convergence to a neighborhood when running the method with constant step size and momentum. Can ”
Accelerated Methods for Non-Convex Optimization (2016, background): “Bubeck et al. [10] develop an AGD algorithm with a geometric interpretation based on shrinking spheres, while the work of Allen-Zhu and Orecchia [5] shows that AGD may be viewed as a coupling between mirror descent [28] and gradient descent; this perspective highlights how to trade each method’s adv”
An introduction to continuous optimization for imaging (2016, background): “Another natural and clever approach to deal with this boundary issue, suggested by Almeida and Figueiredo (2013), is to replace the data term with 1 2‖M(a ∗ u− u )‖2, where M is a diagonal mask which is zero in a strip, of width the size of the support of a, along the boundaries, and 1 in the middle”
Much Faster Algorithms for Matrix Scaling (2017, methodology): “14 Instead, we use the linear-coupling framework of [4] to recover this ε−2/3 convergence rate without using smoothness.”
Distributed Stochastic Variance Reduced Gradient Methods (2015, methodology): “This algorithm is related to the serial accelerated SVRG algorithm in [17] and largely inspired work by the work of [18] in the non-stochastic setting, but the algorithm is more suitable for distributed computation.”
Less than a Single Pass: Stochastically Controlled Stochastic Gradient (2016, background): “The next step is to bound the dual gap [3].”
Convex Optimization: Algorithms and Complexity (2014, methodology): “the method in terms of differential equations, and to Allen-Zhu and Orecchia [2014] for its relation to mirror descent (see Chapter 4).”
Optimal Affine-Invariant Smooth Minimization Algorithms (2018, methodology): “We will consider a slightly different accelerated method that can be seen as a combination of mirror and gradient descent steps (Allen-Zhu and Orecchia, 2014).”
A variational perspective on accelerated methods in optimization (2016, background): “In recent years, the number of explanations and interpretations of acceleration has increased [ 1, 3, 10, 20, 8], but these explanations have been focused on restrictive instances of acceleration, such as ﬁrst-order algorithms, the Euclidean setting, or cases in which the objective function is…”
Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descent (2017, background): “(2014) and Kawaguchi (2016) present such a result for learning neural networks, Bandeira et al. (2016); Mei et al. (2017) for synchronization and MaxCut, Boumal et al. (2016) for smooth semidefinite programs, Bhojanapalli et al. (2016) for matrix sensing, Ge et al. (2016) for matrix completion, and ”