PaperlayerView exact revision on arXiv

Source-linked AI summary

A Generic Acceleration Framework for Stochastic Composite Optimization

Andrei Kulunchakov, Julien Mairal

arXiv:1906.01164v3math.OCcs.LGstat.ML

TL;DR

Stochastic methods target expected risk but are described as having slow rates, and the role of acceleration in stochastic objectives remains poorly understood. The paper extends Catalyst to stochastic optimization and reports optimal finite-sum and stochastic complexities up to logarithmic terms, alongside an analysis of inexact proximal computations.

  • Problem

    Stochastic methods target expected risk but typically have slow rates, while the effect of Nesterov acceleration on stochastic objectives remains poorly understood.

    Source: §1 · pp. 1–2

  • Method

    The paper extends Catalyst by using methods with mild convergence guarantees on strongly convex subproblems to build accelerated stochastic algorithms.

    Source: §1 · p. 2

  • Results

    The finite-sum approach reaches optimal finite-sum and strongly convex stochastic complexities up to logarithmic terms, with a logarithmic factor versus direct acceleration.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The analysis also covers expected approximate subproblem solves and accelerated proximal methods with inexact proximal operators.

    Source: §1 · pp. 2–3

    The authors report a negative result for inexact minimization, suggesting Catalyst is not robust to noise.

    Source: §4.1 · p. 7

Abstract

from arXiv · show

In this paper, we introduce various mechanisms to obtain accelerated first-order stochastic optimization algorithms when the objective function is convex or strongly convex. Specifically, we extend the Catalyst approach originally designed for deterministic objectives to the stochastic setting. Given an optimization method with mild convergence guarantees for strongly convex problems, the challenge is to accelerate convergence to a noise-dominated region, and then achieve convergence with an optimal worst-case complexity depending on the noise variance of the gradients. A side contribution of our work is also a generic analysis that can handle inexact proximal operators, providing new insights about the robustness of stochastic algorithms when the proximal operator cannot be exactly computed.

1 Introduction

Stochastic optimization targets expected risk, but existing stochastic methods are described as having slow rates and the effect of Nesterov acceleration remains poorly understood. The paper extends Catalyst to stochastic objectives and develops complexity guarantees for general methods and finite-sum problems.

1 Introduction

  • Stochastic methods target expected risk, while their convergence rates are typically slow; the role of Nesterov acceleration for stochastic objectives remains poorly understood.The paper identifies achieving optimal behavior both before and after reaching the noise-dominated regime as a central challenge.Source: §1 · pp. 1–2
  • Extending Catalyst, the authors turn a method with mild guarantees on strongly convex subproblems into one with accelerated forgetting of initialization and a stochastic phase typically depending optimally on gradient-noise variance.The framework also treats convex objectives that are not strongly convex.Source: §1 · p. 2
  • The framework recovers optimal finite-sum and strongly convex stochastic complexities up to logarithmic terms, paying a logarithmic factor versus direct acceleration.The finite-sum complexities are described as optimal up to logarithmic terms in L and µ.Source: §1 · p. 2
  • The analysis allows subproblems to be solved approximately in expectation and covers accelerated stochastic gradient descent and proximal methods with inexact proximal operators.The authors describe expected inexact solves as more realistic for stochastic optimization.Source: §1 · pp. 2–3
  • The proposed variant uses a fixed computational budget for subproblems, avoiding the need to define their stopping criteria.The authors describe this Catalyst variant as easier to implement.Source: §1 · p. 3

2 Related Work on Inexact and Stochastic Proximal Point Methods.

Catalyst is presented through the inexact accelerated proximal point method, while the paper distinguishes its stochastic-surrogate approach from sampling-based deterministic subproblems.

2 Related Work on Inexact and Stochastic Proximal Point Methods.

  • Catalyst uses an inexact accelerated proximal point scheme that approximately solves a sequence of subproblems and updates two sequences.The method M is used to obtain approximate minimizers of the subproblems.Source: §2 · p. 3
  • The update uses Nesterov-derived β_k and a regularization parameter κ; linear convergence of M can improve worst-case complexity over applying M directly to f.The passage identifies κ as a chosen regularization parameter and the norm as Euclidean.Source: §2 · p. 3
  • Rather than sampling to create deterministic subproblems, the paper uses more general surrogate functions h_k; without extrapolation, the sampling approach is called stochastic proximal point.The passage names prior work on stochastic proximal point methods.Source: §2 · p. 3

3 Preliminaries: Basic Multi-Stage Schemes

The section presents two multi-stage mechanisms for improving worst-case stochastic optimization complexity before introducing acceleration principles.

Basic restart with mini-batching or decaying step sizes

  • A bias–complexity trade-off supports staged reductions in stochastic error through mini-batching or smaller step sizes, with warm restarts between stages.The example uses exponentially increasing batch sizes after reaching a noise-dominated region.Source: §3 · p. 3
  • For averaged constant-step SGD, the staged scheme combines deterministic-style O((L/µ) log(1/ε)) complexity with the optimal stochastic O(σ²/(µε)) complexity.The example sets B = 1/L, C = 1, and τ = µ/L.Source: §3 · p. 3

Restart: from sub-linear to linear rate with strong convexity

  • Restarting a method with a sublinear guarantee in fixed-length runs can yield the strongly convex convergence relation required by the framework.With D ≥ µ, the run length is ⌈(2D/µ)^(1/d)⌉; the resulting parameters include τ = 1/(2t′).Source: §3 · p. 4

4 Generic Multi-Stage Approaches with Acceleration

The section develops a generic acceleration framework based on strongly convex surrogate problems, then applies it to deterministic and stochastic optimization. Extensions address inexact minimization and show how strongly convex surrogate models can improve stochastic complexity.

4 Generic Multi-Stage Approaches with Acceleration

  • Algorithm 1 presents a generic acceleration framework that iteratively considers surrogates h_k satisfying (H1) and (H2), obtains iterates using method M satisfying (H3), and initially assumes exact minimizers are available.The conditions on h_k bear similarities to Nesterov estimate sequences, while the exact-minimizer assumption differs from Catalyst [33].Source: §4 · p. 4
  • For stochastic proximal gradient, the surrogate analysis gives δk = σ2/(κ + µ); with µ > 0, choosing κ = L − µ yields the stated complexity guarantee.The same framework also recovers accelerated rates for deterministic proximal gradient and proximal point methods.Source: §4 · p. 5
  • For convex objectives, a fixed-horizon choice of κ recovers optimal noise-level dependence, but requires σ2 and an upper bound on ∥x0 − x⋆∥.The passage characterizes this guarantee as non-practical.Source: §4 · p. 5

4.1 Variant with Inexact Minimization

  • Inexact minimization can be performed in expectation, and the extension removes Catalyst’s full-gradient initialization requirement for composite problems [33].For inexact proximal operators, the analysis recovers prior results while allowing expected inexact minimization; maintaining acceleration requires controlled error decay and incurs stated complexity penalties.Source: §4.1 · pp. 6–7

4.2 Exploiting methods M providing strongly convex surrogates

  • Basic stochastic Catalyst can have suboptimal noise dependence, while a closed-form-minimizable model of an approximately minimized strongly convex surrogate enables Algorithm 1 and a 1/√q complexity gain.The paper identifies this route for methods that provide both an approximate minimizer and a surrogate satisfying the framework’s conditions.Source: §4.2 · p. 7
  • The resulting complexity combines Catalyst’s accelerated deterministic rate with a potentially optimal rate for strongly convex stochastic problems.Practical parameter choices are given for proximal stochastic gradient descent and stochastic finite-sum methods.Source: §4.2 · p. 8

5 Experiments

The experiments compare stochastic optimization methods on regularized binary-classification tasks under controlled gradient perturbations. Acceleration is often useful in the stochastic regime, but the authors report poor performance for some very ill-conditioned settings.

Formulations

  • Experiments use logistic or squared-hinge loss, regularization values μ = 1/10n, 1/100n, and 1/1000n, and DropOut perturbations δ = 0, 0.01, or 0.1.DropOut zeros each gradient component with probability δ and rescales it otherwise; squared-hinge gradients are unbounded on the optimization domain.Source: §5 · p. 8

Datasets

  • The evaluation covers alpha, gene, and ckn-cifar datasets, spanning different sample sizes and dimensions.The passage describes alpha as 250,000 points in 500 dimensions, gene as 295 in 8,141, and ckn-cifar as 50,000 in 9,216.Source: §5 · pp. 8–9

Methods

  • The compared methods include SVRG and SAGA variants with decreasing step sizes under noise, plus Katyuasha and acc-SVRG in the stated settings.The smooth-loss experiments use y_{k−1} as the warm start because it performed consistently better there.Source: §5 · p. 9

Practical questions and implementation

  • Step sizes are decayed after 30 epochs, and inner-loop iterations follow the theoretical schedule: n iterations when η_k = 1 and ⌈n/η_k⌉ after decay begins.The authors state that theory does not provide useful guidance on when decay should start because the required time depends on σ².Source: §5 · p. 9

Experiments and conclusions

  • Acceleration may be useful in stochastic optimization, but all acceleration methods may perform poorly at μ = 1/1000n; there, sublinear rates for μ = 0 are typically better than linear rates for μ > 0.The authors note that these ill-conditioned cases are often unrealistic for empirical risk minimization.Source: §5 · p. 9
  • Figure 1 plots objective value on a logarithmic scale against epochs for SVRG-like methods and SAGA; tubes show one standard deviation across five runs.The caption specifies ℓ2-logistic regression with δ = 0.1 and μ = 1/(100n) for the bottom plots.Source: Figure 1 · p. 9

A Useful Results and Definitions

This appendix section introduces the proximal operator and establishes bounds for sequences used in the paper's convergence analysis.

Definitions

  • The proximal operator of a convex lower-semicontinuous function is defined as the unique solution of a strongly convex problem.The passage does not include the problem's full displayed expression.Source: A Useful Results and Definitions · p. 13

Lemma 8

  • For q = 0 and α₀ = 1, the section also states A_k ≤ 4(k + 2)²; for q > 0, it gives A_k = (1 − √q)^k and α_k = √q.The displayed q = 0 bound is supported by the listed result fragment.Source: A Useful Results and Definitions · p. 13
  • For q = 0 and α₀ = 1, the sequence bounds include A_k = α_k² and α_k² ≤ 4(k + 2)² for k ≥ 1.The proof proceeds by induction.Source: A Useful Results and Definitions · p. 13

Proofs

  • The proof outline establishes the sequence results by induction and uses a recursively defined comparison sequence to bound α_k.The fragments also invoke log(1 + u) ≥ u/(1 + u) for u > −1.Source: A Useful Results and Definitions · pp. 13–14

B Details about Complexity Results

The appendix derives complexity bounds by restarting methods, translating a convergence guarantee into the paper's main bounds, and accounting for inner- and outer-loop work.

B.1 Details about (5)

  • The global complexity in (5) follows by running the method until its error reaches the noise scale, then using restart stages that halve the error until the target ε is met.The initial run length depends logarithmically on the initial error divided by ε, and the stages are initialized from the previous stage's output.Source: §B.1 · p. 14

B.2 Obtaining (5) from (6)

  • Restarting the procedure yields the guarantee (2) with C = 1 and τ = 1/(2t′), from which (5) follows.The restart count is set after running t′ iterations, with t′ determined by the strong-convexity parameter and the convergence exponent.Source: §B.2 · pp. 14–15

B.3 Details about (13)

  • The inner-loop cost is Õ(τ/η_k), with Õ(τ) iterations of M to solve the subproblem; the outer-loop iteration count is set using the stated error decrease rate.The inner-loop choice makes the bias η_kBσ² smaller than ε_k.Source: §B.3 · p. 15

B.4 Complexity of accelerated stochastic proximal gradient descent with inexact prox

  • The inexact-prox complexity subsection gives a schedule relating δ_k to ε_k, σ², κ, and μ.The supplied expression is δ_k = 2ε_k + 3σ² 2(κ + μ), without a clearly legible operator between the final terms.Source: §B.4 · p. 16

C.1 Proof of Propositions 1 and 4

The proof develops a Lyapunov-based analysis for the two propositions and treats strongly convex and convex cases separately. It also uses properties of the Moreau–Yosida smoothing in the proof of Proposition 5.

C.1 Proof of Propositions 1 and 4

  • A Lyapunov function is used to organize the convergence proof, with terms involving the iterate and auxiliary point canceling under the stated relation for η_{k−1}.For variant Algorithm 1, the proof sets Δ_k(z_{k−1}) = 0; the strongly convex and convex cases are then handled separately.Source: §C.1 · p. 17
  • In the strongly convex case, the proof uses A_k = (1 − √q)^k to derive the first part of Proposition 1; it separately establishes the convex-case result from bounds on A_k.The proof fragments identify these as the μ > 0 and μ = 0 specializations, respectively.Source: §C.1 · p. 17
  • For Proposition 4, the proof bounds the additional Δ_k term and then unrolls the resulting recursion for the strongly convex and convex cases.For μ = 0, it selects θ_k = γ/(k + 1)^(1 + γ), with γ in (0, 1], and uses bounds on A_k.Source: §C.1 · pp. 18–19

C.2 Proof of Proposition 5

  • The proof of Proposition 5 interprets the auxiliary objective as a Moreau–Yosida smoothing, which is κ-smooth and has gradient κ(y_{k−1} − x⋆_k).The subsequent bound uses proximal-operator non-expansiveness and strong convexity of h_{k−1}.Source: §C.2 · p. 19

C.3 Proof of Proposition 6

The proof derives inner-loop, outer-loop, and global complexity results from the chosen accuracy schedule and the preceding propositions.

Inner-loop complexity

  • The chosen δ_k schedule keeps E[H_k(x_k) − H⋆_k] ≤ δ_k, so Proposition 5’s inner-loop complexity result applies.The passage does not state the resulting complexity expression.Source: §C.3 · p. 19

Outer-loop complexity

  • The outer-loop error is bounded by O((1 − √q/2)^k(F(x_0) − F⋆)/√q).Source: §C.3 · p. 20

Global complexity

  • The global-complexity derivation uses ε = O(ε_K/√q), rather than ε = O(ε_K/q), to obtain the stated complexity.Source: §C.3 · p. 20

D Methods M with Duality Gaps Based on Strongly-Convex Lower Bounds

This method builds on stochastic composite updates and strongly convex quadratic surrogates, applying their guarantees to auxiliary objectives while focusing on quadratic surrogates for simplicity.

Stochastic updates and surrogates

Constant variance

Application to H_k

  • Applying the method to H_k uses the specified initialization and surrogate choices to satisfy the stated conditions for the auxiliary objective.The passages also describe transferring prior guarantees to H_k under the stated parameter condition.Source: D Methods M with Duality Gaps Based on… · pp. 20–21

Variance reduction

Other schemes

E Additional Experimental Material

The experiments were run five times per setup, and the plots show averaged primal gaps with standard-deviation bands.

Computing resources

Experimental protocol

Plot construction

E.1 Additional experiments.

The experiments find stochastic acceleration broadly competitive with accelerated SVRG, while also showing that performance depends on conditioning and loss setting.

No-noise experiments

Stochastic acceleration

Squared hinge loss

  • With squared hinge loss, methods perform similarly to the logistic-loss case despite the bounded-noise assumption not necessarily holding on the optimization domain.Source: §E.1 · p. 21, Figure 8 · p. 24

Ill-conditioned problems

Loading 1906.01164v3…