math.OCJul 15, 2023

Faster Algorithms for Structured Linear and Kernel Support Vector Machines

Authors: Yuzhou Gu, Zhao Song, Lichen Zhang

Organizations: New York University · Simons Institute for the Theory of Computing, UC Berkeley · Massachusetts Institute of Technology

Abstract

Many machine learning problems are quadratic programs, including Support Vector Machines (SVMs). A general quadratic program has input size Θ(n2)Θ(n^2), and assuming the Strong Exponential Time Hypothesis (SETH), no O(n2−o(1))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 nn data points of dimension dd, often much smaller than nn, and have only O(1)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)\mathrm{poly}(n), and some feasible point has all entries between 1/poly(n)1/\mathrm{poly}(n) and poly(n)\mathrm{poly}(n). For linear SVM on dd-dimensional data, our randomized algorithm runs in expected time O~(nd(ω+1)/2log⁡(n/ε))\widetilde O(nd^{(ω+1)/2}\log(n/ε)) when (d+1)ω−1≤n(d+1)^{ω-1}\le n and the data points have norms at most poly(n)\mathrm{poly}(n) and margin at least 1/poly(n)1/\mathrm{poly}(n), where ω<2.258ω<2.258 is the matrix multiplication exponent. Its output satisfies the equality constraint only approximately. For Gaussian kernel SVM, when d=O(log⁡n)d=O(\log n), the squared dataset radius is o(log⁡n/log⁡log⁡n)o(\log n/\log\log n) and the dual variables lie in a box [0,R]n[0,R]^n with R≤poly(n)R\le\mathrm{poly}(n), our randomized algorithm runs in expected time n1+o(1)n^{1+o(1)} for any accuracy ε≥1/poly(n)ε\ge 1/\mathrm{poly}(n). We also prove that, assuming SETH, when the squared dataset radius is Ω(log⁡2n)Ω(\log^2 n), Ω(n2−o(1))Ω(n^{2-o(1)}) time is required on some inputs to reach error exp⁡(−Θ(log⁡2n))\exp(-Θ(\log^2 n)) for the program without the bias term. This improves upon the prior best lower bound in both the dimension dd and the squared dataset radius.

Figures & tables

Explore similar work

Feb 23, 2026

Exploiting Low-Rank Objective Structure in Discrete Quadratic Optimization

We study the problem of maximizing a complex-valued quadratic form over the KthK^{\text{th}} roots of unity. We show that when the objective matrix Q⋆∈Cn×n\mathbf{Q}^\star \in \mathbb{C}^{n \times n} of the quadratic has rank rr, the global maximizer belongs to a candidate set of size O(rn2r−1)O(rn^{2r-1}). This set can be constructed deterministically in O(rn2r+1)O(rn^{2r+1}) time by enumerating the vertices of a hyperplane arrangement in R2r.\mathbb{R}^{2r}. The algorithm is embarrassingly parallel; with~PP processors, the time complexity drops to O(rn2r+1/P)O(r n^{2r+1}/P). For approximately low-rank settings, where the objective matrix is a noise-perturbed variant of a rank-rr matrix, we prove that applying our framework to a spectral truncation yields a multiplicative (1−O(∥H∥2/δ⋆))(1 - O(\left\|\mathbf{H}\right\|_2 / δ^{\star}))-approximation guarantee, where δ⋆δ^{\star} denotes the eigengap of the underlying rank-rr matrix and H\mathbf{H} represents the perturbation. To scale to high-dimensional problems, we establish a randomized sampling variant. We prove that uniformly sampling S≥O(1/εr−1)S \geq O(1/\varepsilon^{r-1}) candidates achieves a (1−ε)cos⁡2(π/K)(1-\varepsilon)\cos^2(π/ K)-approximation of the optimal rank-rr solution with high probability. Crucially, this sample size is entirely independent of nn, reducing the overall runtime to O(S⋅n2)O(S \cdot n^2). Computational experiments on synthetic benchmarks and large-scale graphs for Max-3-Cut confirm that our algorithms match or exceed semi-definite programming solution quality on structured instances while enabling massive parallelization across heterogeneous hardware and scaling seamlessly to problems where n≥106n \geq 10^6.
Sep 20, 2025

Sublinear Time Quantum Sensitivity Sampling

We present a unified quantum sensitivity sampling framework that streamlines coreset construction for many classical approximation problems, significantly speeding up clustering, regression, and low-rank approximation. We assume n,d≥poly(k/ε)n,d\geq\mathrm{poly}(k/ε) and, for regression, n≥poly(d)n\geq\mathrm{poly}(d): - kk-median/kk-means: For nn points in Rd\mathbb{R}^d, we build an εε-coreset of input points of size O~(k4/3ε−2)\tilde O(k^{4/3}ε^{-2}) (resp. O~(k3/2ε−2)\tilde O(k^{3/2}ε^{-2})) in time O~(ε−1n0.5dk1.67)\tilde O(ε^{-1}n^{0.5}dk^{1.67}) (resp. O~(ε−1n0.5dk1.75)\tilde O(ε^{-1}n^{0.5}dk^{1.75})). Our better dd- and linear 1/ε1/ε-dependence improve on [Xue, Chen, Li and Jiang, ICML'23] for d≥Ω(k7/3)d\geqΩ(k^{7/3}) (resp. Ω(k2.5)Ω(k^{2.5})). - ℓp\ell_p regression: For min⁡x∥Ax−b∥p\min_x\|Ax-b\|_p, A∈Rn×dA\in\mathbb{R}^{n\times d}, we build an εε-coreset of size O~p(dmax⁡{1,p/2}ε−2)\tilde O_p(d^{\max\{1,p/2\}}ε^{-2}) in time O~p(n0.5d1.5ε−1)\tilde O_p(n^{0.5}d^{1.5}ε^{-1}) for p≤2p\leq 2 and O~p(n0.5dp/4+1(ε−1+d0.5))\tilde O_p(n^{0.5}d^{p/4+1}(ε^{-1}+d^{0.5})) for p>2p>2, matching [Liu and Ji, ICML'26] for p≤2p\leq 2 and improving on the prior best quantum sampling approach [Apers and Gribling, SICOMP'26] for all p>2p>2. - Low-rank approximation: We give the first quantum sublinear-time algorithm for Frobenius-norm rank-kk approximation of A∈Rd×nA\in\mathbb{R}^{d\times n} free of data-dependent parameters, running in O~(n0.5dk0.5ε−0.5)\tilde O(n^{0.5}dk^{0.5}ε^{-0.5}) time with factored output (plus O~(nk2ε−2)\tilde O(nk^2ε^{-2}) to materialize them). We also give sublinear algorithms for kernel and tensor variants. - Lower bound: For generic sensitivity sampling with total sensitivity SS, any quantum algorithm outputting an εε-coreset of size o(nS)o(\sqrt{nS}) needs Ω(nS)Ω(\sqrt{nS}) queries, so our query complexity is optimal up to poly(ε−1,log⁡n)\mathrm{poly}(ε^{-1},\log n) and VC-dimension factors.
Oct 11, 2026

Revisited Support Vector Machines: A Unified Joint Optimization Framework with Nyström Approximation for Scalable Adaptive Learning

The theoretical elegance of Support Vector Machines (SVMs), grounded in statistical learning theory, establishes them as a reference for robust classification. However, in the era of Big Data, classical SVMs face two major bottlenecks: the prohibitive cubic complexity O(N3)\mathcal{O}(N^3) of training and the rigidity of static kernels. Traditional methodologies treat kernel selection as a discrete, "brute-force" GridSearch problem, effectively decoupling the learning of data representation from the optimization of the decision boundary. This paper proposes a paradigm shift with a so-called "Revisited SVM", a unified framework that recasts the learning process as a continuous %bi-level joint optimization problem. We derive a novel objective function J(α,θ)J(α, θ) that allows for the simultaneous optimization of dual Lagrange multipliers and kernel hyper-parameters. To solve this challenging non-convex problem efficiently, we introduce a hybrid Block Coordinate Ascent (BCA) algorithm, tightly integrated with Nyström-based low-rank approximation, which drastically reduces computational complexity to O(Nm)\mathcal{O}(Nm). Extensive experiments conducted across four heterogeneous domains (Bioinformatics, Finance, Cybersecurity, and Computer Vision) demonstrate that our approach not only matches but often exceeds exhaustive GridSearch accuracy, while delivering training speedups of up to 100x. Notably, on the complex NSL-KDD intrusion detection dataset, our adaptive kernel approach achieves 96.25% accuracy compared to a mere 50% for standard baselines, proving its unique ability to model complex non-linear manifolds in high-dimensional spaces. We validate our results using rigorous statistical tests and provide a theoretical convergence analysis of the proposed algorithm.