PaperlayerView exact revision on arXiv

Source-linked AI summary

Catalyst Acceleration for First-order Convex Optimization: from Theory to Practice

Hongzhou Lin, Julien Mairal, Zaid Harchaoui

arXiv:1712.05654v2stat.MLmath.OC

TL;DR

First-order methods for convex optimization may lack Nesterov-style acceleration, and some incremental methods require strong convexity. Catalyst wraps such methods in an inexact accelerated proximal-point scheme that solves well-conditioned auxiliary problems with practical stopping and warm-start strategies. It yields faster convergence across strongly convex and non-strongly convex objectives, improves numerical stability, and is effective in practice on ill-conditioned problems.

  • Problem

    Many incremental first-order methods did not use Nesterov extrapolation, while some were defined only for strongly convex objectives.

  • Method

    Catalyst accelerates a base method by approximately solving a sequence of strongly convex auxiliary problems within an inexact accelerated proximal-point framework.

  • Results

    Catalyst establishes faster rates for a large class of first-order methods in both strongly convex and non-strongly convex settings.

  • Takeaways & Limitations

    Catalyst is effective in practice for ill-conditioned problems and can improve numerical stability by using better-conditioned auxiliary objectives.

  • Takeaways & Limitations

    The reported overview treats the case ¯L > (n + 2)µ to simplify the analysis.

Abstract

from arXiv · show

We introduce a generic scheme for accelerating gradient-based optimization methods in the sense of Nesterov. The approach, called Catalyst, builds upon the inexact accelerated proximal point algorithm for minimizing a convex objective function, and consists of approximately solving a sequence of well-chosen auxiliary problems, leading to faster convergence. One of the keys to achieve acceleration in theory and in practice is to solve these sub-problems with appropriate accuracy by using the right stopping criterion and the right warm-start strategy. We give practical guidelines to use Catalyst and present a comprehensive analysis of its global complexity. We show that Catalyst applies to a large class of algorithms, including gradient descent, block coordinate descent, incremental algorithms such as SAG, SAGA, SDCA, SVRG, MISO/Finito, and their proximal variants. For all of these methods, we establish faster rates using the Catalyst acceleration, for strongly convex and non-strongly convex objectives. We conclude with extensive experiments showing that acceleration is useful in practice, especially for ill-conditioned problems.

1. Introduction

Catalyst is a generic wrapper that accelerates many first-order methods by approximately solving better-conditioned auxiliary problems and extrapolating their iterates. It extends acceleration to incremental algorithms and non-strongly convex objectives, with practical benefits for ill-conditioned problems.

  • 1. Introduction: The framework applies to composite objectives with a smooth convex part and a possibly non-differentiable convex penalty.This formulation covers regularized empirical-risk problems in which the penalty may promote sparsity.
  • 1. Introduction: Catalyst wraps an optimization method with an accelerated inner-outer scheme that solves auxiliary strongly convex problems and extrapolates iterates.The framework requires linear convergence on strongly convex objectives and uses approximate subproblem solutions.
  • 1. Introduction: Catalyst accelerates incremental methods such as SAG, SAGA, SDCA, SVRG, and MISO/Finito, improving over their non-accelerated variants when the condition number exceeds n.The resulting rates hide logarithmic dependencies on the condition number.
  • 1. Introduction: Acceleration remains available when the objective is merely convex, removing the need to choose a target-dependent regularization parameter in advance.This directly supports methods originally defined only for strongly convex objectives.
  • 1. Introduction: Catalyst improves numerical stability by applying methods to better-conditioned auxiliary subproblems, especially for small strong-convexity constants.The paper also emphasizes practical stopping criteria and warm-start strategies for these subproblems.
  • 1. Introduction: The paper establishes complexity results for Catalyst across strongly convex and non-strongly convex finite-sum settings, with rates optimal up to logarithmic factors.Table 1 summarizes the before-and-after convergence rates for several optimization methods.

2. The Moreau Envelope and its Approximate Variant

The Moreau envelope smooths a convex objective while preserving its minimizers, and can improve conditioning when the original function is strongly convex. Catalyst uses approximate proximal solutions to obtain inexact envelope gradients, because exact proximal evaluations generally require iterative subproblem solves.

  • 2. The Moreau Envelope and its Approximate Variant: The Moreau envelope converts a convex lower semicontinuous function into a smooth function and can improve the conditioning of a smooth convex function.It is formed through infimal convolution with a quadratic penalty.
  • 2. The Moreau Envelope and its Approximate Variant: Because proximal operators usually require iterative computation, Catalyst calls a base method to solve each auxiliary subproblem approximately in an inner-outer construction.This construction supplies the practical route from proximal-point acceleration to general first-order methods.
  • 2. The Moreau Envelope and its Approximate Variant: The envelope and the original objective have the same minimizers, so minimizing either yields the same solution set.This makes smoothing compatible with the original optimization target.
  • 2. The Moreau Envelope and its Approximate Variant: For a µ-strongly convex objective, the envelope is smooth and has condition number (µ+κ)/µ, which can be improved by choosing a small κ.The envelope remains convex and differentiable even when the original objective is non-smooth.
  • 2. The Moreau Envelope and its Approximate Variant: Catalyst interprets accelerated proximal point updates as accelerated optimization of the Moreau envelope using inexact gradients.The exact envelope gradient depends on the proximal operator, which is typically unavailable in closed form.
  • 2. The Moreau Envelope and its Approximate Variant: Approximate proximal solutions can be controlled through absolute or relative accuracy criteria, with gradient mappings providing a practical stopping signal.Gradient-mapping checks may require an additional full gradient and proximal step per iteration.

3. Catalyst Acceleration

Catalyst accelerates first-order methods by repeatedly approximately solving strongly convex auxiliary subproblems with M, using warm starts and controlled stopping criteria. Its practical design balances inner and outer costs through κ, while supporting randomized methods and non-strongly convex objectives.

  • Algorithm: The algorithm initializes y0 and q, repeatedly approximately solves an auxiliary problem with M, and updates yk using Nesterov extrapolation before returning the final estimate.Each inner solve uses a prescribed warm start and one of three stopping strategies: accuracy-based or fixed-budget.
  • Core scheme: Catalyst applies M to strongly convex subproblems, enabling its use with convex objectives that are not themselves strongly convex.The method requires M to have linear convergence on these subproblems.
  • Supported methods: Randomized methods such as block coordinate descent, SAG, SAGA, and SVRG inherit Catalyst complexity results in expectation, while SDCA and MISO/Finito are handled through duality-gap convergence.This extends the framework to several incremental and randomized algorithms.
  • Stopping criteria: Catalyst supports absolute-accuracy, relative-accuracy, and fixed-budget stopping criteria for the inner-loop subproblems.For fixed budgets, the method runs M for T iterations; an aggressive incremental strategy sets T=n.
  • Warm starts: Warm starts use the previous outer iterate and extrapolation information, with proximal-gradient variants for composite objectives; the earlier z0=xk−1 rule performs worse in practice.The proposed warm-start choices depend on whether the objective is smooth or composite.
  • Parameter choice: Choosing κ balances inner-subproblem and outer-loop work; for incremental methods, select κ so (L̄+κ)/(µ+κ) is of order n, yielding inner complexity O(n log(1/ε)).The recommended κ is obtained by minimizing global complexity bounds, and Table 2 lists examples for full-gradient and incremental methods.

4. Convergence and Complexity Analysis

Catalyst’s convergence and complexity analysis separates accelerated outer-loop behavior from inner-loop solution cost, then combines them into global rates for strongly convex and convex objectives.

  • 4.1 Outer-loop convergence: Catalyst’s outer-loop analysis establishes accelerated convergence under inexact subproblem solutions, using criteria (C1) and (C2) with controlled approximation errors.The analysis first treats outer-loop convergence independently of subproblem-solving cost, then compares the two stopping criteria.
  • 4.1.1 Analysis for criterion (C1): For strongly convex objectives, Catalyst achieves linear convergence, with the rate governed by q = µ/(µ + κ), the inverse condition-number dependence of the smoothed objective.The strongly convex specialization uses α_0 = √q and yields geometrically decreasing error bounds.
  • 4.3 Global complexity: The global complexity results are near-optimal up to logarithmic factors for strongly convex and convex objectives, while extending Catalyst to multiple first-order and incremental methods.For finite sums, the resulting complexity is also expressed in gradient evaluations; the convex analysis notes a simplified treated regime.

5. Experimental Study

The experiments evaluate Catalyst across multiple machine-learning formulations and incremental methods, with particular attention to stopping criteria, warm starts, conditioning, and practical metrics. Catalyst often improves optimization on ill-conditioned problems, while its gains depend on the method, problem structure, and evaluation setting.

  • Comparison of stopping criteria and warm-start strategies: For Catalyst-SVRG, criteria C3 and C1* usually perform best because one data pass often reaches the required subproblem accuracy.The two criteria are frequently superimposed, indicating that one pass through the data is sufficient in most cases.
  • Acceleration is not systematic when hidden or local strong convexity makes the problem well-conditioned, where O(n log(1/ε)) is already optimal.The experiments attribute some absent gains to incremental methods adapting to an unknown strong-convexity parameter or local strong convexity near the solution.
  • Comparison of stopping criteria and warm-start strategies: For Catalyst-SAGA, warm-start selection is critical: C1 can oscillate, and C1* can greatly outperform it despite differing only in initialization.The observations suggest greater variance for SAGA than SVRG in some cases.
  • Comparison of stopping criteria and warm-start strategies: Catalyst accelerates MISO on logistic-regression and Elastic-Net formulations and also stabilizes the method.For Lasso, the original Prox-MISO is undefined because the problem is not strongly convex, so the comparison uses Catalyst-SVRG.
  • Catalyst substantially improves optimization on ill-conditioned logistic-regression and Elastic-Net problems across several data sets.The experiments report significant improvements for covtype, real-sim, and rcv1, consistent with the theory for ill-conditioned problems.
  • The chosen κ works best for ill-conditioned problems, whereas the smallest tested κ performs best for alpha and Lasso.These results support using the theoretically optimal κ in ill-conditioned settings, while suggesting different behavior in other regimes.

6. Conclusion

Catalyst extends Nesterov-style acceleration to a broad class of first-order methods and is effective in practice, particularly on ill-conditioned problems. Experiments identify practical variants and show that a single data pass per outer iteration is effective for incremental methods.

  • Catalyst extends Nesterov’s acceleration to a large class of first-order methods and can be effective in practice for ill-conditioned problems.
  • Figure 4 compares original and Catalyst-accelerated SVRG, SAGA, and MISO using relative function-value gaps over gradient evaluations.
  • Figure 5 evaluates training loss, test loss, and test classification error to assess Catalyst’s empirical effect on generalization.
  • Figure 6 evaluates Catalyst-SVRG across values of κ, including the theoretical choice κ0, under stopping criterion C1.
  • For incremental methods, the almost-parameter-free variant using one data pass per outer-loop iteration was the most effective in practice.

B.1 Proof of Lemma 2

The proof bounds the auxiliary objective gap using strong convexity and the gradient norm at the reference point.

  • The derivation uses first-order optimality for the proximal subproblem, strong convexity, and smoothness of h0.
  • The auxiliary objective gap is bounded by one-half the curvature term times the squared gradient norm at z.The displayed result gives h([z]η) − h* ≤ 1/2(κ + µ)||h′(z)||^2.

B.2 Proof of Proposition 5

The proposition specializes the convergence theorem to constant parameters and obtains a geometric objective-gap bound.

  • Choosing α0 = √q makes αk constant and simplifies the sequence Ak to (1 − √q)^k.
  • The bound follows by combining Theorem 3 with the preceding inequality and a monotonicity relation involving ρ and q.
  • The objective gap satisfies f(xk) − f* ≤ 8(√q − ρ)^−2(1 − ρ)^(k+1)(f(x0) − f*).

B.3 Proof of Proposition 6

The proof initializes the relevant sequences and applies the main theorem after bounding the accumulated inexactness terms.

  • The initialization α0 = 1 gives γ0 = κ and S0 = κ.
  • The proof uses Lemma 21 to upper-bound the ratio εj/Aj before applying Theorem 3.
  • The final estimate uses the elementary inequality (a + b)^2 ≤ 2(a^2 + b^2).

B.4 Proof of Lemma 11

The proof begins by abbreviating recurring quantities to simplify the notation.

  • The proof abbreviates τ_M as τ and C_M(h(z_0) − h*) as C before proceeding.

B.5 Proof of coerciveness property of the proximal operator

The section states an inequality for a strongly convex function and justifies it using the proximal point's optimality condition and strong convexity.

  • Lemma 22 considers a μ-strongly convex function with positive parameter κ and establishes an inequality for arbitrary x and y.
  • The proof uses κ(x − p(x)) ∈ ∂f(p(x)), obtained from the optimality condition defining p(x).
  • Rearranging the resulting terms yields the lemma's desired inequality.

Appendix C. Catalyst for MISO/Finito/SDCA

Catalyst is adapted to MISO/Finito by analyzing duality-gap stopping criteria and warm starts for the auxiliary problems. The resulting inner-loop bounds preserve the broader acceleration benefit, including for ill-conditioned problems.

  • Appendix C. Catalyst for MISO/Finito/SDCA: MISO/Finito generates lower bounds d_t, whose minimizers z_t are obtained by proximal steps at selected points w_t.
  • Appendix C. Catalyst for MISO/Finito/SDCA: The computable duality gap h(z_t) − d_t(z_t) upper-bounds the primal suboptimality and can check criteria (C1) and (C2).
  • Appendix C. Catalyst for MISO/Finito/SDCA: The analysis defines target complexity through the first iterate whose duality gap h(z_t) − d_t(z_t) is at most ε.
  • Appendix C. Catalyst for MISO/Finito/SDCA: Catalyst's outer-loop convergence is unchanged when MISO/Finito supplies approximate proximal points satisfying criteria (C1) and (C2).The analysis therefore focuses on controlling the inner-loop complexity.
  • Appendix C. Catalyst for MISO/Finito/SDCA: Warm-start propositions provide criterion-specific initializations and bounds for strongly convex and convex objectives.For criterion (C1), the strongly convex case bounds h*_{k+1} − d_0(z_0) by Cε_{k+1}; the convex case uses a constant B.
  • Appendix C. Catalyst for MISO/Finito/SDCA: The resulting inner-loop complexity differs from related methods only by a constant factor, giving MISO/Finito Catalyst complexity similar to SVRG and acceleration on ill-conditioned problems.
Loading 1712.05654v2…