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.07735v2
Date: Mon, 13 Nov 2023 08:50:53 GMT
ステータス: 処理完了
システム内更新日: 2023-11-14 21:18:25.638653
Title: Faster Algorithms for Structured Linear and Kernel Support Vector Machines
Title（参考訳）: 構造線形およびカーネル支援ベクトルマシンのための高速アルゴリズム
Authors: Yuzhou Gu, Zhao Song, Lichen Zhang
Abstract要約: 木幅が小さい場合や、低ランクの分解を許容する場合に、2次プログラムを解くための最初のニア線形時間アルゴリズムを設計する。正方形のデータセット半径が大きくなると、$Omega(n2-o(1))$ timeが要求される。
参考スコア（独自算出の注目度）: 10.815243076341526
License: http://creativecommons.org/licenses/by-nc-sa/4.0/
Abstract: Quadratic programming is a ubiquitous prototype in convex programming. Many combinatorial optimizations on graphs and machine learning problems can be formulated as quadratic programming; for example, 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)})$ algorithm exists (Backurs, Indyk, and Schmidt, NIPS'17). However, problems such as SVMs usually feature much smaller input sizes: one is given $n$ data points, each of dimension $d$, with $d \ll n$. Furthermore, SVMs are variants with only $O(1)$ linear constraints. This suggests that faster algorithms are feasible, provided the program exhibits certain underlying structures. In this work, we design the first nearly-linear time algorithm for solving quadratic programs whenever the quadratic objective has small treewidth or admits a low-rank factorization, and the number of linear constraints is small. Consequently, we obtain a variety of results for SVMs: * For linear SVM, where the quadratic constraint matrix has treewidth $\tau$, we can solve the corresponding program in time $\widetilde O(n\tau^{(\omega+1)/2}\log(1/\epsilon))$; * For linear SVM, where the quadratic constraint matrix admits a low-rank factorization of rank-$k$, we can solve the corresponding program in time $\widetilde O(nk^{(\omega+1)/2}\log(1/\epsilon))$; * For Gaussian kernel SVM, where the data dimension $d = \Theta(\log n)$ and the squared dataset radius is small, we can solve it in time $O(n^{1+o(1)}\log(1/\epsilon))$. We also prove that when the squared dataset radius is large, then $\Omega(n^{2-o(1)})$ time is required.
Abstract（参考訳）: 擬似プログラミングは凸プログラミングにおけるユビキタスなプロトタイプである。グラフと機械学習の問題に対する多くの組合せ最適化は二次プログラミングとして定式化することができる。線形およびカーネルSVMは、ディープラーニング時代以前の過去30年間、機械学習で最も人気のあるモデルである。一般に、二次プログラムは$\theta(n^2)$の入力サイズを持ち、ここで$n$は変数の数である。強い指数時間仮説(\textsf{seth}$)を仮定すると、o(n^{2-o(1)})$アルゴリズムは存在しないことが知られている(backurs, indyk, and schmidt, nips'17)。しかし、svmのような問題は通常、入力サイズがかなり小さい: 1 には $n$ データポイントが与えられ、それぞれ $d$、$d \ll n$ が与えられる。さらに、SVMは$O(1)$の線形制約を持つ変種である。これは、プログラムが特定の基盤構造を示す場合、より高速なアルゴリズムが実現可能であることを示唆している。本研究では,二次対象が木幅が小さい場合,あるいは低ランク因子化を許容する場合に,二次プログラムを解くための最初の近似時間アルゴリズムを設計し,線形制約の数を小さくする。 Consequently, we obtain a variety of results for SVMs: * For linear SVM, where the quadratic constraint matrix has treewidth $\tau$, we can solve the corresponding program in time $\widetilde O(n\tau^{(\omega+1)/2}\log(1/\epsilon))$; * For linear SVM, where the quadratic constraint matrix admits a low-rank factorization of rank-$k$, we can solve the corresponding program in time $\widetilde O(nk^{(\omega+1)/2}\log(1/\epsilon))$; * For Gaussian kernel SVM, where the data dimension $d = \Theta(\log n)$ and the squared dataset radius is small, we can solve it in time $O(n^{1+o(1)}\log(1/\epsilon))$. また、二乗データセット半径が大きい場合、$\omega(n^{2-o(1)})$時間が必要であることも証明する。

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

関連論文リスト