Skip to content
Preprint

Variance Reduction with Delayed Feedback for Non-Convex Optimization

Oct 2026 · 0 citations · 9 references
Mathematics Computer Science

Abstract

We study variance reduction for non-convex optimization when gradient evaluations return with a delay. The server can update the parameter while earlier evaluations remain unfinished. We first analyze an ordered recursive momentum estimator for stochastic optimization. Under average smoothness and bounded variance, its oracle complexity is $O(1+\sigma^2\epsilon^{-2}+L\Delta_f(1+\sigma/\epsilon+\tau)\epsilon^{-2})$, where the target is an expected squared gradient norm of at most $\epsilon^2$ and $\tau$ bounds the feedback delay. We next study finite sums with $n$ components and obtain $O(n+L\Delta_f(\sqrt n+\min\{\tau,n-1\})\epsilon^{-2})$ evaluations. An asynchronous snapshot variant continues updating during full-gradient computations under an explicit bound on their completion time. For the stochastic method, we further replace a maximum-delay bound by a bound on the weighted amount of missing feedback.

View source

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.