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

Korean

폴리야크 - 루퍼트 사이즈 평균은 SGD와 동력 방법에 동일한 비합리적인 변화를 제공합니다. 우리는 최종 실행이 얼마나 빨리 그것을 달성하고 얼마나 멀리 그들이 병렬 될 수 있는지를 특징화합니다. 첨가 소음으로 강하게 구부러진 사각형을 위해, 우리는 온라인 - 오프라인 브릿지를 증명합니다 : 꼬리 평균의 샘플에 대한 경험적 위험 최소화는 각 온라인 절차의 꼬리 평균 쿼리 지점에서 1 뉴턴 단계입니다. SGD, 무거운 공, 그리고 끊임없는 동시에 Nesterov의 방법을 위해,이 단계는 꼬리의 두 끝에서 경계 용어이며, 꼬리 계산기에 대한 무거운 조건을 중앙, 구동 방향, 오류

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