# A Non-Asymptotic Moreau Envelope Theory for High-Dimensional Generalized Linear Models arXiv: https://arxiv.org/abs/2210.12082 · HTML: https://mlsanity.com/paper/2210.12082/ ## Key facts - Cited by 11 papers in the map (data through 14 Oct 2026). - Builds on 32 of its 83 references that are in the map. - First posted on arXiv 21 Oct 2022. ## Builds on (most cited first, 30 of 32) - [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021) - [Understanding deep learning requires rethinking generalization](https://mlsanity.com/paper/1611.03530/) (2016) - [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014) - [Benign Overfitting in Linear Regression](https://mlsanity.com/paper/1906.11300/) (2019) - [In Search of the Real Inductive Bias: On the Role of Implicit Regularization in Deep Learning](https://mlsanity.com/paper/1412.6614/) (2014) - [Benign overfitting in ridge regression](https://mlsanity.com/paper/2009.14286/) (2020) - [Mean estimation and regression under heavy-tailed distributions--a survey](https://mlsanity.com/paper/1906.04280/) (2019) - [Learning curves of generic features maps for realistic datasets with a teacher-student model](https://mlsanity.com/paper/2102.08127/) (2021) - [Harmless interpolation of noisy data in regression](https://mlsanity.com/paper/1903.09139/) (2019) - [Classification vs regression in overparameterized regimes: Does the loss function matter?](https://mlsanity.com/paper/2005.08054/) (2020) - [A modern maximum-likelihood theory for high-dimensional logistic regression](https://mlsanity.com/paper/1803.06964/) (2018) - [A Model of Double Descent for High-dimensional Binary Linear Classification](https://mlsanity.com/paper/1911.05822/) (2019) - [Universality of empirical risk minimization](https://mlsanity.com/paper/2202.08832/) (2022) - [Uniform Convergence of Interpolators: Gaussian Width, Norm Bounds, and Benign Overfitting](https://mlsanity.com/paper/2106.09276/) (2021) - [Learning without Concentration](https://mlsanity.com/paper/1401.0304/) (2014) - [The phase transition for the existence of the maximum likelihood estimate in high-dimensional logistic regression](https://mlsanity.com/paper/1804.09753/) (2018) - [Multiple Descent: Design Your Own Generalization Curve](https://mlsanity.com/paper/2008.01036/) (2020) - [In Defense of Uniform Convergence: Generalization via derandomization with an application to interpolating predictors](https://mlsanity.com/paper/1912.04265/) (2019) - [A Precise High-Dimensional Asymptotic Theory for Boosting and Minimum-ℓ1-Norm Interpolated Classifiers](https://mlsanity.com/paper/2002.01586/) (2020) - [The Implicit Bias of Benign Overfitting](https://mlsanity.com/paper/2201.11489/) (2022) - [The Impact of Regularization on High-dimensional Logistic Regression](https://mlsanity.com/paper/1906.03761/) (2019) - [Theoretical Insights Into Multiclass Classification: A High-dimensional Asymptotic View](https://mlsanity.com/paper/2011.07729/) (2020) - [On Uniform Convergence and Low-Norm Interpolation Learning](https://mlsanity.com/paper/2006.05942/) (2020) - [Foolish Crowds Support Benign Overfitting](https://mlsanity.com/paper/2110.02914/) (2021) - [Fast Rates for Noisy Interpolation Require Rethinking the Effects of Inductive Bias](https://mlsanity.com/paper/2203.03597/) (2022) - [On the robustness of minimum norm interpolators and regularized empirical risk minimizers](https://mlsanity.com/paper/2012.00807/) (2020) - [Optimistic Rates: A Unifying Theory for Interpolation Learning and Regularization in Linear Regression](https://mlsanity.com/paper/2112.04470/) (2021) - [Tight bounds for minimum l1-norm interpolation of noisy data](https://mlsanity.com/paper/2111.05987/) (2021) - [The Likelihood Ratio Test in High-Dimensional Logistic Regression Is Asymptotically a Rescaled Chi-Square](https://mlsanity.com/paper/1706.01191/) (2017) - [The Asymptotic Distribution of the MLE in High-dimensional Logistic Models: Arbitrary Covariance](https://mlsanity.com/paper/2001.09351/) (2020) ## Built on by (most cited first, 11 of 11) - [H-Consistency Guarantees for Regression](https://mlsanity.com/paper/2403.19480/) (2024) - [Noisy Interpolation Learning with Shallow Univariate ReLU Networks](https://mlsanity.com/paper/2307.15396/) (2023) - [Preventing Model Collapse Under Overparametrization: Optimal Mixing Ratios for Interpolation Learning and Ridge Regression](https://mlsanity.com/paper/2509.22341/) (2025) - [Finite-Sample Analysis of Learning High-Dimensional Single ReLU Neuron](https://mlsanity.com/paper/2303.02255/) (2023) - [Overfitting Behaviour of Gaussian Kernel Ridgeless Regression: Varying Bandwidth or Dimensionality](https://mlsanity.com/paper/2409.03891/) (2024) - [Universality of max-margin classifiers](https://mlsanity.com/paper/2310.00176/) (2023) - [An Agnostic View on the Cost of Overfitting in (Kernel) Ridge Regression](https://mlsanity.com/paper/2306.13185/) (2023) - [Optimistic Rates for Learning from Label Proportions](https://mlsanity.com/paper/2406.00487/) (2024) - [Provable Tempered Overfitting of Minimal Nets and Typical Nets](https://mlsanity.com/paper/2410.19092/) (2024) - [Tight bounds for maximum ℓ1-margin classifiers](https://mlsanity.com/paper/2212.03783/) (2022) - [Understanding Generalization Requires Universal Induction](https://mlsanity.com/paper/2609.34458/) (2026) ## Abstract (arXiv) We prove a new generalization bound that shows for any class of linear predictors in Gaussian space, the Rademacher complexity of the class and the training error under any continuous loss ℓ can control the test error under all Moreau envelopes of the loss ℓ. We use our finite-sample bound to directly recover the "optimistic rate" of Zhou et al. (2021) for linear regression with the square loss, which is known to be tight for minimal ℓ2-norm interpolation, but we also handle more general settings where the label is generated by a potentially misspecified multi-index model. The same argument can analyze noisy interpolation of max-margin classifiers through the squared hinge loss, and establishes consistency results in spiked-covariance settings. More generally, when the loss is only assumed to be Lipschitz, our bound effectively improves Talagrand's well-known contraction lemma by a factor of two, and we prove uniform convergence of interpolators (Koehler et al. 2021) for all smooth, non-negative losses. Finally, we show that application of our generalization bound using localized Gaussian width will generally be sharp for empirical risk minimizers, establishing a non-asymptotic Moreau envelope theory for generalization that applies outside of proportional scaling regimes, handles model misspecification, and complements existing asymptotic Moreau envelope theories for M-estimation.