Review of Two-timescale Stochastic Approximation Algorithms
DOI:
https://doi.org/10.62051/ijcsit.v3n1.02Keywords:
Stochastic Approximation, Two-timescale, Optimization AlgorithmAbstract
Artificial Intelligence has gradually become an important force to drive human beings into the intelligent era, and machine learning has made great contributions to the rise and development of Artificial Intelligence. Stochastic approximation (SA) is a com-monly used optimization algorithm in machine learning, and with the complexity of practical problem scenarios, two-timescale SA have received extensive attention and research. In this paper, the basic idea and development process of SA are introduced firstly, followed by the description of several algorithmic frameworks for linear and nonlinear SA, and the specific applications of two-timescale SA in the fields of opti-mization and reinforcement learning are also introduced. Finally, the two-timescale SA is summarized and outlooked.
Downloads
References
Jordan M I, Mitchell T M. Machine learning: Trends, perspectives, and prospects [J]. Science, 2015, 349(6245): 255-260.
Sun S, Cao Z, Zhu H, et al. A survey of optimization methods from a machine learning perspective [J]. IEEE Transactions on Cybernetics, 2019, 50(8): 3668-3681.
Robbins H, Monro S. A stochastic approximation method [J]. The Annals of Mathematical Statistics, 1951: 400-407.
Vajjha K, Trager B, Shinnar A, et al. Formalization of a stochastic approximation theorem [C]. Proceedings of the 13th International Conference on Interactive Theorem Proving. 2022, 31:1-18.
Kiefer J, Wolfowitz J. Stochastic estimation of the maximum of a regression function [J]. The Annals of Mathematical Statistics, 1952: 462-466.
Ljung L. Analysis of recursive stochastic algorithms [J]. IEEE Transactions on Automatic Control, 1977, 22(4): 551-575.
Kushner H J, Clark D S. Stochastic approximation methods for constrained and unconstrained systems [M]. Springer Science and Business Media, 2012.
Wang M, Fang E X, Liu H. Stochastic compositional gradient descent: algorithms for minimizing compositions of expected-value functions [J]. Mathematical Programming, 2017, 161: 419-449.
Hu W, Li C J, Lian X, et al. Efficient smooth non-convex stochastic compositional optimization via stochastic recursive gradient descent[J]. Advances in Neural Information Processing Systems, 2019, 32.
Lakshminarayanan C, Szepesvari C. Linear stochastic approximation: How far does constant step-size and iterate averaging go? [C]. International Conference on Artificial Intelligence and Statistics. PMLR, 2018: 1347-1355.
Durmus A, Moulines E, Naumov A, et al. Tight high probability bounds for linear stochastic approximation with fixed stepsize [C]. Proceedings of the 35th Conference on Neural Information Processing Systems, 2021, 34: 30063-30074.
Brooms A C. Stochastic approximation and recursive algorithms with applications, 2nd edn by hj kushner and gg yin [J]. 2006.
Bottou L, Curtis F E, Nocedal J. Optimization methods for large-scale machine learning [J]. SIAM Review, 2018, 60(2): 223-311.
Mou W, Pananjady A, Wainwright M J, et al. Optimal and instance-dependent guarantees for Markovian linear stochastic approximation [C]. Proceedings of Machine Learning Research, PMLR, 2022, 2060–2061.
Clifton J, Laber E. Q-learning: Theory and applications [J]. Annual Review of Statistics and Its Application, 2020, 7: 279-301.
Borkar V S. Stochastic approximation: A dynamical systems viewpoint [M]. Springer, 2009.
Srikant R, Ying L. Finite-time error bounds for linear stochastic approximation and td learning [C]. Proceedings of the 32nd Conference on Learning Theory. PMLR, 2019: 2803-2830.
Qu G, Wierman A. Finite-time analysis of asynchronous stochastic approximation and Q-learning [C]. Proceedings of the 33rd Conference on Learning Theory. PMLR, 2020: 3185-3205.
Sun T, Sun Y, Yin W. On markov chain gradient descent [C]. Proceedings of the 32nd Conference on Neural Information Processing Systems, 2018, 31.
Zhang L, Zhou Z H. Stochastic approximation of smooth and strongly convex functions: Beyond the convergence rate [C]. Proceedings of the 32nd Conference on Learning Theory. PMLR, 2019: 3160-3179.
Doan T T, Romberg J. Linear two-time-scale stochastic approximation a finite-time analysis [C]. Proceedings of the 57th Annual Allerton Conference on Communication, Control, and Computing (Allerton). Monticello, IL, USA, 2019: 399-406.
Doan T T. Finite-time analysis and restarting scheme for linear two-time-scale stochastic approximation [J]. SIAM Journal on Control and Optimization, 2021, 59(4): 2798-2819.
Dalal G, Thoppe G, Szörényi B, et al. Finite sample analysis of two-timescale stochastic approximation with applications to reinforcement learning [C]. Proceedings of the 31st Conference On Learning Theory. PMLR, 2018: 1199-1233.
Kaledin M, Moulines E, Naumov A, et al. Finite time analysis of linear two-timescale stochastic approximation with Markovian noise [C]. Proceedings of 33rd Conference on Learning Theory. PMLR, 2020: 2144-2203.
Mokkadem A, Pelletier M. Convergence rate and averaging of nonlinear two-time-scale stochastic approximation algorithms [J]. The Annals of Applied Probability, 2006: 1671-1701.
Chung W, Nath S, Joseph A, et al. Two-timescale networks for nonlinear value function approximation [C]. Proceedings of the International Conference on Learning Representations. 2019.
Doan T T. Nonlinear two-time-scale stochastic approximation convergence and finite-time performance [J]. IEEE Transactions on Automatic Control, 2022.
Amir I, Koren T, Livni R. SGD generalizes better than GD (and regularization doesn’t help) [C]. Proceedings of 34th Conference on Learning Theory. USA: PMLR, 2021: 63-92.
Polyak B T, Juditsky A B. Acceleration of stochastic approximation by averaging [J]. SIAM Journal on Control and Optimization, 1992, 30(4): 838-855.
Mou W, Li C J, Wainwright M J, et al. On linear stochastic approximation: Fine-grained Polyak-Ruppert and non-asymptotic concentration [C]. Proceedings of 33rd Conference on Learning Theory. PMLR, 2020: 2947-2997.
Gadat S, Panloup F, Saadane S. Stochastic heavy ball [J]. Electronic Journal of Statistics, 12:461–529, 2018.
Gitman I, Lang H, Zhang P, et al. Understanding the role of momentum in stochastic gradient methods [C]. Advances in Neural Information Processing Systems, 2019, 32.
Han Y, Li X, Zhang Z. Finite-time decoupled convergence in nonlinear two-time-scale stochastic approximation [J]. arXiv preprint arXiv:2401.03893, 2024.
Huang F, Wu X, Hu Z. Adagda: Faster adaptive gradient descent ascent methods for minimax optimization [C]. International Conference on Artificial Intelligence and Statistics. PMLR, 2023: 2365-2389.
Creswell A, White T, Dumoulin V, et al. Generative adversarial networks: An overview [J]. IEEE signal processing magazine, 2018, 35(1): 53-65.
Kurakin A, Goodfellow I, Bengio S. Adversarial machine learning at scale [J]. arXiv preprint arXiv:1611.01236, 2016.
Lan G, Lee S, Zhou Y. Communication-efficient algorithms for decentralized and stochastic optimization [J]. Mathematical Programming, 2020, 180(1): 237-284.
Maei H, Szepesvari C, Bhatnagar S, et al. Convergent temporal-difference learning with arbitrary smooth function approximation [C]. Proceedings of the 22nd International Conference on Neural Information Processing Systems, 2009: 1204–1212.
Downloads
Published
Issue
Section
License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
How to Cite
