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

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 semigroups. Properties including regularity preserving, L∞ contraction are discussed. These semigroups are the dual of the semigroups for evolution of probability, while the latter are L1 contracting and positivity preserving. Using these properties, we show that stochastic differential equations (SDEs) in Rd (on the sphere Sd-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.

Duke Scholars

Author Jian-Guo Liu Physics