Faster Algorithms for Structured Linear and Kernel Support Vector Machines
math.OC, cs.LG, stat.ML
Submitted: 2023-07-15
Updated: 2026-11-16
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
License: http://creativecommons.org/licenses/by-nc-sa/4.0/
The gist: Many machine learning problems are quadratic programs, including Support Vector Machines (SVMs).
Terminology
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 poly(n), and some feasible point has all entries between 1/poly(n) and poly(n). For linear SVM on d-dimensional data, our randomized algorithm runs in expected time O(nd(ω+1)/2 (n/ε)) when (d+1) ω-1 at most n and the data points have norms at most poly(n) and margin at least 1/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(n), the squared dataset radius is o(n/ n) and the dual variables lie in a box [0,R] n with R at most poly(n), our randomized algorithm runs in expected time n 1+o(1) for any accuracy ε at least 1/poly(n). We also prove that, assuming SETH, when the squared dataset radius is Ω(squared n), Ω(n 2-o(1)) time is required on some inputs to reach error (-Θ(squared 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.
Sources
Related papers
- An Accelerated Proximal Gradient Method for Bures-Wasserstein Space
- FOMTools: Development and AI-Assisted Code Generation for First-Order Methods
- Lions and Muons: Optimization via Stochastic Frank-Wolfe under Heavy-Tailed Noise
- Dynamic Service Recommendation with Congestion-Dependent Joining: Near-Optimal and Constant-Factor Approximation Algorithms
- Integrating Learning and Optimization for Open Transport Capacity Pooling under Disruption
- Zeroth-Order Gradient Estimators under Decision-Dependent Noise