論文の概要: A Nearly-Linear Time Algorithm for Structured Support Vector Machines
- arxiv url: http://arxiv.org/abs/2307.07735v1
- Date: Sat, 15 Jul 2023 07:19:29 GMT
- ステータス: 処理完了
- システム内更新日: 2023-07-18 18:07:40.252920
- Title: A Nearly-Linear Time Algorithm for Structured Support Vector Machines
- Title（参考訳）: 構造化支持ベクトルマシンのニア線形時間アルゴリズム
- Authors: Yuzhou Gu, Zhao Song, Lichen Zhang
- Abstract要約: 低ランク因数分解あるいは低ツリー幅で2次プログラミングを解くための最初のニアリニア時間アルゴリズムと、少数の線形制約を提供する。
その結果,低ツリー幅および低ランクSVMに対するほぼ線形時間アルゴリズムが得られた。
- 参考スコア（独自算出の注目度）: 17.701064031228505
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: Quadratic programming is a fundamental problem in the field of convex
optimization. Many practical tasks can be formulated as quadratic programming,
for example, the support vector machine (SVM). Linear SVM is one of the most
popular tools over the last three decades in machine learning before deep
learning method dominating.
In general, a quadratic program has input size $\Theta(n^2)$ (where $n$ is
the number of variables), thus takes $\Omega(n^2)$ time to solve. Nevertheless,
quadratic programs coming from SVMs has input size $O(n)$, allowing the
possibility of designing nearly-linear time algorithms. Two important classes
of SVMs are programs admitting low-rank kernel factorizations and low-treewidth
programs. Low-treewidth convex optimization has gained increasing interest in
the past few years (e.g.~linear programming [Dong, Lee and Ye 2021] and
semidefinite programming [Gu and Song 2022]). Therefore, an important open
question is whether there exist nearly-linear time algorithms for quadratic
programs with these nice structures.
In this work, we provide the first nearly-linear time algorithm for solving
quadratic programming with low-rank factorization or low-treewidth, and a small
number of linear constraints. Our results imply nearly-linear time algorithms
for low-treewidth or low-rank SVMs.
- Abstract（参考訳）: 二次プログラミングは凸最適化の分野における根本的な問題である。
多くの実用的なタスクは二次プログラミング(例えば、サポートベクトルマシン(SVM))として定式化することができる。
リニアsvmは、ディープラーニングメソッドが主流になる前の過去30年間、マシンラーニングで最もポピュラーなツールの1つです。
一般に、二次プログラムは入力サイズ$\Theta(n^2)$($n$は変数の数である)なので、解くのに$\Omega(n^2)$時間を要する。
それでも、SVMから来る二次プログラムは入力サイズ$O(n)$を持ち、ほぼ線形時間アルゴリズムを設計することができる。
SVMの2つの重要なクラスは、低ランクのカーネル因数分解と低ツリー幅プログラムを認めるプログラムである。
近年,低木幅凸最適化への関心が高まっている(例えば,線形プログラミング [dong, lee and ye 2021] や半定義型プログラミング [gu and song 2022] など)。
したがって、これらの優れた構造を持つ二次プログラムに対して、ほぼ線形時間アルゴリズムが存在するかどうかという重要な疑問がある。
本研究では,低次因子分解や低木幅で二次計画を解くための最初の近似時間アルゴリズムと,少数の線形制約を提案する。
その結果,低ツリー幅および低ランクSVMに対するほぼ線形時間アルゴリズムが得られた。
関連論文リスト
- Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。
これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。
また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
論文 参考訳（メタデータ） (2024-08-16T02:33:07Z) - Solving Dense Linear Systems Faster Than via Preconditioning [1.8854491183340518]
我々のアルゴリズムは$tilde O(n2)$ if $k=O(n0.729)$であることを示す。
特に、我々のアルゴリズムは$tilde O(n2)$ if $k=O(n0.729)$である。
主アルゴリズムはランダム化ブロック座標降下法とみなすことができる。
論文 参考訳（メタデータ） (2023-12-14T12:53:34Z) - Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix
Factorization [54.29685789885059]
本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。
目標は、低ランク因子の積として$mathbfA$を近似することである。
我々の手法はBMF問題の他の一般的な変種に一般化する。
論文 参考訳（メタデータ） (2023-06-02T18:55:27Z) - Randomized and Deterministic Attention Sparsification Algorithms for
Over-parameterized Feature Dimension [18.57735939471469]
我々は注意問題のスパシフィケーションを考慮する。
超大規模特徴量の場合、文の長さをほぼ線形に縮めることができる。
論文 参考訳（メタデータ） (2023-04-10T05:52:38Z) - Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。
また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
論文 参考訳（メタデータ） (2022-04-13T22:18:47Z) - Distribution Compression in Near-linear Time [27.18971095426405]
シンニングアルゴリズムを高速化するシンプルなメタプロデューサであるCompress++を紹介する。
$sqrtn$ポイントを$mathcalO(sqrtlog n/n)$統合エラーで提供し、Monte-Carlo の最大誤差を最大化します。
論文 参考訳（メタデータ） (2021-11-15T17:42:57Z) - The Fine-Grained Hardness of Sparse Linear Regression [12.83354999540079]
この問題に対して、より優れたブルートフォースアルゴリズムは存在しないことを示す。
また,予測誤差が測定された場合,より優れたブラトフォースアルゴリズムが不可能であることを示す。
論文 参考訳（メタデータ） (2021-06-06T14:19:43Z) - Learning a Latent Simplex in Input-Sparsity Time [58.30321592603066]
我々は、$AinmathbbRdtimes n$へのアクセスを考えると、潜入$k$-vertex simplex $KsubsetmathbbRdtimes n$を学習する問題を考える。
実行時間における$k$への依存は、トップ$k$特異値の質量が$a$であるという自然な仮定から不要であることを示す。
論文 参考訳（メタデータ） (2021-05-17T16:40:48Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z) - Maximizing Determinants under Matroid Constraints [69.25768526213689]
我々は、$det(sum_i in Sv_i v_i v_itop)$が最大になるような基底を$S$$$$M$とする問題を研究する。
この問題は、実験的なデザイン、商品の公平な割り当て、ネットワーク設計、機械学習など、さまざまな分野に現れている。
論文 参考訳（メタデータ） (2020-04-16T19:16:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。