A Geometric Phase Boundary for Volume-Sampled Linear Readouts

Kihun Rhee

cs.LGAug 27, 2026

A Geometric Phase Boundary for Volume-Sampled Linear Readouts

Authors: Kihun Rhee

Abstract

Global sharpness of a sampling bound does not determine whether the bound is attainable on a particular fixed design. We study ordinary fixed-size volume sampling followed by selected unweighted least squares, with the feature pool and response fixed; subset selection is the only randomness. We first prove a globally sharp all-budget Loewner envelope for centered, full-Gram-whitened coefficient covariance. We then characterize the fixed-design question left open by global sharpness. On the positive-loss, no-coloop strict-interior domain, a feature-only geometric margin is positive if and only if every compatible residual has strict covariance slack at every strict-interior budget, whereas zero margin holds if and only if one compatible residual reaches the Loewner ceiling in at least one coefficient direction at every strict-interior budget. For real whitened designs without coloops, the phase sign is equivalently determined by a pairwise Naimark-complement minor test, which also yields an explicit lower slack certificate. Residual augmentation exposes the response-aware contraction, and a critical equal-leverage specialization identifies an explicit geometric boundary. Any verified positive lower bound on the margin therefore yields a conservative certificate for strictness and for the subset-refit variance term in fixed-query squared loss. Together, these results give a design-specific phase characterization for this finite-pool randomized linear-readout primitive.

Explore similar work

Sep 3, 2026cs.LG

Restricted Eigenvalues Beyond Gaussian Width: Threshold Occupancy under Heavy Tails

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.

Shi Fu, Huibo Xu, Qixin Zhang +1

Long-Tailed Distribution Largest Eigenvalue Decision Thresholds 3D Gaussian Splatting

Ask PDF

May 2, 2026cs.LG

Linear-Readout Floors and Threshold Recovery in Computation in Superposition

Two recent approaches to computation in superposition reach different recursive capacity regimes: Hänni et al. certify

\tilde{O}(d^{3/2})

computable features in width

d

via an approximate-linear recursive template, while Adler and Shavit reach near-quadratic capacity (up to logarithmic factors) using thresholded Boolean recovery. The main contribution of this paper is conceptual: we argue these results are not contradictory because they maintain different interface invariants, and we formalize the distinction. As a tool, we record a rank-trace Welch-type lower bound for biorthogonal linear readouts: for

F \gg d

, the worst-case off-diagonal cross-talk of any unit-diagonal linear readout is

Ω(d^{-1/2})

, and the bound is tight on average for unit-norm tight frames. At quadratic feature load

F=d^2

, random-support threshold recovery succeeds for sparsities

s=O(d/\log d)

, while linear readouts still incur

Ω(s/d)

average per-coordinate squared error on Bernoulli sparse states. Matching the Welch floor against the published tolerance of the Hänni correction layer explains the

d^{3/2}

scale as a compatibility threshold for that template, not a universal upper bound. Robust nonlinear reset beyond the Hänni template is left open.

Hector Borobia, Elies Seguí-Mas, Guillermina Tormo-Carbó

Readout Sparse Recovery Decision Thresholds Ceiling

Ask PDF

Aug 3, 2026cs.DS

The Condition-Number Barrier in Sparse Least Squares

In [AS21], Axiotis and Sviridenko conjectured that the linear dependence on the restricted condition number in sparse convex optimization cannot be improved by a polynomial-time algorithm. We establish their conjectured lower bound for least-squares objectives, conditional on the randomized exact-volume Small-Set Expansion Hypothesis in the weighted regular-graph formulation of Raghavendra, Steurer, and Tulsiani [RST12]. Concretely, for every fixed

γ\in(0,1]

, there is no randomized polynomial-time algorithm that, with probability at least

2/3

, returns a vector

x

such that, writing

s=\lVert x\rVert_0

\lVert Ax-b\rVert_2^2 \leq \min_{\lVert z\rVert_0\leq k}\lVert Az-b\rVert_2^2+\varepsilon \quad\text{and}\quad s=O\!\left(k\,κ_{s+k}^{\,1-γ}\right),

where

κ_r

is the restricted condition number at sparsity level

r

. The result holds even on rational instances with

A

of full column rank. The proof was first obtained using a fully automated Gemini-based agentic system developed internally at Google. The authors have verified the proof and edited it for clarity of presentation.

Honghao Lin, Vahab Mirrokni, David P. Woodruff

Convex Optimization Least Squares Optimal Sample Complexity Condition Number

Ask PDF