Recognition: unknown
The Gaussian min-max theorem in the Presence of Convexity
read the original 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.
This paper has not been read by Pith yet.
Forward citations
Cited by 4 Pith papers
-
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.
-
When Does $\ell_2$-Boosting Overfit Benignly? High-Dimensional Risk Asymptotics and the $\ell_1$ Implicit Bias
ℓ₂-boosting localizes noise into sparse sets under isotropic pure-noise models, yielding excess variance Θ(σ²/log(p/n)) instead of linear decay, with a tuning-free early stopping rule attaining minimax ℓ₁ rates.
-
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...
-
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 Gaussia...
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.