跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv:2307.07735 · v4

Faster Algorithms for Structured Linear and Kernel Support Vector Machines

首次提交 2023-07-15 15:19
版本更新 2026-11-16 11:38
雷达观测 2026-11-17 17:12
arXiv ↗PDF ↗

摘要

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.

作者备注: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

AI 论文解读

基于摘要 · 非全文审阅

此版本尚未生成 AI 解读。解读由后台任务生成并按论文版本保存,登录后共享已有结果。

版本差异

本站首次收录为 v4,暂无更早版本可对照。

观测到的版本

相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。

v4 · 2026-11-16 11:38 · 最新观测版本

Faster Algorithms for Structured Linear and Kernel Support Vector Machines

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.

查看此版本解读 →查看此版本原文 ↗