PaperlayerView exact revision on arXiv

Source-linked AI summary

Restricted Eigenvalues Beyond Gaussian Width: Threshold Occupancy under Heavy Tails

Shi Fu, Huibo Xu, Qixin Zhang, Dacheng Tao

arXiv:2609.03504v1cs.LG

TL;DR

The paper asks whether the Gaussian-width RE law extends to arbitrary heavy-tailed designs under a uniform small-ball condition. It encodes threshold range spaces into narrow descent-cone geometries and proves that simultaneous occupancy obstructs the proposed law, while isotropy still yields a dimension–radius fallback. The scope is marginal small-ball information alone; stronger moment, increment, or sparsity-specific structure is outside the impossibility claim.

  • Problem

    The paper addresses whether the dimension-free sample-size law 1 + w(A)^2 holds for arbitrary spherical sets under a uniform small-ball condition alone.

  • Method

    The paper encodes finite threshold range spaces in arbitrarily narrow spherical caps, lifts them to polyhedral descent-cone sections, and constructs heavy-tailed, isotropic, and smooth extensions.

  • Results

    The Gaussian-width law fails pathwise on constant-width cones; at threshold VC dimension d, the sharp worst-case complexity is Θ(β^-1[d log(1/β) + log(1/δ)]).

  • Takeaways & Limitations

    Simultaneous threshold occupancy, rather than Gaussian-process geometry alone, governs the unrestricted heavy-tailed problem, while isotropy provides a sharp dimension–radius fallback.

  • Takeaways & Limitations

    The impossibility concerns marginal small-ball information alone; stronger moment or increment assumptions and sparsity-specific structure may exclude the unrestricted encodings.

Abstract

from arXiv · show

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.

1. Introduction

The introduction contrasts Gaussian-width RE laws with the weaker, pointwise guarantees of small-ball conditions and presents simultaneous threshold occupancy as the obstruction. It then states pathwise counterexamples, sharp occupancy complexity, isotropic separations, and an isotropic dimension–radius fallback.

  • Background: For centered isotropic sub-Gaussian rows, the benchmark sample size is controlled by 1 + w(A)^2.Gaussian width acts as an effective dimension of the descent cone, with an additive constant covering zero-width sets.
  • The open problem: A bare small-ball condition detects each fixed direction with probability at least β but does not ensure simultaneous detection over A.Empirical RE requires one common sample to detect every relevant direction, whereas small-ball visibility is pointwise.
  • The paper's answer: The paper shows that the dimension-free Gaussian-width law does not follow from a bare small-ball condition, even for exactly isotropic designs.The results identify simultaneous threshold occupancy as the general obstruction.
  • Main contributions: Constant-width polyhedral descent cones can have zero empirical RE on every sample path whenever n ≤ m/2, despite fixed small-ball constants.This is a deterministic finite-sample obstruction rather than a rare tail event.
  • Main contributions: At threshold VC dimension d, uniform RE requires n ≳ β^-1[d log(2/β) + log(1/δ)], and this order is necessary as β ↓ 0.The sharp law applies to general spherical sets; the cone lift does not preserve the generating range space's VC dimension.
  • Main contributions: Under isotropy, affine dimension times squared enclosing radius replaces Gaussian width squared in a sharp distribution-free fallback.The paper does not assert a joint minimax formula for all complexity pairs.

2. Problem setup and proof ideas

The paper encodes finite range spaces as threshold events in arbitrarily narrow spherical caps, lifts them to polyhedral descent-cone sections, and extends the construction to isotropic designs. It also identifies a dimension–radius guarantee under isotropy.

  • Design construction: The construction uses a centered radial variable with finite moments of every order but infinite positive exponential moments.An independent Rademacher sign centers the designs.
  • Narrow-cap incidence encoding: Every finite range space is encoded in an arbitrarily narrow spherical cap without changing its threshold events.A row stores range incidences, and shrinking the perturbation drives the width to zero.
  • From finite directions to cones: A positive-orthant embedding lifts finite directions to a polyhedral descent-cone section while preserving uniform small-ball mass.A missed range annihilates an extreme ray of the lifted cone.
  • Isotropic extension: Isotropy is restored by constructing anchored Rademacher row types, whitening their near-identity covariance, and retaining the common anchor.The resulting design forms a tight frame while preserving the witness geometry.
  • Positive boundary: For centered isotropic designs, projecting onto the affine span yields a dimension–radius bound governed by q(A)r(A)^2.On the constructed family, q(A) = p and r(A)^2 ≍ k/p, matching the pathwise scale k.

3. A constant-width pathwise counterexample

The paper constructs a constant-width polyhedral descent cone and a centered directionally heavy-tailed design whose empirical RE vanishes pathwise for samples up to half the ambient dimension. The witness is a data-dependent direction that annihilates all observed row types.

  • Construction: For every even m, the paper constructs a polyhedral norm, a descent-cone section, and a centered directionally heavy-tailed design.The construction uses an m-dimensional Euclidean space and a common radial law across dimensions.
  • Pathwise failure: For every n ≤ m/2 and every sample realization, a direction in the cone annihilates every observed row, so empirical RE is zero.Assigning negative signs to observed types and extending them to a balanced sign vector produces the witness direction.
  • Geometry: The cone's normalized directions lie in an O(m^-1/2) spherical cap, yielding constant Gaussian width.The cone separates an anchor coordinate from a balanced perturbation.
  • Pathwise failure: The same sign construction shatters any prescribed m/2 types, exposing threshold occupancy as the source of the obstruction.The observed assignments extend to a balanced sign vector whose scores vanish on the sample.
  • Implication: The counterexample rules out a dimension-free Gaussian-width implication because constant-complexity cones can require measurements proportional to ambient dimension.The failure is pathwise, not a rare concentration event.

4. Threshold occupancy governs the small-ball worst case

The paper identifies simultaneous threshold occupancy as the missing ingredient in small-ball RE guarantees, encoding arbitrary finite range spaces in narrow caps and lifting them to descent-cone sections. This yields a sharp VC-dimension-dependent sample-complexity law for uniform RE.

  • A detected-row threshold count lower-bounds empirical energy, making uniform threshold coverage sufficient for RE.Each row detecting u contributes at least α^2 to the empirical energy; the paper distinguishes this sufficient condition from pointwise necessity for a fixed law.
  • Arbitrary range spaces in narrow caps: Every finite probability range space can be exactly represented by threshold events in an arbitrarily narrow spherical cap.The support-restricted threshold class has the same VC dimension as the original range system, and narrowing the cap preserves every threshold event exactly.
  • Descent-cone universality: A missed range annihilates a generator, and the construction lifts this witness to a full polyhedral descent-cone section while preserving uniform small-ball mass.The descent-cone lift transports the positive orthant through a narrow embedding; averaging preserves small-ball mass over the cone while missed ranges eliminate extreme rays.
  • The resulting obstruction is combinatorial rather than geometric: arbitrarily narrow Euclidean sets can hide finite visibility patterns that require simultaneous sample coverage.The VC formulation applies to pointwise-measurable spherical sets and makes no event simultaneous over all sample sizes.
  • VC envelope and low-mass regime: For threshold VC dimension d, uniform RE holds at n ≳ β^-1[d log(2/β)+log(1/δ)], with this order necessary for each fixed d as β ↓ 0.The lower envelope combines subset, singleton-range, and confidence mechanisms, with the fixed-d product term supplied by a sharp ε-net lower bound.

5. Isotropy does not restore Gaussian width

Exact isotropy and arbitrarily high finite moments do not reconnect Gaussian width with uniform RE: a heavy-tailed design can fail pathwise on a constant-width descent cone, while Gaussian measurements succeed quickly. Isotropy instead supports a sharp dimension–radius fallback on this family.

  • Construction: The anchored-frame construction supplies uniform small-ball mass through a common anchor and well-conditioned row submatrices.Whitening produces an exact tight frame without losing the anchor.
  • Smooth robustness: All finite moments and an everywhere-positive C∞ density still coexist with arbitrarily poor restricted eigenvalues.Gaussian smoothing removes exact kernel directions but leaves restricted energy of order τ^2.
  • Isotropic separation: Exact isotropy does not prevent pathwise zero RE on a polyhedral descent cone with constant Gaussian width.The heavy-tailed law shares covariance and small-ball constants with the Gaussian design.
  • Isotropic separation: O(1 + log(1/δ)) samples suffice for Gaussian measurements on the common cone, but heavy-tailed measurements fail for n ≲√(p/log p).The contrast holds with common absolute small-ball constants.
  • Dimension–radius fallback: For this family, isotropy yields a sharp fallback controlled by affine dimension times squared enclosing radius, not Gaussian width.Here q(Ap,k)=p and r(Ap,k)^2 ≍k/p, giving fixed-confidence complexity Θ(k).

6. Consequences and scope

The pathwise RE obstruction transfers directly to norm-regularized recovery and noisy conditioning, while the paper limits its positive mechanisms to complementary settings rather than a universal joint minimax law.

  • Recovery consequences: Zero empirical RE implies that the relevant norm-regularized estimator does not uniquely recover θ⋆.Closed spherical sections ensure a minimizing witness lies in A∩ker X.
  • Noisy recovery: When κn=0, the inverse modulus Kn is infinite, and poor restricted energy yields deterministic ill-conditioning for the realized design.On the smoothing event, Kn≥1/√(2τ) and 1/Λn≥1/(2τ^2).
  • Scope: The paper does not claim a joint minimax formula combining threshold VC complexity and dimension–radius complexity for every distribution class.The two positive mechanisms are distribution-adapted occupancy and Euclidean isotropic control.

7. Related work

Prior work connects RE and recovery to Gaussian geometry, develops small-ball complexity methods, and obtains stronger guarantees under added tail or coupling assumptions. This paper distinguishes its threshold-occupancy counterexamples from those results and earlier sparse-recovery failures.

  • Gaussian and RE theory: Gaussian width and statistical dimension connect descent cones to sharp recovery transitions, while related bounds cover broader measurement models.These include sub-Gaussian, correlated, anisotropic, and stable-rank settings.
  • Small-ball methods: Small-ball methods control nonnegative empirical processes without upper-tail concentration and extend to distribution-dependent complexities in regularized estimation.Later work relaxes uniform small-ball assumptions and studies moment-based covariance bounds.
  • Stronger assumptions: Uniform ψ1, sub-Weibull, mixed-tail, and thresholding assumptions add coupling or robustness that excludes the paper’s encoding.One cited ψ1 result uses exponential width and threshold VC dimension at n ≳d/β^2.
  • Earlier counterexamples: Earlier spiky isotropic constructions already forced sparse-recovery RE and compatibility quantities to vanish in regimes such as n log n ≲p.The companion note also records basis-pursuit failure.
  • Threshold classes: Classical VC and range-space inequalities provide the background for threshold bounds, but their exact realization in narrow spherical caps is the contribution here.The cited inequalities themselves are not new in this paper.

8. Conclusion

The paper answers the COLT 2015 question negatively: uniform small-ball visibility is pointwise, whereas empirical RE requires simultaneous coverage of all relevant directions. Threshold encodings expose the failure, while isotropy supplies only a dimension–radius fallback.

  • Conclusion: The Gaussian-width principle does not follow from a uniform small-ball condition and can fail pathwise on a constant-width descent cone.The conclusion frames the failure as a quantifier mismatch between pointwise visibility and simultaneous empirical coverage.
  • Open direction: A natural next question is which minimal structure between marginal visibility and full increment control restores Gaussian-width behavior.The paper identifies stronger increment or moment assumptions as possible routes without asserting a universal restoration theorem.
  • Proof strategy: The proof strategy combines small-ball inequalities, Gordon escape bounds, range-space estimates, and geometric cone-realization lemmas.These tools support both the counterexamples and the positive boundary.
  • Geometric realization: Finite spherical constructions are lifted to polyhedral norm descent cones so missed-range witnesses become relevant to regularizer geometry.The cone realization identifies the spherical section with normalized cone mixtures.

A.3. Range-space estimates

The range-space analysis establishes finite β-net lower bounds and clarifies that the sharp threshold β_d depends on fixed VC dimension d.

  • The lower bound follows from the Komlós et al. asymptotic estimate for the supremal minimum β-net size.
  • For fixed d ≥2 and sufficiently small β, finite full-support range spaces require β-nets of order β^-1 log(1/β).The threshold β_d may depend on d, while the numerical constant is universal.
  • The strict-versus-nonstrict measure convention is handled by rescaling the threshold and retaining ranges of mass greater than 2β.
  • The logarithmic threshold statement is not asserted uniformly in d; for VC dimension one, random sampling supplies the logarithm through coupon collection.

Appendix B. Proof of the explicit counterexample

The explicit construction encodes unseen coordinate indices into a polyhedral descent cone, producing a direction annihilated by every sample with at most half the ambient dimension.

  • The constructed maximum of finitely many absolute linear functionals defines a norm on the subspace.
  • The cone constraints are t ≥0 and t ± y_j ≥0, yielding the explicit polyhedral section used in the counterexample.
  • For n ≤m/2, the observed indices fit inside a half-sized set whose sign pattern generates a cone direction with zero measurements.
  • Balanced sign assignments shatter any selected half-sized index set, establishing the large threshold VC dimension of the construction.
  • The threshold encoding preserves the range-space incidence structure, and untruncated energy is positive exactly when every associated range is hit.
  • The represented range system can be placed at arbitrarily small Gaussian width without changing its occupancy structure.

Appendix E. Sharp threshold-complexity law

The appendix proves matching threshold-complexity bounds by combining relative VC upper bounds with explicit range-space lower bounds, then applies them to isotropic heavy-tailed constructions.

  • NRE is defined marginally over each larger sample size, so failure at one size yields a lower bound on the required threshold.
  • N ≥ C[d log(2/β) + log(1/δ)]/β suffices for uniform RE at level β/2 with probability at least 1 −δ.
  • A uniform range space of d-element subsets gives a universal d/β lower bound for hitting all ranges.
  • For VC dimension one, singleton ranges and coupon collection yield a β^-1 log(1/β) lower bound despite the absence of a deterministic-net logarithm.
  • For every fixed d as β decreases, the worst-case threshold complexity has order β^-1[d log(1/β)+log(1/δ)].
  • The isotropic construction conditions every row submatrix of size O(p/log p), then whitening preserves the relevant geometry and failure mechanism.

Appendix H. Smooth-density robustness

Gaussian smoothing replaces discrete heavy-tailed rows by a smooth positive density while preserving the construction’s poor restricted conditioning and directional heavy tails.

  • Convolution with Gaussian noise produces a density that is strictly positive everywhere and belongs to C∞, while retaining finite polynomial moments.
  • The smoothed design remains directionally heavy-tailed, with every positive exponential moment of each nonzero projection infinite.
  • The heavy component can still be annihilated by a sample-dependent descent direction, leaving the restricted energy arbitrarily small after smoothing.
  • The resulting conditioning statement is deterministic for the realized design, but its witness may depend on that realization and is not a fixed-parameter minimax lower bound.
Loading 2609.03504v1…