Double Descent in Random Feature Models: Precise Asymptotic Analysis for General Convex Regularization

• URL: http://arxiv.org/abs/2204.02678v1
• Date: Wed, 6 Apr 2022 08:59:38 GMT
• Title: Double Descent in Random Feature Models: Precise Asymptotic Analysis for General Convex Regularization
• Authors: David Bosch, Ashkan Panahi, Ayca \"Ozcelikkale, Devdatt Dubhash
• Abstract summary: We provide precise expressions for the generalization of regression under a broad class of convex regularization terms. We numerically demonstrate the predictive capacity of our framework, and show experimentally that the predicted test error is accurate even in the non-asymptotic regime.
• Score: 4.8900735721275055
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We prove rigorous results on the double descent phenomenon in random features (RF) model by employing the powerful Convex Gaussian Min-Max Theorem (CGMT) in a novel multi-level manner. Using this technique, we provide precise asymptotic expressions for the generalization of RF regression under a broad class of convex regularization terms including arbitrary separable functions. We further compute our results for the combination of $\ell_1$ and $\ell_2$ regularization case, known as elastic net, and present numerical studies about it. We numerically demonstrate the predictive capacity of our framework, and show experimentally that the predicted test error is accurate even in the non-asymptotic regime.

Related papers

• Statistical Inference in Classification of High-dimensional Gaussian Mixture [1.2354076490479515]
  We investigate the behavior of a general class of regularized convex classifiers in the high-dimensional limit. Our focus is on the generalization error and variable selection properties of the estimators.
  arXiv  Detail & Related papers  (2024-10-25T19:58:36Z)
• 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)
• Precise Asymptotic Analysis of Deep Random Feature Models [37.35013316704277]
  We provide exact expressions for the performance of regression by an $L-$layer deep random feature (RF) model. We characterize the variation of the eigendistribution in different layers of the equivalent Gaussian model.
  arXiv  Detail & Related papers  (2023-02-13T09:30:25Z)
• Simplex Random Features [53.97976744884616]
  We present Simplex Random Features (SimRFs), a new random feature (RF) mechanism for unbiased approximation of the softmax and Gaussian kernels. We prove that SimRFs provide the smallest possible mean square error (MSE) on unbiased estimates of these kernels. We show consistent gains provided by SimRFs in settings including pointwise kernel estimation, nonparametric classification and scalable Transformers.
  arXiv  Detail & Related papers  (2023-01-31T18:53:39Z)
• A Non-Asymptotic Moreau Envelope Theory for High-Dimensional Generalized Linear Models [33.36787620121057]
  We prove a new generalization bound that shows for any class of linear predictors in Gaussian space. We use our finite-sample bound to directly recover the "optimistic rate" of Zhou et al. (2021) We show that application of our bound generalization using localized Gaussian width will generally be sharp for empirical risk minimizers.
  arXiv  Detail & Related papers  (2022-10-21T16:16:55Z)
• Nonconvex Stochastic Scaled-Gradient Descent and Generalized Eigenvector Problems [98.34292831923335]
  Motivated by the problem of online correlation analysis, we propose the emphStochastic Scaled-Gradient Descent (SSD) algorithm. We bring these ideas together in an application to online correlation analysis, deriving for the first time an optimal one-time-scale algorithm with an explicit rate of local convergence to normality.
  arXiv  Detail & Related papers  (2021-12-29T18:46:52Z)
• 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)
• On the Generalization of Stochastic Gradient Descent with Momentum [58.900860437254885]
  We first show that there exists a convex loss function for which algorithmic stability fails to establish generalization guarantees. For smooth Lipschitz loss functions, we analyze a modified momentum-based update rule, and show that it admits an upper-bound on the generalization error. For the special case of strongly convex loss functions, we find a range of momentum such that multiple epochs of standard SGDM, as a special form of SGDEM, also generalizes.
  arXiv  Detail & Related papers  (2021-02-26T18:58:29Z)
• Asymptotic Errors for Teacher-Student Convex Generalized Linear Models (or : How to Prove Kabashima's Replica Formula) [23.15629681360836]
  We prove an analytical formula for the reconstruction performance of convex generalized linear models. We show that an analytical continuation may be carried out to extend the result to convex (non-strongly) problems. We illustrate our claim with numerical examples on mainstream learning methods.
  arXiv  Detail & Related papers  (2020-06-11T16:26:35Z)
• SLEIPNIR: Deterministic and Provably Accurate Feature Expansion for Gaussian Process Regression with Derivatives [86.01677297601624]
  We propose a novel approach for scaling GP regression with derivatives based on quadrature Fourier features. We prove deterministic, non-asymptotic and exponentially fast decaying error bounds which apply for both the approximated kernel as well as the approximated posterior.
  arXiv  Detail & Related papers  (2020-03-05T14:33:20Z)

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.