Restricted Eigenvalues Beyond Gaussian Width: Threshold Occupancy under Heavy Tails

• URL: http://arxiv.org/abs/2609.03504v1
• Date: Thu, 03 Sep 2026 08:05:05 GMT
• Title: Restricted Eigenvalues Beyond Gaussian Width: Threshold Occupancy under Heavy Tails
• Abstract summary: For isotropic sub-Gaussian measurements, the benchmark sample size is $1+w(A)2$, where $w(A)$ is the Gaussian width of the normalized descent cone.<n>We give an explicit and systematic negative answer to the general question as formulated there: the proposed law fails in its full dimension-free, arbitrary-set form.<n>Under isotropy, a distribution-free fallback governed by affine dimension times squared enclosing radius is sharp on this family.
• Score: 47.36630149538994
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Restricted eigenvalue (RE) bounds govern stable recovery by norm-regularized estimators. For isotropic sub-Gaussian measurements, the benchmark sample size is $1+w(A)^2$, where $w(A)$ is the Gaussian width of the normalized descent cone. The COLT 2015 open-problem note (Banerjee et al., 2015) asked whether the same law follows for heavy-tailed designs from a uniform small-ball condition alone. We give an explicit and systematic negative answer to the general question as formulated there: the proposed law fails in its full dimension-free, arbitrary-set form, and the missing obstruction is simultaneous threshold occupancy. A constant-width polyhedral descent cone with fixed small-ball constants has zero empirical RE on every sample path up to half the ambient dimension. More generally, every finite range space admits exact threshold encoding in an arbitrarily narrow spherical cap and a lift to a full polyhedral descent-cone section. For every fixed threshold VC dimension $d$, as $β\downarrow0$, the sharp worst-case sample complexity is $Θ(β^{-1}[d\log(1/β)+\log(1/δ)])$. The separation persists under exact isotropy and all finite moments: on the same constant-width cone, Gaussian measurements succeed with $O(1+\log(1/δ))$ samples, whereas an isotropic heavy-tailed design fails pathwise for $n\lesssim\sqrt{p/\log p}$. Gaussian smoothing yields an everywhere-positive $C^\infty$ density while retaining arbitrarily poor RE. Under isotropy, a distribution-free fallback governed by affine dimension times squared enclosing radius is sharp on this family.

Related papers

• Constrained Online Learning with Noisy Constraint Values [55.29259818039367]
  Under common feasibility, our LEDGER algorithm attains $O(sqrt T)$ expected regret and $O(sqrtTlog(eT))$ expected budget violation.<n>Neither a Slater condition, independence between feedback channels, nor an absolute constraint-value bound is needed.
  arXiv  Detail & Related papers  (2026-09-07T01:38:41Z)
• Demixing Sparse Signals from Nonlinear Observations using Generalized Non-convex Regularization [0.0]
  We consider the recovery of a pair of sparse vectors from a limited number of nonlinear observations of their superposition.<n>We propose a regularization-based framework combining a Huberized data fidelity with generalized folded-concave penalties.<n>We derive estimation error bounds of order $sqrtslog(n)/m$ that hold at emphevery localized stationary point.
  arXiv  Detail & Related papers  (2026-07-12T07:29:39Z)
• Non-asymptotic Tail Bounds for the Kostlan--Shub--Smale Field: Tensor PCA and Spherical $k$-Spin Complexity [0.6627152091494143]
  This paper builds a hierarchy of explicit, non-asymptotic tail bounds for the supremum of the Kostlan--Shub--Smale random field on the sphere.<n>It applies it to two problems: Spiked PCA and the landscape of the spherical $k$-spin model.
  arXiv  Detail & Related papers  (2026-06-16T08:27:25Z)
• A Temporal Spatial Minimax Rate for Smoothly-Varying Distributions in Wasserstein Space [0.0]
  We study the minimax rate of estimating a future value $_t_n+h$ of a curve $tmapsto_t$ in the $2$-Wasserstein space.<n>Our central result is a unified temporal-spatial minimax lower bound: over regular, locally transport-rich subclasses.
  arXiv  Detail & Related papers  (2026-06-05T14:43:10Z)
• Matching Rates and Optimal Allocation for Federated Probe-Logit Distillation under Heterogeneous Bandwidth Budgets [12.805268849262243]
  In language modeling, $K$ nodes each hold $n$ samples but cannot pool data or exchange full-precision gradients or weights.<n>We study the minimax rate at which a conditional distribution over $V$ tokens can be estimated when each node may upload at most $B$ bits per query in a public probe set.
  arXiv  Detail & Related papers  (2026-05-28T09:08:39Z)
• Optimal Dimension-Free Sampling for Regularized Classification [56.72526267755301]
  We prove optimal sampling bounds achieving $(1pmvarepsilon)$-relative error for a broad class of Lipschitz continuous classification loss functions.<n>This includes important functions such as logistic and sigmoid loss, hinge loss, and ReLU loss, as prominent and popular representative examples.
  arXiv  Detail & Related papers  (2026-05-22T15:05:33Z)
• Breaking the Finite-Sample Barrier in Entropy Coupling [9.251944578856843]
  Dependence among marginally constrained observations can break a finite-sample barrier.<n>We formalize this phenomenon by introducing the emphminimum list entropy coupling $H(P|Q_1,dots,Q_m)$.<n>We show that the same framework formalizes finite-sample limits in distribution-matching representation learning and randomness extraction.
  arXiv  Detail & Related papers  (2026-05-15T17:39:57Z)
• Provably Adaptive Linear Approximation for the Shapley Value and Beyond [73.0940890296463]
  A fundamental and long-standing challenge is their efficient approximation.<n>We develop a linear-space algorithm that requires $P(|hatboldsymbol-boldsymbol|_2geq)leq $ for all commonly used semi-values.<n>Our algorithm allows explicit minimization of the mean square error for each specific utility function.
  arXiv  Detail & Related papers  (2026-04-09T16:38:14Z)
• Dimension-Independent Convergence of Underdamped Langevin Monte Carlo in KL Divergence [50.719298242863744]
  Underdamped Langevin dynamics (ULD) is a widely-used sampler for Gibbs distributions $propto e-V$.<n>We prove the first dimension-free KL divergence bounds for discretized ULD.
  arXiv  Detail & Related papers  (2026-03-02T22:14:38Z)
• Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
  Recent studies show that a reproducing kernel Hilbert space (RKHS) is not a suitable space to model functions by neural networks. In this paper, we study a suitable function space for over- parameterized two-layer neural networks with bounded norms.
  arXiv  Detail & Related papers  (2024-04-29T15:04:07Z)

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.