Pith. sign in

REVIEW 2 major objections 2 minor 2 cited by

Concentration of General Stochastic Approximation Under Heavy-Tailed Markovian Noise

T0 review · 2 major / 2 minor · reviewed 2026-05-21 · grok-4.3

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Stochastic approximation achieves concentration bounds whose tail type depends on step sizes and operator expansiveness under Markovian and martingale noise.

desk verdict The paper gives sharp maximal concentration bounds for stochastic approximation under mixed Markovian and martingale noise via a new MGF-based Lyapunov and truncation, but the expansive-operator regime needs checking on moment control. read the letter →

arxiv 2605.20999 v1 pith:SRQTNCAE submitted 2026-05-20 math.PR cs.LGmath.OCstat.ML

Shubhada Agrawal , Siva Theja Maguluri , Martin Zubeldia This is my paper · ORCID
classification math.PRcs.LGmath.OCstat.ML
keywords stochasticapproximationconcentrationboundsMarkoviannoiseheavytailedmartingaledifferencePoissonequationLyapunovfunctiontail
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The authors establish maximal concentration bounds for iterates of stochastic approximation algorithms that include both finite-state Markovian noise and an additional martingale-difference component. For bounded martingale noise, the error tails can be sub-Gaussian, sub-Weibull, or intermediate between Pareto and Weibull, according to the choice of step-size sequence and whether the random operator is contractive almost surely, non-expansive almost surely, or expansive with positive probability. The analysis introduces a Lyapunov function built around the moment-generating function of the Poisson equation solution and employs an auxiliary projected algorithm to manage the dependencies. Similar but adjusted bounds hold for unbounded martingale noise when steps are of order 1/k, with non-expansive operators keeping error tails at most three times the noise tails and expansive ones allowing substantially heavier tails. These findings matter for applications like reinforcement learning and optimization where dependent heavy-tailed noise is common and tail behavior governs the probability of large errors.

What carries the argument

A Lyapunov function that uses the moment-generating function of the solution to a Poisson equation for the Markov process, together with an auxiliary projected stochastic approximation algorithm.

What would settle it

Simulate the stochastic approximation process with an expansive operator and heavy-tailed martingale noise using 1/k steps, then compare the observed error tail decay to the predicted heavier-than-three-times inflation; a mismatch in the tail heaviness would falsify the distinction between non-expansive and expansive cases.

Watch

Extended reading notes

Core claim

The central claim is that maximal concentration bounds exist for stochastic approximation under general step sizes with mixed Markovian and martingale-difference noise, and that the qualitative form of these bounds (sub-Gaussian, sub-Weibull, or Pareto-like) is determined by the step-size schedule and the almost-sure contractiveness properties of the random operator, with matching lower bounds from worst-case examples and a truncation reduction for the unbounded-noise case.

Load-bearing premise

The existence of a Poisson equation solution whose moment-generating function is finite and controllable under the given Markov noise model is required for the Lyapunov construction to yield the stated concentration bounds.

Editorial extensions

If this is right

  • When the martingale-difference noise is bounded and the operator is almost surely contractive, sub-Gaussian tails are achievable for suitable step sizes.
  • Almost sure non-expansiveness leads to sub-Weibull tails.
  • Expansiveness with positive probability produces tails lighter than Pareto but heavier than Weibull.
  • With 1/k step sizes and unbounded noise, non-expansive operators limit tail inflation to a factor of three.
  • Worst-case constructions demonstrate that qualitatively better bounds cannot hold in general.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The truncation argument provides a general technique that might apply to concentration analysis of other dependent stochastic recursions.
  • Algorithm designers could prefer contractive or non-expansive operators to secure lighter error tails in noisy environments.
  • Empirical verification on low-dimensional examples with known Markov chains would test the predicted dependence of tail regimes on expansiveness.
  • These results imply that heavy-tailed noise in iterative methods does not necessarily produce arbitrarily heavy error tails when the operator satisfies suitable contraction properties.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

2 major / 2 minor

Summary. The paper claims to establish maximal concentration bounds for the iterates of stochastic approximation algorithms with general step sizes, where the driving noise consists of a finite-state Markovian component plus a martingale-difference sequence. For bounded martingale-difference noise, the error tails are sub-Gaussian, sub-Weibull, or intermediate (lighter than Pareto but heavier than Weibull) depending on the step-size sequence and on whether the random operator is almost surely contractive, almost surely non-expansive, or expansive with positive probability. The analysis introduces a novel Lyapunov function built from the moment-generating function of the solution to a Poisson equation, together with an auxiliary projected algorithm. The upper bounds are complemented by worst-case examples establishing sharpness. For unbounded martingale-difference noise with contractive average operator and step sizes of order 1/k, the error tail is at most three times the noise tail when the operator is a.s. non-expansive, but can be substantially heavier when the operator is expansive with positive probability; these results are obtained via a black-box truncation argument reducing to the bounded-noise case.

Significance. If the central claims hold, the results provide sharp, maximal concentration inequalities for stochastic approximation under a practically relevant noise model that combines Markovian dependence with heavy tails. This is significant for convergence analysis in stochastic optimization and reinforcement learning. The matching lower bounds via explicit worst-case constructions and the black-box truncation technique for the unbounded-noise regime are particular strengths that could serve as templates for related problems.

major comments (2)
  1. [§3.2–3.3] §3.2–3.3 (Poisson-equation Lyapunov construction): The novel Lyapunov function is defined using the moment-generating function of the solution to the Poisson equation for the finite-state Markov chain. When the random operator is expansive with positive probability, the Poisson solution can grow exponentially along certain trajectories. The manuscript does not supply an explicit a-priori bound establishing that this MGF remains finite and satisfies the uniform estimates needed for the auxiliary projection step, independently of the step-size sequence. This assumption is load-bearing for the claimed tail regimes in the expansive case.
  2. [§5.1] §5.1 (black-box truncation for unbounded noise): The reduction from unbounded to bounded martingale-difference noise via truncation is presented as preserving the maximal character of the bounds. However, when the operator is expansive with positive probability, it is not shown that the truncation threshold can be chosen so that the exponential growth possible in the Poisson solution does not inflate the tail beyond the stated factor of three relative to the noise tail.
minor comments (2)
  1. [Abstract] The abstract's description of the intermediate tail regime ('something lighter than any Pareto but heavier than any Weibull') is informal; a precise statement of the moment or tail index in that regime would improve readability.
  2. [§2] Assumptions on the random operator (contractive/non-expansive/expansive) are referenced repeatedly but would benefit from a single consolidated statement with equation numbers early in the paper.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments. The concerns about explicit bounds on the MGF in the expansive case and the truncation threshold selection are well-taken; we address both by adding the required a-priori estimates and explicit threshold arguments in the revision.

read point-by-point responses

  1. Referee: [§3.2–3.3] §3.2–3.3 (Poisson-equation Lyapunov construction): The novel Lyapunov function is defined using the moment-generating function of the solution to the Poisson equation for the finite-state Markov chain. When the random operator is expansive with positive probability, the Poisson solution can grow exponentially along certain trajectories. The manuscript does not supply an explicit a-priori bound establishing that this MGF remains finite and satisfies the uniform estimates needed for the auxiliary projection step, independently of the step-size sequence. This assumption is load-bearing for the claimed tail regimes in the expansive case.

    Authors: We agree that an explicit uniform bound on the MGF of the Poisson solution is required to justify the construction when the operator is expansive with positive probability. Because the driving chain is finite-state, its transition matrix has a spectral gap that, together with the almost-sure operator properties, yields a bound on the Poisson solution that is independent of the step-size sequence. In the revised manuscript we insert a new lemma (Lemma 3.4) that states and proves this uniform MGF bound; the proofs in §§3.2–3.3 are updated to invoke the lemma when verifying the Lyapunov estimates and the auxiliary projection step. revision: yes

  2. Referee: [§5.1] §5.1 (black-box truncation for unbounded noise): The reduction from unbounded to bounded martingale-difference noise via truncation is presented as preserving the maximal character of the bounds. However, when the operator is expansive with positive probability, it is not shown that the truncation threshold can be chosen so that the exponential growth possible in the Poisson solution does not inflate the tail beyond the stated factor of three relative to the noise tail.

    Authors: We note that the factor-of-three claim is stated only for the almost-surely non-expansive case; for operators that are expansive with positive probability the manuscript already asserts that tails may be substantially heavier. In the revision we add an explicit rule for selecting the truncation level in §5.1: the threshold is set proportionally to the noise tail quantile scaled by the uniform MGF bound supplied by the new Lemma 3.4. With this choice the reduction to the bounded-noise setting is justified, the factor-of-three bound is recovered for the non-expansive case, and the heavier-tail conclusion for the expansive case is preserved without additional inflation. The argument is written as a self-contained black-box lemma. revision: yes

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: novel Lyapunov construction and truncation argument are independent of target bounds

full rationale

The paper's central claims rest on a newly constructed Lyapunov function using the MGF of a Poisson-equation solution plus an auxiliary projected algorithm, followed by a black-box truncation that reduces the unbounded-noise case to the bounded case. These steps are presented as original technical devices rather than re-expressions of prior fitted quantities or self-citations. No equation or definition in the abstract or described derivation chain equates a claimed tail bound to an input parameter by construction, nor does any load-bearing premise collapse to a self-citation whose validity is presupposed. The analysis therefore remains self-contained against external benchmarks.

Assumptions & free parameters 0 free parameters · 2 assumptions · 0 invented entities

The paper rests on standard domain assumptions for stochastic approximation and finite-state Markov chains, plus the novel technical assumption that a suitable Poisson solution exists whose MGF yields a useful Lyapunov function.

assumptions (2)
  • domain assumption The noise process consists of a finite-state Markovian component plus a martingale-difference component.
    Explicitly stated as the noise model in the abstract.
  • domain assumption A solution to the Poisson equation exists and its moment-generating function can be used to construct a Lyapunov function that controls the error process.
    The analysis relies on this construction as described in the abstract.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Concentration of General Stochastic Approximation Under Heavy-Tailed Markovian Noise." pith.science (2026). https://pith.science/paper/SRQTNCAE

@misc{pith2026260520999,
  author       = {Pith},
  title        = {Pith review of: Concentration of General Stochastic Approximation Under Heavy-Tailed Markovian Noise},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/SRQTNCAE}},
  note         = {Machine review of arXiv:2605.20999}
}
abstract

We establish maximal concentration bounds for the iterates generated by stochastic approximation algorithms with general step sizes, where the noise has a finite-state Markovian component plus a Martingale-difference component. When the Martingale-difference noise is bounded, we show that the tail of the error can be sub-Gaussian, sub-Weibull, or something lighter than any Pareto but heavier than any Weibull, depending on the step size sequence and on whether the random operator is almost surely contractive, almost surely non-expansive, or expansive with positive probability. Our analysis relies on a novel Lyapunov function involving the moment-generating function of the solution to a Poisson equation, together with an auxiliary projected algorithm. We complement the upper bounds with worst-case examples showing that qualitatively sharper bounds are impossible. We further study the case of unbounded Martingale-difference noise when the average operator is contractive, and the step sizes are of order $1/k$. In this setting, we show that if the random operator is almost surely non-expansive, then the error tail is at most three times heavier than the noise tail, whereas if the random operator is expansive with positive probability, then the error may have substantially heavier tails. These results are obtained through a novel black-box truncation argument that reduces the unbounded-noise setting to the bounded-noise case.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Concentration and Mean-Square Bounds for Contractive Stochastic Approximation: A Unified Elementary Approach

    cs.LG 2026-07 accept novelty 6.0 of 10

    A unified, elementary analysis gives O(1/k) mean-square and sub-Gaussian maximal concentration bounds for contractive stochastic approximation under multiplicative noise with unbounded iterates.

  2. Non-Asymptotic Convergence of Stochastic Iterative Algorithms: A Lyapunov Framework

    cs.LG 2026-05 unverdicted novelty 2.0 of 10

    A survey of Lyapunov techniques using generalized Moreau envelopes as universal functions for non-asymptotic mean-square convergence analysis of stochastic iterative algorithms under contractive operators.

Reference graph

Works this paper leans on

223 extracted references · 223 canonical work pages · cited by 2 Pith papers

  1. [1]

    The Annals of Applied Probability , volume=

    Convergence rate and averaging of nonlinear two-time-scale stochastic approximation algorithms , author=. The Annals of Applied Probability , volume=

    work page

  2. [2]

    Operations Research , volume=

    A finite time analysis of temporal difference learning with linear function approximation , author=. Operations Research , volume=. 2021 , publisher=

    work page 2021

  3. [3]

    Chen, Zaiwei and Maguluri, Siva T and Shakkottai, Sanjay and Shanmugam, Karthikeyan , journal=. A. 2023 , publisher=

    work page 2023

  4. [4]

    2024 , publisher=

    Li, Gen and Cai, Changxiao and Chen, Yuxin and Wei, Yuting and Chi, Yuejie , journal=. 2024 , publisher=

    work page 2024

  5. [5]

    Na, Hyunjun and Lee, Donghwan , journal=

    work page

  6. [6]

    Conference on Learning Theory , pages=

    Softmax policy gradient methods can take exponential time to converge , author=. Conference on Learning Theory , pages=. 2021 , organization=

    work page 2021

  7. [7]

    2024 , publisher=

    Lee, Donghwan , journal=. 2024 , publisher=

    work page 2024

  8. [8]

    Proceedings of the AAAI Conference on Artificial Intelligence , volume=

    Dalal, Gal and Sz. Proceedings of the AAAI Conference on Artificial Intelligence , volume=

    work page

Show all 223 references
  1. [9]

    Doan, Thinh and Maguluri, Siva and Romberg, Justin , booktitle=

  2. [10]

    The Thirty Seventh Annual Conference on Learning Theory , pages=

    Fast two-time-scale stochastic gradient method with applications in reinforcement learning , author=. The Thirty Seventh Annual Conference on Learning Theory , pages=. 2024 , organization=

    2024

  3. [11]

    Conference On Learning Theory , pages=

    Finite sample analysis of two-timescale stochastic approximation with applications to reinforcement learning , author=. Conference On Learning Theory , pages=. 2018 , organization=

    2018

  4. [12]

    Mathematics of Operations Research , year=

    Finite-time high-probability bounds for Polyak--Ruppert averaged iterates of linear stochastic approximation , author=. Mathematics of Operations Research , year=

  5. [13]

    Prashanth, L. A. and Korda, Nathaniel and Munos, R. Concentration bounds for temporal difference learning with linear function approximation: The case of batch data and uniform sampling , IGNOREurl =. Machine Learning , number =. 2021 , bdsk-url-1 =

    2021

  6. [14]

    Systems & Control Letters , volume=

    A concentration bound for contractive stochastic approximation , author=. Systems & Control Letters , volume=. 2021 , publisher=

    2021

  7. [15]

    Advances in neural information processing systems , volume=

    Training language models to follow instructions with human feedback , author=. Advances in neural information processing systems , volume=

  8. [16]

    International Conference on Artificial Intelligence and Statistics , pages =

    Sample complexity bounds for two timescale value-based reinforcement learning algorithms , author =. International Conference on Artificial Intelligence and Statistics , pages =

  9. [17]

    Sample efficient stochastic policy extragradient algorithm for zero-sum

    Chen, Ziyi and Ma, Shaocong and Zhou, Yi , year = 2021, booktitle =. Sample efficient stochastic policy extragradient algorithm for zero-sum

    2021

  10. [18]

    International Conference on Machine Learning , pages =

    Sample and communication-efficient decentralized actor-critic algorithms with finite-time analysis , author =. International Conference on Machine Learning , pages =

  11. [19]

    Levine, Sergey and Kumar, Aviral and Tucker, George and Fu, Justin , journal=

  12. [20]

    IEEE Transactions on Automatic Control , volume=

    Finite-sample analysis of two-time-scale natural actor--critic algorithm , author=. IEEE Transactions on Automatic Control , volume=. 2022 , publisher=

    2022

  13. [21]

    Preprint arXiv:1902.03736 , year=

    A short note on concentration inequalities for random vectors with subgaussian norm , author=. Preprint arXiv:1902.03736 , year=

    1902 arXiv

  14. [22]

    Advances in Neural Information Processing Systems , volume=

    Weighted importance sampling for off-policy learning with linear function approximation , author=. Advances in Neural Information Processing Systems , volume=

  15. [23]

    Advances in Neural Information Processing Systems , volume=

    Tight high-probability bounds for linear stochastic approximation with fixed stepsize , author=. Advances in Neural Information Processing Systems , volume=

  16. [24]

    Durmus, Alain and Moulines, Eric and Naumov, Alexey and Samsonov, Sergey and Wai, Hoi-To , journal=

  17. [25]

    Stochastic Systems , year=

    Concentration of contractive stochastic approximation and reinforcement learning , author=. Stochastic Systems , year=

  18. [26]

    Li, Gen and Cai, Changxiao and Chen, Yuxin and Gu, Yuantao and Wei, Yuting and Chi, Yuejie , journal=

  19. [27]

    2017 IEEE international conference on robotics and automation (ICRA) , pages=

    Deep reinforcement learning for robotic manipulation with asynchronous off-policy updates , author=. 2017 IEEE international conference on robotics and automation (ICRA) , pages=. 2017 , organization=

    2017

  20. [28]

    Chen, Zaiwei and Maguluri, Siva Theja and Shakkottai, Sanjay and Shanmugam, Karthikeyan , journal=

  21. [29]

    , author=

    Offline policy evaluation across representations with applications to educational games. , author=. AAMAS , pages=

  22. [30]

    Liu, Yao and Gottesman, Omer and Raghu, Aniruddh and Komorowski, Matthieu and Faisal, Aldo A and Doshi-Velez, Finale and Brunskill, Emma , journal=

  23. [31]

    Preprint arXiv:1908.00261 , year=

    On the theory of policy gradient methods: Optimality, approximation, and distribution shift , author=. Preprint arXiv:1908.00261 , year=

    1908

  24. [32]

    1994 , publisher=

    Dayan, Peter and Sejnowski, Terrence J , journal=. 1994 , publisher=

    1994

  25. [33]

    2000 , organization=

    Kearns, Michael J and Singh, Satinder P , booktitle=. 2000 , organization=

    2000

  26. [34]

    2020 , publisher=

    First-order and Stochastic Optimization Methods for Machine Learning , author=. 2020 , publisher=

    2020

  27. [35]

    2012 , publisher=

    Markov Chains and Stochastic Stability , author=. 2012 , publisher=

    2012

  28. [36]

    1999 , organization=

    Sutton, Richard S , booktitle=. 1999 , organization=

    1999

  29. [37]

    1995 , publisher=

    Dynamic Programming and Optimal Control , author=. 1995 , publisher=

    1995

  30. [38]

    The convergence of

    Dayan, Peter , journal=. The convergence of. 1992 , publisher=

    1992

  31. [39]

    Advances in Neural Information Processing Systems , volume=

    A finite-time analysis of two time-scale actor-critic methods , author=. Advances in Neural Information Processing Systems , volume=

  32. [40]

    Primer on monotone operator methods , author=. Appl. Comput. Math , volume=

  33. [41]

    Journal of Machine Learning Research , volume=

    Beyond the regret minimization barrier: Optimal algorithms for stochastic strongly-convex optimization , author=. Journal of Machine Learning Research , volume=

  34. [42]

    Journal of Machine Learning Research , year=

    Beyond sub-Gaussian noises: Sharp concentration analysis for stochastic gradient descent , author=. Journal of Machine Learning Research , year=

  35. [43]

    Automatica , volume=

    Finite-sample analysis of nonlinear stochastic approximation with applications in reinforcement learning , author=. Automatica , volume=. 2022 , publisher=

    2022

  36. [44]

    Nicholas J. A. Harvey and Christopher Liaw and Sikander Randhawa , journal=

  37. [45]

    1996 , publisher=

    Neuro-Dynamic Programming , author=. 1996 , publisher=

    1996

  38. [46]

    2017 , publisher=

    Markov Chains and Mixing Times , author=. 2017 , publisher=

    2017

  39. [47]

    Sutton, Richard S and Barto, Andrew G , year=

  40. [48]

    Finite-sample analysis for

    Zou, Shaofeng and Xu, Tengyu and Liang, Yingbin , booktitle=. Finite-sample analysis for

  41. [49]

    Proceedings of the 25th international conference on Machine learning , pages=

    An analysis of reinforcement learning with function approximation , author=. Proceedings of the 25th international conference on Machine learning , pages=

  42. [50]

    Advances in Neural Information Processing Systems , volume=

    Improving sample complexity bounds for (natural) actor-critic algorithms , author=. Advances in Neural Information Processing Systems , volume=

  43. [51]

    1992 , publisher=

    Watkins, Christopher JCH and Dayan, Peter , journal=. 1992 , publisher=

    1992

  44. [52]

    2012 , publisher=

    Adaptive Algorithms and Stochastic Approximations , author=. 2012 , publisher=

    2012

  45. [53]

    Asynchronous stochastic approximation and

    Tsitsiklis, John N , journal=. Asynchronous stochastic approximation and. 1994 , publisher=

    1994

  46. [54]

    Error bounds for constant step-size

    Beck, Carolyn L and Srikant, Rayadurgam , journal=. Error bounds for constant step-size. 2012 , publisher=

    2012

  47. [55]

    Advances in neural information processing systems , pages=

    Convergence of stochastic iterative dynamic programming algorithms , author=. Advances in neural information processing systems , pages=

  48. [56]

    Machine Learning Proceedings 1995 , pages=

    Residual algorithms: Reinforcement learning with function approximation , author=. Machine Learning Proceedings 1995 , pages=. 1995 , publisher=

    1995

  49. [57]

    Learning rates for

    Even-Dar, Eyal and Mansour, Yishay , journal=. Learning rates for

  50. [58]

    Finite-sample convergence rates for

    Kearns, Michael J and Singh, Satinder P , booktitle=. Finite-sample convergence rates for

  51. [59]

    The asymptotic convergence-rate of

    Szepesv. The asymptotic convergence-rate of. Advances in Neural Information Processing Systems , pages=

  52. [60]

    The Annals of Mathematical Statistics , pages=

    A stochastic approximation method , author=. The Annals of Mathematical Statistics , pages=. 1951 , publisher=

    1951

  53. [61]

    2012 , publisher=

    Stochastic Approximation Methods for Constrained and Unconstrained Systems , author=. 2012 , publisher=

    2012

  54. [62]

    Advances in neural information processing systems , pages=

    Analysis of temporal-difference learning with function approximation , author=. Advances in neural information processing systems , pages=

  55. [63]

    Machine learning , volume=

    Learning to predict by the methods of temporal differences , author=. Machine learning , volume=. 1988 , publisher=

    1988

  56. [64]

    International conference on machine learning , pages=

    Asynchronous methods for deep reinforcement learning , author=. International conference on machine learning , pages=

  57. [65]

    2019 , organization=

    Dann, Christoph and Li, Lihong and Wei, Wei and Brunskill, Emma , booktitle=. 2019 , organization=

    2019

  58. [66]

    A theoretical analysis of deep

    Fan, Jianqing and Wang, Zhaoran and Xie, Yuchen and Yang, Zhuoran , booktitle=. A theoretical analysis of deep. 2020 , organization=

    2020

  59. [67]

    2009 , publisher=

    Stochastic Approximation: A Dynamical Systems Viewpoint , author=. 2009 , publisher=

    2009

  60. [68]

    2019 , publisher=

    Thoppe, Gugan and Borkar, Vivek , journal=. 2019 , publisher=

    2019

  61. [69]

    2002 , publisher=

    Nonlinear Systems , author=. 2002 , publisher=

    2002

  62. [70]

    Haddad, Wassim M and Chellaboina, VijaySekhar , year=

  63. [71]

    1994 , publisher=

    Tesauro, Gerald , journal=. 1994 , publisher=

    1994

  64. [72]

    Nature , volume=

    Mastering the game of Go without human knowledge , author=. Nature , volume=. 2017 , publisher=

    2017

  65. [73]

    Shah, Devavrat and Xie, Qiaomin , booktitle=

  66. [74]

    1999 , publisher=

    Tsitsiklis, John N and Van Roy, Benjamin , journal=. 1999 , publisher=

    1999

  67. [75]

    SIAM Journal on optimization , volume=

    Robust stochastic approximation approach to stochastic programming , author=. SIAM Journal on optimization , volume=. 2009 , publisher=

    2009

  68. [76]

    Lee, Donghwan and He, Niao , journal=

  69. [77]

    Machine Learning Proceedings 1995 , pages=

    Stable function approximation in dynamic programming , author=. Machine Learning Proceedings 1995 , pages=. 1995 , publisher=

    1995

  70. [78]

    2013 , publisher=

    Kober, Jens and Bagnell, J Andrew and Peters, Jan , journal=. 2013 , publisher=

    2013

  71. [79]

    1964 , publisher=

    Principles of Mathematical Analysis , author=. 1964 , publisher=

    1964

  72. [80]

    Advances in Neural Information Processing Systems , pages=

    Managing power consumption and performance of computing systems using reinforcement learning , author=. Advances in Neural Information Processing Systems , pages=

  73. [81]

    Preprint arXiv:1610.03295 , year=

    Safe, multi-agent, reinforcement learning for autonomous driving , author=. Preprint arXiv:1610.03295 , year=

    arXiv

  74. [82]

    Advances in neural information processing systems , pages=

    A convergent O(n) temporal-difference algorithm for off-policy learning with linear function approximation , author=. Advances in neural information processing systems , pages=

  75. [83]

    Liu, Bo and Liu, Ji and Ghavamzadeh, Mohammad and Mahadevan, Sridhar and Petrik, Marek , booktitle=

  76. [84]

    Lakshminarayanan, Chandrashekar and Szepesvari, Csaba , booktitle=

  77. [85]

    Wiley Interdisciplinary Reviews: Computational Statistics , volume=

    Stochastic approximation: a survey , author=. Wiley Interdisciplinary Reviews: Computational Statistics , volume=. 2010 , publisher=

    2010

  78. [86]

    Ghavamzadeh, Mohammad and Kappen, Hilbert J and Azar, Mohammad G and Munos, R. Speedy. Advances in neural information processing systems , pages=

  79. [87]

    Devraj, Adithya M and Meyn, Sean , booktitle=. Zap

  80. [88]

    Puterman, Martin L , journal=

  81. [89]

    Siam Review , volume=

    Optimization methods for large-scale machine learning , author=. Siam Review , volume=. 2018 , publisher=

    2018

  82. [90]

    Stochastic Systems , volume=

    Transform methods for heavy-traffic analysis , author=. Stochastic Systems , volume=. 2020 , publisher=

    2020

  83. [91]

    Journal of Optimization theory and Applications , volume=

    On the existence of fixed points for approximate value iteration and temporal-difference learning , author=. Journal of Optimization theory and Applications , volume=. 2000 , publisher=

    2000

  84. [92]

    Journal of Machine Learning Research , volume=

    Near-optimal regret bounds for reinforcement learning , author=. Journal of Machine Learning Research , volume=

  85. [93]

    Foundations and Trends

    Regret analysis of stochastic and nonstochastic multi-armed bandit problems , author=. Foundations and Trends. 2012 , publisher=

    2012

  86. [94]

    Automatica , volume=

    Average cost temporal-difference learning , author=. Automatica , volume=. 1999 , publisher=

    1999

  87. [95]

    2013 , publisher=

    Stochastic Processes: Theory for Applications , author=. 2013 , publisher=

    2013

  88. [96]

    2019 , publisher=

    High-Dimensional Statistics: A Non-Asymptotic Viewpoint , author=. 2019 , publisher=

    2019

  89. [97]

    Stochastic approximation with cone-contractive operators: Sharp _ -bounds for

    Wainwright, Martin J , journal=. Stochastic approximation with cone-contractive operators: Sharp _ -bounds for

  90. [98]

    Preprint arXiv:2201.08518v1 , year=

    Optimal variance-reduced stochastic approximation in Banach spaces , author=. Preprint arXiv:2201.08518v1 , year=

  91. [99]

    Borkar, Vivek S and Meyn, Sean P , journal=. The. 2000 , publisher=

    2000

  92. [100]

    Improved upper bounds on the expected error in constant step-size

    Beck, Carolyn L and Srikant, Rayadurgam , booktitle=. Improved upper bounds on the expected error in constant step-size. 2013 , organization=

    2013

  93. [101]

    Conference on Learning Theory , pages=

    Finite-time analysis of asynchronous stochastic approximation and Q -learning , author=. Conference on Learning Theory , pages=. 2020 , organization=

    2020

  94. [102]

    Variance-reduced

    Wainwright, Martin J , journal=. Variance-reduced

  95. [103]

    Nature , volume=

    Highly accurate protein structure prediction with AlphaFold , author=. Nature , volume=. 2021 , publisher=

    2021

  96. [104]

    A finite-time analysis of

    Xu, Pan and Gu, Quanquan , booktitle=. A finite-time analysis of. 2020 , organization=

    2020

  97. [105]

    2016 , publisher=

    Silver, David and Huang, Aja and Maddison, Chris J and Guez, Arthur and Sifre, Laurent and Van Den Driessche, George and Schrittwieser, Julian and Antonoglou, Ioannis and Panneershelvam, Veda and Lanctot, Marc and others , journal=. 2016 , publisher=

    2016

  98. [106]

    Preprint arXiv:1312.5602 , year=

    Playing atari with deep reinforcement learning , author=. Preprint arXiv:1312.5602 , year=

    arXiv

  99. [107]

    2004 , publisher=

    Convex Optimization , author=. 2004 , publisher=

    2004

  100. [108]

    2012 , publisher=

    Beck, Amir and Teboulle, Marc , journal=. 2012 , publisher=

    2012

  101. [109]

    On the number of samples required for

    Borkar, VS , booktitle=. On the number of samples required for

  102. [110]

    Advances in Neural Information Processing Systems , pages=

    Learning to navigate in cities without a map , author=. Advances in Neural Information Processing Systems , pages=

  103. [111]

    Journal of Complexity , volume=

    On lower complexity bounds for large-scale smooth convex optimization , author=. Journal of Complexity , volume=. 2015 , publisher=

    2015

  104. [112]

    IEEE Transactions on Automatic Control , volume=

    Convergence results for some temporal difference methods based on least squares , author=. IEEE Transactions on Automatic Control , volume=. 2009 , publisher=

    2009

  105. [113]

    Proceedings of the 26th Annual International Conference on Machine Learning , pages=

    Fast gradient-descent methods for temporal-difference learning with linear function approximation , author=. Proceedings of the 26th Annual International Conference on Machine Learning , pages=

  106. [114]

    On Stochastic Approximation

    Dvoretzky, Aryeh. On Stochastic Approximation. Proceedings of the Third Berkeley Symposium on Mathematical Statistics and Probability, Volume 1: Contributions to the Theory of Statistics. 1956

    1956

  107. [115]

    Sur les op

    Banach, Stefan , journal=. Sur les op

  108. [116]

    Banach Journal of Mathematical Analysis , volume=

    On Stefan Banach and some of his results , author=. Banach Journal of Mathematical Analysis , volume=. 2007 , publisher=

    2007

  109. [117]

    Boundedness of iterates in

    Gosavi, Abhijit , journal=. Boundedness of iterates in. 2006 , publisher=

    2006

  110. [118]

    An analog scheme for fixed point computation -- part

    Borkar, Vivek S and Soumyanatha, K , journal=. An analog scheme for fixed point computation -- part. 1997 , publisher=

    1997

  111. [119]

    nature , volume=

    Mastering the game of Go with deep neural networks and tree search , author=. nature , volume=. 2016 , publisher=

    2016

  112. [120]

    Torchbeast: a

    K. Torchbeast: a. Preprint arXiv:1910.03552 , year=

    1910

  113. [121]

    Automation and Remote Control , volume=

    Pseudogradient adaptation and training algorithms , author=. Automation and Remote Control , volume=

  114. [122]

    Journal of the American Statistical Association , volume=

    Some asymptotic results for learning in single hidden-layer feedforward network models , author=. Journal of the American Statistical Association , volume=. 1989 , publisher=

    1989

  115. [123]

    ICML , pages=

    Off-policy temporal-difference learning with function approximation , author=. ICML , pages=

  116. [124]

    Management science , volume=

    Importance sampling for stochastic simulations , author=. Management science , volume=. 1989 , publisher=

    1989

  117. [125]

    1997 , publisher=

    Linear Algebra , author=. 1997 , publisher=

    1997

  118. [126]

    SIAM Journal on Optimization , volume=

    Stochastic model-based minimization of weakly convex functions , author=. SIAM Journal on Optimization , volume=. 2019 , publisher=

    2019

  119. [127]

    Proximit

    Moreau, Jean-Jacques , journal=. Proximit

  120. [128]

    2005 , publisher=

    Introduction to Hilbert Spaces with Applications , author=. 2005 , publisher=

    2005

  121. [129]

    Foundations and Trends

    Online learning and online convex optimization , author=. Foundations and Trends. 2012 , publisher=

    2012

  122. [130]

    Espeholt, Lasse and Soyer, Hubert and Munos, Remi and Simonyan, Karen and Mnih, Vlad and Ward, Tom and Doron, Yotam and Firoiu, Vlad and Harley, Tim and Dunning, Iain and others , booktitle=

  123. [131]

    Preprint arXiv:1509.02971 , year=

    Continuous control with deep reinforcement learning , author=. Preprint arXiv:1509.02971 , year=

    arXiv

  124. [132]

    Advances in neural information processing systems , pages=

    Actor-critic algorithms , author=. Advances in neural information processing systems , pages=. 2000 , organization=

    2000

  125. [133]

    Preprint arXiv:1611.01224 , year=

    Sample efficient actor-critic with experience replay , author=. Preprint arXiv:1611.01224 , year=

    arXiv

  126. [134]

    Preprint arXiv:1607.07086 , year=

    An actor-critic algorithm for sequence prediction , author=. Preprint arXiv:1607.07086 , year=

    arXiv

  127. [135]

    Neurocomputing , volume=

    Natural actor-critic , author=. Neurocomputing , volume=. 2008 , publisher=

    2008

  128. [136]

    Sadhana , volume=

    The actor-critic algorithm as multi-time-scale stochastic approximation , author=. Sadhana , volume=. 1997 , publisher=

    1997

  129. [137]

    Degris, Thomas and White, Martha and Sutton, Richard , booktitle=

  130. [138]

    Alexander Rakhlin and Ohad Shamir and Karthik Sridharan , booktitle=

  131. [139]

    Econometrica: Journal of the Econometric Society , pages=

    Bayesian inference in econometric models using Monte Carlo integration , author=. Econometrica: Journal of the Econometric Society , pages=. 1989 , publisher=

    1989

  132. [140]

    Journal of Computational and Graphical Statistics , volume=

    Truncated importance sampling , author=. Journal of Computational and Graphical Statistics , volume=. 2008 , publisher=

    2008

  133. [141]

    , author=

    Policy gradient methods for reinforcement learning with function approximation. , author=. NIPs , volume=. 1999 , organization=

    1999

  134. [142]

    Journal of Artificial Intelligence Research , volume=

    Infinite-horizon policy-gradient estimation , author=. Journal of Artificial Intelligence Research , volume=

  135. [143]

    Advances in neural information processing systems , volume=

    A natural policy gradient , author=. Advances in neural information processing systems , volume=

  136. [144]

    Machine Learning , volume=

    Policy gradient in lipschitz markov decision processes , author=. Machine Learning , volume=. 2015 , publisher=

    2015

  137. [145]

    Approximately optimal approximate reinforcement learning , author=. In Proc. 19th International Conference on Machine Learning , year=

  138. [146]

    Mathematics of Operations Research , volume=

    Online Markov decision processes , author=. Mathematics of Operations Research , volume=. 2009 , publisher=

    2009

  139. [147]

    International Conference on Machine Learning , pages=

    A theory of regularized markov decision processes , author=. International Conference on Machine Learning , pages=. 2019 , organization=

    2019

  140. [148]

    The Journal of Machine Learning Research , volume=

    Dynamic policy programming , author=. The Journal of Machine Learning Research , volume=. 2012 , publisher=

    2012

  141. [149]

    Shani, Lior and Efroni, Yonathan and Mannor, Shie , booktitle=

  142. [150]

    International Conference on Machine Learning , pages=

    On the global convergence rates of softmax policy gradient methods , author=. International Conference on Machine Learning , pages=. 2020 , organization=

    2020

  143. [151]

    Preprint arXiv:2007.06558 , year=

    Fast global convergence of natural policy gradient methods with entropy regularization , author=. Preprint arXiv:2007.06558 , year=

    2007

  144. [152]

    Preprint arXiv:2007.11120 , year=

    A note on the linear convergence of policy gradient methods , author=. Preprint arXiv:2007.11120 , year=

    2007

  145. [153]

    Wang, Lingxiao and Cai, Qi and Yang, Zhuoran and Wang, Zhaoran , journal=

  146. [154]

    Preprint arXiv:1906.10306 , year=

    Neural proximal/trust region policy optimization attains globally optimal policy , author=. Preprint arXiv:1906.10306 , year=

    1906

  147. [155]

    International Conference on Machine Learning , pages=

    Reinforcement learning with deep energy-based policies , author=. International Conference on Machine Learning , pages=. 2017 , organization=

    2017

  148. [156]

    SIAM Journal on Control and Optimization , volume=

    Global convergence of policy gradient methods to (almost) locally optimal policies , author=. SIAM Journal on Control and Optimization , volume=. 2020 , publisher=

    2020

  149. [157]

    A. G. IEEE Transactions on Systems, Man, and Cybernetics , title=. 1983 , volume=

    1983

  150. [158]

    Proceedings of the Sixth Yale Workshop on Adaptive and Learning Systems , pages=

    A mathematical analysis of actor-critic architectures for learning optimal controls through incremental dynamic programming , author=. Proceedings of the Sixth Yale Workshop on Adaptive and Learning Systems , pages=. 1990 , organization=

    1990

  151. [159]

    2019 IEEE 58th Conference on Decision and Control (CDC) , pages=

    Convergence and iteration complexity of policy gradient method for infinite-horizon reinforcement learning , author=. 2019 IEEE 58th Conference on Decision and Control (CDC) , pages=. 2019 , organization=

    2019

  152. [160]

    Advances in neural information processing systems , pages=

    A generalized natural actor-critic algorithm , author=. Advances in neural information processing systems , pages=

  153. [161]

    Thomas, Philip S and Dabney, William and Mahadevan, Sridhar and Giguere, Stephen , booktitle=

  154. [162]

    Automatica , volume=

    Natural actor--critic algorithms , author=. Automatica , volume=. 2009 , publisher=

    2009

  155. [163]

    2019 , organization=

    Yang, Lin and Wang, Mengdi , booktitle=. 2019 , organization=

    2019

  156. [164]

    Computer Science Department Faculty Publication Series , pages=

    Eligibility traces for off-policy policy evaluation , author=. Computer Science Department Faculty Publication Series , pages=

  157. [165]

    Proceedings of the 30th International Conference on Neural Information Processing Systems , pages=

    Safe and efficient off-policy reinforcement learning , author=. Proceedings of the 30th International Conference on Neural Information Processing Systems , pages=

  158. [166]

    Optimization Foundations for Reinforcement Learning Workshop at Advances in Neural Information Processing Systems (NeurIPS) , year=

    On the finite-time convergence of actor-critic algorithm , author=. Optimization Foundations for Reinforcement Learning Workshop at Advances in Neural Information Processing Systems (NeurIPS) , year=

  159. [167]

    International Conference on Algorithmic Learning Theory , pages=

    Q( ) with off-policy corrections , author=. International Conference on Algorithmic Learning Theory , pages=. 2016 , organization=

    2016

  160. [168]

    Kumar, Harshat and Koppel, Alec and Ribeiro, Alejandro , journal=

  161. [169]

    A concentration bound for

    Chandak, Siddharth and Borkar, Vivek S , journal=. A concentration bound for. 2026 , publisher=

    2026

  162. [170]

    International Conference on Artificial Intelligence and Statistics , pages=

    Sample complexity of policy-based methods under off-policy sampling and linear function approximation , author=. International Conference on Artificial Intelligence and Statistics , pages=. 2022 , organization=

    2022

  163. [171]

    IEEE Control Systems Letters , volume=

    Finite-sample analysis of off-policy natural actor--critic with linear function approximation , author=. IEEE Control Systems Letters , volume=. 2022 , publisher=

    2022

  164. [172]

    Xu, Tengyu and Wang, Zhe and Liang, Yingbin , journal=

  165. [173]

    1983 , journal=

    Problem complexity and method efficiency in optimization , author=. 1983 , journal=

    1983

  166. [174]

    1999 , publisher=

    Elements of Information Theory , author=. 1999 , publisher=

    1999

  167. [175]

    Journal of computer and system sciences , volume=

    A decision-theoretic generalization of on-line learning and an application to boosting , author=. Journal of computer and system sciences , volume=. 1997 , publisher=

    1997

  168. [176]

    Conference on Learning Theory , pages=

    Stochastic linear optimization never overfits with quadratically-bounded losses on general data , author=. Conference on Learning Theory , pages=. 2022 , organization=

    2022

  169. [177]

    International Conference on Machine Learning , pages=

    Provably convergent two-timescale off-policy actor-critic with function approximation , author=. International Conference on Machine Learning , pages=. 2020 , organization=

    2020

  170. [178]

    Preprint arXiv:1802.07842 , year=

    Convergent actor-critic algorithms under off-policy training and function approximation , author=. Preprint arXiv:1802.07842 , year=

    arXiv

  171. [179]

    2020 , organization=

    Mou, Wenlong and Li, Chris Junchi and Wainwright, Martin J and Bartlett, Peter L and Jordan, Michael I , booktitle=. 2020 , organization=

    2020

  172. [180]

    2021 , publisher=

    Li, Gen and Wei, Yuting and Chi, Yuejie and Gu, Yuantao and Chen, Yuxin , journal=. 2021 , publisher=

    2021

  173. [181]

    International Conference on Machine Learning , pages=

    Interpretable off-policy evaluation in reinforcement learning by highlighting influential transitions , author=. International Conference on Machine Learning , pages=. 2020 , organization=

    2020

  174. [182]

    Chen, Zaiwei and Maguluri, Siva Theja and Zubeldia, Martin , journal=

  175. [183]

    Nature , volume=

    Magnetic control of tokamak plasmas through deep reinforcement learning , author=. Nature , volume=. 2022 , publisher=

    2022

  176. [184]

    On a modification of Chebyshev’s inequality and of the error formula of Laplace , author=. Ann. Sci. Inst. Sav. Ukraine, Sect. Math , volume=

  177. [185]

    The Annals of Mathematical Statistics , pages=

    A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations , author=. The Annals of Mathematical Statistics , pages=. 1952 , publisher=

    1952

  178. [186]

    The collected works of Wassily Hoeffding , pages=

    Probability inequalities for sums of bounded random variables , author=. The collected works of Wassily Hoeffding , pages=. 1994 , publisher=

    1994

  179. [187]

    1957 , publisher=

    Dynamic Programming , author=. 1957 , publisher=

    1957

  180. [188]

    Preprint arXiv:2102.00135 , year=

    Policy mirror descent for reinforcement learning: Linear convergence, new sampling complexity, and generalized problem classes , author=. Preprint arXiv:2102.00135 , year=

  181. [189]

    arXiv preprint arXiv:2411.13711 , year=

    Almost sure convergence rates and concentration of stochastic approximation and reinforcement learning with markovian noise , author=. arXiv preprint arXiv:2411.13711 , year=

  182. [190]

    Foundations of Computational Mathematics , volume=

    Matrix concentration for products , author=. Foundations of Computational Mathematics , volume=. 2022 , publisher=

    2022

  183. [191]

    arXiv preprint arXiv:2511.18273 , year=

    Time-uniform concentration bounds for iterative algorithms , author=. arXiv preprint arXiv:2511.18273 , year=

  184. [192]

    1939 , publisher=

    Etude critique de la notion de collectif , author=. 1939 , publisher=

    1939

  185. [193]

    The Annals of Applied Probability , volume=

    Concentration of contractive stochastic approximation: Additive and multiplicative noise , author=. The Annals of Applied Probability , volume=. 2025 , publisher=

    2025

  186. [194]

    arXiv preprint arXiv:2409.05733 , year=

    Markov Chain Variance Estimation: A Stochastic Approximation Approach , author=. arXiv preprint arXiv:2409.05733 , year=

  187. [195]

    Proceedings of The 28th International Conference on Artificial Intelligence and Statistics , pages =

    Stochastic Approximation with Unbounded Markovian Noise: A General-Purpose Theorem , author =. Proceedings of The 28th International Conference on Artificial Intelligence and Statistics , pages =. 2025 , volume =

    2025

  188. [196]

    arXiv preprint arXiv:2605.07104 , year=

    Almost Sure Convergence Rates of Stochastic Approximation and Reinforcement Learning via a Poisson-Moreau Drift , author=. arXiv preprint arXiv:2605.07104 , year=

    arXiv

  189. [197]

    Operations Research , volume=

    A lyapunov theory for finite-sample guarantees of markovian stochastic approximation , author=. Operations Research , volume=. 2024 , publisher=

    2024

  190. [198]

    Advances in Neural Information Processing Systems , volume=

    Finite-sample analysis of contractive stochastic approximation using smooth convex envelopes , author=. Advances in Neural Information Processing Systems , volume=

  191. [199]

    2017 , publisher=

    First-order methods in optimization , author=. 2017 , publisher=

    2017

  192. [200]

    Linear Algebra and its Applications , volume=

    Concentration inequalities for random matrix products , author=. Linear Algebra and its Applications , volume=. 2020 , publisher=

    2020

  193. [201]

    Conference on learning theory , pages=

    Streaming pca: Matching matrix bernstein and near-optimal finite sample guarantees for oja’s algorithm , author=. Conference on learning theory , pages=. 2016 , organization=

    2016

  194. [202]

    arXiv preprint arXiv:2008.05104 , year=

    A matrix concentration inequality for products , author=. arXiv preprint arXiv:2008.05104 , year=

    2008

  195. [203]

    2018 , publisher=

    Markov chains , author=. 2018 , publisher=

    2018

  196. [204]

    arXiv preprint arXiv:2003.06319 , year=

    On concentration inequalities for random matrix products , author=. arXiv preprint arXiv:2003.06319 , year=

    2003

  197. [205]

    Conference on Learning Theory , pages=

    Finite-time error bounds for linear stochastic approximation andtd learning , author=. Conference on Learning Theory , pages=. 2019 , organization=

    2019

  198. [206]

    arXiv preprint arXiv:2102.01567 , year=

    A Lyapunov theory for finite-sample guarantees of asynchronous Q-learning and TD-learning variants , author=. arXiv preprint arXiv:2102.01567 , year=

  199. [207]

    SIAM Journal on Optimization , volume=

    Ergodic mirror descent , author=. SIAM Journal on Optimization , volume=. 2012 , publisher=

    2012

  200. [208]

    Advances in Neural Information Processing Systems , volume=

    A general-purpose theorem for high-probability bounds of stochastic approximation with polyak averaging , author=. Advances in Neural Information Processing Systems , volume=

  201. [209]

    SIAM journal on control and optimization , volume=

    Acceleration of stochastic approximation by averaging , author=. SIAM journal on control and optimization , volume=. 1992 , publisher=

    1992

  202. [210]

    Annals of Applied Probability , pages=

    Chernoff-type bound for finite Markov chains , author=. Annals of Applied Probability , pages=. 1998 , publisher=

    1998

  203. [211]

    Electronic Journal of Probability , volume=

    Concentration inequalities for Markov chains by Marton couplings and spectral methods , author=. Electronic Journal of Probability , volume=. 2015 , publisher=

    2015

  204. [212]

    arXiv preprint arXiv:1201.0559 , year=

    Chernoff-Hoeffding bounds for Markov chains: Generalized and simplified , author=. arXiv preprint arXiv:1201.0559 , year=

    arXiv

  205. [213]

    Frontiers of Mathematics in China , volume=

    Hoeffding’s inequality for Markov processes via solution of Poisson’s equation , author=. Frontiers of Mathematics in China , volume=. 2021 , publisher=

    2021

  206. [214]

    Statistics & probability letters , volume=

    A Hoeffding inequality for Markov chains using a generalized inverse , author=. Statistics & probability letters , volume=. 2009 , publisher=

    2009

  207. [215]

    2002 , publisher=

    Glynn, Peter W and Ormoneit, Dirk , journal=. 2002 , publisher=

    2002

  208. [216]

    arXiv preprint arXiv:1909.00843 , year=

    Simple and optimal high-probability bounds for strongly-convex stochastic gradient descent , author=. arXiv preprint arXiv:1909.00843 , year=

    1909

  209. [217]

    Conference on Learning Theory , pages=

    Tight analyses for non-smooth stochastic gradient descent , author=. Conference on Learning Theory , pages=. 2019 , organization=

    2019

  210. [218]

    arXiv preprint arXiv:1109.5647 , year=

    Making gradient descent optimal for strongly convex stochastic optimization , author=. arXiv preprint arXiv:1109.5647 , year=

    arXiv

  211. [219]

    On approximation, by finite elements of order one, and resolution, by p

    Glowinski, Roland and Marroco, America , journal=. On approximation, by finite elements of order one, and resolution, by p. 1975 , publisher=

    1975

  212. [220]

    The Journal of Machine Learning Research , volume=

    Beyond sub-gaussian noises: Sharp concentration analysis for stochastic gradient descent , author=. The Journal of Machine Learning Research , volume=. 2022 , publisher=

    2022

  213. [221]

    Mathematics of Operations Research , volume=

    On the efficiency of random permutation for ADMM and coordinate descent , author=. Mathematics of Operations Research , volume=. 2020 , publisher=

    2020

  214. [222]

    Conference on Learning Theory , pages=

    On the stability of random matrix product with markovian noise: Application to linear stochastic approximation and td learning , author=. Conference on Learning Theory , pages=. 2021 , organization=

    2021

  215. [223]

    Journal of Machine Learning Research , year =

    Elad Hazan and Satyen Kale , title =. Journal of Machine Learning Research , year =

Pith tools

Reviewed May 21, 2026 · model on record in the stance chip above.