Source-linked AI summary
Mini-Batch Primal and Dual Methods for SVMs
Martin Takáč, Avleen Bijral, Peter Richtárik, Nathan Srebro
TL;DR
Mini-batching stochastic SVM optimization is studied as a way to overcome the sequential nature of single-example updates and obtain parallelization speedups. The paper analyzes mini-batched Pegasos and SDCA, showing that the data spectral norm controls speedups and using this analysis to develop SDCA variants with guarantees for the original nonsmooth primal objective. These results come with practical sensitivity to spectral-norm-based step-size choices.
Problem
Single-example stochastic SVM updates are inherently sequential, creating a need to determine whether mini-batches can reduce iterations and provide parallelization speedups.
Method
The paper analyzes mini-batched Pegasos and SDCA using the data spectral norm, and develops safe and adaptive SDCA variants.
Results
The data spectral norm controls speedups for both methods, while mini-batched Pegasos and safe mini-batched SDCA receive guarantees tied to the original nonsmooth primal SVM objective.
Takeaways & Limitations
Effective mini-batching is possible for nonsmooth SVM objectives, but SDCA requires modified variants to achieve speedups comparable to Pegasos.
Takeaways & Limitations
Safe mini-batched SDCA requires a spectral-norm-based step-size; overly large steps may prevent convergence, while overly conservative settings reduce speedups.
Abstract
from arXiv · showhide
We address the issue of using mini-batches in stochastic optimization of SVMs. We show that the same quantity, the spectral norm of the data, controls the parallelization speedup obtained for both primal stochastic subgradient descent (SGD) and stochastic dual coordinate ascent (SCDA) methods and use it to derive novel variants of mini-batched SDCA. Our guarantees for both methods are expressed in terms of the original nonsmooth primal problem based on the hinge-loss.
1. Introduction
Mini-batching is proposed to address the sequential bottleneck of stochastic SVM optimization by reducing iterations and enabling parallelization. The paper analyzes mini-batched Pegasos and SDCA, identifying the data spectral norm as the shared speedup-controlling quantity and introducing safer and more aggressive SDCA variants.
- 1. Introduction: Mini-batches process several training points per iteration, potentially reducing required iterations and enabling parallelization speedups.Sequential stochastic methods update the predictor after each point, limiting parallel and distributed computation.
- 1. Introduction: The data spectral norm controls mini-batching and parallelization speedups for both Pegasos and SDCA.The paper studies Pegasos as primal SGD and SDCA as a dual coordinate method.
- 1. Introduction: The paper provides the first analysis showing provable parallelization speedups for mini-batched Pegasos on the original nonsmooth SVM objective.The refined analysis depends on the spectral norm rather than only a radius bound.
- 1. Introduction: Naive mini-batched SDCA can fail for large batches, motivating a safe spectral-norm-dependent variant with primal-suboptimality guarantees.The analysis establishes a duality-gap guarantee and therefore a guarantee for the primal SVM objective.
- 1. Introduction: An aggressive adaptive mini-batched SDCA method is derived from the safe analysis and often outperforms the safe variant in practice.Prior mini-batch coordinate-descent analyses did not directly provide guarantees on the primal suboptimality of the SVM objective.
- 1. Introduction: The results apply to any Lipschitz continuous loss function, although the presentation focuses on hinge loss.The hinge-loss setting matches the SVM objective considered in the paper.
2. Support Vector Machines
The paper formulates linear SVM training through a regularized primal objective and its dual, linking dual solutions to primal predictors. It assumes normalized examples and defines mini-batches as uniformly sampled subsets of fixed size.
- 2. Support Vector Machines: Training a linear SVM seeks a low-norm predictor with small average hinge loss on labeled examples.The examples are normalized so their maximum Euclidean norm is at most 1.
- 2. Support Vector Machines: The hinge loss is ℓ(z) = [1 − z]+ = max{0, 1 − z}.The formulation combines hinge loss with a regularization trade-off parameter λ > 0.
- 2. Support Vector Machines: Because Pegasos and SDCA can be kernelized, the methods and results also apply with kernels, although the presentation focuses on explicit feature maps.The stated focus is the setting where the feature map is given explicitly.
- 2. Support Vector Machines: The paper considers both the primal SVM problem and its dual, with dual optima determining primal predictors.A dual solution α is naturally associated with a linear predictor through the labeled training examples.
- 2. Support Vector Machines: A mini-batch of size b is a uniformly random subset of b training examples.The paper uses restricted matrices and vectors for the selected examples and aggregates their average hinge loss.
3. Mini-Batches in Primal Stochastic Gradient Descent Methods
Mini-batched Pegasos estimates subgradients from sampled subsets, with expected subgradient norms controlled by the data’s spectral norm. The resulting guarantee predicts speedups for favorable data geometry but no benefit in degenerate cases.
- Mini-batched Pegasos: Pegasos with mini-batches updates the iterate using a subgradient of a partial objective formed from a random batch.The batch is sampled uniformly, and the subgradient uses margin-violation indicators for the examples in that batch.
- Spectral-norm analysis: The analysis bounds the expected squared norm of the mini-batch subgradient in terms of the spectral norm of the data.The bound introduces β_b, which is also used in the SDCA analysis.
- Parallelization speedup: For b = 1, β_b = 1 and the guarantee agrees with the standard serial Pegasos analysis.For larger batches, the guarantee depends on β_b and therefore on the spectral norm σ^2.
- Parallelization speedup: When all data points lie on one line, σ^2 = 1 and β_b = b, so larger mini-batches provide no speedup.The same number of iterations is required, producing the same parallel runtime and b times the serial runtime.
- Parallelization speedup: When σ^2 < 1, β_b < 1 can yield a parallelization speedup from mini-batching.If b is at most 1/σ^2, then β_b ≤ 2 and the speedup is essentially linear.
4. Mini-Batches in Dual Stochastic Coordinate Ascent Methods
The section develops mini-batched SDCA, showing that naive parallel updates can fail because coordinate interactions are ignored, while a spectral-norm-based safe variant recovers parallelization speedups and an aggressive variant adapts the step size.
- SDCA background: SDCA updates one randomly selected dual coordinate at a time, preserving box constraints while maximizing the dual objective for that coordinate.Unlike Pegasos, SDCA chooses each coordinate update optimally rather than using a predetermined step size.
- 4.1. Naive Mini-Batching: Naive mini-batched SDCA can increase iteration counts or fail to converge because independently optimal coordinate updates may overshoot when coordinates interact.The problem is especially severe for identical or highly correlated examples, whose updates can suggest essentially the same change to the weight vector.
- 4.2. Safe Mini-Batching: The safe variant replaces the coupled quadratic term with a separable surrogate using β=β_b, reducing step sizes according to potential interactions among parallel coordinates.The surrogate enables parallel coordinate ascent while maintaining an approximate expected lower bound on the dual objective.
- 4.2. Safe Mini-Batching: Safe mini-batched SDCA achieves a speedup of b/β_b, which is essentially linear when b≤1/σ².The fixed-cost term is always reduced by b, while β_b affects only the ϵ-dependent term.
- 4.3. Aggressive Mini-Batching: The aggressive variant adapts β using observed update geometry, aiming for larger steps than the conservative spectral-norm bound permits.It estimates an appropriate step size from the ratio involving the tentative update and uses a weighted geometric average for adaptation.
5. Experiments
Experiments compare Pegasos with naive, safe, and aggressive mini-batched SDCA on four benchmark datasets, showing nearly linear speedups at small batch sizes and distinct behavior at larger sizes.
- Small batches: For small batch sizes, both Pegasos and SDCA exhibit nearly linear parallelization speedups, while SDCA outperforms Pegasos at b=1.The comparison includes naive, safe, and aggressive SDCA variants.
- Large batches: Beyond b≈1/σ², safe SDCA shows little additional speedup but avoids the deterioration observed with naive SDCA.This regime corresponds to significant correlations within mini-batches.
- Large batches: Pegasos and aggressive SDCA continue improving beyond b≈1/σ², with aggressive SDCA maintaining roughly the same empirical speedups as Pegasos for large batches.The aggressive variant continues improving even after naive SDCA fails.
- Convergence behavior: Figure 2 shows naive SDCA causing objective deterioration and failing to converge to the optimum on two datasets after the mini-batch becomes sufficiently large.The figure illustrates the qualitative failure mode predicted by the analysis.
6. Conclusion
The paper identifies the data spectral norm, through β_b, as the quantity governing mini-batch speedups for Pegasos and SDCA. It introduces mini-batched SDCA variants and relates their guarantees to the primal SVM objective.
- The data spectral norm, through β_b, controls parallelization guarantees for mini-batched Pegasos and SDCA.
- The paper gives the first nonsmooth hinge-loss analysis of mini-batched Pegasos that establishes speedups.
- Novel mini-batched SDCA variants are necessary to achieve speedups comparable to Pegasos.
- Safe mini-batched SDCA is analyzed in terms of the primal SVM objective, making it a primal-dual method.
- All results extend from hinge loss to Lipschitz continuous loss functions, with analogous speedups described for population objectives.
- Effective mini-batched SDCA requires spectral-norm-dependent step-size selection, while too-small or too-large β settings can respectively prevent convergence or reduce speedups.
- The analysis concerns iteration complexity and iterate behavior; practical architectural speedups additionally require efficient parallel or distributed implementations.
A. Proof of Theorem 2
The proof extends the SDCA analysis to general individually Lipschitz losses by using a separable approximation, Fenchel conjugates, and a lemma bounding expected dual improvement. It then bounds dual sub-optimality through an inductive recurrence and averaging argument.
- The proof treats general L-Lipschitz, example-specific loss functions and expresses equivalent primal and dual problems.
- For hinge loss, the Fenchel conjugate encodes the dual box constraints, while w(α) links dual variables to the primal iterate.
- The separable approximation H(δ, α) is generalized, and the properties used in Section 4, including Lemma 3, remain valid.
- Lemma 4 bounds expected improvement in the dual objective after one iteration in terms of the duality gap.
- Optimality of δ(t) supplies an upper bound through H−D, while Lipschitzness bounds the relevant subgradients.
- The proof bounds the change in dual sub-optimality and unrolls the resulting recurrence.
- An induction establishes the recurrence, and averaging conditions are then chosen to make the bound at most ε.