A convergence analysis of the perturbed compositional gradient flow: averaging principle and normal deviations

DOI10.3934/DCDS.2018216MaRDI QIDQ1659690zbMATH OpenOpenAlexWikidataFDO

Authors Chris Junchi Li, Wenqing Hu

Publication date 22 August 2018

Published in Discrete and Continuous Dynamical Systems (Search for Journal in Brave)

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

zbMATH Keywords

averaging principlefast-slow dynamical systemsnormal deviationperturbed compositional gradient flowperturbed gradient flowstochastic composite gradient descentstochastic gradient descent

Mathematics Subject Classification ID

Averaging method for ordinary differential equations (34C29) Ordinary differential equations and systems with randomness (34F05) Nonlinear programming (90C30)

Abstract: We consider in this work a system of two stochastic differential equations named the perturbed compositional gradient flow. By introducing a separation of fast and slow scales of the two equations, we show that the limit of the slow motion is given by an averaged ordinary differential equation. We then demonstrate that the deviation of the slow motion from the averaged equation, after proper rescaling, converges to a stochastic process with Gaussian inputs. This indicates that the slow motion can be approximated in the weak sense by a standard perturbed gradient flow or the continuous-time stochastic gradient descent algorithm that solves the optimization problem for a composition of two functions. As an application, the perturbed compositional gradient flow corresponds to the diffusion limit of the Stochastic Composite Gradient Descent (SCGD) algorithm for minimizing a composition of two expected-value functions in the optimization literatures. For the strongly convex case, such an analysis implies that the SCGD algorithm has the same convergence time asymptotic as the classical stochastic gradient descent algorithm. Thus it validates, at the level of continuous approximation, the effectiveness of using the SCGD algorithm in the strongly convex case.

Recommendations

• Stochastic compositional gradient descent: algorithms for minimizing compositions of expected-value functions
• On the fast convergence of random perturbations of the gradient flow
• Analysis of stochastic gradient descent in continuous time
• Multiscale analysis of accelerated gradient methods
• Stochastic modified equations and dynamics of stochastic gradient algorithms. I: Mathematical foundations

Cites work

• A Khasminskii type averaging principle for stochastic reaction-diffusion equations
• Accelerating Stochastic Composition Optimization
• Asymptotics of superregular perturbations of fiber ergodic semigroups
• Central limit theorem for additive functionals of reversible Markov processes and applications to simple exclusions
• Diffusion approximation for slow motion in fully coupled averaging
• Functional Integration and Partial Differential Equations. (AM-109)
• scientific article; zbMATH DE number 1639829 (Why is no real title available?)
• scientific article; zbMATH DE number 3886886 (Why is no real title available?)
• scientific article; zbMATH DE number 5348356 (Why is no real title available?)
• scientific article; zbMATH DE number 48727 (Why is no real title available?)
• scientific article; zbMATH DE number 1239549 (Why is no real title available?)
• scientific article; zbMATH DE number 1245556 (Why is no real title available?)
• scientific article; zbMATH DE number 1972910 (Why is no real title available?)
• scientific article; zbMATH DE number 823069 (Why is no real title available?)
• scientific article; zbMATH DE number 3366247 (Why is no real title available?)
• Normal deviations from the averaged motion for some reaction-diffusion equations with fast oscillating perturbation
• On Poisson equation and diffusion approximation. II.
• On polynomial mixing and convergence rate for stochastic difference and differential equations
• On Stochastic Processes Defined by Differential Equations with a Small Parameter
• On the diffusion approximation of nonconvex stochastic gradient descent
• On the Poisson equation and diffusion approximation. I
• On the Poisson equation and diffusion approximation. III
• Periodic homogenization for hypoelliptic diffusions
• Stochastic compositional gradient descent: algorithms for minimizing compositions of expected-value functions
• Stochastic differential equations. An introduction with applications.
• The exit problem for small random perturbations of dynamical systems with a hyperbolic fixed point

Cited in

(5)

• Averaging principle and normal deviations for multiscale stochastic systems
• On the fast convergence of random perturbations of the gradient flow
• Central limit type theorem and large deviation principle for multi-scale McKean-Vlasov SDEs
• Functional law of large numbers and central limit theorem for slow-fast McKean-Vlasov equations
• Deep relaxation of controlled stochastic gradient descent via singular perturbations

This page was built for publication: A convergence analysis of the perturbed compositional gradient flow: averaging principle and normal deviations

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