PaperlayerView exact revision on arXiv

Source-linked AI summary

Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n)

Francis Bach, Eric Moulines

arXiv:1306.2119v1cs.LGmath.OCstat.ML

TL;DR

The paper addresses the slower convergence available for non-strongly-convex stochastic optimization. It proposes averaged constant-step-size SGD for least-squares and a Newton-like local-quadratic stochastic method for logistic regression, achieving O(1/n) rates in both settings.

  • Problem

    Non-strongly-convex stochastic optimization lacked methods with better function-value convergence than O(1/√n), despite its relevance to supervised learning.

  • Method

    The paper analyzes averaged constant-step-size SGD for least-squares and a stochastic algorithm using successive local quadratic approximations for logistic regression.

  • Results

    The two algorithms achieve O(1/n) rates for least-squares and logistic regression without strong-convexity assumptions, and experiments often show better performance than existing approaches.

  • Takeaways & Limitations

    Averaging and smooth-loss structure can support O(1/n) stochastic approximation rates for these classical supervised-learning problems without strong convexity.

Abstract

from arXiv · show

We consider the stochastic approximation problem where a convex function has to be minimized, given only the knowledge of unbiased estimates of its gradients at certain points, a framework which includes machine learning methods based on the minimization of the empirical risk. We focus on problems without strong convexity, for which all previously known algorithms achieve a convergence rate for function values of O(1/n^{1/2}). We consider and analyze two algorithms that achieve a rate of O(1/n) for classical supervised learning problems. For least-squares regression, we show that averaged stochastic gradient descent with constant step-size achieves the desired rate. For logistic regression, this is achieved by a simple novel stochastic gradient algorithm that (a) constructs successive local quadratic approximations of the loss functions, while (b) preserving the same running time complexity as stochastic gradient descent. For these algorithms, we provide a non-asymptotic analysis of the generalization error (in expectation, and also in high probability for least-squares), and run extensive experiments on standard machine learning benchmarks showing that they often outperform existing approaches.

1 Introduction

The paper targets non-strongly-convex stochastic optimization, where prior methods achieved O(1/√n), and develops smooth-loss algorithms attaining O(1/n) for least-squares and logistic regression.

  • Large-scale learning motivates stochastic methods that process each observation only once or a few times.SGD and its variants remain widely used in this setting.
  • For strongly convex objectives, averaged SGD achieves O(1/µn), whereas non-strongly-convex problems achieve only O(1/√n).The latter rate has matching lower bounds.
  • Typical high-dimensional machine-learning problems may have zero strong-convexity constant because their variables are correlated.
  • The paper aims to handle arbitrarily small strong-convexity constants while achieving O(1/n).
  • Using smoothness, averaged constant-step-size SGD reaches O(1/n) for least-squares, while a local-quadratic stochastic method does so for logistic regression.The logistic method preserves SGD's running-time complexity.
  • The algorithms receive non-asymptotic generalization analyses and extensive benchmark experiments, where they often outperform existing approaches.High-probability analysis is provided for least-squares.

2 Constant-step-size least-mean-square algorithm

For least-squares regression, averaged constant-step-size LMS achieves O(1/n) without strong convexity, with bounds designed to remain valid when covariance eigenvalues are arbitrarily small.

  • 2 Constant-step-size least-mean-square algorithm: Averaging a constant-step-size least-mean-square recursion yields an O(1/n) convergence rate without strong convexity.The algorithm is stochastic gradient descent applied to least-squares regression.
  • Assumptions: The analysis assumes a finite-dimensional Euclidean space and independent, identically distributed observations with finite second moments.
  • Assumptions: The covariance operator is assumed invertible, but its eigenvalues may be arbitrarily small.
  • Algorithm: The stochastic recursion updates θn using the observed covariate xn, response-related vector zn, and constant step-size γ.
  • Convergence in expectation: The expectation bound is designed not to depend on the smallest nonzero covariance eigenvalue while retaining O(1/n) scaling.
  • Proof technique: The proof uses non-asymptotic expansions in powers of γ and a recursion result involving the covariance operator.
  • Optimality: The O(1/n) least-squares rate is stated to be optimal, and the σ²d/n term is unimprovable.
  • Averaging: Averaging produces pointwise convergence to the solution and an O(1/n) expected excess-risk rate for the quadratic loss.

3 Beyond least-squares: M-estimation

For non-quadratic losses, constant-step-size stochastic approximation can converge at O(1/n) to the stationary mean, while quadratic approximations enable a provable O(1/n) logistic-regression rate without strong convexity. The approach uses local Newton-like surrogates and support-point strategies, with practical efficiency but scope-dependent limitations.

  • Stationary behavior: For general losses, averaged constant-step-size iterates converge at O(1/n) to the stationary-distribution mean, not necessarily the optimal predictor.The distance between the stationary mean and the optimum is typically order γ, while averaged iterates can have order γ^2 distance under stronger smoothness conditions.
  • Quadratic approximation: A quadratic surrogate around a support point converts the Newton step into a stochastic approximation problem solvable with constant-step-size LMS.The surrogate matches the loss value, gradient, and Hessian at the support point, and each stochastic update costs only about twice a regular stochastic-approximation step.
  • Logistic regression: The two-stage logistic procedure first estimates a support point with averaged SGD, then applies averaged LMS to the local quadratic approximation.Using n observations for each stage yields an O(1/n) rate, although the paper reports that this version is not the most efficient in practice.
  • Implementation and scope: Updating the support point at every iteration is reported as most efficient in practice, but the paper provides no convergence proof for this variant.The paper also considers less frequent dyadic updates and notes possible connections to two-time-scale algorithms.
  • Bias and related methods: For non-quadratic functions, the method deliberately introduces bias by replacing the true gradient with a local approximation that is valid near the support point.The paper contrasts this with one-step estimators, whose initial estimator typically already has O(1/n) convergence and uses different observations here.
  • Logistic regression: The logistic algorithm achieves O(1/n) convergence without assuming strong convexity, even locally, using self-concordance and sharp Newton-step analysis.This improves over a prior rate proportional to 1/(nλmin(H)).

4 Experiments

Experiments on synthetic and benchmark data compare averaged SGD, SAG, Adagrad, and Newton-based methods for least-squares and logistic regression. Averaging enables O(1/n) behavior in least-squares, while the novel Newton approximation is consistently strong on logistic benchmarks.

  • Synthetic data: Averaged constant-step-size SGD converges at O(1/n) for least-squares, with the same rate across tested constant step-sizes.Without averaging, constant-step-size SGD oscillates and its excess risk depends linearly on γ.
  • Synthetic data: For synthetic logistic regression, averaged SGD converges to a point with error proportional to γ2 rather than the optimum.Non-averaged constant-step-size SGD does not converge and reaches a γ-dependent error floor.
  • Synthetic data: The two-step Newton approximation achieves the theoretical O(1/n) rate, while doubling the schedule avoids the temporary performance worsening at n/2.Updating support points every iteration or at dyadic points also achieves O(1/n) early.
  • Standard benchmarks: On benchmark least-squares tasks, SAG and constant-step-size averaged SGD perform best, with a significant advantage for constant-step-size SGD.Sparse datasets show some overfitting after more than 10 passes, whereas non-sparse datasets generally do not.
  • Standard benchmarks: On benchmark logistic tasks, the novel Newton approximation is consistently better, while averaged SGD can underfit on covertype, alpha, and news.Even when d and κ are large enough to make bounds vacuous, the method remains state of the art and more robust to step-size selection.

5 Conclusion

The paper concludes that two stochastic approximation algorithms achieve O(1/n) rates for logistic and least-squares regression without strong-convexity assumptions. It emphasizes averaging, especially with large step-sizes, and identifies several extensions for future work.

  • 5 Conclusion: Two stochastic approximation algorithms achieve O(1/n) rates for logistic and least-squares regression without strong-convexity assumptions.The conclusion covers both regression settings.
  • 5 Conclusion: The analysis reinforces averaging as important for obtaining fast rates, particularly with large step-sizes.The conclusion highlights averaging as a central feature of the results.
  • 5 Conclusion: Future extensions include adaptive constant-step-sizes, iterate-dependent step-sizes, proximal methods, updated support points, and non-parametric analysis.The proposed directions also include improving theoretical results for large d.

A Proof of Theorem 1

The proof analyzes averaged least-squares SGD through linear stochastic recursions. It separates initial-condition and noise effects, replaces random covariance operators by their expectation, and controls the resulting expansion under a constant-step-size condition.

  • A Proof of Theorem 1: The quadratic loss makes the stochastic recursions linear, enabling closed-form analysis of the averaged iterate.The proof uses a recursion for ηn = θn − θ∗ and the averaged iterate.
  • A Proof of Theorem 1: The argument replaces xn ⊗ xn by its expectation H and studies the remainder through a similar recursion.This extends a fixed-design-style technique to the stochastic setting.
  • A Proof of Theorem 1: The expansion separately bounds the noise process and the noise-free process determined by the initial conditions.These contributions are treated analogously to a bias-variance decomposition.
  • A Proof of Theorem 1: The analysis assumes γR2 ≤ 1, which implies γH ≼ I under the stated covariance and moment conditions.The proof repeatedly uses this stability condition in the recursion bounds.
  • A Proof of Theorem 1: The proof leaves open whether initial conditions can be forgotten at rate O(1/n2), as in the strongly convex case.This is identified as an interesting condition for further analysis.
  • A Proof of Theorem 1: The proof yields the desired bound by combining the expansion estimates and letting the expansion order tend to infinity.The argument applies the auxiliary lemmas recursively before taking the limiting expansion order.

B Proof of Theorem 2

The proof of Theorem 2 controls higher moments of the stochastic recursion using martingale inequalities and expansions in the step-size. It separately bounds initialization, noise, covariance operators, and expansion errors.

  • B Proof of Theorem 2: The proof uses the Burkholder-Rosenthal-Pinelis inequality to control martingale noise terms and higher moments.The inequality is applied to recursively defined stochastic sequences.
  • B Proof of Theorem 2: The analysis splits initial-condition and noise contributions, then expands the noise contribution in powers of γ.This mirrors the proof strategy used for Theorem 1 while extending it to all moments.
  • B Proof of Theorem 2: A kurtosis condition controls products of quadratic forms in the covariates and supports the covariance-operator bounds.The condition bounds E⟨xn, Mxn⟩⟨xn, Nxn⟩ using traces involving H.
  • B Proof of Theorem 2: The constants in one bound could be improved by using a recursive proof.This is an acknowledged proof-level limitation rather than a change in the convergence rate.
  • B Proof of Theorem 2: The moment bounds rely on conditional mean-zero noise, covariance control, bounded noise moments, and the stability condition γH ≼ I.These conditions appear in the auxiliary recursion lemma.
  • B Proof of Theorem 2: The proof combines recursion bounds, expansion-error control, and Minkowski’s inequality to obtain the final result.The resulting estimates are assembled after controlling the noise and deterministic components.

B.4 Proof of Corollary 1

The proof combines approximate Newton-step analysis with stochastic approximation bounds to establish an O(1/n) error rate. The key mechanism is that Newton refinement squares the initial error while the quadratic subproblem is solved to O(1/n) accuracy.

  • Newton refinement: A single Newton step squares the error, so an O(1/√n) initial error yields an O(1/n) Newton error.The argument uses the stated quadratic convergence property of the full Newton step.
  • Quadratic subproblem: The approximate quadratic solution is O(1/n)-optimal, matching the target order for the final iterate.The proof identifies the third iterate as O(1/n)-optimal for the quadratic problem based on averaged LMS results.
  • Proof strategy: The proof combines a deterministic approximate-Newton result with two stochastic approximation results.The deterministic result controls the error after an approximate Newton step; the stochastic results provide the required bounds for the initialization and quadratic subproblem.

C.2 Stochastic analysis

The stochastic analysis constructs the logistic-regression method in two stages: averaged SGD first obtains an initializer, then LMS solves a local quadratic approximation. High-order deviation bounds control the resulting errors.

  • Algorithm: The algorithm first runs averaged stochastic gradient descent for n iterations from θ0 to obtain θ1.The construction uses a constant step-size for the initial averaged SGD phase.
  • Algorithm: Starting from θ1, LMS runs for n steps on the quadratic approximation and produces θ3, an approximation to the Newton step θ2.The Newton step θ2 is the global minimizer of the local quadratic objective.
  • Stochastic control: The analysis separates events and applies Cauchy–Schwarz and Markov inequalities to control the errors ε1 and ε2.ε1 is the error of the first SGD phase, while ε2 is the error made by LMS started from θ1.
  • Stochastic control: Higher-order bounds are required because the proof must control quantities of the form e^αε1.The analysis extends earlier results to obtain finer deviation control for the initial averaged SGD iterate.

D Higher-order bounds for stochastic gradient descent

This section develops high-order stochastic-gradient bounds and self-concordance tools for analyzing logistic regression. These ingredients relate excess risk, weighted distance, Newton decrement, and approximate Newton steps.

  • Higher-order stochastic bounds: Propositions 2 and 3 provide high-order and exponential bounds for averaged stochastic gradient descent under assumptions B1–B4.The results apply to the stochastic gradient recursion and its averaged version.
  • Self-concordance: Self-concordance yields global Taylor expansions showing that the loss behaves similarly to a quadratic function.The section bounds third-order derivatives using second-order derivatives to support these expansions.
  • Risk and distance: Small excess risk implies small weighted distance to the optimum, while the converse is also bounded through dedicated propositions.The weighted norm uses the Hessian at the optimum, H.
  • Newton analysis: The analysis distinguishes bounds for gradients, weighted distance, Hessian variation, and function-value expansions.These propositions supply the local geometric controls needed for approximate Newton-step analysis.
  • Newton analysis: A full Newton step improves the Newton decrement by taking a square.The Newton decrement governs Newton-method convergence, and the squared improvement is used in the later proof.

E.3 Proof of Prop. 1

The proof of Proposition 1 bounds the approximate Newton-step error by combining self-concordance inequalities with separate controls on the initial and quadratic-subproblem errors. It derives the stated cases by analyzing the Newton decrement and weighted distances.

  • Proof of Proposition 1: The proof first invokes Proposition 8 and related bounds to control the initial weighted distance and Newton decrement.The initial excess-risk error ε1 is converted into a bound on weighted distance.
  • Proof of Proposition 1: The Newton decrement at θ2 is then bounded using the improvement property of a full Newton step.This supplies the key refinement from the first iterate to the Newton iterate.
  • Proof of Proposition 1: Two proof paths establish the cases where only ε1 is bounded or where ε2 is also bounded.The latter case uses a computational check with t = 1/16 and u = 1/4 before obtaining Eq. (27).

F Additional experiments

Additional experiments show that performance depends on dataset structure: SAG is strongest on non-sparse data, while constant-step-size SGD performs best on high-dimensional sparse datasets but may not reach the optimum.

  • The experiments include additional results for the quantum and rcv1 datasets, alongside training-objective plots for all methods.
  • SAG achieves the smallest training error on non-sparse datasets.
  • Constant-step-size SGD performs best on high-dimensional sparse datasets.
  • Constant-step-size SGD may fail to converge to the optimal value, notably on the alpha dataset.
Loading 1306.2119v1…