Convergence rate of linear two-time-scale stochastic approximation

By Vijay R. Konda, John N. Tsitsiklis. 2004

162 citations recorded by the source corpus.

We study the rate of convergence of linear two-time-scale stochastic approximation methods. We consider two-time-scale linear iterations driven by i.i.d. noise, prove some results on their asymptotic covariance and establish asymptotic normality. The well-known result [Polyak, B. T. (1990). Automat. Remote Contr. 51 937–946; Ruppert, D. (1988). Technical Report 781, Cornell Univ.] on the optimality of Polyak–Ruppert averaging techniques specialized to linear stochastic approximation is established as a consequence of the general results in this paper.

Subfields: Artificial Intelligence, Finance, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/ef676a7ebead282f9faabf911742b7b0df5dea42

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Sergey Levine
2. Yoshua Bengio
3. Pieter Abbeel
4. Chelsea Finn
5. Quoc V. Le
6. Igor Mordatch
7. Trevor Darrell
8. Dacheng Tao

In Finance

1. Adithya M. Devraj
2. Dileep Manisseri Kalathil
3. Rahul Jain
4. William Benjamin Haskell
5. David Lopez-Paz
6. Hubert Ramsauer
7. Martin Heusel
8. Thomas Unterthiner

In Statistics and Probability

1. David Lopez-Paz
2. Hubert Ramsauer
3. Aravind Rajeswaran
4. Dileep Manisseri Kalathil
5. Günter Klambauer
6. Adithya M. Devraj
7. Igor Mordatch
8. Maxime Oquab

Citations in the corpus

• Empirical Dynamic Programming (2013, methodology): “This led to many subsequent generalizations including the temporal differences methods [9] and actor-critic methods [24, 25].”
• GANs Trained by a Two Time-Scale Update Rule Converge to a Local Nash Equilibrium (2017, methodology): “The next theorem is taken from Konda [30] and Konda & Tsitsiklis [33].”
• GANs Trained by a Two Time-Scale Update Rule Converge to a Nash Equilibrium (2017, methodology): “We report Theorem 3.2 (see also Theorem 7 in [33]) and Theorem 3.13 from [31]: Theorem 4 (Konda & Tsitsiklis).”
• A Game Theoretic Framework for Model Based Reinforcement Learning (2020, background): “We also note that the PAL and MAL families have similarities to multiple timescale algorithms [45, 71, 72] studied for actor-critic temporal difference learning.”
• Zap Q-Learning (2017, background): “First is the remarkable averaging technique introduced in [21, 22, 24] (also see [12]).”
• Geometrical Insights for Implicit Generative Modeling (2017, background): “Such algorithms belong to the general class of stochastic algorithms with two time scales [9, 29].”