Improved SVRG for Non-Strongly-Convex or Sum-of-Non-Convex Objectives

Zeyuan Allen-Zhu; Yang Yuan

Source-linked AI summary

Improved SVRG for Non-Strongly-Convex or Sum-of-Non-Convex Objectives

Zeyuan Allen-Zhu, Yang Yuan

arXiv:1506.01972v3Jun 5, 2015cs.LGcs.DSmath.OCstat.ML

TL;DR

The paper addresses limited convergence guarantees for SVRG beyond strongly convex objectives, which occur in applications such as Lasso, logistic regression, and stochastic PCA. It revisits SVRG and introduces SVRG++ plus refined smoothness-based analysis for non-strongly convex and sum-of-non-convex objectives. The resulting methods improve known running-time bounds while preserving direct or broadly applicable formulations.

Problem
Most variance-reduction methods, including SVRG, had convergence guarantees primarily for strongly convex objectives, although important machine-learning objectives are not strongly convex or contain non-convex components.
Method
The paper applies SVRG directly to non-strongly convex objectives, introduces SVRG++, and analyzes SVRG using separate upper and lower smoothness parameters for non-convex components.
Results
The proposed analyses and variants improve known running times for non-strongly convex, sum-of-non-convex, and combined objectives, including stochastic PCA formulations.
Takeaways & Limitations
SVRG can remain effective beyond its original strongly convex setting, supporting faster algorithms for objectives arising in feature selection and stochastic PCA.
Takeaways & Limitations
Dummy-regularization approaches require choosing λ in advance, can leave error at O(λ), and hurt performance in theory and practice.

Abstract

from arXiv · show

Many classical algorithms are found until several years later to outlive the confines in which they were conceived, and continue to be relevant in unforeseen settings. In this paper, we show that SVRG is one such method: being originally designed for strongly convex objectives, it is also very robust in non-strongly convex or sum-of-non-convex settings. More precisely, we provide new analysis to improve the state-of-the-art running times in both settings by either applying SVRG or its novel variant. Since non-strongly convex objectives include important examples such as Lasso or logistic regression, and sum-of-non-convex objectives include famous examples such as stochastic PCA and is even believed to be related to training deep neural nets, our results also imply better performances in these applications.

1 Introduction

The paper revisits SVRG as a method that can handle non-strongly convex and sum-of-non-convex objectives, addressing the design complexity of specialized optimization algorithms. It introduces SVRG++ and refined analyses that improve theoretical running times while retaining practical relevance for machine learning problems.

Motivation: The work targets optimization settings whose many smoothness and convexity distinctions make designing a separate algorithm for every class unrealistic.A single method that works across multiple classes can reduce this design complexity.
Non-Strongly Convex Objectives: Non-strongly convex objectives include Lasso and ℓ1-Regularized Logistic Regression, both widely used for feature selection.Adding a dummy regularizer requires tuning λ, prevents error convergence below O(λ), and hurts performance in theory and practice.
Non-Strongly Convex Objectives: SVRG++ directly solves non-strongly convex objectives with gradient complexity O(n log 1/ε), improving known direct and indirect methods.It is an anytime method, so it can be interrupted at any time without requiring a dummy regularizer.
Sum-of-Non-Convex Objectives: For sum-of-non-convex objectives, distinguishing upper smoothness L from lower smoothness l yields a more graceful dependence on non-convexity.When l = O(σ), SVRG can have asymptotically convex-like convergence; when l > L, the dependence becomes linear in l rather than quadratic.
Sum-of-Non-Convex Objectives: The refined SVRG analysis improves stochastic PCA algorithms because leading-eigenvector computation can be expressed as a sum-of-non-convex optimization problem.For normalized covariance matrices, the formulation has upper smoothness L = λ and lower smoothness l = 1.
Combined Setting: The paper combines its improvements into SVRG++nc, which handles objectives that are both non-strongly convex and sum-of-non-convex.The combined method is reported to yield faster algorithms than known results.

2 Other Related Work

Related work develops variance-reduction methods for strongly and non-strongly convex objectives, while this paper reports improved accelerated and direct running times.

SAG, SVRG, MISO, and SAGA establish linear convergence for strongly convex and smooth objectives through variance reduction.
Garber and Hazan relate principal-component computation to minimizing a sum-of-non-convex objective parameterized by the eigengap.
The paper improves the accelerated PCA running time to eO(n^3/4λ^1/4d/√δ).
Prior direct methods for non-strongly convex objectives include SAG, MISO, and SAGA, while indirect methods add regularization or use dual formulations.
Concurrent work obtained the SVRG++ running time through reductions, but its algorithm was not direct and therefore was reported as less practical.

3 Notations

The paper assumes differentiable component functions and a convex, lower-semicontinuous proximal term, and distinguishes upper from lower smoothness through Hessian bounds.

Each fi is assumed differentiable, while Ψ is convex and lower semicontinuous.
Related oracle-model results provide comparable bounds to SVRG++, but do not support proximal terms and therefore do not directly apply to Lasso or logistic regression.
A convex differentiable function is 0-lower smooth; an L-smooth function is both L-upper and L-lower smooth.
L-upper smoothness bounds Hessian eigenvalues above by L, whereas l-lower smoothness bounds them below by −l.

4 SVRG++ for Non-Strongly Convex Objectives

SVRG++ addresses non-strongly convex objectives using growing epochs and variance reduction, while SVRG Auto Epoch adapts epoch lengths based on gradient-estimator quality.

SVRG++ for Non-Strongly Convex Objectives: SVRG++ doubles the stochastic-update length between consecutive epochs, distinguishing it from cited variance-reduction methods.
SVRG++ for Non-Strongly Convex Objectives: SVRG++ computes a snapshot full gradient at the previous epoch’s average point and starts the next epoch from the previous epoch’s ending vector.
SVRG++ for Non-Strongly Convex Objectives: SVRG++ achieves gradient complexity O(S · n + 2^S · m0), with η = 1/(7L) in Theorem 4.1.
SVRG++ for Non-Strongly Convex Objectives: The analysis telescopes regret inequalities across both iterations and epochs, avoiding the strong-convexity requirement used by original SVRG.
4.1 Additional Improvements: SVRG Auto Epoch terminates an epoch when recent average gradient differences exceed half the previous epoch’s average, but its complexity remains unproved.
4.1 Additional Improvements: Mini-batching and less accurate early snapshot gradients are described as orthogonal enhancements that can further improve SVRG++.

5 SVRG for Sum-of-Non-Convex Objectives I: Small Lower Smoothness

For strongly convex objectives formed from non-convex components with small lower smoothness, the paper analyzes SVRG using separate upper and lower smoothness parameters and improves its variance bound.

Small Lower Smoothness: The setting assumes σ-strong convexity of f while each fi is L-upper smooth and l-lower smooth with 0 ≤ l ≤ L.
Small Lower Smoothness: The resulting complexity is asymptotically the same as the convex setting when l ≤ O(σ) and degrades linearly as l increases.
SVRG baseline: Original SVRG uses equal-length epochs and initializes each epoch from the previous epoch’s average vector.
Small Lower Smoothness: Theorem 5.1 uses a stepsize η = min{1, ...} and establishes a total gradient complexity for this sum-of-non-convex setting.
Small Lower Smoothness: The new variance upper bound reduces to the convex-setting bound when l is very small.

6 SVRG for Sum-of-Non-Convex Objectives II: Large Lower Smoothness

For objectives whose component functions have large lower smoothness l ≥ L, the paper improves SVRG’s complexity dependence on non-convexity from quadratic to linear.

The best known stochastic-gradient complexity in the l ≥ L regime is improved from an l^2/L^2 penalty to l/L.The paper identifies this as a quadratic improvement over the previous dependence.
The resulting improvement also strengthens the convergence guarantee for stochastic algorithms applied to PCA.The paper connects the result to the known reduction of PCA to this optimization setting.
Theorem 6.1 provides the main SVRG convergence result for L-upper- and l-lower-smooth components when the average objective is σ-strongly convex.The theorem specifies step-length and epoch-length conditions for this setting.
The analysis avoids the l^2 factor in the variance bound by negating the component objectives for analysis, making them l-upper and L-lower smooth.This transformation is used only in the proof and yields a tighter variance bound.
The proof details for the large-lower-smoothness result are deferred to Appendix C.

7 SVRG++

This section combines the paper’s improvements for non-strongly convex and sum-of-non-convex objectives, yielding a direct SVRG++nc algorithm with staged epochs and a stated gradient-complexity bound.

Problem setting: The combined setting allows non-convex component functions while their average objective is convex but not necessarily strongly convex.Each component is assumed L-upper and l-lower smooth.
Comparison: Regularization-based reductions produce indirect and biased algorithms, whereas the proposed SVRG++nc method is direct.The paper presents this distinction as a motivation for the new method.
Algorithm: The method is proposed as a direct algorithm for the combined objective class.The paper contrasts it with indirect regularization-based reductions.
Algorithm: SVRG++nc uses S epochs, doubles the stochastic-step count between epochs, and computes a full gradient at the average point of the previous epoch.The variance-reduced stochastic gradient is defined using that snapshot full gradient.
Guarantee: The convergence result assumes an initial vector whose distance and objective gap from the optimum satisfy stated bounds.These assumptions are given in Theorem 7.1.
Guarantee: The total gradient complexity is expressed as O(S · n + 2^S · m0).The bound is stated in the section’s convergence analysis.

8 Experiments on Empirical Risk Minimization

Experiments on four datasets compare SVRG variants with direct and indirect baselines on Lasso, ridge regression, and ℓ1-regularized logistic regression.

Experimental setup: The study evaluates Lasso, ridge regression, and ℓ1-regularized logistic regression across four datasets and four regularizer weights.Lasso and logistic regression are treated as non-strongly-convex objectives, while ridge regression is strongly convex.
Results: Figure 1 reports selected Lasso and logistic-regression comparisons using Tuning Type I, with additional regularizer weights and ridge results in appendix figures.
Plot interpretation: Plots use training-objective suboptimality on the y-axis and dataset passes on the x-axis.A full-gradient computation counts as an additional pass for SVRG-based methods.
Results: SVRG++ and SVRG Auto Epoch consistently outperform SVRG in all plots for the reported non-strongly-convex comparisons.The authors interpret this as evidence that both variants improve over SVRG in this setting.
Results: SVRG++ and SVRG Auto Epoch outperform SAGA in most cases and are at least comparable in the remaining cases.SAGA is also characterized as a direct method for non-strongly-convex objectives.
Results: SVRG++ and SVRG Auto Epoch significantly outperform SDCA with dummy regularization in non-strongly-convex settings.For strongly convex ridge regression, SDCA is comparable to the other methods.

9 Experiments for Sum-of-Non-Convex Objectives

Synthetic experiments test SVRG on sum-of-non-convex objectives by controlling component smoothness, and the results support linear rather than quadratic dependence on the non-convexity parameters.

Experimental construction: The experiments use n = 500 normalized random vectors in dimension d = 200 to construct synthetic sum-of-non-convex objectives.The covariance matrix is decomposed into component functions whose smoothness parameters can be controlled.
Experimental construction: The construction uses diagonal matrices D_i summing to zero, with negative diagonal entries making individual component functions non-convex.Two matrix-generation schemes target the l ≤ L and l ≥ L regimes.
Experimental scope: The authors do not run real-life PCA experiments because varying the reduction parameter would make the theoretical improvement impossible to observe in plots.They instead use synthetic data to control upper and lower smoothness directly.
Results: For the l ≤ L experiment, SVRG performance scales approximately as lL = O(δ), compared with the prior-work dependence L^2 = O(1).For δ ≤ 0.02, convergence is as fast as in the convex case.
Results: For the l ≥ L experiment, SVRG performance scales approximately as lL = O(k), compared with the prior-work dependence l^2 = O(k^2).This observation is reported as confirmation of the Section 6 result.

A Convergence Analysis for Section 4

Section 4 develops the convergence analysis of SVRG++ through variance-reduction and smoothness arguments, culminating in a gradient-complexity bound.

The analysis introduces inner and outer iteration notation for SVRG++ and establishes lemmas for its stochastic updates.
The proof combines convexity, smoothness, variance identities, and Young’s inequality to derive the convergence recursion.
SVRG++ uses step length η = 1/(7L), sums the recursion across inner iterations, and telescopes across epochs.
SVRG++ computes S full gradients and O(2^S m0) component gradients, giving total gradient complexity O(S · n + 2^S · m0).
Unlike standard SVRG, SVRG++ initializes each epoch with the previous epoch’s ending vector rather than its average, which is reported as beneficial in practice.

B Convergence Analysis for Section 5

Section 5 extends the convergence analysis to the relevant objective setting by using strong convexity and a variance-reduction lemma tailored to the component functions.

The section defines SVRG notation and states a strong-convexity counterpart of the earlier convergence lemma.
The variance bound contains a term with factor 8l^2 + 4Ll, which increases as l increases.
When l = 0, the new variance lemma becomes identical to the earlier lemma; the authors also compare its bound with prior work by Shalev-Shwartz.
The proof constructs φ_i as a convex, (L + l)-smooth function minimized at x∗ to control gradient variance.
The theorem proof combines the strong-convexity lemma, the variance bound, convexity, and epoch averaging to obtain the stated convergence result.

D Convergence Analysis for Section 7

Section 7 proves convergence using a revised step-length analysis that combines bounds across the regimes l ≤ L and l ≥ L, then validates the theory experimentally.

The analysis replaces the earlier lemma with a revised version whose step length varies by epoch.
A unified bound is obtained by combining the variance lemmas for l ≤ L and l ≥ L, covering every l ≥ 0.
The theorem follows after applying the parameter assumptions, bounding the terms in the resulting inequality, and telescoping across epochs.
The figures compare training errors under Tuning Types I and II across the four datasets.