# A Preconditioned Interior Point Method for Support Vector Machines Using an ANOVA-Decomposition and NFFT-Based Matrix-Vector Products

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 44 references that are in the map.
- First posted on arXiv 1 Dec 2023.

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

- [Faster Kernel Ridge Regression Using Sketching and Preconditioning](https://mlsanity.com/paper/1611.03220/) (2016)
- [Preconditioning Kernel Matrices](https://mlsanity.com/paper/1602.06693/) (2016)
- [Randomly pivoted Cholesky: Practical approximation of a kernel matrix with few entry evaluations](https://mlsanity.com/paper/2207.06503/) (2022)
- [ASKIT: Approximate Skeletonization Kernel-Independent Treecode in High Dimensions](https://mlsanity.com/paper/1410.0260/) (2014)
- [NFFT meets Krylov methods: Fast matrix-vector products for the graph Laplacian of fully connected networks](https://mlsanity.com/paper/1808.04580/) (2018)
- [Learning in High-Dimensional Feature Spaces Using ANOVA-Based Fast Matrix-Vector Multiplication](https://mlsanity.com/paper/2111.10140/) (2021)
- [A literature survey of matrix methods for data science](https://mlsanity.com/paper/1912.07896/) (2019)

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

- [Fast Evaluation of Additive Kernels: Feature Arrangement, Fourier Methods, and Kernel Derivatives](https://mlsanity.com/paper/2404.17344/) (2024)
- [Fast and interpretable Support Vector Classification based on the truncated ANOVA decomposition](https://mlsanity.com/paper/2402.02438/) (2024)
- [Preconditioned Additive Gaussian Processes with Fourier Acceleration](https://mlsanity.com/paper/2504.00480/) (2025)

## Abstract (arXiv)

In this paper we consider the numerical solution to the soft-margin support vector machine optimization problem. This problem is typically solved using the SMO algorithm, given the high computational complexity of traditional optimization algorithms when dealing with large-scale kernel matrices. In this work, we propose employing an NFFT-accelerated matrix-vector product using an ANOVA decomposition for the feature space that is used within an interior point method for the overall optimization problem. As this method requires the solution of a linear system of saddle point form we suggest a preconditioning approach that is based on low-rank approximations of the kernel matrix together with a Krylov subspace solver. We compare the accuracy of the ANOVA-based kernel with the default LIBSVM implementation. We investigate the performance of the different preconditioners as well as the accuracy of the ANOVA kernel on several large-scale datasets.