論文の概要: 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 14:56:56.904151
• Title: Resilience of Rademacher chaos of low degree
• Title（参考訳）: 低次ラデマチャーカオスのレジリエンス
• Authors: Elad Aigner-Horev, Daniel Rosenberg, Roi Weiss,
• Abstract要約: ラデマッハカオスのレジリエンスは、カオスが持続できる敵のサインフリップの最大数である。 我々はRadecherカオスの弾力性に関する確率的低バウンド保証を提供する。 次数2のラデマッハカオスと次数2のラデマッハカオスは,同じ概念的枠組みで確立されているが,大きな違いがある。
• 参考スコア（独自算出の注目度）: 5.3390449198644445
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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 によるランダムテンソルの集中結果に代えられる。 我々の結果はインスタンスに依存しており、カオスの順序が一定であれば、レジリエンスの効率的な計算を可能にする。

関連論文リスト

• Regret Bounds for Robust Online Decision Making [49.1574468325115]
  構造化された観察による意思決定」を一般化する枠組みを提案する。 この枠組みでは、各モデルは各決定を結果に対する確率分布の凸集合と関連付ける。 次に、この枠組みに対する後悔の束縛の理論を導出します。
  論文  参考訳（メタデータ） (2025-04-09T12:25:00Z)
• On the Injective Norm of Sums of Random Tensors and the Moments of Gaussian Chaoses [2.918940961856197]
  我々は、下ガウス乱テンソルの和の予想$ell_p$単射ノルムの上界を証明した。 我々の証明は単純であり、明示的な幾何学的あるいは連鎖的な議論には依存していない。
  論文  参考訳（メタデータ） (2025-03-13T17:31:51Z)
• Tensor cumulants for statistical inference on invariant distributions [49.80012009682584]
  我々は,PCAが信号の大きさの臨界値で計算的に困難になることを示す。 我々は、与えられた次数の不変量に対して明示的でほぼ直交的な基底を与える新しい対象の集合を定義する。 また、異なるアンサンブルを区別する新しい問題も分析できます。
  論文  参考訳（メタデータ） (2024-04-29T14:33:24Z)
• On Ranking-based Tests of Independence [0.0]
  2つの確率変数 $mathbfX$ と $mathbfY$ の独立性をテストするための新しい非パラメトリックフレームワークを開発する。 我々は、ROC空間の対角線から逸脱して独立性テストを構築する様々な方法を含む幅広い階級統計を考察する。
  論文  参考訳（メタデータ） (2024-03-12T10:00:00Z)
• High Probability Guarantees for Random Reshuffling [4.794366598086316]
  最適化問題に対処するためにランダムリシャッフル(mathsfRR$)の勾配法を検討する。 本手法の1次複雑性保証を行う。 我々は、$mathsfp$-$mathsfRR$provably escapes strict point and a high tail.
  論文  参考訳（メタデータ） (2023-11-20T15:17:20Z)
• Exact Non-Oblivious Performance of Rademacher Random Embeddings [79.28094304325116]
  本稿では,Rademacherランダムプロジェクションの性能を再検討する。 入力データに関して数値的に鋭く、曖昧でない新しい統計的保証を確立する。
  論文  参考訳（メタデータ） (2023-03-21T11:45:27Z)
• 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)
• Reproducible Bandits [95.8830340560603]
  バンディット環境におけるポリシーは、2つの異なる実行において全く同じ腕列を高い確率で引き出すと再現可能と呼ばれる。 再現可能なポリシが存在するだけでなく、時間的地平線の観点から、ほぼ同じ(再現不可能な)後悔境界を達成することを示す。 以上の結果から,無作為化が探索・探索トレードオフに不可欠であるにもかかわらず,同一の腕を2回の異なるラウンドで引き抜いて最適なバランスをとれることが示唆された。
  論文  参考訳（メタデータ） (2022-10-04T20:36:45Z)
• 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)
• Random Rank: The One and Only Strategyproof and Proportionally Fair Randomized Facility Location Mechanism [103.36492220921109]
  我々は、強い比例性は動機が良く基本的な公理であるが、その性質を満たす決定論的戦略防御機構は存在しないことを示した。 次に、予測において強い比例性を満たすランダムランクと呼ばれるランダム化メカニズムを同定する。 我々の主な特徴はランダムランクを、普遍的真理性、普遍的匿名性、期待における強い比喩性を達成するユニークなメカニズムとして特徴づけている。
  論文  参考訳（メタデータ） (2022-05-30T00:51:57Z)
• $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)
• A PDE-Based Analysis of the Symmetric Two-Armed Bernoulli Bandit [1.2183405753834562]
  この研究は、両腕のベルヌーイ・バンディット問題(英語版)(Bernoulli bandit problem)の、腕の手段の和が1であるバージョンに対処する。 我々は, それぞれの問題を線形熱方程式の解に関連付けることにより, minmax最適後悔と擬似回帰の先行順序項を得る。
  論文  参考訳（メタデータ） (2022-02-11T17:03:18Z)
• A Weaker Faithfulness Assumption based on Triple Interactions [89.59955143854556]
  より弱い仮定として, 2$-adjacency faithfulness を提案します。 より弱い仮定の下で適用可能な因果発見のための音方向規則を提案する。
  論文  参考訳（メタデータ） (2020-10-27T13:04:08Z)
• Probabilistic Sequential Shrinking: A Best Arm Identification Algorithm for Stochastic Bandits with Corruptions [91.8283876874947]
  我々は,T段の固定予算設定において,敵対的腐敗を伴う連続的包帯に対する最適な腕識別(BAI)問題を考察した。 我々は, 汚職の量に依存しない新しいランダム化アルゴリズム, Probabilistic Shrinking($u$) (PSS($u$)) を設計する。 CPS が十分に大きいとき、BAI 確率を$Trightarrow infty$ として達成できるアルゴリズムは存在しない。
  論文  参考訳（メタデータ） (2020-10-15T17:34:26Z)
• Online and Distribution-Free Robustness: Regression and Contextual Bandits with Huber Contamination [29.85468294601847]
  線形回帰と文脈的帯域幅という2つの古典的高次元オンライン学習問題を再考する。 従来の手法が失敗した場合にアルゴリズムが成功することを示す。
  論文  参考訳（メタデータ） (2020-10-08T17:59:05Z)
• 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)
• Finite-Time Analysis of Round-Robin Kullback-Leibler Upper Confidence Bounds for Optimal Adaptive Allocation with Multiple Plays and Markovian Rewards [10.66048003460524]
  本稿では,複数の演奏とマルコフ報酬を含む古典的マルチアームバンディット問題の拡張について検討する。 この問題に対処するために、各段階において、全てのアームのサンプル手段からの情報と、ラウンドロビン方式で選択された単一アームのクルバック・リーバー上信頼境界とを結合する適応的アロケーションルールを検討する。
  論文  参考訳（メタデータ） (2020-01-30T08:09:01Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。