Hitting the High-Dimensional Notes: An ODE for SGD learning dynamics on GLMs and multi-index models
We analyze the dynamics of streaming stochastic gradient descent (SGD) in the high-dimensional limit when applied to generalized linear models and multi-index models (e.g. logistic regression, phase retrieval) with general data-covariance. In particular, we demonstrate a deterministic equivalent of SGD in the form of a system of ordinary differential equations that describes a wide class of statistics, such as the risk and other measures of sub-optimality. This equivalence holds with overwhelming probability when the model parameter count grows proportionally to the number of data. This framework allows us to obtain learning rate thresholds for stability of SGD as well as convergence guarantees. In addition to the deterministic equivalent, we introduce an SDE with a simplified diffusion coefficient (homogenized SGD) which allows us to analyze the dynamics of general statistics of SGD iterates. Finally, we illustrate this theory on some standard examples and show numerical simulations which give an excellent match to the theory.
Code (0)
등록된 구현이 없습니다.
Tasks
RetrievalMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
On Stationary-Point Hitting Time and Ergodicity of Stochastic Gradient Langevin Dynamics
Stochastic gradient Langevin dynamics (SGLD) is a fundamental algorithm in stochastic optimization. Recent work by Zhang et al. [2017] presents an analysis for the hitting time of SGLD for the first and second order stat…
Stochastic OptimizationOptimal Errors and Phase Transitions in High-Dimensional Generalized Linear Models
Generalized linear models (GLMs) arise in high-dimensional machine learning, statistics, communications and signal processing. In this paper we analyze GLMs when the data matrix is random, as relevant in problems such as…
compressed sensingVocal Bursts Intensity PredictionExploration of Multi-Element Collaborative Research and Application for Modern Power System Based on Generative Large Models
The transition to intelligent, low-carbon power systems necessitates advanced optimization strategies for managing renewable energy integration, energy storage, and carbon emissions. Generative Large Models (GLMs) provid…
ManagementSchedulingChasing Convex Functions with Long-term Constraints
We introduce and study a family of online metric problems with long-term constraints. In these problems, an online player makes decisions $\mathbf{x}_t$ in a metric space $(X,d)$ to simultaneously minimize their hitting …
A Muon-Accelerated Algorithm for Low Separation Rank Tensor Generalized Linear Models
Tensor-valued data arise naturally in multidimensional signal and imaging problems, such as biomedical imaging. When incorporated into generalized linear models (GLMs), naive vectorization can destroy their multi-way str…
Computational Efficiency