論文の概要: A Smoothing Algorithm for l1 Support Vector Machines
- arxiv url: http://arxiv.org/abs/2401.09431v1
- Date: Sun, 17 Dec 2023 00:54:56 GMT
- ステータス: 処理完了
- システム内更新日: 2024-01-22 09:25:04.099974
- Title: A Smoothing Algorithm for l1 Support Vector Machines
- Title（参考訳）: l1サポートベクトルマシンの平滑化アルゴリズム
- Authors: Ibrahim Emirahmetoglu, Jeffrey Hajewski, Suely Oliveira, and David E.
Stewart
- Abstract要約: ソフトマージン支援ベクトルマシン(SVM)最適化問題を$ell1$ペナルティで解くためのスムーシングアルゴリズムを提案する。
このアルゴリズムはヒンジロス関数のスムース化と$ell1$ペナルティのアクティブなセットアプローチを使用する。
実験により,本アルゴリズムはトレーニング速度を犠牲にすることなく,試験精度を向上できることが示された。
- 参考スコア（独自算出の注目度）: 0.07499722271664144
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: A smoothing algorithm is presented for solving the soft-margin Support Vector
Machine (SVM) optimization problem with an $\ell^{1}$ penalty. This algorithm
is designed to require a modest number of passes over the data, which is an
important measure of its cost for very large datasets. The algorithm uses
smoothing for the hinge-loss function, and an active set approach for the
$\ell^{1}$ penalty. The smoothing parameter $\alpha$ is initially large, but
typically halved when the smoothed problem is solved to sufficient accuracy.
Convergence theory is presented that shows
$\mathcal{O}(1+\log(1+\log_+(1/\alpha)))$ guarded Newton steps for each value
of $\alpha$ except for asymptotic bands $\alpha=\Theta(1)$ and
$\alpha=\Theta(1/N)$, with only one Newton step provided $\eta\alpha\gg1/N$,
where $N$ is the number of data points and the stopping criterion that the
predicted reduction is less than $\eta\alpha$. The experimental results show
that our algorithm is capable of strong test accuracy without sacrificing
training speed.
- Abstract（参考訳）: ソフトマージン支援ベクトルマシン(SVM)最適化問題を$\ell^{1}$ペナルティで解くための平滑化アルゴリズムを提案する。
このアルゴリズムは、非常に大きなデータセットのコストの重要な尺度であるデータに対するわずかな数のパスを必要とするように設計されている。
このアルゴリズムはヒンジ損失関数の平滑化と$\ell^{1}$ペナルティのアクティブなセットアプローチを使用している。
滑らか化パラメータ $\alpha$ は最初は大きいが、スムーズ化された問題が十分正確に解けると半減する。
収束理論は、_\mathcal{o}(1+\log(1+\log_+(1/\alpha))$ガードされたニュートンステップが、漸近的バンドを除いて$\alpha$の値を示す。$\alpha=\theta(1)$と$\alpha=\theta(1/n)$であり、そのニュートンステップは$\eta\alpha\gg1/n$であり、ここで$n$はデータポイントの数であり、予測された還元が$\eta\alpha$以下である。
実験結果から,本アルゴリズムはトレーニング速度を犠牲にすることなく,試験精度を向上できることがわかった。
関連論文リスト
- Mini-Batch Kernel $k$-means [4.604003661048267]
私たちのアルゴリズムの1つのイテレーションは$widetildeO(kb2)$時間であり、フルバッチカーネルの$k$-meansに必要な$O(n2)$時間よりもはるかに高速です。
実験により,本アルゴリズムは品質の低下を最小限に抑えた10-100倍の高速化を実現していることがわかった。
論文 参考訳（メタデータ） (2024-10-08T10:59:14Z) - Inverting the Leverage Score Gradient: An Efficient Approximate Newton Method [10.742859956268655]
本稿では,レバレッジスコア勾配から固有モデルパラメータを復元することを目的とする。
具体的には、レバレッジスコア勾配の逆転を$g(x)$として精査する。
論文 参考訳（メタデータ） (2024-08-21T01:39:42Z) - Optimal Query Complexities for Dynamic Trace Estimation [59.032228008383484]
我々は,行列がゆっくりと変化している動的環境において,正確なトレース推定に必要な行列ベクトルクエリ数を最小化する問題を考える。
我々は、$delta$失敗確率で$epsilon$エラーまで、すべての$m$トレースを同時に推定する新しいバイナリツリー要約手順を提供する。
我々の下界(1)は、静的な設定においてもフロベニウスノルム誤差を持つ行列ベクトル積モデルにおけるハッチンソン推定子の第一の厳密な境界を与え、(2)動的トレース推定のための最初の無条件下界を与える。
論文 参考訳（メタデータ） (2022-09-30T04:15:44Z) - List-Decodable Sparse Mean Estimation via Difference-of-Pairs Filtering [42.526664955704746]
そこで我々は,リストデコダブルなスパース平均推定のための,新しい,概念的にシンプルな手法を開発した。
特に、$k$-sparse方向の「確実に有界な」$t-thモーメントを持つ分布の場合、このアルゴリズムは、サンプル複雑性$m = (klog(n))O(t)/alpha(mnt)$の誤差を1/alpha(O (1/t)$で達成する。
Gaussian inliers の特別な場合、我々のアルゴリズムは $Theta (sqrtlog) の最適誤差を保証する。
論文 参考訳（メタデータ） (2022-06-10T17:38:18Z) - Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。
また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
論文 参考訳（メタデータ） (2022-04-13T22:18:47Z) - Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean
Estimation [58.24280149662003]
本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。
我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
論文 参考訳（メタデータ） (2021-06-16T03:34:14Z) - On Efficient Low Distortion Ultrametric Embedding [18.227854382422112]
データの基盤となる階層構造を保存するために広く用いられる方法は、データを木や超音波に埋め込む方法を見つけることである。
本稿では,$mathbbRd2(ユニバーサル定数$rho>1$)の点集合を入力として,超測度$Deltaを出力する新しいアルゴリズムを提案する。
我々のアルゴリズムの出力はリンクアルゴリズムの出力に匹敵するが、より高速な実行時間を実現する。
論文 参考訳（メタデータ） (2020-08-15T11:06:45Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z) - Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample
Complexity [59.34067736545355]
S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。
十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
論文 参考訳（メタデータ） (2020-06-06T13:34:41Z) - Maximizing Determinants under Matroid Constraints [69.25768526213689]
我々は、$det(sum_i in Sv_i v_i v_itop)$が最大になるような基底を$S$$$$M$とする問題を研究する。
この問題は、実験的なデザイン、商品の公平な割り当て、ネットワーク設計、機械学習など、さまざまな分野に現れている。
論文 参考訳（メタデータ） (2020-04-16T19:16:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。