論文の概要: On Accelerated Perceptrons and Beyond
- arxiv url: http://arxiv.org/abs/2210.09371v1
- Date: Mon, 17 Oct 2022 19:12:30 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-19 14:15:12.086136
- Title: On Accelerated Perceptrons and Beyond
- Title（参考訳）: 加速パーセプトロン等について
- Authors: Guanghui Wang, Rafael Hanashiro, Etash Guha, Jacob Abernethy
- Abstract要約: RosenblattのPerceptronアルゴリズムは、$n$の線形分離可能なデータポイントを正しく分類する線形しきい値関数を見つけるのに使うことができる。
基本的な結果は、Perceptron が $Omega(sqrtlog n/gamma)$ iterations の後に収束するということである。
最近、より洗練されたアルゴリズムでこの速度を2乗係数で$Omega(sqrtlog n/gamma)$に改善する研究がいくつかある。
- 参考スコア（独自算出の注目度）: 17.479295705933698
- License: http://creativecommons.org/publicdomain/zero/1.0/
- Abstract: The classical Perceptron algorithm of Rosenblatt can be used to find a linear
threshold function to correctly classify $n$ linearly separable data points,
assuming the classes are separated by some margin $\gamma > 0$. A foundational
result is that Perceptron converges after $\Omega(1/\gamma^{2})$ iterations.
There have been several recent works that managed to improve this rate by a
quadratic factor, to $\Omega(\sqrt{\log n}/\gamma)$, with more sophisticated
algorithms. In this paper, we unify these existing results under one framework
by showing that they can all be described through the lens of solving min-max
problems using modern acceleration techniques, mainly through optimistic online
learning. We then show that the proposed framework also lead to improved
results for a series of problems beyond the standard Perceptron setting.
Specifically, a) For the margin maximization problem, we improve the
state-of-the-art result from $O(\log t/t^2)$ to $O(1/t^2)$, where $t$ is the
number of iterations; b) We provide the first result on identifying the
implicit bias property of the classical Nesterov's accelerated gradient descent
(NAG) algorithm, and show NAG can maximize the margin with an $O(1/t^2)$ rate;
c) For the classical $p$-norm Perceptron problem, we provide an algorithm with
$\Omega(\sqrt{(p-1)\log n}/\gamma)$ convergence rate, while existing algorithms
suffer the $\Omega({(p-1)}/\gamma^2)$ convergence rate.
- Abstract（参考訳）: rosenblattの古典的なパーセプトロンアルゴリズムは、クラスがいくつかのマージン$\gamma > 0$で区切られると仮定して、n$の線形分離可能なデータポイントを正しく分類する線形しきい値関数を見つけるのに使うことができる。
基本的な結果として、パーセプトロンは$\omega(1/\gamma^{2})$ 反復後に収束する。
この速度を2乗因子で改善した最近の研究はいくつかあり、より洗練されたアルゴリズムで$\omega(\sqrt{\log n}/\gamma)$となった。
本稿では,これらの既存の結果を一つの枠組みで統一し,これら全てを現代の加速技術を用いて,楽観的なオンライン学習を通じて,min-max問題解決のレンズを通して説明できることを示す。
次に,提案フレームワークが,標準のパーセプトロン設定を超えた一連の問題に対する結果の改善につながることを示す。
具体的には
a) 限界の極大化問題に対しては,その最新結果をo(\log t/t^2)$ から$o(1/t^2)$ に改善する。ただし$t$ はイテレーション数である。
b) 古典的ネステロフ加速度勾配降下法(nag)アルゴリズムの暗黙的バイアス特性を同定する最初の結果を示し,nagが$o(1/t^2)$レートでマージンを最大化できることを示す。
c) 古典的な$p$-ノルムパーセプトロン問題に対して、$\Omega(\sqrt{(p-1)\log n}/\gamma)$収束率のアルゴリズムを提供する一方、既存のアルゴリズムは$\Omega({(p-1)}/\gamma^2)$収束率のアルゴリズムを提供する。
関連論文リスト
- Approximation Rates for Shallow ReLU$^k$ Neural Networks on Sobolev Spaces via the Radon Transform [4.096453902709292]
我々は,ReLU$k$アクティベーション関数がソボレフ空間からの関数をいかに効率的に近似できるかという問題を考察する。
例えば、$qleq p$, $pgeq 2$, $s leq k + (d+1)/2$ などである。
論文 参考訳（メタデータ） (2024-08-20T16:43:45Z) - Faster Linear Systems and Matrix Norm Approximation via Multi-level Sketched Preconditioning [10.690769339903941]
我々は、$Ax = b$という形式の線形系を解くための、新しい条件付き反復法のクラスを示す。
提案手法は,低ランクなNystr"om近似をスパースランダムスケッチを用いて$A$に構築することに基づいている。
我々は、我々の手法の収束が自然平均条件数$A$に依存することを証明し、Nystr"om近似のランクとして改善する。
論文 参考訳（メタデータ） (2024-05-09T15:53:43Z) - Efficient Frameworks for Generalized Low-Rank Matrix Bandit Problems [61.85150061213987]
一般化線形モデル (GLM) フレームワークを用いて, citelu2021low で提案した一般化低ランク行列帯域問題について検討する。
既存のアルゴリズムの計算不可能性と理論的制約を克服するため,まずG-ESTTフレームワークを提案する。
G-ESTT は $tildeO(sqrt(d_1+d_2)3/2Mr3/2T)$ bound of regret を達成でき、G-ESTS は $tildeO を達成できることを示す。
論文 参考訳（メタデータ） (2024-01-14T14:14:19Z) - An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue
Optimization Problems [76.2042837251496]
相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。
注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。
本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
論文 参考訳（メタデータ） (2023-06-30T08:34:29Z) - Accelerated Quasi-Newton Proximal Extragradient: Faster Rate for Smooth
Convex Optimization [26.328847475942894]
我々は,本手法が$Obigl(minfrac1k2, fracsqrtdlog kk2.5bigr)$の収束率を達成できることを証明した。
我々の知る限りでは、この結果はネステロフの加速勾配に対する準ニュートン型法の証明可能な利得を示す最初のものである。
論文 参考訳（メタデータ） (2023-06-03T23:31:27Z) - Tight Bounds for $\gamma$-Regret via the Decision-Estimation Coefficient [88.86699022151598]
任意の構造化バンディット問題に対する$gamma$-regretの統計的特徴を与える。
この$gamma$-regretは、関数クラス$mathcalF$上の構造化バンディット問題に現れる。
論文 参考訳（メタデータ） (2023-03-06T17:54:33Z) - Randomized Block-Coordinate Optimistic Gradient Algorithms for
Root-Finding Problems [8.0153031008486]
大規模設定における非線形方程式の解を近似する2つの新しいアルゴリズムを開発した。
我々は,機械学習における顕著な応用を網羅する大規模有限サム包含のクラスに,本手法を適用した。
論文 参考訳（メタデータ） (2023-01-08T21:46:27Z) - Continuous Submodular Maximization: Boosting via Non-oblivious Function [12.755674710719616]
本稿では、オフラインおよびオンライン設定の両方において制約付きおよび連続的なサブモジュールイテレーションを再考する。
係数回帰最適化方程式を用いて、問題$max_boldsymbolxinmathCf(boldsymbolx)$に対して最適な補助関数$F$を導出する。
オンライン環境では、勾配フィードバックアルゴリズムの強化を提案し、$sqrtD$($D$は勾配フィードバックが$(fracgamma2)$に対する遅延の総和である)を後悔する。
論文 参考訳（メタデータ） (2022-01-03T15:10:17Z) - Gaussian Process Bandit Optimization with Few Batches [49.896920704012395]
有限腕バンディットアルゴリズムにインスパイアされたバッチアルゴリズムを導入する。
O(log T)$ batches in time horizon $T$.sqrtTgamma_T)$ using $O(log T)$ batches in time horizon。
さらに,アルゴリズムの修正版を提案し,バッチ数によって後悔がどう影響するかを特徴付ける。
論文 参考訳（メタデータ） (2021-10-15T00:54:04Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。