PaperlayerView exact revision on arXiv

Source-linked AI summary

Stochastic first-order methods: non-asymptotic and computer-aided analyses via potential functions

Adrien Taylor, Francis Bach

arXiv:1902.00947v6math.OCcs.CCcs.LGcs.NAmath.NA

TL;DR

Analyzing stochastic first-order methods is challenging because common noise assumptions can be restrictive and choosing useful potentials can require substantial intuition. The paper develops a potential-based framework for worst-case analysis and parameter tuning; for a chosen potential structure, it provides the best guarantees available through that approach.

  • Problem

    Uniformly bounded-variance assumptions on stochastic methods have limited applicability, while choosing potential sequences can require substantial intuition and tedious investigation.

    Source: §1.3 · p. 3

  • Method

    The paper adapts performance estimation to potential-based proofs for first-order methods and selects algorithm parameters while designing the potentials.

    Source: §1 · p. 1, §5 · p. 12

  • Results

    For a given potential structure, the methodology obtains the best worst-case guarantees available through a potential-based approach.

    Source: §5 · p. 12

  • Takeaways & Limitations

    The framework can derive step-size policies for first-order methods with the same worst-case guarantees as the analyzed methods using unrealistic line searches.

    Source: §5 · p. 12

    The presented work focuses on unconstrained, smooth problems without strong convexity.

    Source: §5 · p. 12

Abstract

from arXiv · show

We provide a novel computer-assisted technique for systematically analyzing first-order methods for optimization. In contrast with previous works, the approach is particularly suited for handling sublinear convergence rates and stochastic oracles. The technique relies on semidefinite programming and potential functions. It allows simultaneously obtaining worst-case guarantees on the behavior of those algorithms, and assisting in choosing appropriate parameters for tuning their worst-case performances. The technique also benefits from comfortable tightness guarantees, meaning that unsatisfactory results can be improved only by changing the setting. We use the approach for analyzing deterministic and stochastic first-order methods under different assumptions on the nature of the stochastic noise. Among others, we treat unstructured noise with bounded variance, different noise models arising in over-parametrized expectation minimization problems, and randomized block-coordinate descent schemes.

1. Introduction

The paper studies convex stochastic minimization with approximate first-order oracles and introduces a potential-based framework for analyzing first-order methods, especially at sublinear rates. It situates this framework among prior work and outlines its applications and organization.

1. Introduction

  • The paper studies convex stochastic minimization using approximate first-order oracles, including unbiased stochastic oracles and biased block-coordinate directions.The oracle index is uniformly sampled from an index set.Source: §1 · p. 1

1.2. Contributions

  • The framework covers finite-index settings such as empirical risk minimization and block-coordinate methods, while some stochastic-gradient analyses do not depend on index-set cardinality.Cardinality can matter in specific settings, including finite sums and coordinate descent.Source: §1 · p. 1
  • The framework constructs potentials for first-order stochastic algorithms, specializes in sublinear convergence, and supports analyses and parameter selection across stochastic settings.Its tightness property means an unsatisfactory bound can be improved only by enriching the potential class, adding assumptions, or changing the problem class.Source: §1.2 · p. 2

1.3. Prior works

  • Prior work uses stochastic-oracle assumptions such as uniformly bounded variance, which can have limited applicability, and potential functions have a history in first-order convergence analysis.Computer-assisted performance estimation has also been adapted here to potential-based proofs for sublinear rates.Source: §1.3 · p. 3

1.4. Organization

  • The paper presents the methodology and potential design before stochastic applications, with additional techniques and applications covered in the appendix.The appendix includes automatic parameter selection, accelerated methods, weak-growth settings, and coordinate descent.Source: §1.4 · pp. 3–4

2. Potential functions for a restricted class of first-order methods

The section frames a restricted class of stochastic first-order methods, including SGD with possible averaging and momentum. It explains how recursively chosen potential functions turn one-step inequalities into convergence arguments, while systematic potential design addresses a major practical difficulty.

2. Potential functions for a restricted class of first-order methods

  • The restricted method class encompasses SGD with optional averaging and momentum.The iteration uses a sampled random variable at each step.Source: §2 · p. 4
  • Potential proofs study one iteration at a time and choose a sequence of potentials, but selecting that sequence can require substantial intuition and tedious investigation.The paper aims to systematize designing and verifying these potentials.Source: §2 · p. 4
  • A one-step potential inequality with an error term can be iterated to obtain expected convergence bounds, with the error term typically capturing stochastic variance.The expectation is over the sequence of sampled indices; such expected convergence results can typically be converted to almost-sure convergence.Source: §2 · p. 4

3. Design methodology for potential functions

The section turns potential-based convergence proofs into a systematic design and verification procedure using semidefinite programs. Its examples apply the procedure to gradient descent and stochastic methods, including guarantees under bounded-variance assumptions.

3.1. Verifying a potential

  • Potential verification becomes an LMI when consecutive potentials are quadratic in first-order information and coordinates, and linear in function values.The paper says this reformulation is lossless in standard settings, including its listed noise models and quadratic potentials.Source: §3 · p. 5, §3.1 · p. 5

3.2. Strategies for designing sequences of potentials

  • The design procedure numerically searches for potential schedules, simplifies promising schedules, then seeks a feasible one-step proof.For gradient descent, the SDP uses N LMIs of size 3 × 3 and maximizes the certifiable b_N for the chosen potential structure.Source: §3.2 · p. 5, §3.2.1 · pp. 6–7

3.2.1. EXAMPLE I: GRADIENT DESCENT

  • Gradient descent admits simultaneous f(x_k) − f⋆ = O(k^-1) and ∥f′(x_k)∥² = O(k^-2) guarantees from a single potential.The authors describe this as the first use of standard function-value techniques to prove a gradient-norm rate; their feasible sequence uses d_k = (2k + 1)L and b_k = k(k + 2).Source: §3.2.1 · pp. 6–7

3.2.2. EXAMPLE II: STOCHASTIC SMOOTH CONVEX MINIMIZATION, BOUNDED VARIANCE

  • Stochastic analyses rely on finite support for the sampled index, enabling the LMI reformulation to average over its n = |I| scenarios.The bounded-variance examples use a uniformly bounded variance assumption, which the paper describes as restrictive.Source: §3.2.2 · pp. 7–8
  • For SGD with bounded variance, the bounds apply for all α, with the same optimal α = 2/3 as the compared prior result, which covered only α ∈ (1/2, 1).The authors note that their result has more limited assumptions but a considerably simpler proof than Bach and Moulines (2011).Source: §3.2.2 · p. 9
  • For Polyak-Ruppert averaging, bounds hold for all α and retain the same optimal α = 1/2, versus the prior range α ∈ (1/2, 1).The potential bound propagates only for decreasing step sizes.Source: §3.2.2 · p. 10
  • Primal averaging evaluates the stochastic gradient at the averaged iterate; the paper also gives a version that uses this evaluation for any step-size policy.The proposed fixed-step variant is introduced as an alternative to averaging.Source: §3.2.2 · p. 10

4. Application to stochastic convex minimization for over-parameterized models

For over-parameterized models with an interpolating optimum, the paper proposes primal averaging, evaluating stochastic gradients at the averaged iterate. The authors report better worst-case guarantees and simpler analysis than vanilla SGD in this setting.

4. Application to stochastic convex minimization for over-parameterized models

  • Under the interpolation condition f′_i(x⋆) = 0 for every i, primal averaging is simpler to analyze and has better worst-case guarantees than vanilla SGD.The best guarantee reached for vanilla SGD without averaging in this setup was O(k^-1/2).Source: §4 · p. 11

5. Conclusion

The framework gives potential-based worst-case analyses with tightness guarantees and supports extensions to several optimization settings. It also supports parameter selection and applications to proximal and coordinate-descent methods.

5. Conclusion

  • The method provides the best worst-case guarantees certifiable with a chosen potential structure; improving an unsatisfactory bound requires changing that structure, assumptions, or problem class.The framework also helps assess new ideas and develop algorithms for new settings.Source: §5 · p. 12
  • Automatic step-size selection adapts an approach based on idealized line searches to derive policies with matching worst-case guarantees.The approach is inspired by constructive methods for efficient first-order algorithms and earlier acceleration developments.Source: §5 · p. 12
  • The framework extends to projected and proximal settings, with a proximal-gradient potential given in the appendix.Source: §5 · p. 12
  • Coordinate-descent schemes are treated under assumptions that differ from standard ones, and the example also incorporates strong convexity.Source: §5 · p. 12

Codes

The paper provides code for generating and validating its results, while the appendix collects proofs and application examples. Appendix sections explain proof generation, parameter selection, and computational costs.

Codes

  • Code for generating and validating the results is available at the project’s GitHub repository.Source: Codes · p. 13

Appendix A. How to read the appendix

  • The appendix contains proofs omitted from the main text and complementary application examples, organized by optimization setup.Its sections begin with proofs and, in early settings, derive linear matrix inequalities and parameter-selection techniques.Source: Appendix A · p. 19
  • Computer-generated proofs come from numerically solving the analysis problem and combining weighted inequalities, chiefly interpolation inequalities.The appendix explains how to verify these proofs through weighted sums, dual variables, or numerical validation.Source: Appendix A · p. 19
  • The paper reports example runtimes and LMI sizes rather than general complexity figures, which depend on the potential, stochastic setting, method, and solver structure.Source: Appendix A · p. 20

Appendix B. Methodologies for computer-assisted worst-case analyses

The paper adapts performance-estimation techniques to verify potential inequalities, targeting sublinear and stochastic analyses. Its lossless formulation offers best-possible bounds within a chosen potential class and makes failure informative.

Appendix B. Methodologies for computer-assisted worst-case analyses

  • The PEP approach formulates the worst-case performance of N iterations as an optimization problem and can provide tight results through lossless semidefinite reformulations.Source: Appendix B · p. 21
  • PEP’s main analytical difficulty is turning numerical solutions into proofs, especially when large semidefinite matrices arise in stochastic settings.Source: Appendix B · p. 21
  • IQCs were initially developed for linear rates, but later work extended them to sublinear rates, stochastic methods, and algorithm design.Source: Appendix B · p. 21
  • The approach uses the PEP technique for lossless verification of potential inequalities, yielding simpler proofs and allowing analysis with randomness and stochasticity.Source: Appendix B · p. 21
  • Unlike standard IQC comparisons, the framework handles sublinear rates with broader potential functions, obtains best possible bounds for a chosen iteration count and potential class, and covers stochastic models without strong convexity.Source: Appendix B · p. 21

Appendix C. A parameter selection technique

The technique selects algorithm parameters by analyzing idealized methods and suitable potential families, then recovering fixed-step policies. The appendix also gives a gradient-method proof and notes limits of the relaxed selection problem.

Appendix C. A parameter selection technique

  • Jointly finding valid potentials and optimized parameters leads to bilinear matrix inequalities, so the proposed workaround studies a line-search variant and relaxed potential-verification conditions.In general, the relaxed verifiable set can be smaller than the set of valid potentials, so this selection analysis may fail even when a suitable potential sequence exists.Source: Appendix C · pp. 22–23
  • The selection strategy uses an idealized algorithm, often with line searches, and a potential family that makes some parameters optimizable while replacing others with line searches.The broader objective is to improve worst-case guarantees through parameter choices.Source: Appendix C · p. 22
  • A fixed-step gradient method can attain the same worst-case guarantee as its line-search procedure.The example chooses a step size for smooth strongly convex minimization using a potential with contraction factor ρ.Source: Appendix C · pp. 23–24
  • The parameter-selection technique can be adapted to stochastic methods, coordinate descent, and finite sums; an unprovided strong-growth example yields accelerated methods similar to those of Vaswani et al. (2019).Source: Appendix C · p. 24

D.1. Proof of Theorem 3

  • The gradient-method proof is formed by combining weighted convexity and smoothness inequalities to obtain the desired result.Source: §D.1 · p. 25

D.2. Proximal gradient method

The section extends potential-based analysis to proximal gradient for a smooth convex function plus a closed, proper convex term. Its potential is nearly the same as for gradient descent, with the stated analysis assuming dom f = R^d for simplicity.

D.2. Proximal gradient method

  • The proximal-gradient potential is nearly the same as the gradient-method potential, assuming dom f=R^d for simplicity.The passage notes that other inequalities are needed when this domain assumption does not hold.Source: §D.2 · p. 26
  • The proximal-gradient theorem establishes a potential inequality for the stated iterates and subgradient selections, with parameters b_k,d_k ≥ 0.The setup assumes f is smooth and convex, h is closed, proper, and convex, and x_{k+1} is obtained by a proximal step.Source: §D.2 · p. 26
  • The parameter choices use b_{k+1}=L+b_k and d_{k+1}=2L+d_k, with a natural next subgradient tied to the proximal operation.The stated choice is F′(x_{k+1})=L(x_k−x_{k+1})−f′(x_k)+f′(x_{k+1}).Source: §D.2 · p. 26
  • The proof combines weighted smoothness and convexity inequalities for f with a convexity inequality for h to recover the desired result.The weighted sum is reformulated as the desired result plus a positive term.Source: §D.2 · pp. 26–27

D.3. Design of accelerated methods

This section develops first-order method design and analysis using potential and parameter design, LMI formulations, and weighted inequalities. It covers accelerated methods and bounded-variance stochastic-gradient analyses, including asymptotic rates for several methods and an iterative scheme that evaluates the stochastic gradient at the true averaged iterate.

D.3. Design of accelerated methods

  • Parameter choices growing as O(k^2) give acceleration for each of two designed methods, with theorems specifying conditions under which their potential inequalities hold.The first method allows schedules with b_k = 0; the second also has a schedule with b_k = d_k.Source: §D.3 · p. 28
  • A second accelerated method uses only two sequences, illustrating that the design choices for the first method are not unique.Its theorem gives a sufficient condition for the potential inequality, and a parameter schedule with b_k = d_k = O(k^2) reaches acceleration.Source: §D.3 · pp. 31–33

D.4. Linear matrix inequalities for the gradient method

  • For vanilla gradient descent, smooth-convex interpolation constraints reformulate the performance condition as an LMI whose feasibility is equivalent to the primal formulation by strong duality.The LMI can be checked with standard semidefinite programming packages.Source: §D.4 · pp. 34, 36

D.5. Linear matrix inequalities for the design procedure

  • The design-procedure LMI encodes interpolation and line-search constraints as a sufficient, not exact, condition for the potential to hold for method (11).The formulation also permits optimizing the parameters (δ_k, γ_k) through an SDP relaxation.Source: §D.5 · pp. 37–39

E.1. Proof of Theorem 5

  • Theorem 5’s proof combines weighted inequalities, reformulates their sum, and rearranges it to obtain the result.Source: §E.1 · p. 40

E.2. Proof of Theorem 6

  • Theorem 6’s proof uses a weighted-sum reformulation and rearrangement, with the final inequality relying on δkL(1 − δkL) + 1 ≥ 0.Source: §E.2 · pp. 40–41

E.3. Proof of Theorem 7

  • Theorem 7’s proof combines weighted inequalities, reformulates their sum, and rearranges the terms to obtain the result.Source: §E.3 · pp. 41–42

E.4. Evaluation of the stochastic gradient at the true averaged iterate

  • The section presents an iterative scheme for evaluating the stochastic gradient at the true averaged iterate.Source: §E.4 · p. 42

E.5. Convergence rates

  • The section also derives asymptotic rates for stochastic gradient descent with averaging and with primal averaging, under the stated restrictions on α.Source: §E.5 · pp. 44–45

E.6. Better worst-case guarantees and rates

The section discusses ways to improve stochastic-method worst-case guarantees, including fixed-horizon choices and added memory, and presents LMI formulations for analyzing stochastic gradient methods. Its appendix material covers over-parameterized models and weak-growth conditions.

E.6. Better worst-case guarantees and rates

  • Knowing the iteration count in advance and using a compact domain are presented as ways to improve worst-case guarantees; the framework assumes limited memory and does not directly cover dual averaging.The authors say the framework might be adapted to dual averaging but leave this for future work.Source: §E.6 · p. 45
  • O(N^3) variance accumulation accompanies pure acceleration without damping, while d_N=O(N^2); the authors say this accumulation can hardly be avoided without damping.Dual averaging is given as a usual way to achieve damping.Source: §E.6 · p. 46

E.7. Linear matrix inequalities

  • The appendix gives an LMI formulation for the basic stochastic gradient method, with parameter selection following the same approach as earlier sections.The stated equivalence between the SDP and LMI may rely on a standard Slater argument, which is not provided here.Source: §E.7 · pp. 48–49

Appendix F. Stochastic gradients for over-parameterized models

  • Appendix F contains the proof of Theorem 8, discusses the parameter-selection path to primal averaging, and gives an LMI formulation for that scheme.Source: Appendix F · p. 50

F.1. Proof of Theorem 8

The appendix develops analyses and parameter choices for over-parameterized stochastic models, then gives a weak-growth analysis. It uses weighted inequalities and LMI formulations, with primal averaging emerging from parameter selection.

F.1. Proof of Theorem 8

  • The proof of Theorem 8 combines weighted inequalities and adds an averaged-smoothness inequality to compensate a nonpositive term.Source: §F.1 · p. 50

F.2. Parameter selection

  • Parameter selection for over-parameterized models uses a line-search formulation and a family of potentials, yielding primal averaging; numerical results are shown in Figure 5.The chosen potential targets the terminal function-value gap weighted by d_N.Source: §F.2 · p. 51

F.3. Linear matrix inequalities for over-parametrized models

  • The over-parameterized-model LMI formulation uses a Gram matrix; adding function values at stochastic next iterates did not improve results and enlarged it by n^2 rows and columns.In the reported Figure 5 scenarios, q_1,k was numerically about 10^-7 throughout.Source: §F.3 · p. 52, Figure 5 · p. 52

Appendix G. Stochastic gradients under weak growth conditions

  • O(k^-1) convergence is reported for function values at the last iterate under weak growth, while Vaswani et al. (2019) had shown the same rate for averaged iterates.The passage describes the last-iterate method as the best obtained with the preceding methodology.Source: Appendix G · p. 54

G.1. Proof of Theorem 14

These appendix sections prove a weak-growth result, treat stochastic gradients with bounded variance at the optimum, and extend the analyses to randomized block-coordinate descent. For smooth strongly convex objectives, the block-coordinate result gives linear convergence in distance to optimality.

G.1. Proof of Theorem 14

  • The proof of Theorem 14 obtains its result by combining inequalities with corresponding weights and rearranging the weighted sum.Source: §G.1 · p. 55

Appendix H. Bounded variance at optimum

  • The bounded-variance-at-optimum analysis again yields primal averaging, but with smaller allowed step sizes.Source: Appendix H · p. 56

Appendix I. Randomized block-coordinate descent

  • The randomized block-coordinate scheme samples a block uniformly and updates along that block's directional derivative; the analysis uses the global Lipschitz constant for convenience.The authors say the results can be adapted to block-specific Lipschitz constants or separable proximal operators.Source: Appendix I · p. 57

I.1. Block-coordinate descent for smooth convex minimization

  • For smooth convex minimization, the proof establishes a step-size condition using a negative-definite quadratic in the step size.The passage specifies 0≤δ_k≤1/L.Source: §I.1 · p. 58

I.2. Block-coordinate descent for smooth strongly convex minimization

  • For smooth strongly convex minimization, the result is linear convergence expressed in distance to optimality.Source: §I.2 · p. 58

Related papers

Loading 1902.00947v6…