Scaling Limit: Exact and Tractable Analysis of Online Learning Algorithms with Applications to Regularized Regression and PCA

We present a framework for analyzing the exact dynamics of a class of online learning algorithms in the high-dimensional scaling limit. Our results are applied to two concrete examples: online regularized linear regression and principal component analysis. As the ambient dimension tends to infinity, and with proper time scaling, we show that the time-varying joint empirical measures of the target feature vector and its estimates provided by the algorithms will converge weakly to a deterministic measured-valued process that can be characterized as the unique solution of a nonlinear PDE. Numerical solutions of this PDE can be efficiently obtained. These solutions lead to precise predictions of the performance of the algorithms, as many practical performance metrics are linear functionals of the joint empirical measures. In addition to characterizing the dynamic performance of online learning algorithms, our asymptotic analysis also provides useful insights. In particular, in the high-dimensional limit, and due to exchangeability, the original coupled dynamics associated with the algorithms will be asymptotically "decoupled", with each coordinate independently solving a 1-D effective minimization problem via stochastic gradient descent. Exploiting this insight for nonconvex optimization problems may prove an interesting line of future research.

• Publication year

  2017

• Venue

  arXiv.org

• Publication date

  2017-12-08

• Fields of study

  Mathematics, Computer Science

• Identifiers
  arXiv 1712.04332
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Vector Approximate Message Passing

  2019cited by this paper
• The scaling limit of high-dimensional online independent component analysis

  2017cited by this paper
• Online learning for sparse PCA in high dimensions: Exact dynamics and phase transitions

  2016cited by this paper
• Tradeoffs Between Convergence Speed and Reconstruction Accuracy in Inverse Problems

  2016cited by this paper
• Sharp Time–Data Tradeoffs for Linear Inverse Problems

  2015cited by this paper
• Phase transitions in semidefinite relaxations

  2015cited by this paper
• Time-Data Tradeoffs by Aggressive Smoothing

  2014cited by this paper
• The squared-error of generalized LASSO: A precise analysis

  2013cited by this paper
• Stochastic Approximation approach to Stochastic Programming

  2013cited by this paper
• Proximal Algorithms

  2013cited by this paper
• Living on the edge: phase transitions in convex programs with random data

  2013cited by this paper
• Sparse phase retrieval: Convex algorithms and limitations

  2013cited by this paper
• A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets

  2012cited by this paper
• Compressed Sensing

  2012cited by this paper
• Computational and statistical tradeoffs via convex relaxation

  2012cited by this paper
• Phase recovery, MaxCut and complex semidefinite programming

  2012cited by this paper
• Optimal scaling for the transient phase of the random walk Metropolis algorithm: The mean-field limit

  2012cited by this paper
• Expectation-Maximization Gaussian-Mixture Approximate Message Passing

  2012cited by this paper
• PhaseLift: Exact and Stable Signal Recovery from Magnitude Measurements via Convex Programming

  2011cited by this paper
• Hybrid Approximate Message Passing

  2011cited by this paper
• Making Gradient Descent Optimal for Strongly Convex Stochastic Optimization

  2011cited by this paper
• The Convex Geometry of Linear Inverse Problems

  2010cited by this paper
• The dynamics of message passing on dense graphs, with applications to compressed sensing

  2010cited by this paper
• Generalized approximate message passing for estimation with random linear mixing

  2010cited by this paper
• This is SPIRAL-TAP: Sparse Poisson Intensity Reconstruction ALgorithms—Theory and Practice

  2010cited by this paper
• Primal-dual subgradient methods for minimizing uniformly convex functions

  2010cited by this paper
• A typical reconstruction limit for compressed sensing based on Lp-norm minimization

  2009cited by this paper
• Asymptotic Analysis of MAP Estimation via the Replica Method and Applications to Compressed Sensing

  2009cited by this paper
• Message-passing algorithms for compressed sensing

  2009cited by this paper
• Robust principal component analysis?

  2009cited by this paper
• Observed universality of phase transitions in high-dimensional geometry, with implications for modern data analysis and signal processing

  2009cited by this paper
• Matrix Completion from Noisy Entries

  2009cited by this paper
• Single-pixel imaging via compressive sampling

  2008cited by this paper
• Modern Coding Theory

  2008cited by this paper
• Random Sparse Linear Systems Observed Via Arbitrary Channels: A Decoupling Principle

  2007cited by this paper
• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization

  2007cited by this paper
• Sparse Principal Component Analysis

  2006cited by this paper
• Counting faces of randomly-projected polytopes when the projection radically lowers dimension

  2006cited by this paper
• Markov Processes: Characterization and Convergence

  2005cited by this paper
• Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?

  2004cited by this paper
• A Direct Formulation for Sparse PCA Using Semidefinite Programming

  2004cited by this paper
• Beyond the Kalman Filter: Particle Filters for Tracking Applications

  2004cited by this paper
• Stochastic Approximation and Recursive Algorithms and Applications

  2003cited by this paper
• A statistical-mechanics approach to large-system analysis of CDMA multiuser detectors

  2002cited by this paper
• On the distribution of the largest eigenvalue in principal components analysis

  2001cited by this paper
• Weak convergence and optimal scaling of random walk Metropolis algorithms

  1997cited by this paper
• A stochastic particle method for the McKean-Vlasov and the Burgers equation

  1997cited by this paper
• Information, physics, and computation

  1996cited by this paper
• Topics in propagation of chaos

  1991influential reference
• Adaptive Algorithms and Stochastic Approximations

  1990cited by this paper
• Robust Principal Components

  1989cited by this paper
• A propagation of chaos result for a system of particles with moderate interaction

  1987cited by this paper
• Stochastic Differential Equations

  1985cited by this paper
• Exchangeability and related topics

  1985cited by this paper
• On stochastic approximation of the eigenvectors and eigenvalues of the expectation of a random matrix

  1985cited by this paper
• The Fokker-Planck Equation: Methods of Solution and Applications

  1984cited by this paper
• Problem Complexity and Method Efficiency in Optimization

  1983cited by this paper
• Finite Exchangeable Sequences

  1980cited by this paper
• Finite forms of de Finetti's theorem on exchangeability

  1977cited by this paper
• A CLASS OF MARKOV PROCESSES ASSOCIATED WITH NONLINEAR PARABOLIC EQUATIONS

  1966cited by this paper
• Markets with a continuum of traders

  1964cited by this paper
• Mathematical Programming manuscript No. (will be inserted by the editor) Pegasos: Primal Estimated sub-GrAdient SOlver for SVM

  year unknowncited by this paper

• Interactive Learning of Single-Index Models via Stochastic Gradient Descent

  2026cites this paper
• Universality of high-dimensional scaling limits of stochastic gradient descent

  2025cites this paper
• Implicitly Normalized Online PCA: A Regularized Algorithm with Exact High-Dimensional Dynamics

  2025cites this paper
• Statistical Inference for Linear Functionals of Online Least-Squares SGD When t ≳ d1+δ

  2025cites this paper
• High-Dimensional Learning Dynamics of Quantized Models with Straight-Through Estimator

  2025influential citation
• Limit Theorems for Stochastic Gradient Descent with Infinite Variance

  2024cites this paper
• Hitting the High-dimensional notes: an ODE for SGD learning dynamics on GLMs and multi-index models

  2024cites this paper
• High-dimensional scaling limits and fluctuations of online least-squares SGD with smooth covariance

  2023cites this paper
• Asymptotic Distribution of Stochastic Mirror Descent Iterates in Average Ensemble Models

  2023cites this paper
• High-dimensional limit of one-pass SGD on least squares

  2023cites this paper
• Statistical Inference for Linear Functionals of Online SGD in High-dimensional Linear Regression

  2023cites this paper
• Stochastic Mirror Descent in Average Ensemble Models

  2022cites this paper
• High‐dimensional limit theorems for SGD: Effective dynamics and critical scaling

  2022cites this paper
• A Mean-Field Theory for Learning the Schönberg Measure of Radial Basis Functions

  2020cites this paper
• Online stochastic gradient descent on non-convex losses from high-dimensional inference

  2020cites this paper
• A Mean-Field Theory for Kernel Alignment with Random Features in Generative and Discriminative Models

  2019cites this paper
• Blind calibration for compressed sensing: state evolution and an online algorithm

  2019cites this paper
• A Mean-Field Theory for Kernel Alignment with Random Features in Generative Adversarial Networks

  2019cites this paper
• PR ] 3 J un 2 01 9 Mean Field Analysis of Neural Networks : A Central Limit Theorem

  2019cites this paper
• Mean Field Analysis of Deep Neural Networks

  2019cites this paper
• Generalisation dynamics of online learning in over-parameterised neural networks

  2019influential citation
• Mean Field Analysis of Neural Networks: A Law of Large Numbers

  2018cites this paper
• Subspace Estimation From Incomplete Observations: A High-Dimensional Analysis

  2018cites this paper
• Mean field analysis of neural networks: A central limit theorem

  2018cites this paper
• One lecture on two-layer neural networks

  2018cites this paper
• A mean field view of the landscape of two-layer neural networks

  2018cites this paper
• Online Power Iteration For Subspace Estimation Under Incomplete Observations: Limiting Dynamics And Phase Transitions

  2018cites this paper
• A Solvable High-Dimensional Model of GAN

  2018cites this paper
• Streaming PCA and Subspace Tracking: The Missing Data Case

  2018cites this paper
• The scaling limit of high-dimensional online independent component analysis

  2017cites this paper