Source-linked AI summary
Optimal Regularization Can Mitigate Double Descent
Preetum Nakkiran, Prayaag Venkat, Sham Kakade, Tengyu Ma
TL;DR
Double descent makes test performance non-monotonic with sample or model size, motivating the question of whether optimal regularization can remove it. The paper studies this theoretically and empirically, finding monotonicity for certain isotropic linear models and mitigation in richer models, including neural networks.
Problem
The paper asks when optimally tuned regularization can mitigate or remove double descent in learning algorithms.
Method
The paper combines theoretical analysis of optimally tuned ℓ2-regularized ridge regression with empirical studies of more general models.
Results
For certain linear regression models with isotropic covariates, optimally tuned ℓ2 regularization gives monotonic test performance with both sample size and model size, and empirically mitigates double descent in models including neural networks.
Takeaways & Limitations
Test-risk scaling may be more informative when learning algorithms are evaluated with appropriately tuned regularization.
Takeaways & Limitations
The theory relies on isotropic covariance, and optimal ridge regression is not always sample-monotonic for non-Gaussian covariates with heteroscedastic noise.
Abstract
from arXiv · showhide
Recent empirical and theoretical studies have shown that many learning algorithms -- from linear regression to neural networks -- can have test performance that is non-monotonic in quantities such the sample size and model size. This striking phenomenon, often referred to as "double descent", has raised questions of if we need to re-think our current understanding of generalization. In this work, we study whether the double-descent phenomenon can be avoided by using optimal regularization. Theoretically, we prove that for certain linear regression models with isotropic data distribution, optimally-tuned $\ell_2$ regularization achieves monotonic test performance as we grow either the sample size or the model size. We also demonstrate empirically that optimally-tuned $\ell_2$ regularization can mitigate double descent for more general models, including neural networks. Our results suggest that it may also be informative to study the test risk scalings of various algorithms in the context of appropriately tuned regularization.
1 Introduction
The paper asks when optimal regularization can mitigate double descent and studies this question theoretically and empirically. It proves sample-wise and model-wise monotonicity for certain isotropic linear models and reports mitigation in richer models.
- 1 Introduction: The central question is whether optimally tuned regularization can mitigate or remove double descent, which is often observed in unregularized or under-regularized models.
- 1 Introduction: Optimal ℓ2 regularization yields monotonic test performance as either sample size or model size grows in certain isotropic linear regression settings.The paper presents these as non-asymptotic results for linear regression.
- 1 Introduction: Empirically, optimal ℓ2 regularization can mitigate double descent in random-feature classifiers and convolutional neural networks.
- 1 Introduction: The theoretical results are non-asymptotic and concern actual test risk rather than only generalization bounds.
- 1 Introduction: The main theory relies on isotropic covariance, while a non-Gaussian, heteroscedastic setting provides a counterexample to sample monotonicity.
- 1 Introduction: For non-isotropic Gaussian covariates, covariance-dependent regularization achieves sample-wise monotonicity, while standard ℓ2 monotonicity remains conjectural.
2 Sample Monotonicity in Ridge Ridgression
This section proves that optimally regularized ridge regression has monotonic expected test risk as samples increase under isotropic Gaussian covariates and linear response. The proof uses a risk representation based on singular values and interlacing when one sample is added.
- 2 Sample Monotonicity in Ridge Regression: The setting uses isotropic Gaussian covariates, a linear response model, and regularized least squares evaluated by expected population risk.
- 2 Sample Monotonicity in Ridge Regression: Optimally regularized isotropic linear regression has expected test risk that decreases monotonically as the number of samples increases.The result holds for every fixed ground truth and all finite sample sizes and dimensions.
- 2 Sample Monotonicity in Ridge Regression: The proof couples data matrices differing by one row and uses singular-value interlacing to compare their expected test risks.
- 2 Sample Monotonicity in Ridge Regression: The optimal ridge parameter is constant across sample sizes in this setting, simplifying the comparison of risks as data are added.
- 2 Sample Monotonicity in Ridge Regression: Over-regularized ridge regression is also monotonic in samples, extending the result beyond the exactly optimal parameter.
3 Model-wise Monotonicity in Ridge Regression
For a random-projection linear model with isotropic Gaussian covariates, optimally tuned ridge regression prevents test-risk deterioration as model size grows.
- The result applies to isotropic Gaussian covariates and linear responses under the specified random-projection model.The covariates are generated from N(0, I_p), with responses formed using an unknown linear parameter and Gaussian noise.
- The model projects p-dimensional inputs onto a random d-dimensional subspace before fitting ridge regression, with d ≤ p defining model size.The projected features are ex = Px, and ridge regression operates in the resulting d-dimensional space.
- Optimally regularized ridge regression has expected test risk monotonic in model size, so larger models are not worse than smaller models.This is the section’s main model-wise monotonicity result.
- The optimal ridge parameter is constant across model sizes in this setting.The accompanying lemma states that the optimal ridge parameter does not vary with d.
4 Counterexamples to Monotonicity
Optimal ridge regularization is not universally sample-monotonic: a non-Gaussian, heteroscedastic example has higher expected test risk with two samples than with one.
- The counterexample combines one clean coordinate with one noisy coordinate while retaining a linear conditional mean.The optimal predictor is β* = [1, 0], but the noise is heteroscedastic.
- With one sample, instance-dependent regularization can choose λ = 0 for the clean coordinate and λ = ∞ for the noisy coordinate.This adaptive choice exploits whether the observed coordinate is clean or noisy.
- With two samples hitting both coordinates, a single shared λ creates a suboptimal tradeoff between regularizing noise and estimating the clean signal.Strong regularization helps the noisy coordinate but harms estimation of the clean coordinate.
- A modified construction also yields a counterexample when λ depends only on the sample count rather than on the individual sample instance.Thus the failure is not limited to instance-dependent regularization.
- Expected test risk increases from n = 1 to n = 2 for a well-specified two-dimensional distribution with non-Gaussian covariates and heteroscedastic noise.This counterexample lies outside the jointly Gaussian isotropic setting of the main theorem.
5 Experiments
Experiments show that optimally tuned ℓ2 regularization can induce monotonic test performance across non-isotropic regression, random-feature classifiers, and convolutional networks, mitigating sample-wise and model-wise double descent.
- 5 Experiments: The experiments extend the regularization result beyond the paper’s theoretical settings to random feature classifiers and convolutional neural networks.The random-feature model is equivalent to a two-layer network with a frozen random first layer, trained with weight decay.
- 5.1 Sample Monotonicity: Optimally-regularized ridge regression is empirically monotonic in samples for non-isotropic covariates, whereas unregularized regression exhibits triple descent.The unregularized setting has peaks near n = 15 and n = d; the optimal λ varies with n.
- 5.1 Sample Monotonicity: For random ReLU features on Fashion-MNIST, optimal ℓ2 regularization makes test error monotonic as the number of samples increases.The experiment uses D = 500 random features, and the optimal ridge parameter appears constant across n.
- 5.2 Model-size Monotonicity: For random ReLU features with n = 500, optimal ℓ2 regularization prevents model-wise double descent as feature count increases.Varying feature count corresponds to varying the width of the associated two-layer neural network.
- 5.2 Model-size Monotonicity: For 5-layer CNNs on CIFAR-100, optimally regularized models have largely monotonic test error across model sizes, unlike unregularized and underregularized models.The optimal weight decay varies with model size, so no single regularization value is optimal for all models.
6 Towards Monotonicity with General Covariates
The paper extends its monotonicity analysis to non-isotropic Gaussian covariates, proving monotonicity with a covariance-dependent regularizer and conjecturing it for standard ℓ2 regularization.
- 6 Towards Monotonicity with General Covariates: For Gaussian covariates with covariance Σ, a covariance-dependent regularizer yields sample-monotonic ridge regression when λ is optimally tuned.This follows from the isotropic result by a change of variables, and Σ may potentially be estimated from unlabeled data.
- 6 Towards Monotonicity with General Covariates: The paper conjectures that standard optimally tuned ridge regression is sample-monotonic for all positive semidefinite Gaussian covariances.The conjecture states that expected test risk is monotone non-increasing in the number of samples.
- 6 Towards Monotonicity with General Covariates: A sufficient technical condition for the conjecture is numerically verified across varied settings, but remains unproved in general.The condition is established for isotropic covariates and implies the broader conjecture there.
7 Discussion and Conclusion
The discussion concludes that appropriate regularization can eliminate non-monotonic behavior in supported settings, while broader monotonicity results and explanations for practical neural-network behavior remain open.
- 7 Discussion and Conclusion: The paper reports that appropriate regularization can eliminate the non-monotonic behavior often seen in unregularized or underregularized models.Its theoretical results cover certain isotropic linear-regression models, while empirical results include more general models and neural networks.
- 7 Discussion and Conclusion: Sample-wise monotonicity for optimally tuned ridge regression with non-isotropic Gaussian covariates remains open, despite a conjecture and numerical checks.The non-isotropic setting differs because the optimal regularization can depend on the sample count.
- 7 Discussion and Conclusion: Monotonicity for broader nonlinear models remains open and may require new, potentially data-dependent regularizers near the sample-size/model-size transition.The paper notes that precise characterization of deep-model test risk remains elusive.
- 7 Discussion and Conclusion: It also remains open why large neural networks can be sample-monotonic in realistic regimes without carefully chosen regularization.
A Appendix
The appendix contains proofs of sample-monotonicity and model-size monotonicity, along with additional and omitted plots.
- A Appendix: Appendix Sections A.1 and A.2 provide the monotonicity proofs, while Section A.4 adds supplementary plots.
A.1 Sample Monotonicity Proofs
The proofs establish monotonic test risk under optimally tuned ridge regularization by comparing how singular values and their contributions change when samples are added.
- The proof strategy first determines the optimal ridge parameter, then evaluates the corresponding test risk through the preceding risk expression.
- Adding a sample preserves the relevant singular-value ordering, enabling a comparison of optimally regularized test risks.The proof uses singular-value interlacing and a coupling between data-matrix singular values.
- The resulting coupling argument implies that optimally regularized test risk is monotonic as the sample size increases.
A.2 Projection Model Proofs
The projection-model proofs reduce random-feature regression to singular-value behavior of projected data, using Gaussian projection assumptions and interlacing couplings across model sizes.
- Orthogonal projection onto a random d-dimensional subspace supplies the symmetry used to simplify the expected error terms.
- The projected model decomposes responses into projected signal, orthogonal-projection error, and observation noise.Conditioned on the projection, these components are independent, and the projection error is Gaussian.
- The risk calculation uses the projected design matrix's singular values and the independence between that matrix and the projected target coefficients.
- Increasing model size is analyzed by coupling the singular-value distributions for projected data matrices at dimensions d and d+1.The coupled singular values are interlaced, paralleling the sample-wise proof strategy.
A.3 Nonisotropic Reduction
The nonisotropic analysis reduces covariance-weighted ridge regression to the isotropic case, showing sample monotonicity when the regularizer is adapted to the input covariance.
- The reduction proves that the expected test risks of isotropic and covariance-transformed regression problems are identical.
- If the input covariance Σ is known, a Σ^-1 regularizer makes ridge regression sample-monotonic.This follows by transforming the nonisotropic problem into an equivalent isotropic one.
- The theorem considers Gaussian covariates with covariance Σ and defines optimal regularization through the minimum expected test risk.
- Under optimal regularization, the expected test risk is monotonic in the number of samples.
- The proof handles boundary and interior cases for the optimizing regularization parameter, including limits at zero and infinity.