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 L¹ 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.