Two-Point Deterministic Equivalence for Stochastic Gradient Dynamics in Linear Models

• URL: http://arxiv.org/abs/2502.05074v1
• Date: Fri, 07 Feb 2025 16:45:40 GMT
• Title: Two-Point Deterministic Equivalence for Stochastic Gradient Dynamics in Linear Models
• Authors: Alexander Atanasov, Blake Bordelon, Jacob A. Zavatone-Veth, Courtney Paquette, Cengiz Pehlevan,
• Abstract summary: We derive a novel deterministic equivalence for the two-point function of a random resolvent. We give a unified derivation of the performance of a wide variety of high-dimensional trained linear models with gradient descent.
• Score: 76.52307406752556
• License:
• Abstract: We derive a novel deterministic equivalence for the two-point function of a random matrix resolvent. Using this result, we give a unified derivation of the performance of a wide variety of high-dimensional linear models trained with stochastic gradient descent. This includes high-dimensional linear regression, kernel regression, and random feature models. Our results include previously known asymptotics as well as novel ones.

Related papers

• 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)
• Stochastic Gradient Descent for Gaussian Processes Done Right [86.83678041846971]
  We show that when emphdone right -- by which we mean using specific insights from optimisation and kernel communities -- gradient descent is highly effective. We introduce a emphstochastic dual descent algorithm, explain its design in an intuitive manner and illustrate the design choices. Our method places Gaussian process regression on par with state-of-the-art graph neural networks for molecular binding affinity prediction.
  arXiv  Detail & Related papers  (2023-10-31T16:15:13Z)
• High-dimensional analysis of double descent for linear regression with random projections [0.0]
  We consider linear regression problems with a varying number of random projections, where we provably exhibit a double descent curve for a fixed prediction problem. We first consider the ridge regression estimator and re-interpret earlier results using classical notions from non-parametric statistics. We then compute equivalents of the generalization performance (in terms of bias and variance) of the minimum norm least-squares fit with random projections, providing simple expressions for the double descent phenomenon.
  arXiv  Detail & Related papers  (2023-03-02T15:58:09Z)
• 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)
• Gradient flow in the gaussian covariate model: exact solution of learning curves and multiple descent structures [14.578025146641806]
  We provide a full and unified analysis of the whole time-evolution of the generalization curve. We show that our theoretical predictions adequately match the learning curves obtained by gradient descent over realistic datasets.
  arXiv  Detail & Related papers  (2022-12-13T17:39:18Z)
• Second-order regression models exhibit progressive sharpening to the edge of stability [30.92413051155244]
  We show that for quadratic objectives in two dimensions, a second-order regression model exhibits progressive sharpening towards a value that differs slightly from the edge of stability. In higher dimensions, the model generically shows similar behavior, even without the specific structure of a neural network.
  arXiv  Detail & Related papers  (2022-10-10T17:21:20Z)
• Time varying regression with hidden linear dynamics [74.9914602730208]
  We revisit a model for time-varying linear regression that assumes the unknown parameters evolve according to a linear dynamical system. Counterintuitively, we show that when the underlying dynamics are stable the parameters of this model can be estimated from data by combining just two ordinary least squares estimates.
  arXiv  Detail & Related papers  (2021-12-29T23:37:06Z)
• Estimation of Switched Markov Polynomial NARX models [75.91002178647165]
  We identify a class of models for hybrid dynamical systems characterized by nonlinear autoregressive (NARX) components. The proposed approach is demonstrated on a SMNARX problem composed by three nonlinear sub-models with specific regressors.
  arXiv  Detail & Related papers  (2020-09-29T15:00:47Z)
• Understanding Implicit Regularization in Over-Parameterized Single Index Model [55.41685740015095]
  We design regularization-free algorithms for the high-dimensional single index model. We provide theoretical guarantees for the induced implicit regularization phenomenon.
  arXiv  Detail & Related papers  (2020-07-16T13:27:47Z)
• 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)

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.