# Scaling SVM and Least Absolute Deviations via Exact Data Reduction

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

## Key facts

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

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

- [Recasting Self-Attention with Holographic Reduced Representations](https://mlsanity.com/paper/2305.19534/) (2023)
- [Expanding boundaries of Gap Safe screening](https://mlsanity.com/paper/2102.10846/) (2021)
- [Generalized Low-Rank Update: Model Parameter Bounds for Low-Rank Training Data Modifications](https://mlsanity.com/paper/2306.12670/) (2023)
- [Low-Rank Multitask Learning based on Tensorized SVMs and LSSVMs](https://mlsanity.com/paper/2308.16056/) (2023)
- [A Safe Screening Rule with Bi-level Optimization of nu Support Vector Machine](https://mlsanity.com/paper/2403.01769/) (2024)
- [Guarded Block Transfers for Polytope Distance: Linear Convergence with Explicit Constants and Gap-Certified Screening for SVM Training](https://mlsanity.com/paper/2610.15829/) (2026)

## Abstract (arXiv)

The support vector machine (SVM) is a widely used method for classification. Although many efforts have been devoted to develop efficient solvers, it remains challenging to apply SVM to large-scale problems. A nice property of SVM is that the non-support vectors have no effect on the resulting classifier. Motivated by this observation, we present fast and efficient screening rules to discard non-support vectors by analyzing the dual problem of SVM via variational inequalities (DVI). As a result, the number of data instances to be entered into the optimization can be substantially reduced. Some appealing features of our screening method are: (1) DVI is safe in the sense that the vectors discarded by DVI are guaranteed to be non-support vectors; (2) the data set needs to be scanned only once to run the screening, whose computational cost is negligible compared to that of solving the SVM problem; (3) DVI is independent of the solvers and can be integrated with any existing efficient solvers. We also show that the DVI technique can be extended to detect non-support vectors in the least absolute deviations regression (LAD). To the best of our knowledge, there are currently no screening methods for LAD. We have evaluated DVI on both synthetic and real data sets. Experiments indicate that DVI significantly outperforms the existing state-of-the-art screening rules for SVM, and is very effective in discarding non-support vectors for LAD. The speedup gained by DVI rules can be up to two orders of magnitude.