Stochastic recursive inclusion in two timescales with an application to the Lagrangian dual problem

In this paper we present a framework to analyze the asymptotic behavior of two timescale stochastic approximation algorithms including those with set-valued mean fields. This paper builds on the works of Borkar and Perkins & Leslie. The framework presented herein is more general as compared to the synchronous two timescale framework of Perkins & Leslie, however the assumptions involved are easily verifiable. As an application, we use this framework to analyze the two timescale stochastic approximation algorithm corresponding to the Lagrangian dual problem in optimization theory.

• Publication year

  2015

• Venue

  arXiv.org

• Publication date

  2015-02-06

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1080/17442508.2016.1215450arXiv 1502.01956
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Set-Valued Analysis

  2021cited by this paper
• Two timescale convergent Q-learning for sleep-scheduling in wireless sensor networks

  2013cited by this paper
• Perturbations of Set-Valued Dynamical Systems, with Applications to Game Theory

  2012cited by this paper
• Asynchronous stochastic approximation with differential inclusions

  2011cited by this paper
• Convex Optimization Theory

  2009cited by this paper
• Stochastic Approximations and Differential Inclusions

  2005cited by this paper
• Stochastic Approximation and Recursive Algorithms and Applications

  2003cited by this paper
• Analysis of Recursive Stochastic Algorithms

  2001cited by this paper
• Dynamics of stochastic approximation algorithms

  1999cited by this paper
• Stochastic approximation with two time scales

  1997influential reference
• Asymptotic pseudotrajectories and chain recurrent flows, with applications

  1996cited by this paper
• A Dynamical System Approach to Stochastic Approximations

  1996influential reference
• A tutorial survey of reinforcement learning

  1994cited by this paper
• Differential inclusions set-valued maps and viability theory

  1984cited by this paper
• On the continuity of the minimum set of a continuous function

  1967influential reference

• Reinforcement Learning with Quasi-Hyperbolic Discounting

  2024cites this paper
• Near-optimal control of a stochastic avian influenza model with multi-time delays and spatial diffusion on complex networks

  2024cites this paper
• Remarks on Differential Inclusion limits of Stochastic Approximation

  2023cites this paper
• Multi Timescale Stochastic Approximation: Stability and Convergence

  2021cites this paper
• Constrained Search via Penalization for Continuous Simulation Optimization

  2020cites this paper
• Two-Timescale Networks for Nonlinear Value Function Approximation

  2019influential citation
• GANs Trained by a Two Time-Scale Update Rule Converge to a Nash Equilibrium

  2017cites this paper
• GANs Trained by a Two Time-Scale Update Rule Converge to a Local Nash Equilibrium

  2017cites this paper
• Stochastic Recursive Inclusions in two timescales with non-additive iterate dependent Markov noise

  2016influential citation