Constant step stochastic approximations involving differential inclusions: stability, long-run convergence and applications

DOI10.1080/17442508.2018.1539086MaRDI QIDQ5086426zbMATH OpenOpenAlexWikidataFDO

Authors Pascal Bianchi, W. Hachem, Adil Salim

Publication date 5 July 2022

Published in Stochastics (Search for Journal in Brave)

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

zbMATH Keywords

differential inclusionsdynamical systemsnon-convex optimizationqueueing systemsstochastic approximation with constant step

Mathematics Subject Classification ID

Ordinary differential inclusions (34A60) Random measures (60G57) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Queueing theory (aspects of probability theory) (60K25)

Abstract: We consider a Markov chain $(x_n)$ whose kernel is indexed by a scaling parameter $gamma>0$, refered to as the step size. The aim is to analyze the behavior of the Markov chain in the doubly asymptotic regime where $noinfty$ then $gammao0$. First, under mild assumptions on the so-called drift of the Markov chain, we show that the interpolated process converges narrowly to the solutions of a Differential Inclusion (DI) involving an upper semicontinuous set-valued map with closed and convex values. Second, we provide verifiable conditions which ensure the stability of the iterates. Third, by putting the above results together, we establish the long run convergence of the iterates as $gammao0$, to the Birkhoff center of the DI. The ergodic behavior of the iterates is also provided. Application examples are investigated. We apply our findings to 1) the problem of nonconvex proximal stochastic optimization and 2) a fluid model of parallel queues.

Recommendations

• Stochastic approximations with constant step size and differential inclusions
• Stochastic Recursive Inclusions in Two Timescales with Nonadditive Iterate-Dependent Markov Noise
• Stochastic recursive inclusions with non-additive iterate-dependent Markov noise
• Stochastic Minimization with Constant Step-Size: Asymptotic Laws
• Stochastic Approximations and Differential Inclusions

Cites work

• Asymptotic Behavior of a Markovian Stochastic Algorithm with Constant Step
• Convex analysis and monotone operator theory in Hilbert spaces
• Dynamical behavior of a stochastic forward-backward algorithm using random monotone operators
• Ergodic convergence of a stochastic proximal point algorithm
• Ergodic properties of weak asymptotic pseudotrajectories for semiflows
• ERGODIC PROPERTIES OF WEAK ASYMPTOTIC PSEUDOTRAJECTORIES FOR SET-VALUED DYNAMICAL SYSTEMS
• From error bounds to the complexity of first-order descent methods for convex functions
• scientific article; zbMATH DE number 3855514 (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 1278731 (Why is no real title available?)
• scientific article; zbMATH DE number 1354815 (Why is no real title available?)
• scientific article; zbMATH DE number 1972910 (Why is no real title available?)
• scientific article; zbMATH DE number 1405930 (Why is no real title available?)
• scientific article; zbMATH DE number 3398324 (Why is no real title available?)
• Invariant Measures for Set-Valued Dynamical Systems
• Monotone Operators and the Proximal Point Algorithm
• Poincaré's recurrence theorem for set-valued dynamical systems
• Stochastic approximation algorithms with constant step size whose average is cooperative
• Stochastic Approximations and Differential Inclusions
• Stochastic Approximations and Differential Inclusions, Part II: Applications
• Stochastic approximations of set-valued dynamical systems: convergence with positive probability to an attractor
• Stochastic approximations with constant step size and differential inclusions
• Stochastic Recursive Inclusions in Two Timescales with Nonadditive Iterate-Dependent Markov Noise
• Theory of Random Sets

Cited in

(9)

• Conservative set valued fields, automatic differentiation, stochastic gradient methods and deep learning
• Convergence of constant step stochastic gradient descent for non-smooth non-convex functions
• Stochastic approximations with constant step size and differential inclusions
• scientific article; zbMATH DE number 7079312 (Why is no real title available?)
• Convergence and dynamical behavior of the ADAM algorithm for nonconvex stochastic optimization
• A generalization of the Borkar-Meyn theorem for stochastic recursive inclusions
• Lyapunov stability of the subgradient method with constant step size
• Long term dynamics of the subgradient method for Lipschitz path differentiable functions
• Global stability of first-order methods for coercive tame functions

This page was built for publication: Constant step stochastic approximations involving differential inclusions: stability, long-run convergence and applications

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