Variance reduction improves delayed feedback in non convex optimization
Variance Reduction with Delayed Feedback for Non-Convex Optimization
Machine Learning
Summary
Optimizing complex problems often requires calculating gradients, but sometimes these calculations come back late, slowing progress. The authors studied ways to reduce the randomness (variance) in gradient estimates when feedback is delayed. They designed a method that handles these delays while still effectively improving the solution, especially for problems with many data parts. Their approach also works when updates keep happening even while waiting for some calculations to finish. This helps make optimization faster and more reliable despite delays.
What this means in practice
- •For machine learning engineers: Speed up training of complex neural networks when gradient computations are delayed or asynchronous.
- •For distributed system developers: Improve reliability and efficiency of optimization algorithms in distributed computing environments with communication delays.
Authors
Wei Jiang, Dingzhi Yu, Zechao Li
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+σ^2ε^{-2}+LΔ_f(1+σ/ε+τ)ε^{-2})$, where the target is an expected squared gradient norm of at most $ε^2$ and $τ$ bounds the feedback delay. We next study finite sums with $n$ components and obtain $O(n+LΔ_f(\sqrt n+\min\{τ,n-1\})ε^{-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.