論文の概要: Resilience of Rademacher chaos of low degree
- arxiv url: http://arxiv.org/abs/2402.10504v3
- Date: Sat, 15 Mar 2025 18:59:02 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-03-18 12:32:47.520369
- Title: Resilience of Rademacher chaos of low degree
- Title（参考訳）: 低次ラデマチャーカオスのレジリエンス
- Authors: Elad Aigner-Horev, Daniel Rosenberg, Roi Weiss,
- Abstract要約: ラデマッハカオスのレジリエンスは、カオスが持続できる敵のサインフリップの最大数である。
我々はRadecherカオスの弾力性に関する確率的低バウンド保証を提供する。
次数2のラデマッハカオスと次数2のラデマッハカオスは,同じ概念的枠組みで確立されているが,大きな違いがある。
- 参考スコア（独自算出の注目度）: 5.3390449198644445
- License:
- Abstract: The resilience of a Rademacher chaos is the maximum number of adversarial sign-flips that the chaos can sustain without having its largest atom probability significantly altered. Inspired by probabilistic lower-bound guarantees for the resilience of linear Rademacher chaos, obtained by Bandeira, Ferber, and Kwan (Advances in Mathematics, Vol. $319$, $2017$), we provide probabilistic lower-bound guarantees for the resilience of Rademacher chaos of arbitrary yet sufficiently low degree. Our main results distinguish between Rademacher chaos of order two and those of higher order. In that, our first main result pertains to the resilience of decoupled bilinear Rademacher forms where different asymptotic behaviour is observed for sparse and dense matrices. For our second main result, we bootstrap our first result in order to provide resilience guarantees for quadratic Rademacher chaos. Our third main result, generalises the first and handles the resilience of decoupled Rademacher chaos of arbitrary yet sufficiently low order. Our results for decoupled Rademacher chaos of order two and that of higher order whilst are established through the same conceptual framework, differ substantially. A difference incurred due to the implementation of the same conceptual argument. The order two result is established using Dudley's maximal inequality for sub-Gaussian processes, the Hanson-Wright inequality, as well as the Kolmogorov-Rogozin inequality. To handle higher order chaos, appeals to Dudley's inequality as well as the Hanson-Wright inequality are replaced with tools suited for random tensors. Appeals to the Hanson-Wright inequality are replaced with appeals to a concentration result for random tensors put forth by Adamczak and Wolff. Our results are instance-dependent and thus allow for the efficient computation of resilience guarantees provided the order of the chaos is constant.
- Abstract（参考訳）: ラデマッハカオスのレジリエンスは、最大の原子の確率を著しく変化させることなくカオスが持続できる敵のサインフリップの最大数である。
Bandeira, Ferber, Kwan (Advances in Mathematics, Vol. $319$, $2017$) が取得した線形ラデマッハカオスのレジリエンスに対する確率的下界保証に着想を得て, 任意の低次ラデマッハカオスのレジリエンスに対する確率的下界保証を提供する。
我々の主な結果は2階のラデマチャーカオスと高階のラデマチャーカオスとを区別する。
本研究の最初の成果は, 疎度・密度のマトリックスに対して異なる漸近挙動が観察される, 分離した双線形ラデマチャー形状のレジリエンスに関するものである。
第2の成果として、第1の成果をブートストラップして、二次ラデマッハカオスに対するレジリエンスの保証を提供します。
第3の結果は、第一を一般化し、疎結合なラデマッハカオスの弾力性を扱うことである。
次数2のラデマッハカオスと次数2のラデマッハカオスは,同じ概念的枠組みで確立されているが,大きな違いがある。
同じ概念的議論の実装によって違いが生じた。
順序 2 の結果は、ダドリーの準ガウス過程における最大不等式、ハンソン・ライト不等式、コルモゴロフ・ロゴジン不等式を用いて成立する。
高次カオスに対処するために、ダドリーの不等式やハンソン・ライトの不等式へのアピールは、ランダムテンソルに適したツールに置き換えられる。
ハンソン・ライトの不等式に対する不等式は、Adamczak と Wolff によるランダムテンソルの集中結果に代えられる。
我々の結果はインスタンスに依存しており、カオスの順序が一定であれば、レジリエンスの効率的な計算を可能にする。
関連論文リスト
- Local minima of the empirical risk in high dimension: General theorems and convex examples [8.748904058015574]
我々は、データベクトル$mathbfxi$が$d-最小化であるような高次元経験的リスクの一般的なモデルを考える。
我々は推定誤差と予測誤差に基づいてシャープを導出する。
論文 参考訳（メタデータ） (2025-02-04T03:02:24Z) - Tensor cumulants for statistical inference on invariant distributions [49.80012009682584]
我々は,PCAが信号の大きさの臨界値で計算的に困難になることを示す。
我々は、与えられた次数の不変量に対して明示的でほぼ直交的な基底を与える新しい対象の集合を定義する。
また、異なるアンサンブルを区別する新しい問題も分析できます。
論文 参考訳（メタデータ） (2024-04-29T14:33:24Z) - Average-Case Complexity of Tensor Decomposition for Low-Degree
Polynomials [93.59919600451487]
多くの統計的推論タスクにおいて「統計計算ギャップ」が発生する。
1つの成分が他の成分よりもわずかに大きいランダムオーダー3分解モデルを考える。
テンソルエントリは$ll n3/2$のとき最大成分を正確に推定できるが、$rgg n3/2$のとき失敗する。
論文 参考訳（メタデータ） (2022-11-10T00:40:37Z) - Learning a Single Neuron with Adversarial Label Noise via Gradient
Descent [50.659479930171585]
モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。
学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
論文 参考訳（メタデータ） (2022-06-17T17:55:43Z) - $O(N^2)$ Universal Antisymmetry in Fermionic Neural Networks [107.86545461433616]
我々は、置換同変アーキテクチャを提案し、その上で行列式 Slater を適用して反対称性を誘導する。
FermiNetは、単一の行列式を持つ普遍近似能力があることが証明されている。
これは実装が容易であり、計算コストを$O(N2)$に下げることができる。
論文 参考訳（メタデータ） (2022-05-26T07:44:54Z) - A Law of Robustness beyond Isoperimetry [84.33752026418045]
我々は、任意の分布上でニューラルネットワークパラメータを補間する頑健性の低い$Omega(sqrtn/p)$を証明した。
次に、$n=mathrmpoly(d)$のとき、スムーズなデータに対する過度なパラメータ化の利点を示す。
我々は、$n=exp(omega(d))$ のとき、$O(1)$-Lipschitz の頑健な補間関数の存在を否定する。
論文 参考訳（メタデータ） (2022-02-23T16:10:23Z) - Suboptimality of Constrained Least Squares and Improvements via
Non-Linear Predictors [3.5788754401889014]
有界ユークリッド球における正方形損失に対する予測問題と最良の線形予測器について検討する。
最小二乗推定器に対する$O(d/n)$過剰リスク率を保証するのに十分な分布仮定について論じる。
論文 参考訳（メタデータ） (2020-09-19T21:39:46Z) - Statistical Query Lower Bounds for Tensor PCA [10.701091387118023]
Richard と Montanari が導入した PCA 問題では、$n$サンプル $mathbbEmathbfT_1:n$ of i.d. Perkins Gaussian tensors of order $k$ からなるデータセットが与えられ、$mathbbEmathbfT_1:n$ はランク 1 である。
目標は$mathbbE mathbfT_1$を見積もることである。
最適なサンプルの複雑さを鋭く分析する。
論文 参考訳（メタデータ） (2020-08-10T13:14:34Z) - Robustly Learning any Clusterable Mixture of Gaussians [55.41573600814391]
本研究では,高次元ガウス混合系の対向ロバスト条件下での効率的な学習性について検討する。
理論的に最適に近い誤り証明である$tildeO(epsilon)$の情報を、$epsilon$-corrupted $k$-mixtureで学習するアルゴリズムを提供する。
我々の主な技術的貢献は、ガウス混合系からの新しい頑健な識別可能性証明クラスターであり、これは正方形の定度証明システムによって捉えることができる。
論文 参考訳（メタデータ） (2020-05-13T16:44:12Z) - The Bethe and Sinkhorn Permanents of Low Rank Matrices and Implications
for Profile Maximum Likelihood [33.51964370430905]
我々はベーテとシンクホーンの永久体の近似の質に関する新しい限界を提供する。
先行研究における凸緩和とベーテ近似とシンクホーン近似との驚くべき関係を確立する。
論文 参考訳（メタデータ） (2020-04-06T06:40:03Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。