論文の概要: 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によって可能であると推測された。
次元自由係数を持つ双線型ラデマッハ形式は、特にアロン、ヘフェッツ、クリヴェレーヴィチ、ティオムキンによって予想されるエッジ統計学予想の密度のケースで自然に生じる。
この予想のケースはクワンとソーアマンによって解決された。
クワン、スダコフ、トランの著作におけるメカ=グエン=ヴー古典的境界への上訴を、我々のすぐに証明された結果と置き換えることで、エッジ統計学予想の密接なケースのさらなる証明が得られた。
関連論文リスト
- A Unified Framework for Uniform Signal Recovery in Nonlinear Generative
Compressed Sensing [68.80803866919123]
非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。
本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。
また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
論文 参考訳(メタデータ) (2023-09-25T17:54:19Z) - 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) - Adversarial Examples in Random Neural Networks with General Activations [14.12513604585194]
逆の例は、サブ指数幅とReLUまたはスムーズなアクティベーションを持つ2層ネットワークでユビキタスである。
逆の例 $boldsymbol x'$ が勾配の方向に沿って高い確率で見つかることを示す。
論文 参考訳(メタデータ) (2022-03-31T17:36:15Z) - Provable Robustness of Adversarial Training for Learning Halfspaces with
Noise [95.84614821570283]
ラベル雑音の存在下での敵対的ロバストなハーフスペースの特性を分析する。
我々の知る限りでは、これは敵の訓練がノイズの分類子を与えることを示す最初の研究である。
論文 参考訳(メタデータ) (2021-04-19T16:35:38Z) - On the computational and statistical complexity of over-parameterized
matrix sensing [30.785670369640872]
FGD法(Factorized Gradient Descend)を用いた低ランク行列検出の解法を検討する。
分解行列 $mathbff$ を分離列空間に分解することにより、$|mathbff_t - mathbff_t - mathbfx*|_f2$ が統計誤差に収束することを示す。
論文 参考訳(メタデータ) (2021-01-27T04:23:49Z) - Extensions to the Proximal Distance Method of Constrained Optimization [7.813460653362097]
損失 $f(boldsymbolx)$ を S$ の $boldsymbolx の形に制約する問題について検討する。
融合制約は、滑らかさ、疎さ、あるいはより一般的な制約パターンをキャプチャすることができる。
論文 参考訳(メタデータ) (2020-09-02T03:32:41Z) - Optimal Combination of Linear and Spectral Estimators for Generalized
Linear Models [59.015960528781115]
最適に $hatboldsymbol xrm L$ と $hatboldsymbol xrm s$ を組み合わせる方法を示す。
我々は,$(boldsymbol x, hatboldsymbol xrm L, hatboldsymbol xrm s)$の制限分布を確立するために,Adroximate Message Passing (AMP)アルゴリズムの設計と解析を行う。
論文 参考訳(メタデータ) (2020-08-07T18:20:05Z) - Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and
ReLUs under Gaussian Marginals [49.60752558064027]
ガウス境界の下では、半空間とReLUを不可知的に学習する基本的な問題について検討する。
我々の下限は、これらのタスクの現在の上限が本質的に最良のものであるという強い証拠を与える。
論文 参考訳(メタデータ) (2020-06-29T17:10:10Z) - A Concentration of Measure and Random Matrix Approach to Large
Dimensional Robust Statistics [45.24358490877106]
本稿では,データコレクションである$X = (x_1,ldots,x_n)$を,$x_i = sqrt tau_i z_i + m$で推定する。
我々は、この半測度と測度引数の集中を利用して、ロバストな推定器の存在と特異性を証明し、その制限スペクトル分布を評価する。
論文 参考訳(メタデータ) (2020-06-17T09:02:26Z) - Agnostic Learning of a Single Neuron with Gradient Descent [92.7662890047311]
期待される正方形損失から、最も適合した単一ニューロンを学習することの問題点を考察する。
ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。
ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。
論文 参考訳(メタデータ) (2020-05-29T07:20:35Z) - On the robustness of the minimum $\ell_2$ interpolator [2.918940961856197]
一般高次元線形回帰フレームワークにおいて最小$ell$-norm$hatbeta$で補間を解析する。
高い確率で、この推定器の予測損失は、上から$(|beta*|2r_cn(Sigma)vee |xi|2)/n$で有界であることを証明する。
論文 参考訳(メタデータ) (2020-03-12T15:12:28Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。