Research map / Learning theory and algorithms / Matrix and tensor methods
Faster Algorithms for Structured Linear and Kernel Support Vector Machines
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Gives a nearly-linear-time robust interior point method for low-rank convex QPs with few equality constraints, yielding faster linear SVM training and almost-linear Gaussian kernel SVM for small dimension and radius, plus SETH hardness bounds.
Problem
Solving high-precision quadratic programs, particularly SVM dual QPs, faster than the quadratic input size, for linear SVMs and Gaussian kernel SVMs.
Approach
A robust IPM whose per-iteration linear algebra is maintained via Woodbury identity and lazy sparse updates when the quadratic objective is low-rank (Q = UV^T) and there are few equality constraints; combined with a low-rank polynomial approximation of the Gaussian kernel for kernel SVM.
Key results
- Linear SVM solved in O~(n d^((omega+1)/2) log(1/eps)) time, improving on the prior O(n^1.5 d^(omega-1) log(1/eps)) IPM bound.
- Gaussian kernel SVM solved in O(n^(1+o(1)) log(1/eps)) time when d=O(log n) and squared radius B=o(log n / log log n).
- SETH lower bound: no O(n^(2-o(1))) algorithm for Gaussian kernel SVM without bias when B=Omega(log^2 n) and d=Omega(log n), improving prior lower bounds in d and B.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the low-rank QP algorithm for d-dimensional linear SVM | Linear SVM · Linear SVM | running time: O(n^{1.5}d^{\omega-1}\log(1/\epsilon)) -> \widetilde O(nd^{(\omega+1)/2}\log(n/\epsilon)) | Helped |
| Use a rank-n^{o(1)} Gaussian kernel factorization with the low-rank QP solver under the stated dimension and radius conditions | Gaussian kernel SVM · Gaussian kernel SVM | running time: O(n^{1+o(1)}\log(1/\epsilon)) | Helped |
| Set d=\Omega(\log n) and B=\Omega(\log^2 n) for SVM without bias | Gaussian kernel SVM without bias · Gaussian kernel SVM without bias | required running time: \Omega(n^{2-o(1)}) | Hurt |
| Set d=\Omega(\log n) and B=\Omega(\log^6 n) for SVM with bias | Gaussian kernel SVM with bias · Gaussian kernel SVM with bias | required running time: \Omega(n^{2-o(1)}) | Hurt |
Limitations
- Runtime depends polynomially on rank k (k^((omega+1)/2)) and on number of equality constraints m.
- Gaussian kernel algorithm requires d=O(log n) and B=o(log n / log log n), which is restrictive.
- Purely theoretical; no experiments.
Experimental setup
Metrics: runtime complexity
Baselines: interior point method for linear SVM (O(n^1.5 d^(omega-1) log(1/eps))) stochastic subgradient SVM solvers LIBSVM
Builds on: robust interior point method Backurs-Indyk-Schmidt SETH hardness low-rank Gaussian kernel approximation (Alman-Song) LIBSVM
Closest papers by meaning
- Improved Algorithms for Kernel Matrix-Vector Multiplication Under Sparsity Assumptions (ICLR 2025 · similarity 0.87)
- An exact solver for the Weston-Watkins SVM subproblem (ICML 2021 · similarity 0.87)
- Support vector machines and linear regression coincide with very high-dimensional features (NeurIPS 2021 · similarity 0.86)
- Nyström-Accelerated Primal LS-SVMs: Breaking the $O(an^3)$ Complexity Bottleneck for Scalable ODEs Learning (NeurIPS 2025 · similarity 0.86)
- Joker: Joint Optimization Framework for Lightweight Kernel Machines (ICML 2025 · similarity 0.86)
- Learning with Exact Invariances in Polynomial Time (ICML 2025 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.