Semi-Stochastic Gradient Descent Methods

Jakub Konečný; Peter Richtárik

Source-linked AI summary

Semi-Stochastic Gradient Descent Methods

Jakub Konečný, Peter Richtárik

arXiv:1312.1666v2Dec 5, 2013stat.MLcs.LGmath.NAmath.OC

TL;DR

The paper addresses minimizing the average of a large number of smooth convex losses, where full-gradient iterations are costly and stochastic methods can be unstable. It proposes S2GD, combining one full gradient with a geometrically distributed number of stochastic updates, and reports an O((κ/n) log(1/ε)) workload for ε-accurate solutions under strong convexity, while S2GD+ remains unanalyzed.

Problem
The paper studies minimizing the average of many smooth convex loss functions in settings where the number of examples n is very large.
Method
S2GD combines a full gradient with a geometrically distributed number of stochastic-gradient steps per epoch, while S2GD+ starts with an SGD pass and then uses fixed inner-loop lengths.
Results
O((κ/n) log(1/ε)) total work is achieved for ε-accurate solutions by running O(log(1/ε)) epochs with h = O(1/L) and m = O(κ).
Takeaways & Limitations
The method provides a workload-efficient variance-reduced approach for high-accuracy optimization, with SVRG arising as a special case.
Takeaways & Limitations
S2GD+ shows superior experimental performance but its complexity is not analyzed, and some complexity results distinguish expectation from high-probability guarantees.

Abstract

from arXiv · show

In this paper we study the problem of minimizing the average of a large number ($n$) of smooth convex loss functions. We propose a new method, S2GD (Semi-Stochastic Gradient Descent), which runs for one or several epochs in each of which a single full gradient and a random number of stochastic gradients is computed, following a geometric law. The total work needed for the method to output an $\varepsilon$-accurate solution in expectation, measured in the number of passes over data, or equivalently, in units equivalent to the computation of a single gradient of the loss, is $O((κ/n)\log(1/\varepsilon))$, where $κ$ is the condition number. This is achieved by running the method for $O(\log(1/\varepsilon))$ epochs, with a single gradient evaluation and $O(κ)$ stochastic gradient evaluations in each. The SVRG method of Johnson and Zhang arises as a special case. If our method is limited to a single epoch only, it needs to evaluate at most $O((κ/\varepsilon)\log(1/\varepsilon))$ stochastic gradients. In contrast, SVRG requires $O(κ/\varepsilon^2)$ stochastic gradients. To illustrate our theoretical results, S2GD only needs the workload equivalent to about 2.1 full gradient evaluations to find an $10^{-6}$-accurate solution for a problem with $n=10^9$ and $κ=10^3$.

1 Introduction

The paper frames large-scale loss minimization as a trade-off between GD’s costly full gradients and SGD’s cheaper but higher-variance updates, motivating variance-reduced methods such as S2GD.

Problem setting: Large data-science problems can be formulated as minimizing the average of many example-specific loss functions.In big-data applications, the number of examples n is typically much larger than the number of features d.
Gradient methods: GD computes a full gradient using all n component gradients, making each iteration prohibitive when n is large.The full gradient is the gradient of the average loss.
Gradient methods: SGD reduces per-iteration work by a factor of n by sampling one component gradient, but its stochastic gradients can vary substantially or point in opposite directions.SGD is therefore preferable when only low-accuracy solutions are sufficient.
Motivation: S2GD combines GD and SGD steps to retain SGD’s work-efficiency while improving stability and speed through reduced stochastic-gradient variance.The paper places S2GD among methods with linear convergence for smooth strongly convex losses.
Related work: SVRG is identified as a special case of the proposed framework, while related methods include SAG, coordinate descent, and other variance-reduction approaches.The introduction also notes prior semi-stochastic gradient descent work.

2 Semi-Stochastic Gradient Descent

The paper introduces S2GD, which combines one full gradient with a geometrically distributed number of stochastic updates per epoch; S2GD+ adds an empirically stronger but unanalyzed variant.

Algorithm overview: S2GD and S2GD+ are introduced as novel algorithms, but only S2GD is analyzed theoretically.Experiments report superior convergence properties for S2GD+.
Assumptions: S2GD assumes convex, L-smooth component losses and can additionally use strong convexity of the average loss.The strongly convex analysis assumes a strong-convexity constant µ > 0.
S2GD: S2GD uses stepsize h, an epoch cap m, and ν, a lower bound on the strong-convexity constant; it also works with ν = 0.Thus, knowledge of the strong-convexity parameter is not required for the algorithm to operate.
S2GD: Each S2GD epoch computes the full gradient at the current iterate, then performs a random number of inner stochastic-gradient steps governed by a geometric law.The inner updates use two stochastic-gradient evaluations per step and correct the full gradient with sampled component gradients.
Implementation: A memory-saving implementation can compute one stochastic gradient per inner iteration, but storing all component gradients is impractical for very large n.The standard implementation computes two stochastic gradients per step.
S2GD: The expected inner-loop length depends on ν, h, and m, with its lower and upper bounds attained at ν = 0 and νh → 1, respectively.The paper gives the expected number of inner iterations as a parameter-dependent quantity.
S2GD+: S2GD+ begins with one SGD pass and then uses fixed inner-loop lengths of n or a small multiple of n, but its complexity is not analyzed.Its motivation is that SGD can progress more in one data pass than GD can in one gradient step.

3 Summary of Results

For strongly convex losses, S2GD achieves logarithmic-accuracy complexity using logarithmically many full-gradient evaluations and O(κ) stochastic gradients per epoch. The method also provides improved convex-case complexity, optimally chosen parameters, and practical advantages over several alternatives.

Complexity for strongly convex f: S2GD requires O(log(1/ε)) full-gradient evaluations and O(κ log(1/ε)) stochastic-gradient evaluations for strongly convex losses.The condition number is κ = L/µ, and the method uses h = O(1/L), O(log(1/ε)) epochs, and m = O(κ).
Complexity for convex f: S2GD applied to a perturbed non-strongly-convex problem recovers an ε-accurate solution with arbitrarily high probability and total work ˜O(1/ε).The resulting rate is stated to be better than the standard rate of SGD.
Optimal parameters: O(log(1/ε)) epochs, h = O(1/L), and m = O(κ) approximately minimize S2GD’s total workload.Workload counts stochastic-gradient evaluations, treating one full-gradient evaluation as n stochastic-gradient evaluations.
One epoch: With one epoch, S2GD with ν = µ has a favorable workload comparison with the optimal ν = 0 case, which reduces to SVRG.The cited summary states these one-epoch results in terms of stochastic-gradient work.
Special cases: S2GD contains GD and SVRG as special cases, corresponding to m = 1 and ν = 0, respectively.The analysis is too coarse to provide a meaningful complexity result for the m = 1 GD case.
Experiments: S2GD+ performs vastly better than tested alternatives in experiments, while S2GD alone is better than GD and SGD when high accuracy is required.S2GD+ is not analyzed, and S2GD’s performance is reported as roughly comparable to SAG, with an experimental edge for S2GD.

4 Complexity Analysis: Strongly Convex Loss

The paper establishes expectation and high-probability convergence results for S2GD on strongly convex losses, using an analysis of its stochastic inner iterations and outer epochs. In the special case ν=0, the method recovers SVRG’s result, while ν=µ yields an improved contraction expression.

Proof strategy: The analysis derives an auxiliary identity for a fixed epoch and tracks expected distance to the optimum through the stochastic inner iterations.The proof conditions on the algorithm’s history and sums weighted one-step inequalities across each epoch.
Expectation convergence: Theorem 4 establishes linear convergence in expectation for S2GD under the stated parameter conditions.The theorem’s conclusion is introduced as convergence in expectation, with the contraction controlled by the derived quantity c.
Expectation convergence: S2GD is analyzed under 0 ≤ ν ≤ µ, stepsize 0 < h < 1/(2L), and a sufficiently large inner-loop limit m.The theorem’s assumptions define the admissible parameter range for the strongly convex convergence guarantee.
Relation to SVRG: ν=0 recovers the Johnson–Zhang SVRG result, while ν=µ produces a major improvement in the expression for c.The paper notes a minor improvement in SVRG’s second term and explicitly compares the ν=µ expression favorably with the ν=0 form.
High-probability convergence: High-probability guarantees follow from the expected-value result through Markov’s inequality.The paper states that this conversion is straightforward and later reuses it for the non-strongly convex case.

5 Optimal Choice of Parameters

The paper formulates parameter selection as minimizing expected workload subject to an accuracy constraint, then approximately optimizes the epoch count, stepsize, and inner-loop length. The resulting choice uses O(log(1/ε)) epochs and O(κ) stochastic-gradient work per epoch, with an illustrative workload equivalent to 2.12 full-gradient evaluations.

Optimization formulation: The parameter-tuning problem minimizes W(j,m,h)=j(n+2m) subject to c ≤ ε^(1/j).Here workload counts one full gradient as n stochastic-gradient evaluations.
Optimization formulation: For fixed j, the method approximately minimizes m subject to c ≤ ε^(1/j) by fine-tuning h.A closed-form solution is available for ν=0, but not generally for ν>µ.
Accuracy guarantee: Theorem 6 chooses parameters guaranteeing E(f(x_j)−f(x*)) ≤ ε(f(x_0)−f(x*)).The construction fixes j, defines Δ=ε^(1/j), and selects the stepsize and inner-loop length accordingly.
Workload: O(log(1/ε)) full-gradient evaluations and O(κ log(1/ε)) stochastic-gradient evaluations suffice with the recommended parameter choice.The full-gradient count is independent of κ, while the stochastic-gradient count follows from O(κ) work per epoch.
Parameter refinements: The theorem’s stepsize is slightly suboptimal, but the resulting m(j) has the correct optimal order in Δ.The paper also discusses simpler formulas for m when κ≥2 and stepsize choices that do not require a good estimate of µ.
Workload: 2.12 full-gradient-equivalent evaluations suffice for n=10^9, κ=10^3, and ε=10^-6.The workload is computed from the paper’s optimization formula using the specified m(j).

6 Complexity Analysis: Convex Loss

For convex but not strongly convex losses, the paper applies S2GD to a strongly convex perturbed problem and transfers approximate optimality back to the original problem. This yields a complexity result under the perturbation and parameter conditions stated in Theorem 8.

Perturbation strategy: The paper perturbs a convex objective by adding a quadratic term, making the modified objective µ-strongly convex and (L+µ)-smooth.S2GD is then applied to the perturbed problem rather than directly to the original objective.
Accuracy transfer: An approximate solution of the perturbed problem is also an approximate solution of the original problem through the connection established in Lemma 7.The lemma relates perturbed-objective suboptimality to the original problem’s objective and distance terms.
Complexity result: Choosing µ=ε and the parameters from Theorem 6 gives a work guarantee for the original convex problem.The resulting bound uses the condition number of the perturbed problem, stated as κ=(L+ε)/ε.

7 Numerical Experiments

The experiments compare S2GD with theoretical bounds and other optimization methods on synthetic least-squares and real logistic-regression datasets. They also demonstrate a sparse implementation using lazy updates and evaluate the tuned S2GD+ variant.

7.2 Sparse implementation: The sparse-data setting covers important models including linear and logistic regression, where each example has relatively few nonzero features.For a data point a_i, ω_i denotes the number of nonzero features, and computing a stochastic gradient costs O(ω_i).
7.2 Sparse implementation: S2GD can be implemented efficiently for sparse data by delaying dense updates and applying only the coordinates needed by the active sparse example.The lazy implementation produces the same result as S2GD while iteration cost is O(ω_i) and memory overhead is O(d).
7.3 Comparison with other methods: Experiments evaluate L2-regularized logistic regression on freely available benchmark binary-classification datasets, using data passes as the primary work-equivalent comparison.The datasets include ijcnn, rcv, realsim, and url; the regularization choice sets κ = O(n).
7.3 Comparison with other methods: Reduced-variance methods consistently outperform L-BFGS in the experiments, while S2GD is supported as faster than SAG by the authors’ computational comparison.The paper notes that SAG needs about 10-
7.3 Comparison with other methods: S2GD+ consistently improves over S2GD, but its advantage depends on choosing the SGD-initialization stepsize well.Poor parameter choices can make S2GD+ perform worse than S2GD, whereas the other three algorithms require no parameter tuning in these experiments.

8 Conclusion

The paper concludes that S2GD provides favorable complexity for smooth convex and strongly convex losses, while S2GD+ performs best empirically but remains unanalyzed. The conclusion also situates S2GD relative to existing variance-reduced methods.

8 Conclusion: O((κ/n) log(1/ε)) work suffices for the proposed methods, measured in units equivalent to one full-gradient evaluation.Here κ = L/µ for L-smooth, µ-strongly convex losses, and κ ≤ 2L/ε when the loss is merely L-smooth.
8 Conclusion: S2GD+ exhibits superior experimental performance to all tested methods, including S2GD, but its complexity is not analyzed and remains an open problem.The boosted method adds an SGD preprocessing step.
8 Conclusion: S2GD’s strongly convex complexity results match or improve on several recent results while generalizing and simplifying their analysis.The paper specifically identifies SVRG as a special case of its framework and reports better constants in its complexity results.