Semigroups of stochastic gradient descent and online principal component analysis: properties and diffusion approximations

DOI10.4310/CMS.2018.V16.N3.A8MaRDI QIDQ1990549zbMATH OpenWikidataFDO

Authors Yuanyuan Feng, Lei Li, Jian-Guo Liu

Publication date 25 October 2018

Published in Communications in Mathematical Sciences (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1712.06509

zbMATH Keywords

Markov chainonline principle component analysissemigroupstochastic differential equationsstochastic gradient descent

Mathematics Subject Classification ID

Applications of stochastic analysis (to PDEs, etc.) (60H30) Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20)

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^{infty}$ contraction are discussed. These semigroups are the dual of the semigroups for evolution of probability, while the latter are $L^1$ contracting and positivity preserving. Using these properties, we show that stochastic differential equations (SDEs) in $mathbb{R}^d$ (on the sphere $mathbb{S}^{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.

Recommendations

• Stochastic modified equations and dynamics of stochastic gradient algorithms. I: Mathematical foundations
• Analysis of stochastic gradient descent in continuous time
• Uniform-in-time weak error analysis for stochastic gradient descent algorithms via diffusion approximation
• Stochastic gradient descent in continuous time: a central limit theorem
• Stochastic gradient descent with noise of machine learning type. I: Discrete time analysis

Cited in

(15)

• On the mean field limit of the random batch method for interacting particle systems
• Approximation to stochastic variance reduced gradient Langevin dynamics by stochastic delay differential equations
• Random batch methods (RBM) for interacting particle systems
• Online learning in optical tomography: a stochastic approach
• Stochastic modified equations and dynamics of stochastic gradient algorithms. I: Mathematical foundations
• Continuous time analysis of momentum methods
• A Continuous-Time Analysis of Distributed Stochastic Gradient
• Convergence of the random batch method for interacting particles with disparate species and weights
• A probability approximation framework: Markov process approach
• Stochastic Gauss-Newton algorithms for online PCA
• A random batch method for efficient ensemble forecasts of multiscale turbulent systems
• Geometric ergodicity of SGLD via reflection coupling
• Stochastic modified flows for Riemannian stochastic gradient descent
• Convergence of Markov chains for constant step-size stochastic gradient descent with separable functions
• An orthonormalization-free and inversion-free algorithm for online estimation of principal eigenspace

This page was built for publication: Semigroups of stochastic gradient descent and online principal component analysis: properties and diffusion approximations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1990549)