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

dynamical systemsnon-convex optimizationdifferential inclusionsqueueing systemsstochastic approximation with constant step

Mathematics Subject Classification ID

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

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

• 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?)
• 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 PROPERTIES OF WEAK ASYMPTOTIC PSEUDOTRAJECTORIES FOR SET-VALUED DYNAMICAL SYSTEMS
• Ergodic convergence of a stochastic proximal point algorithm
• Ergodic properties of weak asymptotic pseudotrajectories for semiflows
• From error bounds to the complexity of first-order descent methods for convex functions
• Invariant Measures for Set-Valued Dynamical Systems
• Monotone Operators and the Proximal Point Algorithm
• Poincaré's recurrence theorem for set-valued dynamical systems
• Stochastic Approximations and Differential Inclusions
• Stochastic Approximations and Differential Inclusions, Part II: Applications
• Stochastic Recursive Inclusions in Two Timescales with Nonadditive Iterate-Dependent Markov Noise
• Stochastic approximation algorithms with constant step size whose average is cooperative
• Stochastic approximations of set-valued dynamical systems: convergence with positive probability to an attractor
• Stochastic approximations with constant step size and differential inclusions
• Theory of Random Sets

Cited in

(9)

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

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)