Polyak-Ruppert Averaging

Latest papers

8 papers1 paper in the last four weeks, with none the four weeks before. 0.0% of all new papers.

Clipped or Unclipped? Finite-Sample Trade-offs for Averaged SGD under Heavy-Tailed Noise
Sep 26, 2026Alexandra Suvorikova, Egor Gladin, Darina Dvinskikh +5Polyak-Ruppert Averaging Stochastic Optimization
Independent Researcher · HSE University · MBZUAI +3
A Single Stepsize Suffices for Unprojected Linear TD(0): Simultaneous Robust and Fast Rates via Polyak--Ruppert Averaging
Jun 23, 2026Wei-Cheng Lee, Francesco OrabonaStochastic Approximation Temporal-Difference Learning
King Abdullah University of Science and Technology (KAUST) Thuwal, 23955-6900, Kingdom of Saudi Arabia
Online Covariance Estimation in Averaged SGD: Improved Batch-Mean Rates and Minimax Optimality via Trajectory Regression
Apr 12, 2026Yijin Ni, Xiaoming HuoPolyak-Ruppert Averaging Covariance Estimation
H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology
Gaussian Approximation for Asynchronous Q-learning
Apr 8, 2026Artemy Rubtsov, Sergey Samsonov, Vladimir Ulyanov +1Polyak-Ruppert Averaging Q-Learning
HSE University, Moscow, Russia · HSE University & Lomonosov MSU, Moscow, Russia · HSE University & Steklov Mathematical Institute of Russian Academy of Sciences, Moscow, Russia
Sharp asymptotic theory for Q-learning with LDTZ learning rate and its generalization
Apr 5, 2026Soham Bonnerjee, Zhipeng Lou, Wei Biao WuPolyak-Ruppert Averaging Q-Learning
Department of Statistics, University of Chicago · Department of Mathematics, University of California, San Diego
Finite-Time Analysis of Projected Two-Time-Scale Stochastic Approximation
Mar 31, 2026Yitao Bai, Thinh T. Doan, Justin RombergPolyak-Ruppert Averaging Stochastic Approximation
Department of Aerospace Engineering, University of Texas at Austin · Department of Electrical and Computer Engineering, Georgia Tech
High-Order Error Bounds for Markovian LSA with Richardson-Romberg Extrapolation
Aug 7, 2025Ilya Levin, Alexey Naumov, Sergey SamsonovPolyak-Ruppert Averaging Richardson Extrapolation
HSE University
Nonasymptotic CLT and Error Bounds for Linear Two-Time-Scale Stochastic Approximation
Feb 14, 2025Seo Taek Kong, Sihan Zeng, Thinh T. Doan +1Stochastic Approximation Two-Timescale Stochastic Approximation
Coordinated Science Laboratory, Department of Electrical and Computer Engineering, University of Illinois Urbana-Champaign, Urbana, IL 61801 USA · JP Morgan AI Research, Palo Alto, CA 94304 USA · Aerospace Engineering and Engineering Mechanics Department at University of Texas, Austin, Austin, TX 78712 USA

Sep 26, 2026J/K move · Enter open · S save

Clipped or Unclipped? Finite-Sample Trade-offs for Averaged SGD under Heavy-Tailed Noise

Alexandra Suvorikova, Egor Gladin, Darina Dvinskikh, Artem Agafonov+4

Independent Researcher · HSE University · MBZUAI+3

Polyak-Ruppert Averaging Stochastic Optimization Gradient Clipping Stochastic Gradient Descent Heavy-Tailed Stochastic Optimization

Open paper AskPDF arXiv

Gradient clipping is widely used to stabilize training, but it need not improve the statistical accuracy of averaged SGD, even under heavy-tailed noise. We derive a finite-sample comparison of clipped and unclipped Polyak-Ruppert averaged SGD under finite conditional

p

-th moments,

p\ge2

. Our main result gives explicit accuracy and confidence conditions under which, for

p>2

, the Gaussian term dominates the unclipped deviation bound, so clipping need not improve its leading order. By balancing clipping bias and concentration, we obtain a bound in which the heavy-tail correction depends logarithmically rather than polynomially on the inverse failure probability. At

p=2

, this improves the confidence dependence of the leading bound. We establish sharpness of the unclipped heavy-tail term through an exact one-dimensional quadratic recursion and extend the comparison to projected convex SGD. We also prove concrete costs of clipping: every fixed finite threshold increases asymptotic variance on a scalar Gaussian quadratic, while whole-gradient clipping can shift the limiting point under asymmetric noise.