論文の概要: Provable Training of a ReLU Gate with an Iterative Non-Gradient
Algorithm
- arxiv url: http://arxiv.org/abs/2005.04211v5
- Date: Fri, 1 Apr 2022 15:56:40 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-05 12:15:40.660507
- Title: Provable Training of a ReLU Gate with an Iterative Non-Gradient
Algorithm
- Title(参考訳): 反復的非勾配アルゴリズムによるReLUゲートの確率的学習
- Authors: Sayar Karmakar and Anirbit Mukherjee
- Abstract要約: 我々は,未調査体制下での1つのReLUゲートのトレーニングについて,証明可能な保証を示す。
我々は,真のラベルに対する(オンライン)データポゾン攻撃の下で,真のラベル生成パラメータを近似的に復元することを示す。
我々の保証は最悪の場合ほぼ最適であることが示され、真の重量回復の精度は攻撃の確率と大きさの増大とともに優雅に低下する。
- 参考スコア(独自算出の注目度): 0.7614628596146599
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this work, we demonstrate provable guarantees on the training of a single
ReLU gate in hitherto unexplored regimes. We give a simple iterative stochastic
algorithm that can train a ReLU gate in the realizable setting in linear time
while using significantly milder conditions on the data distribution than
previous such results.
Leveraging certain additional moment assumptions, we also show a
first-of-its-kind approximate recovery of the true label generating parameters
under an (online) data-poisoning attack on the true labels, while training a
ReLU gate by the same algorithm. Our guarantee is shown to be nearly optimal in
the worst case and its accuracy of recovering the true weight degrades
gracefully with increasing probability of attack and its magnitude.
For both the realizable and the non-realizable cases as outlined above, our
analysis allows for mini-batching and computes how the convergence time scales
with the mini-batch size. We corroborate our theorems with simulation results
which also bring to light a striking similarity in trajectories between our
algorithm and the popular S.G.D. algorithm - for which similar guarantees as
here are still unknown.
- Abstract(参考訳): 本研究では,非探索的体制下での単一ReLUゲートのトレーニングについて,実証可能な保証を示す。
そこで,本研究では,線形時間にreluゲートを訓練し,従来よりもデータ分布の微弱な条件を用いる単純な反復的確率的アルゴリズムを提案する。
また、ある追加モーメント仮定を応用し、同じアルゴリズムでReLUゲートをトレーニングしながら、真のラベル生成パラメータを真のラベルに対して(オンライン)データポゾン攻撃下で近似的に復元することを示す。
我々の保証は最悪の場合にほぼ最適であり、真の重量の回復の精度は攻撃の確率と大きさの増加によって優雅に低下する。
上記のような実現可能ケースと実現不可能なケースの両方について,本解析によりミニバッチ化が可能となり,収束時間とミニバッチサイズとのスケーリングの計算が可能となる。
我々は、我々の定理をシミュレーションの結果と調和させ、我々のアルゴリズムと人気のあるs.g.d.アルゴリズムの軌跡の著しい類似性に光を当てる。
関連論文リスト
- Differentiable Annealed Importance Sampling and the Perils of Gradient
Noise [68.44523807580438]
Annealed importance sample (AIS) と関連するアルゴリズムは、限界推定のための非常に効果的なツールである。
差別性は、目的として限界確率を最適化する可能性を認めるため、望ましい性質である。
我々はメトロポリス・ハスティングスのステップを放棄して微分可能アルゴリズムを提案し、ミニバッチ計算をさらに解き放つ。
論文 参考訳(メタデータ) (2021-07-21T17:10:14Z) - Robust Regression Revisited: Acceleration and Improved Estimation Rates [25.54653340884806]
強い汚染モデルの下で, 統計的回帰問題に対する高速アルゴリズムについて検討する。
目的は、逆向きに破損したサンプルを与えられた一般化線形モデル(GLM)を概ね最適化することである。
実行時や推定保証が改善された頑健な回帰問題に対して,ほぼ直線的な時間アルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-06-22T17:21:56Z) - Sparse Bayesian Learning via Stepwise Regression [1.2691047660244335]
我々は、RMP(Relevance Matching Pursuit)と呼ばれるSBLのための座標加算アルゴリズムを提案する。
ノイズ分散パラメータがゼロになるにつれて、RMPはステップワイド回帰と驚くべき関係を示す。
ステップワイド回帰アルゴリズムの新たな保証を導き、RMPにも光を当てる。
論文 参考訳(メタデータ) (2021-06-11T00:20:27Z) - Risk Minimization from Adaptively Collected Data: Guarantees for
Supervised and Policy Learning [57.88785630755165]
経験的リスク最小化(Empirical Risk Minimization, ERM)は、機械学習のワークホースであるが、適応的に収集されたデータを使用すると、そのモデルに依存しない保証が失敗する可能性がある。
本研究では,仮説クラス上での損失関数の平均値を最小限に抑えるため,適応的に収集したデータを用いた一般的な重み付きERMアルゴリズムについて検討する。
政策学習では、探索がゼロになるたびに既存の文献のオープンギャップを埋める率-最適後悔保証を提供する。
論文 参考訳(メタデータ) (2021-06-03T09:50:13Z) - Stochastic Reweighted Gradient Descent [4.355567556995855]
SRG(stochastic reweighted gradient)と呼ばれる重要サンプリングに基づくアルゴリズムを提案する。
我々は、提案手法の時間とメモリオーバーヘッドに特に注意を払っています。
我々はこの発見を裏付ける実験結果を示す。
論文 参考訳(メタデータ) (2021-03-23T04:09:43Z) - Experimental Design for Regret Minimization in Linear Bandits [19.8309784360219]
オンライン・リニア・バンドレットにおける後悔を最小限に抑える設計に基づく新しいアルゴリズムを提案する。
我々は、現在最先端の有限時間後悔保証を提供し、このアルゴリズムが帯域幅と半帯域幅の両方のフィードバックシステムに適用可能であることを示す。
論文 参考訳(メタデータ) (2020-11-01T17:59:19Z) - Investigating the Scalability and Biological Plausibility of the
Activation Relaxation Algorithm [62.997667081978825]
アクティベーション・リラクシエーション(AR)アルゴリズムは、誤りアルゴリズムのバックプロパゲーションを近似するためのシンプルでロバストなアプローチを提供する。
このアルゴリズムは、学習可能な後方重みセットを導入することにより、さらに単純化され、生物学的に検証可能であることを示す。
また、元のARアルゴリズム(凍結フィードフォワードパス)の別の生物学的に信じられない仮定が、パフォーマンスを損なうことなく緩和できるかどうかについても検討する。
論文 参考訳(メタデータ) (2020-10-13T08:02:38Z) - Provably Efficient Reward-Agnostic Navigation with Linear Value
Iteration [143.43658264904863]
我々は、最小二乗値スタイルのアルゴリズムで一般的に使用される、より標準的なベルマン誤差の概念の下での反復が、ほぼ最適値関数の学習において強力なPAC保証を提供することを示す。
そこで本稿では,任意の(線形な)報酬関数に対して,最適に近いポリシーを学習するためにどのように使用できるかを示す。
論文 参考訳(メタデータ) (2020-08-18T04:34:21Z) - Fast OSCAR and OWL Regression via Safe Screening Rules [97.28167655721766]
順序付き$L_1$ (OWL)正規化回帰は、高次元スパース学習のための新しい回帰分析である。
近勾配法はOWL回帰を解くための標準手法として用いられる。
未知の順序構造を持つ原始解の順序を探索することにより、OWL回帰の最初の安全なスクリーニングルールを提案する。
論文 参考訳(メタデータ) (2020-06-29T23:35:53Z) - Least Squares Regression with Markovian Data: Fundamental Limits and
Algorithms [69.45237691598774]
マルコフ連鎖からデータポイントが依存しサンプリングされる最小二乗線形回帰問題について検討する。
この問題を$tau_mathsfmix$という観点から、鋭い情報理論のミニマックス下限を確立する。
本稿では,経験的リプレイに基づくアルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-06-16T04:26:50Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。