Fugu-MT 論文翻訳(概要): Faster Algorithms for Structured Linear and Kernel Support Vector Machines

論文の概要: Faster Algorithms for Structured Linear and Kernel Support Vector Machines

arxiv url: http://arxiv.org/abs/2307.07735v3
Date: Tue, 11 Feb 2025 21:37:03 GMT
ステータス: 翻訳完了
システム内更新日: 2025-02-13 13:46:41.219909
Title: Faster Algorithms for Structured Linear and Kernel Support Vector Machines
Title（参考訳）: 構造線形およびカーネル支援ベクトルマシンのための高速アルゴリズム
Authors: Yuzhou Gu, Zhao Song, Lichen Zhang,
Abstract要約: 二次的目的が低ランクの分解を許容する場合に、2次プログラムを解くための最初のニア線形時間アルゴリズムを設計する。正方形のデータセット半径が少なくとも$Omega(log2 n)$の場合、$Omega(n2-o(1))$ timeが要求される。
参考スコア（独自算出の注目度）: 9.62296035593105
License:
Abstract: 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(n^2)$, where $n$ is the number of variables. Assuming the Strong Exponential Time Hypothesis ($\textsf{SETH}$), it is known that no $O(n^{2-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^{(\omega+1)/2}\log(1/\epsilon))$ where $\omega\approx 2.37$ is the fast matrix multiplication exponent; * For Gaussian kernel SVM, when the data dimension $d = {\color{black}O(\log n)}$ and the squared dataset radius is sub-logarithmic in $n$, our algorithm runs in time $O(n^{1+o(1)}\log(1/\epsilon))$. We also prove that when the squared dataset radius is at least $\Omega(\log^2 n)$, then $\Omega(n^{2-o(1)})$ time is required. This improves upon the prior best lower bound in both the dimension $d$ and the squared dataset radius.
Abstract（参考訳）: 擬似プログラミングは凸プログラミングにおけるユビキタスなプロトタイプである。多くの機械学習問題は、有名なSVM(Support Vector Machines)など、二次プログラミングとして定式化することができる。線形およびカーネルSVMは、ディープラーニング時代以前の過去30年間、機械学習で最も人気のあるモデルである。一般に、二次プログラムの入力サイズは$\Theta(n^2)$で、$n$は変数の数である。強い指数時間仮説(英語版)(\textsf{SETH}$)を仮定すると、二次目的行列が正半定値であるとき、O(n^{2-o(1)})$時間アルゴリズムは存在しないことが知られている(Backurs, Indyk, Schmidt, NeurIPS'17)。しかし、SVMのような問題は通常、より小さな入力サイズを許容する: 1つは$n$のデータポイントを与えられ、各次元は$d$、$d$は$n$よりもはるかに小さい。さらに、SVMプログラムは$O(1)$等値線形制約しか持たない。これは、プログラムが特定の構造を示す場合、より高速なアルゴリズムが実現可能であることを示唆している。本研究では,2次的目的が低ランクの分解を許容し,線形制約の数が少ない場合に2次的プログラムを解くための,最初のニア線形時間アルゴリズムを設計する。入力データが$d$-dimensionalであるような線形SVMの場合、我々のアルゴリズムは時間$\widetilde O(nd^{(\omega+1)/2}\log(1/\epsilon))$ where $\omega\approx 2.37$ is the fast matrix multiplication exponent; * ガウスカーネルSVMの場合、データ次元$d = {\color{black}O(\log n)}$と平方データセット半径が$n$の対数である場合、我々のアルゴリズムは時間$O(n^{1+o(1)}\log(1/\epsilon)$で実行される。また、二乗データセット半径が少なくとも$\Omega(\log^2 n)$の場合、$\Omega(n^{2-o(1)})$ timeが必要であることも証明した。これにより、次元$d$と正方形データセット半径の両方において、前の最下界が改善される。

論文の概要: Faster Algorithms for Structured Linear and Kernel Support Vector Machines

関連論文リスト