ℓ₂-Boosting exhibits benign overfitting with logarithmic excess variance decay Θ(σ²/log(p/n)) under isotropic noise due to ℓ₁ bias, and a subdifferential early stopping rule recovers minimax-optimal ℓ₁ rates.
The Gaussian min--max theorem in the presence of convexity
4 Pith papers cite this work. Polarity classification is still indexing.
4
Pith papers citing it
abstract
Gaussian comparison theorems are useful tools in probability theory; they are essential ingredients in the classical proofs of many results in empirical processes and extreme value theory. More recently, they have been used extensively in the analysis of non-smooth optimization problems that arise in the recovery of structured signals from noisy linear observations. We refer to such problems as Primary Optimization (PO) problems. A prominent role in the study of the (PO) problems is played by Gordon's Gaussian min-max theorem (GMT) which provides probabilistic lower bounds on the optimal cost via a simpler Auxiliary Optimization (AO) problem. Motivated by resent work of M. Stojnic, we show that under appropriate convexity assumptions the (AO) problem allows one to tightly bound both the optimal cost, as well as the norm of the solution of the (PO). As an application, we use our result to develop a general framework to tightly characterize the performance (e.g. squared-error) of a wide class of convex optimization algorithms used in the context of noisy signal recovery.
citation-role summary
background 1
method 1
citation-polarity summary
years
2026 4representative citing papers
Introduces a TAP-motivated framework and constructs explicit parameter-free spectral algorithms that achieve strong detection and weak recovery thresholds in three canonical correlated two-view models with matching lower bounds.
PRADAS derives a Bayes-optimal mirror statistic for any splitting scheme, establishes asymptotic FDR control under weak dependence, and optimizes the split ratio as a stopping time to improve power over standard equal-split methods.
In high-dimensional convex ERM with non-Gaussian data, the projection of the estimator onto a test covariate asymptotically follows the convolution of a generally non-Gaussian term with an independent centered Gaussian whose variance is the trace of the estimator covariance times the data second-mom
citing papers explorer
-
When Does $\ell_2$-Boosting Overfit Benignly? High-Dimensional Risk Asymptotics and the $\ell_1$ Implicit Bias
ℓ₂-Boosting exhibits benign overfitting with logarithmic excess variance decay Θ(σ²/log(p/n)) under isotropic noise due to ℓ₁ bias, and a subdifferential early stopping rule recovers minimax-optimal ℓ₁ rates.
-
Optimal Spectral Algorithms for Correlated Two-view Models in High Dimensions
Introduces a TAP-motivated framework and constructs explicit parameter-free spectral algorithms that achieve strong detection and weak recovery thresholds in three canonical correlated two-view models with matching lower bounds.
-
PRADAS: PRior-Assisted DAta Splitting for False Discovery Rate Control
PRADAS derives a Bayes-optimal mirror statistic for any splitting scheme, establishes asymptotic FDR control under weak dependence, and optimizes the split ratio as a stopping time to improve power over standard equal-split methods.
-
Characterization of Gaussian Universality Breakdown in High-Dimensional Empirical Risk Minimization
In high-dimensional convex ERM with non-Gaussian data, the projection of the estimator onto a test covariate asymptotically follows the convolution of a generally non-Gaussian term with an independent centered Gaussian whose variance is the trace of the estimator covariance times the data second-mom