Newest papers

When Momentum Helps Polyak--Ruppert Averaging

Alexandra Suvroikova, Darina Dvinskikh, Yuriy V. Dorn, Alexander Vladimirovich Gasnikov · 2026 · arXiv (Cornell University)

DOI: 10.48550/arxiv.2610.27990 · cited by 0 works (OpenAlex) · open-access PDF

Vietnamese

Các điều kiện được xác định là tần số cực đoan là tần số cực đoan cho SGD và các phương pháp nhịp điệu cùng một covariance vô trùng. Chúng tôi đặc trưng như thế nào nhanh chóng chạy cuối cùng đạt được nó và mức độ mà chúng có thể được song song. Đối với tần số cực đoan với tiếng ồn phụ gia, chúng tôi chứng minh một cây cầu trực tuyến-offline: các nhà giảm thiểu rủi ro thực nghiệm trên các mẫu của trung bình đuôi là một bước Newton từ điểm truy vấn trung bình đuôi của bất kỳ thủ tục trực tuyến nào. Vì vậy, đối với SGD, quả bóng nặng, và phương pháp của Nesterov với nhịp điệu liên tục, bước này là một thuật ngữ biên giới ở hai đầu đuôi và phân chia khoảng cách với máy tính đánh giá ngoại tuyến thành trung tâm, covariance, và sai

Machine translation (Meta M2M100); the English original follows.

Abstract

Polyak--Ruppert averaging gives SGD and momentum methods the same asymptotic covariance. We characterize how fast finite runs reach it and how far they can be parallelized. For strongly convex quadratics with additive noise, we prove an online--offline bridge: the empirical risk minimizer on the samples of a tail average is one Newton step from the tail-averaged query point of any online procedure. For SGD, heavy ball, and Nesterov's method with constant momentum, this step is a boundary term at the two ends of the tail and splits the gap to the offline estimator into center, covariance, and shape errors. Necessary and sufficient conditions show that, on the least curved direction, the center error sets the pace: SGD needs $m\ggκ^2$ rounds but momentum only $m\ggκ$, where $κ$ is the condition number, so at sample size $N$ the critical batch size grows from $Θ(\sqrt{N}/κ)$ to $Θ(\sqrt{N/κ})$. The covariance error separates the momentum methods: heavy ball has relative variance excess $Θ(κ^{3/2}/m)$ along the stiffest direction, whereas Nesterov has relative error $O(\sqrtκ/m)$ in every direction. The shape error is method-independent by a Berry--Esseen bound uniform in $κ$ and batch size, so confidence intervals are valid when the other two errors vanish. We further examine how the conclusions change under heavy-tailed or state-dependent noise and clipping, and establish a first-order comparison with ERM for nonlinear Nesterov averaging under explicit conditions.

Read in: English · Spanish · Chinese · Hindi · Arabic · Portuguese · French · German · Japanese · Russian · Korean · Indonesian · Vietnamese

Topics: Mathematics, Estimator, Ball (mathematics), Upper and lower bounds, Momentum (technical analysis), Covariance

Sources: OpenAlex (CC0), arXiv, Crossref. Agent Exchange