REVIEW 5 cited by
Computational-Statistical Gaps in Gaussian Single-Index Models
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
abstract
Single-Index Models are high-dimensional regression problems with planted structure, whereby labels depend on an unknown one-dimensional projection of the input via a generic, non-linear, and potentially non-deterministic transformation. As such, they encompass a broad class of statistical inference tasks, and provide a rich template to study statistical and computational trade-offs in the high-dimensional regime. While the information-theoretic sample complexity to recover the hidden direction is linear in the dimension $d$, we show that computationally efficient algorithms, both within the Statistical Query (SQ) and the Low-Degree Polynomial (LDP) framework, necessarily require $\Omega(d^{k^\star/2})$ samples, where $k^\star$ is a "generative" exponent associated with the model that we explicitly characterize. Moreover, we show that this sample complexity is also sufficient, by establishing matching upper bounds using a partial-trace algorithm. Therefore, our results provide evidence of a sharp computational-to-statistical gap (under both the SQ and LDP class) whenever $k^\star>2$. To complete the study, we provide examples of smooth and Lipschitz deterministic target functions with arbitrarily large generative exponents $k^\star$.
Forward citations
Cited by 5 Pith papers
-
Approximate Message Passing with Random Initialization for Phase Retrieval
Randomly initialized Bayes-optimal AMP provably achieves the weak-recovery threshold δ=1/2 and arbitrarily accurate recovery for δ>1.13 in proportional-regime noiseless phase retrieval.
-
When pre-training hurts LoRA fine-tuning: a dynamical analysis via single-index models
In a Gaussian single-index model with one-pass SGD, the LoRA escape time scales as τ(μ) log d / 2, where τ(μ) increases with pre-training strength μ and diverges for odd Hermite activations at a critical μ.
-
The Multiscale Single-Index Model: A Stylized Model for Hierarchical Feature Learning
Online SGD on the correlation loss recovers Multiscale Single-Index Model features at n=Õ(d^{K-1}) samples, matching Tensor PCA, while shallow nets cannot approximate the target under higher-chaos non-cancellation.
-
On the Implicit Flatness Bias of Sharpness-Aware Minimization: A Linear Stability Analysis with Quantitative Hyperparameter Bounds
SAM's largest Hessian eigenvalue is bounded by the cube root of bGamma/(2*rho*eta^2), so larger radius, smaller batch, or larger learning rate restrict linearly stable minima to flatter regions.
-
Joint Learning in the Gaussian Single Index Model
In Gaussian single-index models, joint gradient flow over direction and link function converges to the true regression function from either sign of initial alignment, with rate governed by the information exponent.
Discussion (0). Continue with ORCID to comment.