Source-linked AI summary
Variance-Reduced and Projection-Free Stochastic Optimization
Elad Hazan, Haipeng Luo
TL;DR
Stochastic Frank-Wolfe optimization remains less studied than projected-gradient methods despite its advantages for structured constraints and large datasets. The paper introduces two variance-reduced Frank-Wolfe variants, reports substantially improved stochastic-gradient complexity, and observes theoretical improvements in multiclass-classification experiments.
Problem
Stochastic Frank-Wolfe methods are relatively understudied compared with projected-gradient variants, despite projection-free optimization being useful for large-scale objectives with structured constraints.
Method
The paper combines variance reduction with stochastic Frank-Wolfe, including a mini-batch method with periodic snapshots and a variance-reduced SCGS-based method.
Results
The proposed algorithms substantially reduce stochastic-gradient evaluations for 1-ε accuracy while retaining the number of linear optimizations used by previous work.
Takeaways & Limitations
Variance reduction can substantially speed up projection-free algorithms, with improvements also observed on three large real-world multiclass-classification datasets.
Takeaways & Limitations
The paper leaves open whether STORC's strongly convex stochastic-gradient complexity and its number of linear optimizations can be further improved.
Abstract
from arXiv · showhide
The Frank-Wolfe optimization algorithm has recently regained popularity for machine learning applications due to its projection-free property and its ability to handle structured constraints. However, in the stochastic learning setting, it is still relatively understudied compared to the gradient descent counterpart. In this work, leveraging a recent variance reduction technique, we propose two stochastic Frank-Wolfe variants which substantially improve previous results in terms of the number of stochastic gradient evaluations needed to achieve $1-ε$ accuracy. For example, we improve from $O(\frac{1}ε)$ to $O(\ln\frac{1}ε)$ if the objective function is smooth and strongly convex, and from $O(\frac{1}{ε^2})$ to $O(\frac{1}{ε^{1.5}})$ if the objective function is smooth and Lipschitz. The theoretical improvement is also observed in experiments on real-world datasets for a multiclass classification application.
1. Introduction
The paper studies stochastic optimization with projection-free algorithms for large-scale machine-learning objectives over domains where linear optimization is faster than projection. It proposes variance-reduced Frank-Wolfe methods that improve stochastic-gradient complexity while preserving the number of linear optimizations used by prior work.
- Motivation: Large training sets make stochastic optimization attractive, while structured domains can make linear optimization much faster than projection.The paper highlights multiclass classification, multitask learning, recommendation systems, and matrix learning as examples.
- Motivation: Frank-Wolfe is suitable because it is projection-free and handles structured constraints, but its stochastic-learning efficiency remains relatively understudied.The comparison is specifically with projected-gradient-descent variants.
- Contribution: The paper proposes two variance-reduced stochastic Frank-Wolfe algorithms to improve stochastic-gradient evaluations needed for 1-ε accuracy.The stated goal measures both stochastic-gradient evaluations and linear optimizations.
- Contribution: The proposed methods keep the number of linear optimizations unchanged relative to previous work while reducing stochastic-gradient complexity.The detailed comparisons are presented in Table 1 and Table 2.
- Contribution: The algorithms require at most O(ln 1/ε) extra exact-gradient computations, described as computationally insignificant compared with other operations.The paper presents this overhead as more affordable than computing exact gradients at every non-stochastic Frank-Wolfe iteration.
- Experiments: Experiments on three large real-world datasets for multiclass classification show significant improvement over prior projection-free and projected stochastic-gradient methods.The comparison includes projected stochastic gradient descent and its variance-reduced version.
2. Preliminary and Related Work
This section defines the smooth stochastic optimization setting, illustrates it with multiclass classification, and reviews projection-free and variance-reduced Frank-Wolfe methods. It motivates the proposed variants by comparing their stochastic-gradient and linear-optimization costs with prior approaches.
- Optimization setting: The framework assumes convex smooth component functions over a compact convex domain where linear optimization is faster than projection.The domain has diameter D, and some settings additionally assume Lipschitz components or strong convexity of the objective.
- Example application: Multiclass logistic regression uses a trace-norm-constrained matrix, making linear optimization substantially cheaper than projection by avoiding a full singular-value decomposition.Projection requires an SVD, whereas linear optimization uses a top singular vector computation.
- Stochastic Frank-Wolfe: Stochastic Frank-Wolfe replaces exact gradients with uniformly sampled component gradients and measures efficiency by exact-gradient, stochastic-gradient, and linear-optimization counts.The target is an expected objective gap of at most ε.
- Variance reduction: Variance reduction combines current and snapshot stochastic gradients with a precomputed snapshot gradient, preserving unbiasedness while reducing variance.The variance bound depends on the current point’s and snapshot’s distances from the optimum.
3. Stochastic Variance-Reduced Frank-Wolfe
SVRF replaces exact gradients in Frank-Wolfe with mini-batches of variance-reduced stochastic gradients and periodic full-gradient snapshots. Its convergence analysis yields logarithmic linear-optimization complexity for 1−ε accuracy while controlling stochastic-gradient cost through geometrically increasing inner-loop lengths.
- Algorithm: SVRF uses mini-batches of variance-reduced stochastic gradients and periodic snapshots of the exact gradient.The algorithm averages iid variance-reduced stochastic gradients within inner iterations and resets from a snapshot point.
- Convergence: SVRF sets γ_k=2/(k+1), m_k=96(k+1), and N_t=2^(t+3)−2.These parameters are given in Theorem 1 for the convergence guarantee.
- Complexity: O(ln(LD^2/ε)) linear optimizations are sufficient for Algorithm 1 to achieve 1−ε accuracy.The proof derives T=Θ(log_2(1/ε)) and geometrically increasing inner-loop lengths.
- Convergence: The analysis proves the required gradient-estimation error bound by induction across inner iterations and outer snapshot stages.The proof uses mini-batch variance reduction to establish Lemma 2’s condition and then completes the convergence induction.
4. Stochastic Variance-Reduced Conditional Gradient Sliding
STORC applies variance reduction to conditional gradient sliding, combining snapshot-based stochastic gradients with Nesterov-style auxiliary sequences and approximate regularized subproblem solves. Its analysis establishes convergence across three cases while retaining logarithmic linear-optimization complexity.
- Algorithm: STORC replaces stochastic gradients in SCGS with mini-batches of variance-reduced gradients and periodic snapshots.The method is presented as a variance-reduced version of stochastic conditional gradient sliding.
- Algorithm: The algorithm uses auxiliary sequences x_k and z_k, with x_k obtained by approximately solving a square-norm-regularized linear optimization.The approximate solve is performed with standard Frank-Wolfe until a prescribed duality gap is reached.
- Analysis: STORC computes stochastic gradients at z_k rather than y_k, requiring the analysis to establish convergence of the auxiliary sequence z_k.The paper identifies this auxiliary-sequence convergence as a key analytical step.
- Complexity: O(ln(LD^2/ε)) linear optimizations are required for Algorithm 2 to achieve 1−ε accuracy.The corresponding stochastic-gradient evaluation counts are stated separately for Cases (a), (b), and (c).
- Analysis: The convergence proof treats three cases separately and uses induction to bound the expected objective gap across inner iterations.The cases correspond to different smoothness, Lipschitz, and strong-convexity conditions.
5. Experiments
The experiments evaluate six algorithms on three large LIBSVM multiclass-classification datasets using actual running time and loss decrease. Projection-free methods and variance-reduced variants show empirical advantages, although simpler SFW and SVRF outperform STORC in these experiments.
- Setup: The study evaluates six algorithms on three relatively large multiclass-classification datasets from LIBSVM.The comparison includes SFW, SCGS, SVRF, STORC, projected SGD, and SVRG.
- Setup: The experiments compare actual running time against loss decrease because gradient, linear-optimization, and projection costs differ substantially.The evaluation focuses on how quickly the loss decreases rather than only final test error.
- Results: SGD and SVRG are significantly slower than the other methods because their projection steps are expensive.This result supports the practical relevance of projection-free optimization in the tested setting.
- Results: Variance reduction produces large empirical improvements, especially for SCGS versus STORC and SFW versus SVRF on the aloi dataset.The reported comparison highlights gains from adding variance reduction to projection-free methods.
- Results: Although STORC has the best theoretical results, SFW and SVRF consistently perform better empirically in these experiments.The empirical ranking therefore differs from the theoretical ranking for the tested datasets and settings.
6. Omitted Proofs
The omitted proofs establish stochastic-gradient variance bounds and use smoothness, convexity, and Frank-Wolfe updates to derive recursive objective-gap bounds. These arguments complete the convergence analysis for the stochastic variance-reduced methods.
- Lemma 1: The proof of Lemma 1 bounds stochastic-gradient differences using smoothness, unbiasedness, variance control, and optimality of w*.The argument reduces individual terms to objective gaps through a smoothness inequality.
- Lemma 2: The proof of Lemma 2 applies smoothness to the Frank-Wolfe convex-combination update and bounds the step diameter by D.Convexity controls the optimality term, while Cauchy-Schwarz bounds the gradient-estimation error.
- Lemma 2: The resulting recursion controls E[f(x_s)−f(w*)] using the prescribed gradient-estimation error condition.The induction closes after substituting the variance bound and applying Jensen’s inequality.
7. Conclusion and Open Problems
Variance reduction is useful for speeding up projection-free algorithms, but the strongly convex stochastic-gradient complexity of STORC remains open for improvement.
- Variance reduction can substantially speed up projection-free algorithms.
- The strongly convex stochastic-gradient complexity of STORC remains an open question.
- Improving the number of linear optimizations in the strongly convex case is also identified as an open question.
A. Proof of Property (1)
The proof introduces an auxiliary function by subtracting a linearization at v, making v a minimizer and enabling the desired inequality after rearrangement.
- The proof defines g(w) = f(w) − ∇f(v)ᵀw, which remains convex and L-smooth on Ω.
- Because ∇g(v) = 0, the point v is one of the minimizers of g.
- Rearranging the resulting inequality and substituting the definition of g completes the proof.
B. Analysis for SFW
The SFW analysis specifies its stochastic-gradient estimator and convergence parameters, then derives an O(LD²/ε³) stochastic-gradient requirement for 1−ε accuracy.
- Algorithm and estimator: SFW uses ˜∇k, the average of mk independent stochastic gradients evaluated at wk−1.
- Convergence parameters: Theorem 3 assumes each fi is G-Lipschitz and sets γk = 2/(k+1) together with a specified mk.
- Convergence analysis: With these parameter choices, the analysis establishes a convergence bound for SFW at each iteration k.
- Proof strategy: The proof uses convexity, Cauchy–Schwarz, Jensen’s inequality, and induction to derive the bound.
- Complexity: O(LD²/ε³) stochastic gradients are sufficient for SFW to achieve 1−ε accuracy.
C. Proof of Lemma 3
The proof of Lemma 3 tracks variance-reduced gradient errors through a recursive inequality, defines a product sequence Γs, and substitutes the algorithm parameters to obtain the final bound.
- The proof defines δs = ˜∇s − ∇f(zs) to represent the stochastic-gradient error.
- A recursive inequality combines function values, linearization terms, and the error contribution at iteration s.
- The sequence Γs is defined recursively and verified by induction as Γs = 2/[s(s+1)].
- Substituting γs, βs, ηt,s, Γs, and the distance bound E[∥x0 − w*∥²] ≤ D² yields the final estimate.