Prelimit Coupling and Steady-State Convergence of Constant-Step-Size Nonsmooth Contractive Stochastic Approximation

References

• Andradottir S (1991) A projected stochastic approximation algorithm. 1991 Winter Simulation Conf. Proc. (IEEE Computer Society, Washington, DC), 954–955.Google Scholar
• Bertsekas DP (2019) Reinforcement Learning and Optimal Control (Athena Scientific, Belmont, MA).Google Scholar
• Bonis T (2020) Stein’s method for normal approximation in Wasserstein distances with application to the multivariate central limit theorem. Probab. Theory Related Fields 178(3–4):827–860.Crossref, Google Scholar
• Bramson M (1998) State space collapse with application to heavy traffic limits for multiclass queueing networks. Queueing Systems 30:89–140.Crossref, Google Scholar
• Braverman A, Dai JG, Miyazawa M (2017) Heavy traffic approximation for the stationary distribution of a generalized Jackson network: The BAR approach. Stochastic Systems 7(1):143–196.Link, Google Scholar
• Braverman A, Dai JG, Miyazawa M (2025) The BAR approach for multiclass queueing networks with SBP service policies. Stochastic Systems 15(1):1–49.Link, Google Scholar
• Chen Z, Mou S, Maguluri ST (2022a) Stationary behavior of constant stepsize SGD type algorithms: An asymptotic characterization. Proc. ACM Measurement Anal. Comput. Systems 6(1):1–24.Crossref, Google Scholar
• Chen Z, Maguluri ST, Zubeldia M (2025) Concentration of contractive stochastic approximation: Additive and multiplicative noise. Ann. Appl. Probab. 35(2):1298–1352.Google Scholar
• Chen Z, Maguluri ST, Shakkottai S, Shanmugam K (2020) Finite-sample analysis of contractive stochastic approximation using smooth convex envelopes. Larochelle H, Ranzato M, Hadsell R, Balcan MF, Lin H, eds. NIPS’20: Proc. 34th Internat. Conf. Neural Inform. Processing Systems (Curran Associates, Inc., Red Hook, NY), 8223–8234.Google Scholar
• Chen Z, Maguluri ST, Shakkottai S, Shanmugam K (2023) A Lyapunov theory for finite-sample guarantees of Markovian stochastic approximation. Oper. Res. 72(4):1352–1367.Link, Google Scholar
• Clarke FH (1990) Optimization and Nonsmooth Analysis (Society for Industrial and Applied Mathematics, Philadelphia).Crossref, Google Scholar
• Dieuleveut A, Durmus A, Bach F (2020) Bridging the gap between constant step size stochastic gradient descent and Markov chains. Ann. Statist. 48(3):1348–1382.Crossref, Google Scholar
• Durmus A, Moulines É (2017) Nonasymptotic convergence analysis for the unadjusted Langevin algorithm. Ann. Appl. Probab. 27(3):1551–1587.Crossref, Google Scholar
• Durmus A, Moulines É (2019) High-dimensional Bayesian inference via the unadjusted Langevin algorithm. Bernoulli 25(4A):2854–2882.Crossref, Google Scholar
• Durmus A, Jiménez P, Moulines E, Said S (2021) On Riemannian stochastic approximation schemes with fixed step-size. Banerjee A, Fukumizu K, eds. Proc. 24th Internat. Conf. Artificial Intelligence Statist., Proceedings of Machine Learning Research, vol. 130 (PMLR, New York), 1018–1026.Google Scholar
• Euler L (2000) Foundations of Differential Calculus (Springer, New York).Crossref, Google Scholar
• Folland GB (1999) Real Analysis: Modern Techniques and Their Applications, Pure and Applied Mathematics: A Wiley Series of Texts, Monographs and Tracts, 2nd ed. (John Wiley & Sons, New York).Google Scholar
• Gamarnik D, Zeevi A (2006) Validity of heavy traffic steady-state approximation in generalized Jackson networks. Ann. Appl. Probab. 16(1):56–90.Crossref, Google Scholar
• Gurvich I (2014) Validity of heavy-traffic steady-state approximations in multiclass queueing networks: The case of queue-ratio disciplines. Math. Oper. Res. 39(1):121–162.Link, Google Scholar
• Hildebrand FB (1987) Introduction to Numerical Analysis, Dover Books on Mathematics, 2nd ed. (Dover Publications, Mineola, NY).Google Scholar
• Hiriart-Urruty J-B, Lemaréchal C (2004) Fundamentals of Convex Analysis (Springer, Berlin, Heidelberg).Google Scholar
• Huo D, Chen Y, Xie Q (2023) Effectiveness of constant stepsize in Markovian LSA and statistical inference. Preprint, submitted December 18, https://arxiv.org/abs/2312.10894.Google Scholar
• Huo D, Chen Y, Xie Q (2026) Bias and extrapolation in Markovian linear stochastic approximation with constant step sizes. Math. Oper. Res., ePub ahead of print June 1, https://doi.org/10.1287/moor.2024.0471.Google Scholar
• Huo DL, Zhang Y, Chen Y, Xie Q (2024) The collusion of memory and nonlinearity in stochastic approximation with constant stepsize. Globerson A, Mackey L, Belgrave D, Fan A, Paquet U, Tomczak J, Zhang C, Wallach HM, Larochelle H, Beygelzimer A, d’Alché-Buc F, Fox EB, eds. NIPS’24: Proc. 38th Internat. Conf. Neural Inform. Processing Systems (Curran Associates, Inc., Red Hook, NY), 21699–21762.Google Scholar
• Jain P, Kakade SM, Kidambi R, Netrapalli P, Sidford A (2018) Parallelizing stochastic gradient descent for least squares regression: Mini-batching, averaging, and model misspecification. J. Machine Learn. Res. 18(223):1–42.Google Scholar
• Kushner HJ, Yin GG (2003) Stochastic Approximation and Recursive Algorithms and Applications, Stochastic Modelling and Applied Probability, vol. 35 (Springer, New York).Google Scholar
• Lan G (2020) First-Order and Stochastic Optimization Methods for Machine Learning, Springer Series in the Data Sciences, vol. 1 (Springer, Cham, Switzerland).Crossref, Google Scholar
• Li J, Lou Z, Richter S, Wu WB (2023) The stochastic gradient descent from a nonlinear time series perspective. Working paper, Heidelberg University, Heidelberg, Germany.Google Scholar
• Lindeberg JW (1922) Eine neue herleitung des exponentialgesetzes in der wahrscheinlichkeitsrechnung. Math. Z. 15(1):211–225.Crossref, Google Scholar
• Moulines E, Bach F (2011) Non-asymptotic analysis of stochastic approximation algorithms for machine learning. Shawe-Taylor J, Zemel R, Bartlett P, Pereira F, Weinberger KQ, eds. NIPS’11: Proc. 25th Internat. Conf. Neural Inform. Processing Systems (Curran Associates, Inc., Red Hook, NY), 8223–8234.Google Scholar
• Parikh N, Boyd S (2014) Proximal algorithms. Foundations Trends Optim. 1(3):127–239.Crossref, Google Scholar
• Poliquin R, Rockafellar R (1996) Prox-regular functions in variational analysis. Trans. Amer. Math. Soc. 348(5):1805–1838.Crossref, Google Scholar
• Polyak BT, Juditsky AB (1992) Acceleration of stochastic approximation by averaging. SIAM J. Control Optim. 30(4):838–855.Crossref, Google Scholar
• Rockafellar RT, Wets RJB (1998) Variational Analysis, Grundlehren der Mathematischen Wissenschaften, vol. 317 (Springer, Berlin, Heidelberg).Crossref, Google Scholar
• Ruppert D (1988) Efficient estimations from a slowly convergent Robbins-Monro process. Technical report, School of Operations Research and Industrial Engineering, Cornell University, Ithaca, NY.Google Scholar
• Sagastizábal C (2013) Composite proximal bundle method. Math. Programming 140(1):189–233.Crossref, Google Scholar
• Shapiro A (2003) On a class of nonsmooth composite functions. Math. Oper. Res. 28(4):677–692.Link, Google Scholar
• Srikant R, Ying L (2019) Finite-time error bounds for linear stochastic approximation and TD learning. Beygelzimer A, Hsu D, eds. Proc. 32nd Conf. Learn. Theory, Proceedings of Machine Learning Research, vol. 99 (PMLR, New York), 2803–2830.Google Scholar
• Sutton RS, Barto AG (2018) Reinforcement Learning: An Introduction (MIT Press, Cambridge, MA).Google Scholar
• Wainwright MJ (2019) Stochastic approximation with cone-contractive operators: Sharp ℓ∞-bounds for Q-learning. Preprint, submitted May 15, https://arxiv.org/abs/1905.06265.Google Scholar
• Watkins CJCH, Dayan P (1992) Q-learning. Machine Learn. 8(3):279–292.Crossref, Google Scholar
• Ye H-Q, Yao DD (2016) Diffusion limit of fair resource control—Stationarity and interchange of limits. Math. Oper. Res. 41(4):1161–1207.Link, Google Scholar
• Ye H-Q, Yao DD (2018) Justifying diffusion approximations for multiclass queueing networks under a moment condition. Ann. Appl. Probab. 28(6):3652–3697.Crossref, Google Scholar
• Yu L, Balasubramanian K, Volgushev S, Erdogdu MA (2021) An analysis of constant step size SGD in the non-convex regime: Asymptotic normality and bias. Ranzato M, Beygelzimer A, Dauphin Y, Liang PS, Wortman Vaughan J, eds. NIPS’21: Proc. 35th Internat. Conf. Neural Inform. Processing Systems (Curran Associates, Inc., Red Hook, NY), 4234–4248.Google Scholar
• Zhang Y, Xie Q (2024) Constant stepsize Q-learning: Distributional convergence, bias and extrapolation. Reinforcement Learn. J. 3:1168–1210.Google Scholar
• Zhang Y, Huo D, Chen Y, Xie Q (2025) A piecewise Lyapunov analysis of sub-quadratic SGD: Applications to robust and quantile regression. ACM SIGMETRICS Performance Evaluation Rev. 53(1):85–87.Crossref, Google Scholar