# Training very large scale nonlinear SVMs using Alternating Direction Method of Multipliers coupled with the Hierarchically Semi-Separable kernel approximations

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 50 references that are in the map.
- First posted on arXiv 9 Aug 2021.

## Builds on (most cited first, 9 of 9)

- [Less is More: Nystr"om Computational Regularization](https://mlsanity.com/paper/1507.04717/) (2015)
- [Revisiting the Nystrom Method for Improved Large-Scale Machine Learning](https://mlsanity.com/paper/1303.1849/) (2013)
- [Faster Kernel Ridge Regression Using Sketching and Preconditioning](https://mlsanity.com/paper/1611.03220/) (2016)
- [ASKIT: Approximate Skeletonization Kernel-Independent Treecode in High Dimensions](https://mlsanity.com/paper/1410.0260/) (2014)
- [A Study of Clustering Techniques and Hierarchical Matrix Formats for Kernel Ridge Regression](https://mlsanity.com/paper/1803.10274/) (2018)
- [Accurate, Fast and Scalable Kernel Ridge Regression on Parallel and Distributed Systems](https://mlsanity.com/paper/1805.00569/) (2018)
- [Managing Randomization in the Multi-Block Alternating Direction Method of Multipliers for Quadratic Optimization](https://mlsanity.com/paper/1903.01786/) (2019)
- [A Hardware-Efficient ADMM-Based SVM Training Algorithm for Edge Computing](https://mlsanity.com/paper/1907.09916/) (2019)
- [Random multi-block ADMM: an ALM based view for the QP case](https://mlsanity.com/paper/2012.09230/) (2020)

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

- [A Robust Twin Parametric Margin Support Vector Machine for Multiclass Classification](https://mlsanity.com/paper/2306.06213/) (2023)

## Abstract (arXiv)

Typically, nonlinear Support Vector Machines (SVMs) produce significantly higher classification quality when compared to linear ones but, at the same time, their computational complexity is prohibitive for large-scale datasets: this drawback is essentially related to the necessity to store and manipulate large, dense and unstructured kernel matrices. Despite the fact that at the core of training a SVM there is a textitsimple convex optimization problem, the presence of kernel matrices is responsible for dramatic performance reduction, making SVMs unworkably slow for large problems. Aiming to an efficient solution of large-scale nonlinear SVM problems, we propose the use of the textitAlternating Direction Method of Multipliers coupled with textitHierarchically Semi-Separable (HSS) kernel approximations. As shown in this work, the detailed analysis of the interaction among their algorithmic components unveils a particularly efficient framework and indeed, the presented experimental results demonstrate a significant speed-up when compared to the textitstate-of-the-art nonlinear SVM libraries (without significantly affecting the classification accuracy).