On the resilience of the quadratic Littlewood-Offord problem

• URL: http://arxiv.org/abs/2402.10504v2
• Date: Mon, 5 Aug 2024 08:22:56 GMT
• Title: On the resilience of the quadratic Littlewood-Offord problem
• Abstract summary: We study the statistical resilience of the anti-concentration properties of Rademacher computations in face of adversarial noise. Special emphasis is put on bilinear and quadratic forms, for which strengthened estimates are attained.
• Score: 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.

Related papers

• Self-Normalized Martingales and Uniform Regret Bounds for Linear Regression [65.82017723631897]
  We show that scale-invariant upper bounds on self-normalized martingales are possible.<n>We derive a self-normalized concentration inequality free of the usual regularization penalties.
  arXiv  Detail & Related papers  (2026-05-02T22:39:00Z)
• Are Stochastic Multi-objective Bandits Harder than Single-objective Bandits? [4.452583096196013]
  Multi-objective bandits have attracted increasing attention because of their broad applicability and elegance, where the reward of each arm is a multi-dimensional vector rather than a scalar.<n>A long-standing question in this area is whether performance is harder to optimize because of this added complexity.<n>We develop a new algorithm that achieves the minimum marginal regret of order (fracKlog Tgdagger)
  arXiv  Detail & Related papers  (2026-04-08T13:48:54Z)
• Regularized Online RLHF with Generalized Bilinear Preferences [68.44113000390544]
  We consider the problem of contextual online RLHF with general preferences.<n>We adopt the Generalized Bilinear Preference Model to capture preferences via low-rank, skew-symmetric matrices.<n>We prove that the dual gap of the greedy policy is bounded by the square of the estimation error.
  arXiv  Detail & Related papers  (2026-02-26T15:27:53Z)
• Optimism Stabilizes Thompson Sampling for Adaptive Inference [9.558593674952654]
  Thompson sampling (TS) is widely used for multi-armed bandits, yet its inferential properties under adaptive data collection are subtle.<n>We study this phenomenon in the $K$-armed Gaussian bandit and identify emphoptimism as a key mechanism for restoring emphstability<n>We prove that variance-inflated TS citephalder2025stable is stable for any $K ge 2$, including the challenging regime where multiple arms are optimal.
  arXiv  Detail & Related papers  (2026-02-05T18:52:54Z)
• Row-stochastic matrices can provably outperform doubly stochastic matrices in decentralized learning [10.686669655748702]
  Decentralized learning often involves a weighted global loss with heterogeneous node weights $$.<n>We develop a weighted Hilbert-space framework $L2(mathbbRd)$ and obtain convergence rates that are strictly tighter than those from Euclidean analysis.<n>We then derive sufficient conditions under which the row-stochastic design converges faster even with a smaller spectral gap.
  arXiv  Detail & Related papers  (2025-11-24T02:58:38Z)
• Regret Bounds for Robust Online Decision Making [49.1574468325115]
  We propose a framework which generalizes "decision making with structured observations" In this framework, each model associates each decision with a convex set of probability distributions over outcomes. We then derive a theory of regret bounds for this framework.
  arXiv  Detail & Related papers  (2025-04-09T12:25:00Z)
• On the Injective Norm of Sums of Random Tensors and the Moments of Gaussian Chaoses [2.918940961856197]
  We prove an upper bound on the expected $ell_p$ injective norm of sums of subgaussian random tensors. Our proof is simple and does not rely on any explicit geometric or chaining arguments.
  arXiv  Detail & Related papers  (2025-03-13T17:31:51Z)
• Tensor cumulants for statistical inference on invariant distributions [49.80012009682584]
  We show that PCA becomes computationally hard at a critical value of the signal's magnitude. We define a new set of objects, which provide an explicit, near-orthogonal basis for invariants of a given degree. It also lets us analyze a new problem of distinguishing between different ensembles.
  arXiv  Detail & Related papers  (2024-04-29T14:33:24Z)
• On Ranking-based Tests of Independence [0.0]
  We develop a novel nonparametric framework to test the independence of two random variables $mathbfX$ and $mathbfY$. We consider a wide class of rank statistics encompassing many ways of deviating from the diagonal in the ROC space to build tests of independence.
  arXiv  Detail & Related papers  (2024-03-12T10:00:00Z)
• A measure of chaos from eigenstate thermalization hypothesis [0.0]
  Eigenstate thermalization hypothesis is a detailed statement of the matrix elements of few-body operators in energy eigenbasis of a chaotic Hamiltonian. We propose that the exponent ($gamma>0$) is a measure of quantum chaos.
  arXiv  Detail & Related papers  (2024-01-24T18:01:49Z)
• High Probability Guarantees for Random Reshuffling [4.794366598086316]
  We consider the gradient method with random reshuffling ($mathsfRR$) for tackling optimisation problems. We provide first-order complexity guarantees for the method. We derive that $mathsfp$-$mathsfRR$provably escapes strict points and a high tail.
  arXiv  Detail & Related papers  (2023-11-20T15:17:20Z)
• Exact Non-Oblivious Performance of Rademacher Random Embeddings [79.28094304325116]
  This paper revisits the performance of Rademacher random projections. It establishes novel statistical guarantees that are numerically sharp and non-oblivious with respect to the input data.
  arXiv  Detail & Related papers  (2023-03-21T11:45:27Z)
• Average-Case Complexity of Tensor Decomposition for Low-Degree Polynomials [93.59919600451487]
  "Statistical-computational gaps" occur in many statistical inference tasks. We consider a model for random order-3 decomposition where one component is slightly larger in norm than the rest. We show that tensor entries can accurately estimate the largest component when $ll n3/2$ but fail to do so when $rgg n3/2$.
  arXiv  Detail & Related papers  (2022-11-10T00:40:37Z)
• Reproducible Bandits [95.8830340560603]
  A policy in the bandit environment is called reproducible if it pulls, with high probability, the exact same sequence of arms in two different executions. We show that not only do reproducible policies exist, but also they achieve almost the same optimal (non-reproducible) regret bounds in terms of the time horizon. Our results show that even though randomization is crucial for the exploration-exploitation trade-off, an optimal balance can still be achieved while pulling the exact same arms in two different rounds of executions.
  arXiv  Detail & Related papers  (2022-10-04T20:36:45Z)
• Learning a Single Neuron with Adversarial Label Noise via Gradient Descent [50.659479930171585]
  We study a function of the form $mathbfxmapstosigma(mathbfwcdotmathbfx)$ for monotone activations. The goal of the learner is to output a hypothesis vector $mathbfw$ that $F(mathbbw)=C, epsilon$ with high probability.
  arXiv  Detail & Related papers  (2022-06-17T17:55:43Z)
• Random Rank: The One and Only Strategyproof and Proportionally Fair Randomized Facility Location Mechanism [103.36492220921109]
  We show that although Strong Proportionality is a well-motivated and basic axiom, there is no deterministic strategyproof mechanism satisfying the property. We then identify a randomized mechanism called Random Rank which satisfies Strong Proportionality in expectation. Our main characterizes Random Rank as the unique mechanism that achieves universal truthfulness, universal anonymity, and Strong Proportionality in expectation.
  arXiv  Detail & Related papers  (2022-05-30T00:51:57Z)
• $O(N^2)$ Universal Antisymmetry in Fermionic Neural Networks [107.86545461433616]
  We propose permutation-equivariant architectures, on which a determinant Slater is applied to induce antisymmetry. FermiNet is proved to have universal approximation capability with a single determinant, namely, it suffices to represent any antisymmetric function. We substitute the Slater with a pairwise antisymmetry construction, which is easy to implement and can reduce the computational cost to $O(N2)$.
  arXiv  Detail & Related papers  (2022-05-26T07:44:54Z)
• A Law of Robustness beyond Isoperimetry [84.33752026418045]
  We prove a Lipschitzness lower bound $Omega(sqrtn/p)$ of robustness of interpolating neural network parameters on arbitrary distributions. We then show the potential benefit of overparametrization for smooth data when $n=mathrmpoly(d)$. We disprove the potential existence of an $O(1)$-Lipschitz robust interpolating function when $n=exp(omega(d))$.
  arXiv  Detail & Related papers  (2022-02-23T16:10:23Z)
• A PDE-Based Analysis of the Symmetric Two-Armed Bernoulli Bandit [1.2183405753834562]
  This work addresses a version of the two-armed Bernoulli bandit problem where the sum of the means of the arms is one. We obtain the leading order terms of the minmax optimal regret and pseudoregret for this problem by associating each of them with a solution of a linear heat equation.
  arXiv  Detail & Related papers  (2022-02-11T17:03:18Z)
• A Weaker Faithfulness Assumption based on Triple Interactions [89.59955143854556]
  We propose a weaker assumption that we call $2$-adjacency faithfulness. We propose a sound orientation rule for causal discovery that applies under weaker assumptions.
  arXiv  Detail & Related papers  (2020-10-27T13:04:08Z)
• Probabilistic Sequential Shrinking: A Best Arm Identification Algorithm for Stochastic Bandits with Corruptions [91.8283876874947]
  We consider a best arm identification (BAI) problem for Sequential bandits with adversarial corruptions in the fixed-budget setting of T steps. We design a novel randomized algorithm, Probabilistic Shrinking($u$) (PSS($u$)), which is agnostic to the amount of corruptions. We show that when the CPS is sufficiently large, no algorithm can achieve a BAI probability tending to $1$ as $Trightarrow infty$.
  arXiv  Detail & Related papers  (2020-10-15T17:34:26Z)
• Online and Distribution-Free Robustness: Regression and Contextual Bandits with Huber Contamination [29.85468294601847]
  We revisit two classic high-dimensional online learning problems, namely linear regression and contextual bandits. We show that our algorithms succeed where conventional methods fail.
  arXiv  Detail & Related papers  (2020-10-08T17:59:05Z)
• Suboptimality of Constrained Least Squares and Improvements via Non-Linear Predictors [3.5788754401889014]
  We study the problem of predicting as well as the best linear predictor in a bounded Euclidean ball with respect to the squared loss. We discuss additional distributional assumptions sufficient to guarantee an $O(d/n)$ excess risk rate for the least squares estimator.
  arXiv  Detail & Related papers  (2020-09-19T21:39:46Z)
• Statistical Query Lower Bounds for Tensor PCA [10.701091387118023]
  In the PCA problem introduced by Richard and Montanari, one is given a dataset consisting of $n$ samples $mathbbEmathbfT_1:n$ of i.i.d. Perkins Gaussian tensors of order $k$ with the promise that $mathbbEmathbfT_1:n$ is a rank-1. The goal is to estimate $mathbbE mathbfT_1$, but no time estimator is known. We provide a sharp analysis of the optimal sample complexity
  arXiv  Detail & Related papers  (2020-08-10T13:14:34Z)
• Robustly Learning any Clusterable Mixture of Gaussians [55.41573600814391]
  We study the efficient learnability of high-dimensional Gaussian mixtures in the adversarial-robust setting. We provide an algorithm that learns the components of an $epsilon$-corrupted $k$-mixture within information theoretically near-optimal error proofs of $tildeO(epsilon)$. Our main technical contribution is a new robust identifiability proof clusters from a Gaussian mixture, which can be captured by the constant-degree Sum of Squares proof system.
  arXiv  Detail & Related papers  (2020-05-13T16:44:12Z)
• The Bethe and Sinkhorn Permanents of Low Rank Matrices and Implications for Profile Maximum Likelihood [33.51964370430905]
  We provide new bounds on the quality of approximation of the Bethe and Sinkhorn permanents. We establish a surprising connection between the convex relaxation in prior work and the well-studied Bethe and Sinkhorn approximations.
  arXiv  Detail & Related papers  (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]
  We study an extension of the classic multi-armed bandit problem which involves multiple plays and Markovian rewards in the rested bandits setting. In order to tackle this problem we consider an adaptive allocation rule which at each stage combines the information from the sample means of all the arms, with the Kullback-Leibler upper confidence bound of a single arm which is selected in round-robin way.
  arXiv  Detail & Related papers  (2020-01-30T08:09:01Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.