# Mini-Batch Primal and Dual Methods for SVMs

arXiv: https://arxiv.org/abs/1303.2314 · HTML: https://mlsanity.com/paper/1303.2314/

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Mar 2013.

## Built on by (most cited first, 12 of 12)

- [Variance Reduced ProxSkip: Algorithm, Theory and Application to Federated Learning](https://mlsanity.com/paper/2207.04338/) (2022)
- [Distributed Second Order Methods with Fast Rates and Compressed Communication](https://mlsanity.com/paper/2102.07158/) (2021)
- [FRUGAL: Memory-Efficient Optimization by Reducing State Overhead for Scalable Training](https://mlsanity.com/paper/2411.07837/) (2024)
- [Remove that Square Root: A New Efficient Scale-Invariant Version of AdaGrad](https://mlsanity.com/paper/2403.02648/) (2024)
- [Muon with Nesterov Momentum: Heavy-Tailed Noise and (Randomized) Inexact Polar Decomposition](https://mlsanity.com/paper/2605.06884/) (2026)
- [Random-reshuffled SARAH does not need a full gradient computations](https://mlsanity.com/paper/2111.13322/) (2021)
- [Towards a Better Theoretical Understanding of Independent Subnetwork Training](https://mlsanity.com/paper/2306.16484/) (2023)
- [Continuous Concepts Removal in Text-to-image Diffusion Models](https://mlsanity.com/paper/2412.00580/) (2024)
- [Revisiting LocalSGD and SCAFFOLD: Improved Rates and Missing Analysis](https://mlsanity.com/paper/2501.04443/) (2025)
- [Gradient Clipping Beyond Vector Norms: A Spectral Approach for Matrix-Valued Parameters](https://mlsanity.com/paper/2605.11838/) (2026)
- [Adjusted Shuffling SARAH: Advancing Complexity Analysis via Dynamic Gradient Weighting](https://mlsanity.com/paper/2506.12444/) (2025)
- [Why Clipping Matters in AdaGrad? Toward a High-Probability Theory under Generalized Smoothness](https://mlsanity.com/paper/2609.30276/) (2026)

## Abstract (arXiv)

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.