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

DOI10.1080/17442508.2018.1539086zbMATH Open1500.60040arXiv1612.03831OpenAlexW2772653370WikidataQ129037052 ScholiaQ129037052MaRDI QIDQ5086426FDOQ5086426

Authors: Pascal Bianchi, W. Hachem, Adil Salim 

Publication date: 5 July 2022

Published in: Stochastics (Search for Journal in Brave)

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.

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

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

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)

Cites Work

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

Cited In (9)

• 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
• Title not available (Why is that?)
• Convergence of constant step stochastic gradient descent for non-smooth non-convex 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)