# Faster Algorithms for Structured Linear and Kernel Support Vector Machines

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Jul 2023.

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

- [A Fast Optimization View: Reformulating Single Layer Attention in LLM Based on Tensor and SVM Trick, and Solving It in Matrix Multiplication Time](https://mlsanity.com/paper/2309.07418/) (2023)
- [GradientCoin: A Peer-to-Peer Decentralized Large Language Models](https://mlsanity.com/paper/2308.10502/) (2023)
- [A Tighter Complexity Analysis of SparseGPT](https://mlsanity.com/paper/2408.12151/) (2024)
- [Unmasking Transformers: A Theoretical Approach to Data Recovery via Attention Weights](https://mlsanity.com/paper/2310.12462/) (2023)
- [Is Solving Graph Neural Tangent Kernel Equivalent to Training Graph Neural Network?](https://mlsanity.com/paper/2309.07452/) (2023)
- [Only Large Weights (And Not Skip Connections) Can Prevent the Perils of Rank Collapse](https://mlsanity.com/paper/2505.16284/) (2025)
- [Convergence of Two-Layer Regression with Nonlinear Units](https://mlsanity.com/paper/2308.08358/) (2023)
- [How to Inverting the Leverage Score Distribution?](https://mlsanity.com/paper/2404.13785/) (2024)
- [Binary Hypothesis Testing for Softmax Models and Leverage Score Models](https://mlsanity.com/paper/2405.06003/) (2024)
- [Tight Generalization Bounds for Large-Margin Halfspaces](https://mlsanity.com/paper/2502.13692/) (2025)
- [Data Depth as a Risk](https://mlsanity.com/paper/2507.08518/) (2025)
- [Differential Privacy for Euclidean Jordan Algebra with Applications to Private Symmetric Cone Programming](https://mlsanity.com/paper/2509.16915/) (2025)
- [Which Coauthor Should I Nominate in My 99 ICLR Submissions? A Mathematical Analysis of the ICLR 2026 Reciprocal Reviewer Nomination Policy](https://mlsanity.com/paper/2512.17950/) (2025)

## Abstract (arXiv)

Quadratic programming is a ubiquitous prototype in convex programming. Many machine learning problems can be formulated as quadratic programming, including the famous Support Vector Machines (SVMs). Linear and kernel SVMs have been among the most popular models in machine learning over the past three decades, prior to the deep learning era. Generally, a quadratic program has an input size of Theta(n2), where n is the number of variables. Assuming the Strong Exponential Time Hypothesis (textsfSETH), it is known that no O(n2-o(1)) time algorithm exists when the quadratic objective matrix is positive semidefinite (Backurs, Indyk, and Schmidt, NeurIPS'17). However, problems such as SVMs usually admit much smaller input sizes: one is given n data points, each of dimension d, and d is oftentimes much smaller than n. Furthermore, the SVM program has only O(1) equality linear constraints. This suggests that faster algorithms are feasible, provided the program exhibits certain structures. In this work, we design the first nearly-linear time algorithm for solving quadratic programs whenever the quadratic objective admits a low-rank factorization, and the number of linear constraints is small. Consequently, we obtain results for SVMs: * For linear SVM when the input data is d-dimensional, our algorithm runs in time widetilde O(nd(ω+1)/2log(1/ε)) where ω≈ 2.37 is the fast matrix multiplication exponent; * For Gaussian kernel SVM, when the data dimension d = colorblackO(log n) and the squared dataset radius is sub-logarithmic in n, our algorithm runs in time O(n1+o(1)log(1/ε)). We also prove that when the squared dataset radius is at least Omega(log2 n), then Omega(n2-o(1)) time is required. This improves upon the prior best lower bound in both the dimension d and the squared dataset radius.