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

1. Introduction

• Catalyst accelerates methods that linearly converge on strongly convex problems, including incremental algorithms, and improves their complexity when the condition number exceeds n.The framework can also accelerate when the objective is not strongly convex, including µ = 0, while matching optimal incremental-method bounds up to logarithmic factors.Source: §1 · p. 3, §1.1 · p. 4
• Catalyst directly handles non-strongly convex objectives without preselecting a target-dependent regularization parameter and improves numerical stability through better-conditioned auxiliary subproblems.This addresses limitations of methods such as MISO, SDCA, and SVRG when applied to general or weakly strongly convex objectives.Source: §1 · p. 3

1.1 Related Work

• Catalyst generalizes accelerated inexact proximal-point methods through an approximate sufficient descent condition that supports global complexity analysis for strongly and non-strongly convex objectives.This criterion enables systematic acceleration with optimization method M and refutes the conjecture that the criterion was too weak to guarantee acceleration.Source: §1.1 · p. 4

1.2 Overview of Catalyst

• Catalyst wraps an algorithm M in inner-outer loops: M solves better-conditioned strongly convex auxiliary problems, outer iterates use Nesterov extrapolation, and parameters balance both costs.Choosing the smoothing parameter, stopping criterion, and warm-start strategy appropriately yields near-optimal complexity; the reported rates are optimal up to logarithmic factors.Source: §1.2 · pp. 5–6

2. The Moreau Envelope and its Approximate Variant

• The Moreau envelope or Moreau-Yosida smoothing uses infimal convolution with a quadratic penalty to turn any convex lower semicontinuous function into a smooth function and an ill-conditioned smooth convex function into a well-conditioned one.Its associated quantity p(x) does not admit a closed form in general, so computing it requires solving the subproblem to high accuracy with an iterative algorithm.Source: §2 · pp. 6–7

2.1 Basic Properties of the Moreau Envelope

• The Moreau envelope is convex, continuously differentiable, and κ-smooth, preserves the minimizers of f, and improves conditioning for strongly convex f.If f is µ-strongly convex, the envelope is µ_F-strongly convex with µ_F = µκ/(µ+κ), and its condition number is (µ+κ)/µ; choosing small κ can make it arbitrarily well conditioned.Source: §2.1 · p. 7

2.2 A Fresh Look at Catalyst

• Since gradient descent on the Moreau envelope equals the proximal point algorithm, Nesterov extrapolation yields Güler’s accelerated proximal point method (Güler, 1992).In practice, evaluating each proximal operator requires an iterative inner solve, so Catalyst calls an optimization method M to obtain inexact subproblem solutions and must control inner-loop complexity.Source: §2.2 · p. 8

2.3 The Approximate Moreau Envelope

• Catalyst controls inexact Moreau-envelope gradients using absolute or relative accuracy criteria, with gradient mappings providing a practical absolute-accuracy test.The gradient-mapping test guarantees an ε-approximate proximal point but requires an additional full gradient and proximal step per iteration; relative accuracy scales with the squared distance between the proximal center and candidate point and has the same per-iteration cost.Source: §2.3 · pp. 9–10

Algorithm and requirements

• Catalyst applies a linearly convergent method M to strongly convex subproblems, enabling acceleration even when the original objective is convex but not strongly convex.The inner method must solve subproblems efficiently enough to control total complexity.Source: §3 · p. 11
• When M satisfies the required convergence bound in expectation, Catalyst’s complexity guarantees extend to randomized block-coordinate and incremental methods, including SAG, SAGA, SVRG, SDCA, and MISO/Finito.Duality-gap linear convergence is also covered for methods such as SDCA and MISO/Finito.Source: §3 · p. 12

Stopping criteria

• Catalyst offers absolute-accuracy, relative-accuracy, and fixed-budget stopping criteria; for incremental methods, the practical fixed-budget “one-pass” strategy sets T = n.Theoretical fixed budgets are described as pessimistic and impractical, motivating the aggressive one-pass choice.Source: §3 · pp. 12–13

Warm-starts in inner loops

• Warm starts use extrapolated previous iterates, or proximal-gradient variants for composite objectives, while the earlier z0 = xk−1 rule performs worse in practice.For fixed budgets, Catalyst recommends the same warm-start strategy used for the corresponding inner-loop method.Source: §3 · p. 13

Optimal balance: choice of parameter κ

• Choosing κ by minimizing global complexity balances inner and outer work; for incremental methods, setting the condition number to order n yields inner complexity O(n log(1/ε)).Table 2 illustrates κ choices for full-gradient and incremental methods.Source: §3 · pp. 13–14, Table 2 · p. 14

4. Convergence and Complexity Analysis

• Catalyst’s analysis separates outer-loop convergence, inner-loop computation costs, and their combination into global complexity for a method M.The inner-loop analysis assumes M has linear convergence on strongly convex problems.Source: §4 · p. 14, §4.2 · p. 20

4.1.1 Analysis for Criterion (C1)

• For criterion (C1), the outer loop has accelerated O(1/k^2) convergence for convex objectives and linear convergence for strongly convex objectives.The rate depends on q = µ/(µ+κ), the inverse condition number of the Moreau envelope.Source: §4.1.1 · pp. 15, 18

4.1.2 Analysis for Criterion (C2)

• Criterion (C2) provides outer-loop guarantees similar to (C1), with specialized strongly convex and convex parameter choices.For convex objectives, δ_k = 1/(k+1)^2, and δ_k can be improved to 1/(k+1)^(1+γ) for any γ > 0 at the cost of a larger constant.Source: §4.1.2 · pp. 19–20

4.2 Analysis of Warm-start Strategies for the Inner Loop

• For a linearly convergent inner method M, the number of iterations needed for target accuracy ε is controlled by the initialization gap h(z0)−h∗.This relation is established for both deterministic and randomized variants of M, making good initialization essential for fast inner convergence.Source: §4.2 · p. 20

4.2.1 Warm Start Strategies for Criterion (C1)

• For criterion (C1), Proposition 12 specifies warm starts z0 = xk + κ/(κ+µ)(yk − yk−1) for smooth f and a proximal-gradient construction for composite f = f0 + ψ.For convex f with bounded level sets, it states existence of a constant B > 0 depending only on f, x0 and κ.Source: §4.2.1 · p. 21
• Under criterion (C1), warm starts yield E[Tk+1] = ˜O(1/τM) for µ > 0 and E[Tk+1] = ˜O(log(k + 2)/τM) for µ = 0 when M is randomized.The logarithmic notation hides dependencies on µ, L, κ, CM, τM, and f(x0) − f∗.Source: §4.2.1 · p. 24

4.2.2 Warm Start Strategies for Criterion (C2)

• Criterion (C2) has asymptotically similar inner-loop complexity to criterion (C1) but significantly better constants, and its convex analysis does not require bounded level sets.A sufficient condition for (C2) is combined with a warm start and Lemma 11 to derive deterministic and randomized complexity bounds.Source: §4.2.2 · p. 24, Proof · pp. 25–26

4.3 Global Complexity Analysis

• Catalyst derives global complexity bounds for strongly convex (µ > 0) and convex (µ = 0) objectives by combining outer- and inner-loop convergence, with deterministic method M requiring at most NM iterations to achieve f(ˆx) − f∗ ≤ ε.Source: §4.3 · p. 26, §4.3.1 · p. 27, §4.3.2 · p. 28

4.3.1 Strongly Convex Case

• For strongly convex objectives, both criteria require a constant number of inner iterations, yielding a global rate optimized through τM/√(µ + κ).The resulting total work is expressed in terms of the number of outer iterations and the constant inner-loop cost, with analogous expected bounds for randomized methods.Source: §4.3.1 · pp. 26–27

4.3.2 Convex, but not Strongly Convex Case

• For convex but not strongly convex objectives, inner-loop work grows logarithmically, so the global rate is near-optimal up to a logarithmic factor.The analysis compares this rate with the optimal O(1/s^2) rate and states that analogous expected guarantees hold for randomized methods.Source: §4.3.2 · pp. 27–28

4.3.3 Practical Aspects of the Theoretical Analysis

• Choosing κ by minimizing the global complexity is theoretically motivated, but Catalyst often remains robust to smaller κ values than the worst-case choice.The theoretical κ performs reasonably well, whereas fixed-budget bounds are relatively poor; nevertheless, one-pass budgets such as TM = n can work well for incremental algorithms.Source: §4.3.2 · p. 28, §4.3.3 · p. 30

4.3.2 Convex, but not Strongly Convex Case

• For finite-sum objectives, Catalyst yields near-optimal gradient-evaluation rates up to logarithmic constants for gradient descent and SVRG, and extends to SAG/SAGA, MISO/Finito, and SDCA.The SVRG discussion explicitly treats the case ¯L > (n + 2)µ, while the broader extension and near-optimality claim are stated for related incremental algorithms.Source: §4.3.2 · p. 29

5.1 Data sets, Formulations, and Metric

• The experiments consider six machine-learning datasets and three optimization formulations: ℓ2-regularized logistic regression, ℓ1-regularized linear regression (LASSO), and Elastic-Net regularization, including strongly convex structure.Objective values are plotted against the number of gradients evaluated during optimization, identified as the computational bottleneck of the algorithms considered.Source: §5.1 · pp. 30–32

5.2 Choice of Hyper-parameters and Variants

• The default methods are proximal SVRG, SAGA, and proximal MISO, with κ chosen from theoretical global-complexity minimization and inner loops controlled by theoretically motivated stopping criteria.The variants also test one-pass stopping and warm starts; the one-pass criterion is heuristic, while sufficiently large inner-loop budgets guarantee convergence.Source: §5.2 · p. 32

5.3 Comparison of Stopping Criteria and Warm-start Strategies

• For Catalyst-SVRG, (C3) and (C1*) perform best and never degrade performance; acceleration is significant for logistic regression but occurs in only 7 of 12 sparse cases.For SAGA, C1 can oscillate and differ greatly from C1* solely because of warm starts, making initialization crucial; Catalyst-MISO accelerates and stabilizes MISO in ill-conditioned settings.Source: §5.3 · p. 35
• The experiments indicate that absent Catalyst acceleration may reflect unknown or local strong convexity, motivating adaptivity to the effective conditioning of incremental optimization.When µ′/L ≥ 1/n, the regime is well-conditioned and O(n log(1/ε)) is already theoretically optimal; sparse problems may also be conditioned by their solution subspace.Source: §5.3 · p. 35

5.4 Acceleration of Existing Methods

• Catalyst significantly improves SVRG, SAGA, and related methods on ill-conditioned covtype, real-sim, and rcv1 problems, while alpha gains little because hidden strong convexity already makes incremental methods near-optimal.The comparison uses the best stopping criterion, (C3), and contrasts original algorithms with their Catalyst-accelerated versions.Source: §5.4 · p. 38

5.5 Empirical Effect on the Generalization Error

• Training-loss acceleration appears in 5 of 6 cases, test-loss acceleration in 4 of 6, and important test-accuracy acceleration in 2 cases.The study uses cross-validated logistic-regression regularization with 80% training and 20% test data.Source: §5.5 · p. 38

5.6 Study of the Parameter κ

• For ill-conditioned problems, the theoretically optimal κ0 performs much better than alternatives, whereas alpha and Lasso favor the smallest tested value, κ = 0.01κ0.The tested values are κ = 10^iκ0 for i = −2, −1, …, 2, suggesting hidden strong convexity in alpha and Lasso.Source: §5.6 · p. 38

6. Conclusion

• Catalyst extends Nesterov’s acceleration to a large class of first-order methods and is effective in practice, especially for ill-conditioned problems.It also improves numerical stability through better-conditioned auxiliary problems and supports convex objectives and algorithms that originally require strong convexity.Source: §6 · pp. 38, 42
• For incremental methods, the almost-parameter-free variant using one data pass per outer iteration was the most effective experimentally.The conclusion also reports experiments on accelerated SVRG, SAGA, and MISO, including objective-gap and generalization-error evaluations.Source: §6 · pp. 39, 40, 42
• Catalyst is versatile beyond finite-sum optimization and could accelerate additional algorithms not considered in the paper.The conclusion identifies this extensibility as a central feature of the approach.Source: §6 · p. 42

Appendix A. Useful Lemmas

• Appendix A states a quadratic-function lemma for vectors x, y, z in R^p and θ > 0.The lemma is presented as a basic auxiliary result for the analysis.Source: Appendix A · p. 42

Proof

• The proof appendix gives an elementary induction proof for the non-negative-sequence lemma and identifies it with an earlier Catalyst lemma inspired by inexact proximal-gradient analysis.The proof establishes the recurrence relation by induction from the base case k = 0.Source: Proof · pp. 42–43
• Lemma 21 bounds the sequence A_k defined by the Catalyst recurrence as 2(k + 2)^2 ≤ A_k ≤ 4(k + 2)^2.The proof derives the upper bound from an earlier lemma and the recurrence for α_k, then establishes the lower bound.Source: Proof · p. 44

B.1 Proof of Lemma 2

• The first-order conditions defining [z]_η identify the gradient-mapping relation η(z − [z]_η).Source: §B.1 · p. 44
• Strong convexity yields the intermediate lower bound involving h([z]_η) − 1/2(κ + µ)∥u∥².Source: §B.1 · p. 44
• The proof’s first inequality follows from the relation in Nesterov (2004, Theorem 2.1.5), using the fact that h0 is (1/η)-smooth.Source: §B.1 · p. 45
• h([z]_η) − h* ≤ 1/2(κ + µ)∥h′(z)∥², establishing the lemma’s central bound.The proof first obtains h([z]_η) − h* ≤ 1/2(κ + µ)∥u∥² and then bounds ∥u∥ by ∥h′(z)∥.Source: §B.1 · p. 45

Proof of Proposition 5

• Specializing Theorem 3 with α_0 = √q gives α_k = √q and A_k = (1 − √q)^k for all k ≥ 0.These parameter choices produce the simplified algorithmic sequence used throughout the proof.Source: §B.2 · p. 45
• The proof identifies γ_0 = µ(1 − √q) and invokes strong convexity of f before applying Theorem 3.Source: §B.2 · pp. 45–46
• f(x_k) − f* ≤ 8(√q − ρ)^−2(1 − ρ)^{k+1}(f(x_0) − f*) .This is obtained by combining Theorem 3 with the preceding inequality and the monotonicity relation involving ρ and q.Source: §B.2 · p. 46

• Setting α0 = 1 gives γ0 = κ and S0 = κ.Source: §B.3 · p. 46
• Lemma 21 is used to upper-bound the ratio εj/Aj.Source: §B.3 · p. 46
• Applying Theorem 3 yields the stated result, with the final inequality using (a + b)2 ≤2(a2 + b2).Source: §B.3 · p. 46

B.4 Proof of Lemma 11

• The proof abbreviates τ_M as τ and sets C = C_M(h(z_0) − h*) to simplify notation.The supplied passage ends after introducing this setup.Source: §B.4 · p. 47

B.5 Proof of coerciveness property of the proximal operator

• Lemma 22 states the coerciveness inequality for the proximal operator of any µ-strongly convex function f with positive parameter κ.The result applies for arbitrary x, y ∈ R^p.Source: §B.5 · p. 47
• The proof uses the proximal optimality condition 0 ∈ ∂f(p(x)) + κ(p(x) − x), equivalently κ(x − p(x)) ∈ ∂f(p(x)).This subgradient relation enables application of strong convexity.Source: §B.5 · p. 48
• Applying strong convexity and rearranging the resulting terms yields the desired inequality.Source: §B.5 · p. 48

Catalyst for MISO/Finito/SDCA

• Catalyst applies to MISO/Finito, viewed as a variant of SDCA (Mairal, 2015; Defazio et al., 2014b), whose iterates minimize algorithmic lower bounds.The iterates arise from closed-form minimization of lower bounds and can be expressed through proximal steps.Source: Appendix C · p. 48
• The computable duality gap h(zt)−dt(zt) upper-bounds the primal error and provides a stopping criterion for Catalyst’s inner solves.This changes the complexity analysis from controlling a primal gap to controlling a dual gap.Source: Appendix C · pp. 48–49
• MISO/Finito retains the Section 4.2.2 inner-loop complexity up to a constant factor, giving Catalyst a global complexity similar to SVRG and acceleration on ill-conditioned problems.The outer-loop complexity remains unchanged when approximate proximal points satisfy criteria (C1) and (C2).Source: Appendix C · pp. 49–50
• For strongly convex and bounded-level-set objectives, specialized warm starts bound the initial dual gap for criterion (C1), matching the corresponding Catalyst constants.The strongly convex case gives h*_{k+1}−d0(z0) ≤ Cε_{k+1}, while the bounded-level-set case uses a constant B.Source: Appendix C · p. 49
• The criterion (C2) warm start yields an inner-loop complexity matching Proposition 15 up to a constant factor.The corresponding bound differs only in its constant factor, so the same inner-loop analysis applies.Source: Appendix C · pp. 49–50