論文の概要: 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によって可能であると推測された。 次元自由係数を持つ双線型ラデマッハ形式は、特にアロン、ヘフェッツ、クリヴェレーヴィチ、ティオムキンによって予想されるエッジ統計学予想の密度のケースで自然に生じる。 この予想のケースはクワンとソーアマンによって解決された。 クワン、スダコフ、トランの著作におけるメカ=グエン=ヴー古典的境界への上訴を、我々のすぐに証明された結果と置き換えることで、エッジ統計学予想の密接なケースのさらなる証明が得られた。

関連論文リスト

• 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)

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

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