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

Abstract

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.

References in corpus (10)

• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• Message Passing Algorithms for Compressed Sensing
• A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets
• Expectation-Maximization Gaussian-Mixture Approximate Message Passing
• Making Gradient Descent Optimal for Strongly Convex Stochastic Optimization
• Observed Universality of Phase Transitions in High-Dimensional Geometry, with Implications for Modern Data Analysis and Signal Processing
• Computational and Statistical Tradeoffs via Convex Relaxation
• Phase Transitions in Semidefinite Relaxations
• Primal-dual subgradient methods for minimizing uniformly convex functions
• The Scaling Limit of High-Dimensional Online Independent Component Analysis

Cited by in corpus (7)

• A Mean Field View of the Landscape of Two-Layers Neural Networks
• Subspace Estimation from Incomplete Observations: A High-Dimensional Analysis
• Online stochastic gradient descent on non-convex losses from high-dimensional inference
• Generalisation dynamics of online learning in over-parameterised neural networks
• Blind calibration for compressed sensing: State evolution and an online algorithm
• A Mean-Field Theory for Kernel Alignment with Random Features in Generative and Discriminative Models
• A Mean-Field Theory for Learning the Schönberg Measure of Radial Basis Functions