Semi-groups of stochastic gradient descent and online principal component analysis: properties and diffusion approximations

2017/12/18 by Yuanyuan Feng, Lei Li, Feng, Yuanyuan +3 · 1 citation
Computer Science · Mathematics · Physics and Astronomy · #60J20 #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Model Reduction and Neural Networks #Probability (math.PR) #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.1712.06509

openalex publication_date 2017/12/18 · openalex created_date 2019/07/30 · openalex updated_date 2026/08/01

Abstract

We study the Markov semigroups for two important algorithms from machine learning: stochastic gradient descent (SGD) and online principal component analysis (PCA). We investigate the effects of small jumps on the properties of the semi-groups. Properties including regularity preserving, L^∞ contraction are discussed. These semigroups are the dual of the semigroups for evolution of probability, while the latter are L¹ contracting and positivity preserving. Using these properties, we show that stochastic differential equations (SDEs) in ℝ^d (on the sphere \mathbbS^d-1) can be used to approximate SGD (online PCA) weakly. These SDEs may be used to provide some insights of the behaviors of these algorithms.

Citations

• Optimization Methods for Large-Scale Machine Learning
• First Efficient Convergence for Streaming k-PCA: a Global, Gap-Free, and Near-Optimal Rate
• On the diffusion approximation of nonconvex stochastic gradient descent

Cited by

• A Hybrid Framework for Healing Semigroups with Machine Learning

Related

• Diffusion approximations of Oja's online principal component analysis
• Diffusion Approximations for Online Principal Component Estimation and\n Global Convergence
• A probability approximation framework: Markov process approach
• Non-Asymptotic Analysis of Online Multiplicative Stochastic Gradient Descent
• Stochastic Modified Equations and Dynamics of Stochastic Gradient Algorithms I: Mathematical Foundations