The Predictive Normalized Maximum Likelihood for Over-parameterized Linear Regression with Norm Constraint: Regret and Double Descent

• URL: http://arxiv.org/abs/2102.07181v1
• Date: Sun, 14 Feb 2021 15:49:04 GMT
• Title: The Predictive Normalized Maximum Likelihood for Over-parameterized Linear Regression with Norm Constraint: Regret and Double Descent
• Authors: Koby Bibas and Meir Feder
• Abstract summary: We show that modern machine learning models do not obey a trade-off between the complexity of a prediction rule and its ability to generalize. We use the recently proposed predictive normalized maximum likelihood (pNML) which is the min-max regret solution for individual data. We demonstrate the use of the pNML regret as a point-wise learnability measure on synthetic data and that it can successfully predict the double-decent phenomenon.
• Score: 12.929639356256928
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: A fundamental tenet of learning theory is that a trade-off exists between the complexity of a prediction rule and its ability to generalize. The double-decent phenomenon shows that modern machine learning models do not obey this paradigm: beyond the interpolation limit, the test error declines as model complexity increases. We investigate over-parameterization in linear regression using the recently proposed predictive normalized maximum likelihood (pNML) learner which is the min-max regret solution for individual data. We derive an upper bound of its regret and show that if the test sample lies mostly in a subspace spanned by the eigenvectors associated with the large eigenvalues of the empirical correlation matrix of the training data, the model generalizes despite its over-parameterized nature. We demonstrate the use of the pNML regret as a point-wise learnability measure on synthetic data and that it can successfully predict the double-decent phenomenon using the UCI dataset.

Related papers

• Revisiting Optimism and Model Complexity in the Wake of Overparameterized Machine Learning [6.278498348219108]
  We revisit model complexity from first principles, by first reinterpreting and then extending the classical statistical concept of (effective) degrees of freedom. We demonstrate the utility of our proposed complexity measures through a mix of conceptual arguments, theory, and experiments.
  arXiv  Detail & Related papers  (2024-10-02T06:09:57Z)
• Scaling and renormalization in high-dimensional regression [72.59731158970894]
  This paper presents a succinct derivation of the training and generalization performance of a variety of high-dimensional ridge regression models. We provide an introduction and review of recent results on these topics, aimed at readers with backgrounds in physics and deep learning.
  arXiv  Detail & Related papers  (2024-05-01T15:59:00Z)
• A PAC-Bayesian Perspective on the Interpolating Information Criterion [54.548058449535155]
  We show how a PAC-Bayes bound is obtained for a general class of models, characterizing factors which influence performance in the interpolating regime. We quantify how the test error for overparameterized models achieving effectively zero training error depends on the quality of the implicit regularization imposed by e.g. the combination of model, parameter-initialization scheme.
  arXiv  Detail & Related papers  (2023-11-13T01:48:08Z)
• Analysis of Interpolating Regression Models and the Double Descent Phenomenon [3.883460584034765]
  It is commonly assumed that models which interpolate noisy training data are poor to generalize. The best models obtained are overparametrized and the testing error exhibits the double descent behavior as the model order increases. We derive a result based on the behavior of the smallest singular value of the regression matrix that explains the peak location and the double descent shape of the testing error as a function of model order.
  arXiv  Detail & Related papers  (2023-04-17T09:44:33Z)
• Optimal regularizations for data generation with probabilistic graphical models [0.0]
  Empirically, well-chosen regularization schemes dramatically improve the quality of the inferred models. We consider the particular case of L 2 and L 1 regularizations in the Maximum A Posteriori (MAP) inference of generative pairwise graphical models.
  arXiv  Detail & Related papers  (2021-12-02T14:45:16Z)
• On the Double Descent of Random Features Models Trained with SGD [78.0918823643911]
  We study properties of random features (RF) regression in high dimensions optimized by gradient descent (SGD) We derive precise non-asymptotic error bounds of RF regression under both constant and adaptive step-size SGD setting. We observe the double descent phenomenon both theoretically and empirically.
  arXiv  Detail & Related papers  (2021-10-13T17:47:39Z)
• Information-Theoretic Generalization Bounds for Iterative Semi-Supervised Learning [81.1071978288003]
  In particular, we seek to understand the behaviour of the em generalization error of iterative SSL algorithms using information-theoretic principles. Our theoretical results suggest that when the class conditional variances are not too large, the upper bound on the generalization error decreases monotonically with the number of iterations, but quickly saturates.
  arXiv  Detail & Related papers  (2021-10-03T05:38:49Z)
• A Farewell to the Bias-Variance Tradeoff? An Overview of the Theory of Overparameterized Machine Learning [37.01683478234978]
  The rapid recent progress in machine learning (ML) has raised a number of scientific questions that challenge the longstanding dogma of the field. One of the most important riddles is the good empirical generalization of over parameterized models.
  arXiv  Detail & Related papers  (2021-09-06T10:48:40Z)
• Good Classifiers are Abundant in the Interpolating Regime [64.72044662855612]
  We develop a methodology to compute precisely the full distribution of test errors among interpolating classifiers. We find that test errors tend to concentrate around a small typical value $varepsilon*$, which deviates substantially from the test error of worst-case interpolating model. Our results show that the usual style of analysis in statistical learning theory may not be fine-grained enough to capture the good generalization performance observed in practice.
  arXiv  Detail & Related papers  (2020-06-22T21:12:31Z)
• An Investigation of Why Overparameterization Exacerbates Spurious Correlations [98.3066727301239]
  We identify two key properties of the training data that drive this behavior. We show how the inductive bias of models towards "memorizing" fewer examples can cause over parameterization to hurt.
  arXiv  Detail & Related papers  (2020-05-09T01:59:13Z)
• Optimal Regularization Can Mitigate Double Descent [29.414119906479954]
  We study whether the double-descent phenomenon can be avoided by using optimal regularization. We demonstrate empirically that optimally-tuned $ell$ regularization can double descent for more general models, including neural networks.
  arXiv  Detail & Related papers  (2020-03-04T05:19:09Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.