PaperlayerView exact revision on arXiv

Source-linked AI summary

Linear Coupling: An Ultimate Unification of Gradient and Mirror Descent

Zeyuan Allen-Zhu, Lorenzo Orecchia

arXiv:1407.1537v5cs.DScs.LGmath.NAmath.OCstat.ML

TL;DR

Large-scale convex optimization needs fast first-order methods, but gradient descent and mirror descent emphasize complementary primal and dual progress. The paper introduces linear coupling to combine them, reconstruct Nesterov’s accelerated methods, and extend the framework beyond their original scope. The resulting approach supports constrained and unconstrained problems under general norms, while the warm-up method’s caveats are addressed by variable step lengths.

  • Problem

    First-order methods largely rely on gradient descent and mirror descent, whose complementary primal and dual perspectives motivate a unified acceleration framework.

  • Method

    The paper linearly couples gradient-descent and mirror-descent sequences, using a shared gradient at a carefully chosen convex combination of their iterates.

  • Results

    The framework reconstructs Nesterov’s accelerated gradient methods and extends to settings beyond their original scope, including constrained problems and general norms.

  • Takeaways & Limitations

    Linear coupling provides a simple, complete accelerated gradient method and supports applications where classical accelerated methods do not apply.

  • Takeaways & Limitations

    The warm-up fixed-step algorithm requires knowledge of Θ, an initial distance bound d, and restarting; variable step lengths address these caveats.

Abstract

from arXiv · show

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.

1 Introduction

First-order methods are central for large-scale convex optimization, where gradient descent and mirror descent provide complementary primal and dual progress. The paper couples these approaches to reconstruct accelerated gradient methods and extend them beyond their classical scope.

  • First-order methods are widely used for large-scale convex problems because their iterations are cheap and often highly parallelizable.
  • Gradient descent emphasizes primal progress, while mirror descent constructs lower bounds and focuses on the dual problem.
  • The resulting method applies to any norm and both constrained and unconstrained settings, while extending to applications beyond classical accelerated gradient methods.
  • Gradient and mirror descent cannot simply be interleaved: mirror steps may increase the objective, while intervening gradient steps can disrupt mirror-descent convergence.
  • Linear coupling combines the two updates through x_k+1 = τz_k + (1 −τ)y_k and evaluates the same gradient for both sequences.With a carefully chosen τ, the coupled sequences recover Nesterov’s convergence guarantee.

2 Key Lemmas of Gradient and Mirror Descent

The paper reviews gradient descent as a smoothness-based primal method and mirror descent as a regularized-regret method for constructing dual lower bounds. Their analyses depend on norms, constraints, smoothness or Lipschitz assumptions, and the chosen regularizer.

  • 2.1 Review of Gradient Descent: For an L-smooth convex function on Q, gradient descent uses a step based on the smoothness upper bound to obtain guaranteed objective decrease.
  • 2.1 Review of Gradient Descent: In Euclidean unconstrained problems, the gradient update has the familiar form x_k+1 = x_k −1/L∇f(x_k), while general norms can produce different updates.
  • 2.2 Review of Mirror Descent: A distance generating function is required to be 1-strongly convex with respect to the chosen norm, yielding a nonnegative divergence used by mirror descent.
  • 2.2 Review of Mirror Descent: Euclidean quadratic and entropy regularizers instantiate mirror descent for ℓ2 and ℓ1 geometries, respectively.
  • 2.2 Review of Mirror Descent: Mirror descent minimizes regularized regret using a strongly convex regularizer, driving the maximum regularized regret down as iterations increase.

3 Warm-Up Method with Fixed Step Length

The warm-up method linearly couples gradient and mirror steps by interpolating their iterates, balancing objective decrease with mirror-descent progress to obtain acceleration.

  • Algorithm: The method combines a gradient step and a mirror step at every iteration, with their iterates linked through a coupling parameter τ.It initializes x0 = y0 = z0, forms xk+1 from zk and yk, then updates yk+1 and zk+1.
  • Parameter choice: The mirror-step length α is chosen from mirror-descent analysis, while τ balances the gradient and mirror contributions.The paper explicitly relates α to the mirror-descent guarantee and τ to balancing the two steps.
  • Linear coupling: Linear coupling resolves the incompatibility between telescoping regret terms and telescoping objective decreases caused by choosing either τ = 1 or τ = 0.τ = 1 preserves the regret structure but loses objective telescoping, whereas τ = 0 reverses that trade-off.
  • Linear coupling: The coupled analysis balances the objective decrease f(xk+1) − f(yk+1) against the possible increase f(yk) − f(xk+1).This balance is the role assigned to τ in the proof.
  • Convergence: Halving the distance to the optimum in each restarted run yields an ε-approximate solution, with running time matching Nesterov’s accelerated methods.The warm-up procedure requires repeated restarts, and the resulting rate is reported as matching Nesterov’s accelerated methods.
  • Caveats: The fixed-step version requires knowledge of Θ, an initial distance bound d, and repeated restarts.The subsequent variable-step method is introduced to overcome these caveats.

4 Final Method with Variable Step Lengths

The final method replaces fixed parameters with iteration-dependent step lengths and coupling rates, extending linear coupling to constrained smooth convex optimization.

  • Final method: The final method recovers accelerated gradient methods in the constrained setting using linear coupling.The paper presents this as recovering the main constrained result of prior accelerated-gradient work.
  • Convergence: For L-smooth f and a 1-strongly convex distance-generating function w, AGM guarantees f(yT) ≤ f(x∗) + 4ΘL/(T+1)^2.The bound follows by telescoping the variable-step convergence inequality.
  • Algorithm: AGM interpolates zk and yk to form xk+1, then performs both a gradient step and a mirror step at each iteration.The algorithm starts from x0 = y0 = z0 and updates yk+1 and zk+1 after forming the coupled point.
  • Parameter choice: The coupling rate τk is set from the variable mirror-step length αk+1 and smoothness parameter L, with τk constrained to (0, 1].The stated choice is τk = 1/(αk+1L), and αk+1 is selected so this range holds.
  • Scope and comparison: The variable-step construction removes the fixed-step method’s dependence on Θ, an initial distance bound, and repeated restarts.The paper introduces changing α and τ across iterations to overcome those earlier caveats and handle constrained Q.
  • Scope and comparison: The method allows arbitrary starting points and general norms, unlike the better-known momentum method, which does not apply to non-Euclidean settings.The paper also notes that its mirror-step formulation differs from the cited dual-averaging version.
  • Implications: Linear coupling also provides a complete proof of the existing accelerated gradient methods, including the strong-convexity version recovered in an appendix.This conclusion is stated explicitly after the constrained AGM result.

5 Beyond Accelerated Gradient Methods

Linear coupling extends beyond standard accelerated gradient methods by combining gradient and mirror-descent ideas in settings where Nesterov’s methods do not apply. The framework supports non-smooth, stochastic, coordinate-descent, and non-convex problems.

  • Extension 1: Strengthening (5.2) and (5.1): Linear coupling can combine strengthened objective-decrease and mirror-descent lemmas to obtain faster methods beyond Nesterov’s scope.This extension applies when objectives have useful properties beyond smoothness or when non-strongly convex regularizers are needed.
  • Extension 1: Strengthening (5.2) and (5.1): For positive linear programs, linear coupling produces faster algorithms than naively applying Nesterov’s methods to a smoothed objective in all parameter regimes.The approach uses a weaker objective-decrease bound based on the original non-smooth objective.
  • Extension 2: Three-Point Coupling: Three-point coupling restores acceleration for stochastic gradients by combining gradient, mirror-descent, and variance-reduction inequalities.The coupling uses a rarely refreshed snapshot point whose full gradient is computed exactly.
  • Extension 3: Optimal Sampling Probability: Choosing coordinate i with probability proportional to √Li yields the fastest accelerated coordinate-descent method described here.The choice follows by balancing the gradient and coupling terms, 1/(2Li)(∇if(x))2 and α2/(2p_i^2)(∇if(x))2.
  • Extension 4: Supporting Non-Convexity: For non-convex smooth objectives, a quadratic lower bound replaces the unavailable convexity inequality, yielding a weaker linear-coupling method.The resulting stochastic algorithm converges to approximate saddle-points and outperforms gradient descent and stochastic gradient descent.

A Several Remarks on First-Order Methods

The paper emphasizes that first-order methods depend on the geometry induced by the chosen norm. For simplex saddle-point problems, the ℓ1 geometry can provide more natural smoothness conditions and faster positive-LP solvers than ℓ2 geometry.

  • Norms: The ℓ1 norm is crucial for some applications, including minimum enclosing balls and nearly-linear-time maximum flow.The paper contrasts these uses with methods restricted to the Euclidean norm.
  • Saddle-point formulation: For the simplex saddle-point problem, optimizing the smoothed objective over x ∈∆n yields an additive ε/2 solution to the original problem.The smoothing parameter is set to µ = ε/(2 log m).
  • Norm-dependent smoothness: The smoothed objective is 1/µ-smooth in the ℓ1 norm when A’s entries lie in [−1,1].This condition is weaker and more natural than the corresponding ℓ2 requirement.
  • Norm-dependent smoothness: The ℓ2 smoothness condition requires every row of A to have squared entries summing to at most 1, whereas the ℓ1 condition only bounds A’s entries.The ℓ1 condition leads to the fastest approximate width-dependent positive-LP solver cited here.
  • Norm-dependent updates: Different norm choices produce different gradient and mirror-descent updates on the simplex.In the ℓ2 case, both steps have the same stated minimization form, unlike the ℓ1 case.

A.2 Folklore Relationship Between Multiplicative Weight Updates and Mirror Descent

The appendix re-derives multiplicative weight updates as a mirror-descent method on the simplex. Its regret guarantee follows by applying mirror-descent analysis to bounded loss vectors.

  • MWU setting: MWU chooses actions in the simplex and observes a loss vector only after each action is played.The incurred loss is ⟨ℓk, xk⟩.
  • MWU guarantee: If every loss vector satisfies ∥ℓk∥∞≤ρ, MWU guarantees a bounded average regret against any action in the simplex.The average regret compares suffered loss with the best action in hindsight.
  • Mirror-descent derivation: Using the entropy distance-generating function yields the multiplicative update xk+1,i = xk,i · exp(−αℓk,i)/Zk.The normalization factor ensures the updated vector remains on the simplex.
  • Mirror-descent derivation: The mirror-descent proof telescopes over iterations and uses ∥ℓk∥∞≤ρ and Vx0(u)≤log n to recover the average-regret bound.The same analysis extends to matrix MWU and width-reduction techniques, though those extensions are outside this paper’s scope.

A.3 Deducing the Mirror-Descent Guarantee via Gradient Descent

The appendix derives mirror-descent convergence from gradient descent by viewing dual averaging as gradient descent on a Fenchel-dual regularized-regret objective. This recovers the same convergence rate as the original mirror-descent analysis.

  • Gradient-descent interpretation: Dual averaging steps are equivalent to gradient steps on the Fenchel dual of regularized regret.A similar derivation exists for mirror steps but is more notationally involved.
  • Regret framework: The regret framework bounds the distance between f(u) and the average iterate x = 1/T (x0 + ··· + xT−1).The bound applies to any comparator u in the constraint set.
  • Regularized regret: Selecting x0 at the minimizer of the regularizer and choosing subsequent points through the regularized-regret changes controls the cumulative regret.The starting-point choice is standard for the cleanest analysis but can be relaxed to an arbitrary point.
  • Regularized regret: Smoothness of the Fenchel dual bounds each step’s regularized-regret increase by α2ρ2/2.The resulting cumulative bound is bR(x0,…,xT−1) ≤ −w(x0) + α2ρ2T/2.
  • Convergence guarantee: The resulting convergence rate is the same as the mirror-descent rate in equation (2.4).The appendix obtains this rate from the gradient-descent interpretation rather than directly from mirror steps.

B Missing Proof of Section 2

This section provides self-contained proofs for the mirror descent guarantees discussed in the paper.

  • The section supplies self-contained proofs of the mirror descent guarantees.
  • The proofs are presented for completeness alongside the paper’s development of mirror descent.
  • These guarantees form the formal basis for the mirror-descent analysis used in the paper.

B.1 Missing Proof for Gradient Descent

The gradient-descent proof combines smoothness, convexity, and monotone objective decrease to relate gradient size to progress and derive convergence.

  • The proof uses the smoothness assumption to establish a decrease inequality for each gradient step.
  • The stated gradient-descent fact applies to convex differentiable L-smooth functions on Q = R^n after T gradient steps.
  • Convexity and Cauchy–Schwarz bound the objective gap by the gradient norm and the distance to an optimum.
  • Defining D_k as the objective gap, the proof combines per-step decrease with D_k ≤ R · ∥∇f(x_k)∥_* to obtain convergence.
  • Because the objective decreases at every round, D_k ≥ D_{k+1}, enabling the final telescoping argument.

C Missing Proofs of Section 4

The Section 4 proofs establish the coupling inequalities by combining gradient-descent progress with mirror-descent analysis and carefully chosen interpolation parameters.

  • Lemma 4.2 supplies a mirror-descent inequality when τ_k = 1/(α_{k+1}L).
  • The second coupling inequality invokes the gradient-descent guarantee, while the unconstrained case uses Prog(x_{k+1}) = 1/(2L)∥∇f(x_{k+1})∥_*^2.
  • The mirror-descent step is defined by minimizing a Bregman-divergence term plus a linearized objective term over Q.
  • Strong convexity of the distance-generating function converts the Bregman divergence into a squared-norm bound.
  • The proof chooses x_{k+1} through τ_k(x_{k+1} − z_k) = (1 − τ_k)(y_k − x_{k+1}) and uses convexity, Lemma 4.2, and the parameter choice.

D Strong Convexity Version of Accelerated Gradient Method

The paper recovers the strongly convex accelerated method by modifying the mirror-descent analysis or recursively applying its main theorem, achieving logarithmic accuracy dependence.

  • For objectives that are both σ-strongly convex and L-smooth under the same norm, an accelerated method achieves log(1/ε) convergence.
  • One recovery route replaces mirror-descent regret analysis with a strong-convexity, or logarithmic-regret, counterpart.
  • A simpler route recursively applies Theorem 4.1, repeatedly feeding each run’s output into the next run.
  • The analysis bounds the final function gap by 4 · 1/2∥x_0 − x*∥_2^2 · L/T^2 and relates it to the squared distance to x*.
  • The paper notes that heuristic adaptive restarting has been reported to practically outperform Nesterov’s original method.
Loading 1407.1537v5…