Paperlane

no. 16 · Tuesday 17 November 2026

Faster Algorithms for Structured Linear and Kernel Support Vector Machines

Yuzhou Gu, Zhao Song and Lichen Zhang

math.OC · v4

Abstract

Many machine learning problems are quadratic programs, including Support Vector Machines (SVMs). A general quadratic program has input size $Θ(n^2)$, and assuming the Strong Exponential Time Hypothesis (SETH), no $O(n^{2-o(1)})$ time algorithm exists when the objective matrix is positive semidefinite (Backurs, Indyk, and Schmidt, NeurIPS'17). SVMs, however, are given by $n$ data points of dimension $d$, often much smaller than $n$, and have only $O(1)$ equality constraints. In this work, we design the first nearly-linear time algorithm for solving quadratic programs whenever a low-rank factorization of the quadratic objective matrix is given, the number of linear constraints is small, the coefficients of the objective and some optimal solution are bounded by $\mathrm{poly}(n)$, and some feasible point has all entries between $1/\mathrm{poly}(n)$ and $\mathrm{poly}(n)$. For linear SVM on $d$-dimensional data, our randomized algorithm runs in expected time $\widetilde O(nd^{(ω+1)/2}\log(n/ε))$ when $(d+1)^{ω-1}\le n$ and the data points have norms at most $\mathrm{poly}(n)$ and margin at least $1/\mathrm{poly}(n)$, where $ω<2.258$ is the matrix multiplication exponent. Its output satisfies the equality constraint only approximately. For Gaussian kernel SVM, when $d=O(\log n)$, the squared dataset radius is $o(\log n/\log\log n)$ and the dual variables lie in a box $[0,R]^n$ with $R\le\mathrm{poly}(n)$, our randomized algorithm runs in expected time $n^{1+o(1)}$ for any accuracy $ε\ge 1/\mathrm{poly}(n)$. We also prove that, assuming SETH, when the squared dataset radius is $Ω(\log^2 n)$, $Ω(n^{2-o(1)})$ time is required on some inputs to reach error $\exp(-Θ(\log^2 n))$ for the program without the bias term. This improves upon the prior best lower bound in both the dimension $d$ and the squared dataset radius.

comments
ICLR 2025. This version corrects the Gaussian kernel result, which needs accuracy at least $1/\mathrm{poly}(n)$, and the comparison with the lower bound of Backurs, Indyk and Schmidt. Abstract shortened to meet arxiv requirement
fields
Optimization and Control
pdf ↗ page arXiv:2307.07735 ↗