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

Journal Article (Journal Article)

© 2018 International Press. 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.

Full Text

Duke Authors

Cited Authors

  • Feng, Y; Li, L; Liu, JG

Published Date

  • January 1, 2018

Published In

Volume / Issue

  • 16 / 3

Start / End Page

  • 777 - 789

Electronic International Standard Serial Number (EISSN)

  • 1945-0796

International Standard Serial Number (ISSN)

  • 1539-6746

Digital Object Identifier (DOI)

  • 10.4310/cms.2018.v16.n3.a8

Citation Source

  • Scopus