A General-Purpose Theorem for High-Probability Bounds of Stochastic Approximation with Polyak Averaging 0 0 footnotetext: A version of this paper was first submitted to a conference in May 2025.

Sajad Khodadadian, Martin Zubeldia · 2025

Read A General-Purpose Theorem for High-Probability Bounds of Stochastic Approximation with Polyak Averaging 0 0 footnotetext: A version of this paper was first submitted to a conference in May 2025. by Sajad Khodadadian, Martin Zubeldia (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-21796.txt.

Introduction

Sajad Khodadadian and Martin Zubeldia present a 2025 math paper on step-by-step algorithms that learn from noisy data. Averaging the steps of such an algorithm is a classic trick that gives the best possible spread of results in the long run. Firm guarantees for the averaged result at finite times, though, were missing in general settings.

Their framework starts from bounds on single steps and builds a sharp bound for the average. An example shows the bound cannot be tightened beyond a constant factor. The result applies at once to shrinking-type algorithms and to learning methods used in games and control. New bounds follow in settings where older analysis struggled.

Catalog record

CREATORSajad Khodadadian, Martin Zubeldia
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE114 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-21796

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

A General-Purpose Theorem for High-Probability Bounds of Stochastic Approximation with Polyak Averaging 0 0 footnotetext: A version of this paper was first submitted to a conference in May 2025. Sajad Khodadadian, Martin Zubeldia Abstract Polyak–Ruppert averaging is a widely used technique to achieve the optimal asymptotic variance of stochastic approximation (SA) algorithms, yet its high-probability performance guarantees remain underexplored in general settings. In this paper, we present a general framework for establishing non-asymptotic concentration bounds for the error of averaged SA iterates. Our approach assumes access to individual concentration bounds for the unaveraged iterates and yields a sharp bound on the averaged iterates. We also construct an example, showing the tightness of our result up to constant multiplicative factors. As direct applications, we derive tight concentration bounds for contractive SA algorithms and for algorithms such as temporal difference learning and Q Q -learning with averaging, obtaining new bounds in settings where traditional analysis is challenging. $*$ $*$ footnotetext: Equal contribution between Sajad Khodadadian and Martin Zubeldia. Introduction Stochastic approximation (SA) algorithms are central to modern machine learning and optimization, serving as the foundation for methods ranging from stochastic gradient descent to Reinforcement Learning (RL) algorithms such as temporal difference (TD) learning and Q -learning. The general form of an SA algorithm is given by \displaystyle x_{k+1}=(1-\alpha_{k})x_{k}+\alpha_{k}F(x_{k},w_{k+1}), (1.1) where \alpha_{k}=\alpha/(k+h)^{\xi} for some h>1 , \alpha>0 , and \xi\in[0,1] is the step size, and w_{k+1} represents random noise, possibly arising from sampling or environmental interactions. A significant body of work has been devoted to analyzing the convergence of such algorithms, providing both mean-square and high-probability error bounds under various assumptions (e.g., [ 42 , 12 , 18 ] ). A key technique for improving the asymptotic variance and robustness of SA algorithms is Polyak-Ruppert averaging , where instead of using the iterates x_{k} directly, one uses the averaged sequence \displaystyle y_{k}=\frac{1}{k+1}\sum_{i=0}^{k}x_{i}. (1.2) This averaging has been shown to achieve optimal asymptotic behavior in a variety of settings, including stochastic gradient descent [ 33 , 31 , 1 ] , contractive SA [ 10 ] , and RL algorithms [ 30 , 29 ] . Despite its empirical and theoretical effectiveness, sharp finite-time high-probability bounds for averaged SA in general settings remain underexplored. Our Contributions In this paper, we develop a general-purpose framework for deriving finite-time high-probability bounds for averaged SA iterates. Specifically, we assume that the base SA iterates x_{i} , with probability at least 1-\delta^{\prime} , satisfies a high-probability bound of the form \|x_{i}-x^{*}\|_{c}^{2}\leq\alpha_{i}f(\delta^{\prime},k) for all \delta^{\prime}\in(0,1) and 0\leq i\leq k , where x^{*} is the limit point (e.g., the fixed point or optimum), and f is a known function of \delta^{\prime} and k . Building on this assumption, we establish that for any \delta\in(0,1) , with probability at least 1-\delta , the averaged iterates satisfy the bound \displaystyle\|y_{k}-x^{*}\|_{c}^{2}\leq c\frac{\log(1/\delta)+d}{k+1}\bar{\sigma}^{2}+o\left(\frac{\log(1/\delta)}{k}\right), where d is the dimension of the variables, \bar{\sigma}^{2} is a variance proxy, and c is a universal constant. We also construct an example to show that our result is tight up to the constant factor c . Our general theorem has several important consequences. First, we provide a principled way to select the step size schedule \{\alpha_{k}\}_{k\geq 0} to optimize the concentration of averaged SA under a variety of operators F . Second, we apply our framework to contractive SA algorithms , establishing sharp concentration bounds in these settings. Third, we leverage our results to derive new high-probability bounds on the convergence of averaged TD-learning improving upon the prior result. Furthermore, we establish concentration bounds on the convergence of averaged Q -learning and off-policy TD-learning, which to the best of our knowledge are the first in the literature. Finally, the general nature of our framework allows it to be used to obtain high-probability bounds of averaged SA iterates based on future refinements of non-average SA bounds (e.g., if high-probability bounds for SA under more general assumptions are developed in the future). Related Work Finite-Sample Guarantees for Contractive SA. Recent advances have significantly improved finite-time analyses of SA algorithms in contractive and strongly-monotone settings, often driven by applications in RL and optimization. Early finite-sample mean-square error bounds were established for specific SA instances such as TD-learning [ 6 , 15 , 16 ] and Q -learning [ 19 , 3 ] , but lacked tail probability guarantees. Subsequent work provided high-probability concentration results. For instance, [ 42 ] introduced non-asymptotic bounds for unprojected linear SA, and [ 34 ] analyzed asynchronous Q -learning. Using martingale concentration techniques [ 20 , 22 ] , [ 44 ] obtained an \mathcal{O}(k^{-1/2}) tail bound, while [ 12 ] utilized Lyapunov methods with convex envelopes to achieve finite-time results. This research culminated in general frameworks for Markovian SA: [ 13 ] provides polynomial tail bounds applicable to nonlinear contractive SA with Markovian noise. In particular, [ 14 ] (also [ 9 , 8 ] ) showed subgaussian concentration under minimal noise assumptions via exponential supermartingales, extending results beyond the i.i.d. setting. Sharper concentration bounds emerged for linear SA (LSA). [ 18 ] derived tight \mathcal{O}(1/k) error rates for constant step size LSA. Concurrently, [ 30 ] provided detailed non-asymptotic bounds and asymptotic variances for averaged LSA (see also [ 24 ] ). In nonlinear SA, notably Q -learning, averaging enhances performance. [ 46 ] established exponential tail bounds for averaged Q -learning, while [ 26 ] (also [ 28 ] ) derived functional CLTs and optimal non-asymptotic error bounds for synchronous averaged Q -learning. Similarly, [ 48 ] demonstrated minimax-optimal complexity using averaging in variance-reduced Q -learning. Addressing practical concerns, [ 38 ] showed universal step sizes combined with tail-averaging yield near-optimal guarantees for linear TD-learning without projections or feature knowledge. Polyak-Ruppert Averaging in Stochastic Approximation. Averaging is a classical variance-reduction technique in SA, known to improve the asymptotic efficiency of iterates [ 33 ] . For linear SA, which includes TD-learning with linear function approximation, [ 17 ] provide finite-time high-probability bounds for averaging. Their bounds match the minimax asymptotic variance and are instance-optimal. [ 39 ] strengthen this by showing that tail-averaged TD-learning with constant step sizes achieves optimal-order bias and variance, without requiring step size tuning. In Q -learning and other nonlinear SA settings, [ 27 ] establish tight sample complexity bounds. Follow-up work shows Polyak-averaged Q -learning achieves asymptotic efficiency [ 29 ] . [ 29 ] also provides a statistical analysis showing convergence to the minimax lower bound for tabular Q -learning. [ 41 ] derive a non-asymptotic CLT using Stein’s method, applied to TD-learning. [ 37 ] prove Berry–Esseen bounds and establish bootstrap validity for linear SA. These enable rigorous confidence intervals in reinforcement learning. In actor-critic and other two-time-scale SA, [ 23 ] prove the first non-asymptotic CLT under averaging. [ 7 ] and [ 10 ] obtain finite-time bounds, showing that averaging improves rates from \mathcal{O}(k^{-2/3}) to \mathcal{O}(k^{-1}) . High probability bounds vs bound on the distribution: Most of the prior work on the concentration of SA considers a step size which depends on the target probability \delta [ 29 , 39 , 27 ] . Such analysis only provides a bound on a single point in the distribution of error. In contrast, in this paper, our

Read the complete text