論文の概要: On the resilience of the quadratic Littlewood-Offord problem
- arxiv url: http://arxiv.org/abs/2402.10504v2
- Date: Mon, 5 Aug 2024 08:22:56 GMT
- ステータス: 処理完了
- システム内更新日: 2024-08-06 23:36:13.570863
- Title: On the resilience of the quadratic Littlewood-Offord problem
- Title（参考訳）: 二次リトルウッド・オフォード問題のレジリエンスについて
- Authors: Elad Aigner-Horev, Daniel Rosenberg, Roi Weiss,
- Abstract要約: 本稿では,Rademacher計算の反集束特性の統計的レジリエンスについて検討する。
双線型形式と二次形式に特に重点を置いており、より強く見積もられている。
- 参考スコア（独自算出の注目度）: 5.3390449198644445
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the statistical resilience of the anti-concentration properties of Rademacher polynomials in face of adversarial deterministic noise taking the form of sign-flips. Given a multilinear polynomial $f:\mathbb{R}^n \to \mathbb{R}$ and a Rademacher vector $\boldsymbol{\xi} \in \{\pm 1\}^n$ (with independent entries), our results provide probabilistic lower bound estimations on the number of sign-flips that $\boldsymbol{\xi}$ can sustain without ``inflating" the atom probability $\sup_{x \in \mathbb{R} } \mathbb{P}\{f(\boldsymbol{\xi}) = x\}$ otherwise resulting in an adversarially biased distribution. Special emphasis is put on bilinear and quadratic forms, for which strengthened estimates are attained. From a computational perspective, our results in this venue are instance-bound in such a way that allows for an efficient computation of the statistical resilience guarantees from the quadratic polynomial itself directly. All of our probabilistic lower bound resilience guarantees are asymptotically tight. On route, we provide a short proof for a new small-ball probability estimate fitting Rademacher multilinear polynomials $f: \mathbb{R}^n \to \mathbb{R}$ removeing a polylog-factor from the classical Meka-Nguyen-Vu bound provided the coefficients are independent of $n$ (dimension-free, hereafter). This removal was conjectured to be possible by Meka-Nguyen-Vu regardless of our assumption. Bilinear Rademacher forms with dimension-free coefficients arise naturally in Combinatorics and specifically in the dense case of the edge-statistics conjecture posed by Alon, Hefetz, Krivelevich, and Tyomkyn. This case of the conjecture was resolved by Kwan and Sauermann. Replacing the appeal to the Meka-Nguyen-Vu classical bound in the work of Kwan, Sudakov, and Tran with our shortly proved result attains an additional proof of the dense case of the edge-statistics conjecture.
- Abstract（参考訳）: 本研究では, 逆行列雑音に面したラデマッハ多項式の反集束特性の統計的レジリエンスについて, サインフリップの形で検討した。
多重線型多項式 $f:\mathbb{R}^n \to \mathbb{R}$ と Rademacher ベクトル $\boldsymbol{\xi} \in \{\pm 1\}^n$ (独立なエントリを持つ)が与えられたとき、我々の結果は、$\boldsymbol{\xi}$ が "inflating" なしで持続できる符号フリップ数の確率的下界推定を提供する。
双線型形式と二次形式に特に重点を置いており、より強く見積もられている。
計算の観点からは、この場所における我々の結果は、二次多項式自身から直接統計的レジリエンス保証の効率的な計算を可能にするような、インスタンスバウンドである。
確率的な低拘束力保証はすべて、漸近的に厳格です。
ルート上では、ラデマッハ多重線型多項式 $f: \mathbb{R}^n \to \mathbb{R}$ を固定した新しい小球確率推定の短い証明を与える。
この除去は、我々の仮定にかかわらず、Meka-Nguyen-Vuによって可能であると推測された。
次元自由係数を持つ双線型ラデマッハ形式は、特にアロン、ヘフェッツ、クリヴェレーヴィチ、ティオムキンによって予想されるエッジ統計学予想の密度のケースで自然に生じる。
この予想のケースはクワンとソーアマンによって解決された。
クワン、スダコフ、トランの著作におけるメカ=グエン=ヴー古典的境界への上訴を、我々のすぐに証明された結果と置き換えることで、エッジ統計学予想の密接なケースのさらなる証明が得られた。
関連論文リスト
- 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。