Convergence and Inference of Stream Stochastic Gradient Descent, with Applications to Queueing Systems and Inventory Control

References

• Agarwal A, Duchi JC (2013) The generalization ability of online algorithms for dependent data. IEEE Trans. Inform. Theory 59(1):573–587.Crossref, Google Scholar
• Ajalloeian A, Stich SU (2020) On the convergence of SGD with biased gradients. Preprint, submitted July 31, https://arxiv.org/abs/2008.00051v1.Google Scholar
• Benveniste A, Métivier M, Priouret P (2012) Adaptive Algorithms and Stochastic Approximations, Applications of Mathematics, vol. 22 (Springer Science & Business Media, Berlin).Google Scholar
• Beznosikov A, Samsonov S, Sheshukova M, Gasnikov A, Naumov A, Moulines E (2024) First order methods with Markovian noise: From acceleration to variational inequalities. Advances in Neural Information Processing Systems, vol. 37 (Curran Associates, Inc., Red Hook, NY), 44820–44835.Google Scholar
• Blanchet J, Chen X (2020) Rates of convergence to stationarity for reflected Brownian motion. Math. Oper. Res. 45(2):660–681.Link, Google Scholar
• Blanchet J, Dong J, Pei Y (2018) Perfect sampling of GI/GI/c queues. Queueing Systems 90:1–33.Crossref, Google Scholar
• Boob D, Deng Q, Lan G (2023) Stochastic first-order methods for convex and nonconvex functional constrained optimization. Math. Programming 197(1):215–279.Crossref, Google Scholar
• Bubeck S (2015) Convex optimization: Algorithms and complexity. Foundations Trends Machine Learn. 8(3–4):231–357.Crossref, Google Scholar
• Carè A, Csáji BC, Gerencsér B, Gerencsér L, Rásonyi M (2019) Poisson equations, Lipschitz continuity and controlled queues. Preprint, submitted June 22, https://arxiv.org/abs/1906.09464v2.Google Scholar
• Chandak S, Borkar VS, Dodhia P (2022) Concentration of contractive stochastic approximation and reinforcement learning. Stochastic Systems 12(4):411–430.Link, Google Scholar
• Che E, Dong J, Tong XT (2024) Stochastic gradient descent with adaptive data. Preprint, submitted October 2, https://arxiv.org/abs/2410.01195.Google Scholar
• Chen X, Jasin S, Shi C (2022) The Elements of Joint Learning and Optimization in Operations Management (Springer, Cham, Switzerland).Crossref, Google Scholar
• Chen X, Liu Y, Hong G (2024) An online learning approach to dynamic pricing and capacity sizing in service systems. Oper. Res. 72(6):2677–2697.Link, Google Scholar
• Chen X, Lai Z, Li H, Zhang Y (2021) Online statistical inference for stochastic optimization via Kiefer-Wolfowitz methods. Preprint, submitted February 5, https://arxiv.org/abs/2102.03389v1.Google Scholar
• Chen X, Lee JD, Tong XT, Zhang Y (2020) Statistical inference for model parameters in stochastic gradient descent. Ann. Statist. 48(1):251–273.Crossref, Google Scholar
• Doan TT (2023) Finite-time analysis of Markov gradient descent. IEEE Trans. Automatic Control 68(4):2140–2153.Crossref, Google Scholar
• Doucet A, Tadic V (2017) Asymptotic bias of stochastic gradient search. Ann. Appl. Probab. 27(6):3255–3304.Google Scholar
• Drusvyatskiy D, Xiao L (2023) Stochastic optimization with decision-dependent distributions. Math. Oper. Res. 48(2):954–998.Link, Google Scholar
• Duchi JC, Agarwal A, Johansson M, Jordan MI (2012) Ergodic mirror descent. SIAM J. Optim. 22(4):1549–1578.Crossref, Google Scholar
• Even M (2023) Stochastic gradient descent under Markovian sampling schemes. Internat. Conf. Machine Learn. (PMLR, Honolulu, Hawaii), 9412–9439.Google Scholar
• Fu MC (1990) Convergence of a stochastic approximation algorithm for the GI/G/1 queue using infinitesimal perturbation analysis. J. Optim. Theory Appl. 65:149–160.Crossref, Google Scholar
• Geunes J (2002) Foundations of inventory management. Interfaces 32(1):108–110.Google Scholar
• Glynn PW, Iglehart DL (1990) Simulation output analysis using standardized time series. Math. Oper. Res. 15(1):1–16.Link, Google Scholar
• Han Y, Li X, Zhang Z (2024a) Finite-time decoupled convergence in nonlinear two-time-scale stochastic approximation. Preprint, submitted November 26, https://arxiv.org/abs/2401.03893.Google Scholar
• Han Y, Li X, Liang J, Zhang Z (2024b) Decoupled functional central limit theorems for two-time-scale stochastic approximation. Preprint, submitted December 22, https://arxiv.org/abs/2412.17070v1.Google Scholar
• Heyman DP, Sobel MJ (2004) Stochastic Models in Operations Research: Stochastic Optimization, Dover Books on Computer Science Series (Dover, New York).Google Scholar
• Hong M, Wai H-T, Wang Z, Yang Z (2023) A two-timescale stochastic algorithm framework for bilevel optimization: Complexity analysis and application to actor-critic. SIAM J. Optim. 33(1):147–180.Crossref, Google Scholar
• Huh WT, Rusmevichientong P (2009) A nonparametric asymptotic analysis of inventory planning with censored demand. Math. Oper. Res. 34(1):103–123.Link, Google Scholar
• Huh WT, Janakiraman G, Muckstadt JA, Rusmevichientong P (2009) An adaptive algorithm for finding the optimal base-stock policy in lost sales inventory systems with censored demand. Math. Oper. Res. 34(2):397–416.Link, Google Scholar
• Kalashnikov VV (2013) Mathematical Methods in Queuing Theory, vol. 271 (Springer Science & Business Media, Dordrecht, Netherlands).Google Scholar
• Kaledin M, Moulines E, Naumov A, Tadic V, Wai H-T (2020) Finite time analysis of linear two-timescale stochastic approximation with Markovian noise. Conf. Learn. Theory (PMLR, New York), 2144–2203.Google Scholar
• Karimi B, Miasojedow B, Moulines E, Wai H-T (2019) Non-asymptotic analysis of biased stochastic approximation scheme. Conf. Learn. Theory (PMLR, New York), 1944–1974.Google Scholar
• Khodadadian S, Doan TT, Romberg J, Maguluri ST (2023) Finite-sample analysis of two-time-scale natural actor-critic algorithm. IEEE Trans. Automatic Control 68(6):3273–3284.Crossref, Google Scholar
• Kushner H, Yin GG (2003) Stochastic Approximation and Recursive Algorithms and Applications, vol. 35 (Springer Science & Business Media, New York).Google Scholar
• Lan G (2020) First-Order and Stochastic Optimization Methods for Machine Learning, vol. 1 (Springer, Cham, Switzerland).Crossref, Google Scholar
• L’Ecuyer P, Glynn PW (1994) Stochastic optimization by simulation: Convergence proofs for the GI/GI/1 queue in steady state. Management Sci. 40(11):1562–1578.Link, Google Scholar
• L’Ecuyer P, Giroux N, Glynn PW (1994) Stochastic optimization by simulation: Numerical experiments with the M/M/1 queue in steady-state. Management Sci. 40(10):1245–1261.Link, Google Scholar
• Lee S, Liao Y, Seo MH, Shin Y (2022a) Fast and robust online inference with stochastic gradient descent via random scaling. Proc. AAAI Conf. Artificial Intelligence 36:7381–7389.Crossref, Google Scholar
• Lee S, Liao Y, Seo MH, Shin Y (2022b) Fast inference for quantile regression with tens of millions of observations. Preprint, submitted November 21, https://dx.doi.org/10.2139/ssrn.4263158.Google Scholar
• Lei J, Shanbhag UV (2025) Variance-reduced accelerated first-order methods: Central limit theorems and confidence statements. Math. Oper. Res. 50(2):1364–1397.Link, Google Scholar
• Li Q, Wai H-T (2022) State dependent performative prediction with stochastic approximation. Internat. Conf. Artificial Intelligence Statist. (PMLR, New York), 3164–3186.Google Scholar
• Li X, Liang J, Zhang Z (2023a) Online statistical inference for nonlinear stochastic approximation with Markovian data. Preprint, submitted February 20, https://arxiv.org/abs/2302.07690.Google Scholar
• Li X, Liang J, Chang X, Zhang Z (2022) Statistical estimation and online inference via Local SGD. Loh P-L, Raginsky M, eds. Conf. Learn. Theory, vol. 178 (PMLR, New York), 1613–1661.Google Scholar
• Li X, Yang W, Zhang Z, Jordan MI (2023b) A statistical analysis of Polyak-Ruppert averaged Q-Learning. Internat. Conf. Artificial Intelligence Statist. (PMLR, New York), 2207–2261.Google Scholar
• Liang F (2010) Trajectory averaging for stochastic approximation MCMC algorithms. Ann. Statist. 38(5):2823–2856.Crossref, Google Scholar
• Liang T, Su WJ (2019) Statistical inference for the population landscape via moment-adjusted stochastic gradients. J. Roy. Statist. Soc. 81(2):431–456.Crossref, Google Scholar
• Lindvall T (2002) Lectures on the Coupling Method (Courier Corporation, North Chelmsford, MA).Google Scholar
• Mendler-Dünner C, Perdomo J, Zrnic T, Hardt M (2020) Stochastic optimization for performative prediction. Advances in Neural Information Processing Systems, vol. 33 (Curran Associates, Inc., Red Hook, NY), 4929–4939.Google Scholar
• Moulines E, Bach F (2011) Non-asymptotic analysis of stochastic approximation algorithms for machine learning. Advances in Neural Information Processing Systems, vol. 24 (Curran Associates, Inc., Red Hook, NY), 451–459.Google Scholar
• Polyak BT, Juditsky AB (1992) Acceleration of stochastic approximation by averaging. SIAM J. Control Optim. 30(4):838–855.Crossref, Google Scholar
• Ramprasad P, Li Y, Yang Z, Wang Z, Sun WW, Cheng G (2023) Online bootstrap inference for policy evaluation in reinforcement learning. J. Amer. Statist. Assoc. 118(544):2901–2914.Crossref, Google Scholar
• Ravner L, Snitkovsky RI (2024) Stochastic approximation of symmetric Nash equilibria in queueing games. Oper. Res. 72(6):2698–2725.Link, Google Scholar
• Robbins H, Monro S (1951) A stochastic approximation method. Ann. Math. Statist. 22(3):400–407.Google Scholar
• Robbins H, Siegmund D (1971) A convergence theorem for non-negative almost supermartingales and some applications. Rustagi JS, ed. Optimizing Methods in Statistics (Elsevier, Amsterdam), 233–257.Google Scholar
• Ruppert D (1988) Efficient estimations from a slowly convergent Robbins-Monro process. Technical report, Cornell University Operations Research and Industrial Engineering, Ithaca, NY.Google Scholar
• Shalev-Shwartz S (2025) Online learning and online convex optimization. Foundations Trends Machine Learn. 4(2):107–194.Crossref, Google Scholar
• Su WJ, Zhu Y (2023) HiGrad: Uncertainty quantification for online learning and stochastic approximation. J. Machine Learn. Res. 24(124):1–53.Google Scholar
• Sun T, Sun Y, Yin W (2018) On Markov chain gradient descent. Advances in Neural Information Processing Systems, vol. 31 (Curran Associates Inc., Red Hook, NY), 9918–9927.Google Scholar
• Suri R, Zazanis MA (1988) Perturbation analysis gives strongly consistent sensitivity estimates for the M/G/1 queue. Management Sci. 34(1):39–64.Link, Google Scholar
• Toulis P, Airoldi EM (2017) Asymptotic and finite-sample properties of estimators based on stochastic gradients. Ann. Statist. 45(4):1694–1727.Crossref, Google Scholar
• Van der Vaart AW (2000) Asymptotic Statistics, vol. 3 (Cambridge University Press, Cambridge, UK).Google Scholar
• Villani C (2009) Optimal Transport: Old and New, vol. 338 (Springer, Heidelberg, Germany).Crossref, Google Scholar
• Yang S, Li X, Lan G (2025) Data-driven minimax optimization with expectation constraints. Oper. Res. 73(3):1345–1365.Link, Google Scholar
• Yuan H, Luo Q, Shi C (2021) Marrying stochastic gradient descent with bandits: Learning algorithms for inventory systems with fixed costs. Management Sci. 67(10):6089–6115.Link, Google Scholar
• Zhang H, Chao X, Shi C (2020) Closing the gap: A learning algorithm for lost-sales inventory systems with lead times. Management Sci. 66(5):1962–1980.Link, Google Scholar
• Zhu Y, Dong J (2021) On constructing confidence region for model parameters in stochastic gradient descent via batch means. 2021 Winter Simulation Conf. (IEEE, Piscataway, NJ), 1–12.Google Scholar
• Zhu W, Chen X, Wu WB (2023) Online covariance matrix estimation in stochastic gradient descent. J. Amer. Statist. Assoc. 118:393–404.Crossref, Google Scholar