論文の概要: Learning Constant-Depth Circuits in Malicious Noise Models
- arxiv url: http://arxiv.org/abs/2411.03570v1
- Date: Wed, 06 Nov 2024 00:19:58 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-11-07 19:23:38.696927
- Title: Learning Constant-Depth Circuits in Malicious Noise Models
- Title（参考訳）: 悪騒音モデルにおける定深さ回路の学習
- Authors: Adam R. Klivans, Konstantinos Stavropoulos, Arsen Vasilyan,
- Abstract要約: 我々は、定数深度回路を学習するためのLinial, Mansour, Nisanの準ポリノミカル時間アルゴリズムを証明した。
ノイズ率に最も依存しうることを達成し、最も厳しいノイズモデルの実現に成功した。
- 参考スコア（独自算出の注目度）: 9.036777309376697
- License:
- Abstract: The seminal work of Linial, Mansour, and Nisan gave a quasipolynomial-time algorithm for learning constant-depth circuits ($\mathsf{AC}^0$) with respect to the uniform distribution on the hypercube. Extending their algorithm to the setting of malicious noise, where both covariates and labels can be adversarially corrupted, has remained open. Here we achieve such a result, inspired by recent work on learning with distribution shift. Our running time essentially matches their algorithm, which is known to be optimal assuming various cryptographic primitives. Our proof uses a simple outlier-removal method combined with Braverman's theorem for fooling constant-depth circuits. We attain the best possible dependence on the noise rate and succeed in the harshest possible noise model (i.e., contamination or so-called "nasty noise").
- Abstract（参考訳）: Linial, Mansour, Nisan のセミナルな研究は、ハイパーキューブ上の均一分布に関して、定数深度回路(\mathsf{AC}^0$)を学習するための準ポリノミカル時間アルゴリズムを与えた。
アルゴリズムを悪質なノイズの設定に拡張することで、共変量とラベルの両方が逆向きに破損する可能性がある。
ここでは、分布シフトによる学習に関する最近の研究から着想を得た、そのような結果を得る。
我々の実行時間は基本的にアルゴリズムと一致しており、様々な暗号プリミティブを仮定すると最適であることが知られている。
我々の証明は、定数深度回路を騙すブラバーマンの定理と組み合わさった単純な外周除去法を用いている。
ノイズ率に最も依存しうることを達成し、最も厳しいノイズモデル(汚染またはいわゆる「有害ノイズ」)を成功させる。
関連論文リスト
- Already Moderate Population Sizes Provably Yield Strong Robustness to Noise [53.27802701790209]
2つの進化的アルゴリズムは、OneMaxベンチマークのランタイムを増大させることなく、一定のノイズ確率を許容できることを示す。
この結果は、ノイズのない子孫は親と騒々しい子孫の間に偏りのある均一な交叉と見なすことができるという、新しい証明の議論に基づいている。
論文 参考訳（メタデータ） (2024-04-02T16:35:52Z) - Super Non-singular Decompositions of Polynomials and their Application to Robustly Learning Low-degree PTFs [39.468324211376505]
低次しきい値関数 (PTF) の, 対向汚職の一定割合の存在下での効率的な学習性について検討した。
提案アルゴリズムは,線形しきい値関数の学習に使用されていた局所化手法に着想を得た反復的手法を用いている。
論文 参考訳（メタデータ） (2024-03-31T02:03:35Z) - Scalable noisy quantum circuits for biased-noise qubits [37.69303106863453]
安定猫量子ビットの既存システムに動機づけられたビットフリップ誤差のみに影響されるバイアスノイズ量子ビットを考察する。
現実的なノイズモデルでは、位相フリップは無視できないが、Pauli-Twirling近似では、ベンチマークが最大106ドルのゲートを含む回路の正しさを確認できる。
論文 参考訳（メタデータ） (2023-05-03T11:27:50Z) - Certified Adversarial Robustness Within Multiple Perturbation Bounds [38.3813286696956]
ランダムスムーシング(Randomized smoothing、RS)は、敵の攻撃に対するよく知られた防御である。
本研究では,複数の摂動境界に対して同時に認証された対向ロバスト性を改善することを目的としている。
論文 参考訳（メタデータ） (2023-04-20T16:42:44Z) - A Robust Phased Elimination Algorithm for Corruption-Tolerant Gaussian
Process Bandits [118.22458816174144]
そこで本稿では,エポックで動作するロバストな除去型アルゴリズムを提案し,探索と頻繁な切替を併用して,小さなアクションサブセットを選択し,各アクションを複数タイミングで実行する。
我々のアルゴリズムであるGP Robust Phased Elimination (RGP-PE) は、探索とエクスプロイトによる汚職に対するロバストネスのバランスに成功している。
GPバンディット設定におけるロバスト性の最初の実証的研究を行い,アルゴリズムが様々な敵攻撃に対してロバストであることを示す。
論文 参考訳（メタデータ） (2022-02-03T21:19:36Z) - Breaking the Moments Condition Barrier: No-Regret Algorithm for Bandits
with Super Heavy-Tailed Payoffs [27.636407641546914]
実験的な中央値列の経験的平均を計算し,確率変数を推定する,新しい頑健な統計推定器を提案する。
非常に重みのある雑音であっても, 後悔の限界がほぼ最適であることを示す。
論文 参考訳（メタデータ） (2021-10-26T17:30:44Z) - Plug-And-Play Learned Gaussian-mixture Approximate Message Passing [71.74028918819046]
そこで本研究では,従来のi.i.d.ソースに適した圧縮圧縮センシング(CS)リカバリアルゴリズムを提案する。
我々のアルゴリズムは、Borgerdingの学習AMP(LAMP)に基づいて構築されるが、アルゴリズムに普遍的な復調関数を採用することにより、それを大幅に改善する。
数値評価により,L-GM-AMPアルゴリズムは事前の知識を必要とせず,最先端の性能を実現する。
論文 参考訳（メタデータ） (2020-11-18T16:40:45Z) - A Polynomial Time Algorithm for Learning Halfspaces with Tsybakov Noise [55.45544638410858]
本研究では,Tsybakovノイズの存在下でのPAC学習の相同性半空間の問題について検討する。
我々のアルゴリズムは、任意の精度$epsilon$で真のハーフスペースを学習する。
論文 参考訳（メタデータ） (2020-10-04T22:19:06Z) - Learning Halfspaces with Tsybakov Noise [50.659479930171585]
テュバコフ雑音の存在下でのハーフスペースの学習可能性について検討する。
真半空間に関して誤分類誤差$epsilon$を達成するアルゴリズムを与える。
論文 参考訳（メタデータ） (2020-06-11T14:25:02Z) - TAdam: A Robust Stochastic Gradient Optimizer [6.973803123972298]
機械学習アルゴリズムは、特にロボット分野において、いくつかのノイズを含むかもしれない観察からパターンを見つけることを目的としている。
このようなノイズにうまく対処するためには、外乱を検知し、必要に応じて破棄できると期待している。
そこで本研究では,アルゴリズムに頑健性を直接組み込んだ勾配最適化手法を提案し,その中核となる概念として頑健な学生分布を用いた。
論文 参考訳（メタデータ） (2020-02-29T04:32:36Z) - Learning with Differentiable Perturbed Optimizers [54.351317101356614]
本稿では,操作を微分可能で局所的に一定ではない操作に変換する手法を提案する。
提案手法は摂動に依拠し,既存の解法とともに容易に利用することができる。
本稿では,この枠組みが,構造化予測において発達した損失の族とどのように結びつくかを示し,学習課題におけるそれらの使用に関する理論的保証を与える。
論文 参考訳（メタデータ） (2020-02-20T11:11:32Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。