PaperlayerView exact revision on arXiv

Source-linked AI summary

A Universal Catalyst for First-Order Optimization

Hongzhou Lin, Julien Mairal, Zaid Harchaoui

arXiv:1506.02186v2math.OC

TL;DR

First-order methods need faster convergence for composite and large-sum objectives, including settings where some methods require strong convexity. The paper introduces Catalyst, which approximately minimizes well-chosen quadratic-regularized auxiliary problems while using extrapolation and inexactness control. It accelerates a broad family of methods, supports non-strongly convex objectives, and improves performance in ill-conditioned experiments.

  • Problem

    Existing methods such as Finito/MISO, SDCA, and SVRG may require strong convexity, while faster first-order rates are sought for general convex objectives and large sums.

  • Method

    Catalyst wraps a linearly convergent first-order method by approximately minimizing a sequence of quadratic-regularized auxiliary objectives with extrapolation.

  • Results

    Catalyst accelerates a large class of methods, provides support for non-strongly convex objectives, and produces significant practical speed-ups for ill-conditioned problems.

  • Takeaways & Limitations

    The scheme extends acceleration beyond classical methods to incremental algorithms and can stabilize MISO in a small-µ regime.

  • Takeaways & Limitations

    Acceleration of stochastic gradient methods is beyond the scope of the work, and some algorithms may require additional analysis or initialization.

Abstract

from arXiv · show

We introduce a generic scheme for accelerating first-order optimization methods in the sense of Nesterov, which builds upon a new analysis of the accelerated proximal point algorithm. Our approach consists of minimizing a convex objective by approximately solving a sequence of well-chosen auxiliary problems, leading to faster convergence. This strategy applies to a large class of algorithms, including gradient descent, block coordinate descent, SAG, SAGA, SDCA, SVRG, Finito/MISO, and their proximal variants. For all of these methods, we provide acceleration and explicit support for non-strongly convex objectives. In addition to theoretical speed-up, we also show that acceleration is useful in practice, especially for ill-conditioned problems where we measure significant improvements.

1 Introduction

The paper targets faster first-order optimization for composite objectives and large sums of functions. Its catalyst scheme accelerates many existing methods and directly supports non-strongly convex objectives.

  • Problem setting: Composite objectives combine a smooth data-fitting term with a possibly nonsmooth convex regularizer or constraint indicator.The smooth term may be a large sum, while the regularizer can promote sparsity or encode constraints.
  • Motivation: Gradient descent has O(1/k) convergence for convex objectives, while optimal first-order rates are O(1/k2); strong convexity yields linear convergence.Nesterov’s acceleration improves the known gradient-descent rates for convex and strongly convex objectives.
  • Motivation: Incremental methods reduce per-iteration cost independently of n by storing moderate information about past iterates.This contrasts with full-gradient methods that compute and average n gradients at every iteration.
  • Contributions: The catalyst is a generic acceleration scheme for full-gradient, block-coordinate, and incremental methods including SAG, SAGA, SDCA, SVRG, and Finito/MISO.Whether such incremental methods could be accelerated was presented as an important open question.
  • Contributions: The approach directly supports non-strongly convex objectives, avoiding the advance choice of a regularization parameter ε required by some methods.It also extends Finito/MISO to composite problems and removes its “big data condition” n ≥ βL/µ through a primal construction.
  • Related work: The analysis builds on an inexact accelerated proximal point perspective and uses estimate sequences to establish convergence under a criterion previously conjectured too weak for acceleration.The paper states that its analysis refutes that conjecture.

2 The Catalyst Acceleration

Catalyst wraps a linearly convergent first-order method in an accelerated procedure that approximately minimizes regularized auxiliary objectives. The quadratic regularization improves conditioning, while extrapolation and controlled inexactness support faster convergence.

  • Core scheme: Catalyst can wrap any first-order method with linear convergence on strongly convex objectives into an accelerated algorithm.The resulting method may also handle µ = 0 and achieve near-optimal convergence ˜O(1/k2).
  • Core scheme: At iteration k, the algorithm replaces F with an auxiliary objective Gk formed by adding a quadratic term around an extrapolated point yk, then minimizes Gk approximately.The inner method M solves each auxiliary problem to accuracy εk.
  • Conditioning: For gradient descent, the auxiliary objective has rate parameter τM,Gk = (µ + κ)/(L + κ) > τM,F = µ/L.The parameter κ trades off inner-solver time against how closely Gk approximates F.
  • Acceleration mechanism: The extrapolation step drives the next auxiliary solution toward yk and reduces the number of iterations when the subproblems are solved exactly.With εk = 0, this recovers the exact accelerated proximal point setting.
  • Inexactness: The weaker inexactness criterion Gk(xk) − Gk* ≤ εk is fixed from the initial point and enables complexity control using M’s linear convergence.In practice, the condition can often be checked through duality gaps.

3 Convergence Analysis

The analysis establishes convergence guarantees for the catalyst framework in both strongly convex and non-strongly convex settings, while accounting for the cost of approximately solving auxiliary problems.

  • Convergence analysis: The proof uses Nesterov estimate sequences extended to handle inexact auxiliary solves, covering both strongly convex and non-strongly convex objectives.The analysis controls accumulated errors through a methodology borrowed from inexact proximal-gradient methods.
  • Inner-loop complexity: Each strongly convex auxiliary problem reaches precision ε_k in ˜O(1/τ_M) inner iterations when initialized at the previous outer iterate.The resulting bound hides universal constants and logarithmic dependencies in µ and κ.
  • Strongly convex objectives: For strongly convex objectives, the catalyst method has a global linear convergence rate characterized by a user-selected parameter ρ.The theorem leaves ρ to the user and states that ρ = 0.9√... can safely be used.
  • Parameter choice: Choosing κ balances auxiliary-problem conditioning against the acceleration rate through the ratio τ_M/√(µ + κ).Larger κ improves the method's rate on the auxiliary objective, but κ is selected to maximize the stated ratio.
  • Non-strongly convex objectives: For non-strongly convex objectives, the method achieves the first-order optimal rate up to a logarithmic factor after accounting for inner-loop work.Producing x_k requires at most kT_M log(k + 2) calls to M, yielding a rate near-optimal relative to O(1/s^2).

4 Acceleration in Practice

The catalyst framework accelerates many first-order methods by approximately solving better-conditioned auxiliary problems, including composite and proximal variants. The section develops Proximal MISO, removes its big-data condition, and provides convergence certificates without duality.

  • Global acceleration: Catalyst accelerates full-gradient, coordinate, incremental, and randomized methods by optimizing a parameter κ for the inner and outer convergence rates.The global complexity combines inner-loop and outer-loop iteration bounds, with κ chosen to maximize the relevant rate ratio.
  • Proximal MISO: MISO-Prox extends Finito/MISO to composite objectives and removes the condition n ≥ βL/µ through modified lower-bound updates.Its iterate minimizes a lower bound, while the proximal extension computes the minimizer using the proximal operator of ψ.
  • Full gradient method: 123 Full gradient acceleration reaches ˜O(n√(L/µ) log(1/ε)), matching AFG up to logarithmic terms.A similar accelerated result is obtained for randomized coordinate descent.
  • Incremental methods: For incremental methods, acceleration is presented in the ill-conditioned regime n ≤ L/µ; outside that regime, the table reports no acceleration.The relevant κ choices have method-specific forms for SAG, SAGA, SVRG, SDCA, and Finito/MISO.
  • Proximal MISO: MISO-Prox uses the certificate F(xk) − Dk(xk), which upper-bounds the objective gap and converges linearly without requiring duality.The method is closely related to proximal SDCA but uses a purely primal construction and a different step size.

5 Experiments

The experiments evaluate Catalyst on SAG, SAGA, and MISO-Prox for ill-conditioned logistic-regression problems. Acceleration is especially effective for MISO, while the results also highlight the value of adapting to unknown strong convexity.

  • Experimental setup: The experiments test Catalyst on SAG, SAGA, and MISO-Prox using ℓ2-regularized logistic regression across real-sim, rcv1, and ocr.The datasets include up to n = 2 500 000 points and p = 47 152 variables, with regimes µ = 0, µ/L = 0.001/n, and µ/L = 0.1/n.
  • Experimental setup: The restarting strategy reuses gradients from the previous inner run, and AMISO2 restricts the inner method to at most one pass over the data.AMISO1 denotes the regular accelerated MISO variant.
  • Results: MISO obtains a huge speed-up from Catalyst, while AMISO2 is almost systematically the best performer in the small-µ regime.Catalyst also stabilizes MISO when the condition number is very large, including µ/L = 10−3/n = 4.10−10 for ocr.
  • Results: Catalyst accelerates SAG and SAGA generally, but the improvement is less significant than for MISO and SAGA without acceleration is best on ocr.The experiment suggests that adaptivity to unknown strong convexity is highly valuable for incremental optimization.
  • Results: Figure 1 compares objective value or duality gap against dataset passes, with AMISO, ASAGA, and ASAG denoting accelerated MISO, SAGA, and SAG.The legend for all curves is placed at the top right.

A.1 Proof of Theorem A.3

The proof constructs an approximate estimate sequence for Catalyst because its auxiliary problems are solved inexactly. It controls accumulated errors and applies extended sequence inequalities to derive convergence rates.

  • Approximate estimate sequence: The functions φk are constructed as quadratic approximate estimate-sequence functions with a canonical form.Their structure is characterized through minimizers vk, curvature γk, and recursive relations.
  • Approximate estimate sequence: The analysis replaces the exact estimate-sequence lower bound involving x∗k with an approximate bound based on xk and controls the resulting error.The approximation error is tied to Gk(xk) − Gk(x∗k).
  • Recursion: Algorithm 1 approximately satisfies the estimate-sequence condition, with the deviations represented by the sequence ξk.The choices of αk and yk cancel terms involving yk−1 − xk in the recursion.
  • Convergence bound: A proposition bounds the iterates through λk, the minimum value F∗, the minimizer x∗, and accumulated approximation terms.The proof combines strong convexity, the canonical form, and recurrences for the estimate-sequence quantities.
  • Convergence bound: Lemma A.10 controls the nonnegative error sequences needed to bound the accumulated inexactness and complete Theorem A.3.The final step applies the lemma to the recurrence and obtains the desired result.
  • Specialization: With α0 = √q, the recursion simplifies to λk = (1 − √q)k, yielding the stated specialized convergence result.The specialization uses γ0 = µ and strong convexity of F.

B.2 Proof of Proposition 3.2

The proof of Proposition 3.2 bounds the work required to solve each auxiliary problem. It relates successive auxiliary objectives, controls extrapolation-point differences, and derives an inner-iteration bound.

  • Boundary cases: The proof handles k = 1 and k = 2 separately before applying the general k ≥ 3 bound.For k = 1, x0 = y0 implies G1(x0) = F(x0).
  • Auxiliary-objective bounds: The proof starts by bounding Gk(xk−1) − G∗k through relations between successive auxiliary objectives.The identity for Gk(x) − Gk−1(x) introduces a term involving yk−1 − yk−2.
  • Extrapolation control: A separate lemma controls ∥yk−1 − yk−2∥2 using the generated iterates and the quantity δk satisfying F(xk) − F∗ ≤ δk.This bound is also used in the convergence analysis of accelerated SDCA.
  • Iteration complexity: The resulting upper bound determines the number of iterations TM required by M to reach auxiliary accuracy εk.The global complexity is obtained by combining this inner-loop bound with the number of outer iterations.

B.3 Proof of Theorem 3.3.

The proof controls the growth of the acceleration sequence and uses this bound to establish the non-strongly convex convergence result. The argument combines parameter identities, auxiliary lemmas, and bounds on the relevant error ratio.

  • Sequence growth: Lemma B.3 bounds the growth of the sequence (λk) generated by Algorithm 1 when µ = 0.The proof derives the bound from the recurrence defining αk and the initialization α0 = √2.
  • Sequence growth: The initialization makes γ0 equal to κ, allowing Lemma A.4 to provide an upper bound on λk.The proof states that λk ≤ 4/(k + 3) for k ≥ 1.
  • Convergence bound: The proof applies Theorem A.3 after controlling the ratio εi/λi with Lemma B.3.This links the sequence-growth estimate to the convergence bound.
  • Convergence bound: The elementary inequality (a + b)^2 ≤ 2(a^2 + b^2) is used in the final bounding step.It simplifies the quadratic terms in the proof.

B.4 Proof of Proposition 3.4

For the non-strongly convex case, the proof retains Proposition B.1 but replaces the unavailable Lemma B.2 argument with bounded-level-set reasoning. The resulting bound yields the stated iteration complexity.

  • Non-strongly convex case: When µ = 0, Proposition B.1 remains valid but Lemma B.2 does not.The proof identifies controlling ∥yk−1 − yk−2∥ as the main difficulty.
  • Non-strongly convex case: Bounded level sets provide B > 0 such that ∥xk − x∗∥ ≤ B for every iterate.The argument uses the boundedness of F(xk) − F∗ to invoke this assumption.
  • Iteration complexity: Because κ > 0 makes Gk strongly convex, the number of calls to M can be bounded using the strongly convex argument.The proof then upper-bounds this quantity before applying the final complexity relation.
  • Iteration complexity: The right-hand side is bounded by O((k + 2)^(4+η)), which gives the desired result after substitution into (38).This is the final complexity estimate in the proof.

C Derivation of Global Convergence Rates

The global-rate derivation gives a template for accelerating randomized first-order methods by selecting κ, bounding outer iterations, and summing expected inner iterations. It then specializes the framework to MISO/Finito and its linear convergence rate.

  • Generic rate derivation: The acceleration template computes κ, the outer iteration count, and the expected inner iteration count for a given method M.The framework is intended for randomized first-order methods, with deterministic methods as a straightforward specialization.
  • Generic rate derivation: The analysis assumes that M has an expected linear convergence rate E[F(xk) − F∗] ≤ CM,F(1 − τM,F)^k.Stopping-time bounds convert this rate into an expected iteration complexity.
  • Parameter choice: For strongly convex objectives, κ is selected by optimizing the method-dependent convergence ratio involving τM,Gk and µ + κ.For non-strongly convex objectives, the suggested ratio uses L + κ, and κ affects only multiplicative constants.
  • MISO/Finito specialization: The framework covers proximal and non-proximal settings for most considered methods, while SAG proximal variants and prior Finito/MISO analyses were limited.The paper extends MISO to composite minimization and establishes corresponding convergence rates.

D.2 Proximal MISO

Proximal MISO extends MISO/Finito to composite objectives and removes its large-sample condition. It maintains lower bounds that yield both a convergence analysis and a practical primal stopping certificate, with accelerated complexity guarantees.

  • Composite extension: Proximal MISO handles composite objectives with differentiable fi and a convex possibly nondifferentiable ψ whose proximal operator is easy to compute.The method is initialized with lower bounds for the component functions.
  • Convergence: The choice of δ ensures convergence even when n < 2L/µ, removing the original large-sample condition.The update of zi remains the same as in the original MISO/Finito algorithm.
  • Relation to SDCA: Proximal MISO is almost identical to a proximal SDCA variant but uses a different stepsize and a convergence proof that does not rely on duality.Its optimality certificate is correspondingly primal rather than a Fenchel-duality gap.
  • Algorithm: The algorithm randomly updates one component lower bound and minimizes the resulting aggregate lower-bound function to produce the next iterate.This is the core MISO-Prox update mechanism.
  • Certificate: F(xk) − Dk(xk) is an optimality certificate that upper-bounds F(xk) − F∗ and converges linearly to zero.Because Dk is a lower bound of F, the certificate also supplies a practical stopping criterion.
  • Acceleration: The accelerated MISO-Prox algorithm has an expected iteration-complexity upper bound for reaching accuracy ε on strongly convex objectives.The complexity is obtained by reinitializing MISO-Prox appropriately across the auxiliary problems.

E Implementation Details of Experiments

The experiments compare accelerated and unaccelerated SAG, SAGA, and MISO-Prox on l2-logistic regression, using theoretically selected Catalyst and solver parameters. They evaluate both strongly convex and non-strongly convex regimes through prescribed subproblem tolerances and initialization choices.

  • Experimental setup: The experiments compare SAG, SAGA, and MISO-Prox with and without acceleration on an l2-logistic regression problem.Observed data are normalized before regression.
  • Regimes and parameters: The l2 regularization term generates the strongly convex regimes, while the unregularized logistic objective has µ = 0.The logistic function's Lipschitz gradient parameter is set to L = 1/4.
  • Regimes and parameters: Catalyst's κ is set to its theoretically optimal value, with algorithm-specific coefficients for SAG, SAGA, and MISO-Prox.The selected coefficients are (2, −2), (1/2, 1/2), and (1, 1), respectively.
  • Accuracy schedules: The strongly convex and non-strongly convex subproblem tolerances are set to ε_k = (2/9)F(x0)(1 −ρ)^k and ε_k = 2F(x0)/9(k + 2)4+η, respectively.The free parameters are fixed at ρ = 0.9√q and η = 0.1.
  • Subproblem solution: Subproblem step sizes use theoretical values depending on µ, L, and κ, and all compared methods store n gradients from previous iterates.For MISO, a theory-based initialization moves xk−1 closer to yk−1 and farther from yk−2; using it for SAGA performed slightly better than xk−1.
Loading 1506.02186v2…