← Research

Variance Reduction with Delayed Feedback for Non-Convex Optimization

Wei Jiang, Dingzhi Yu, Zechao Li

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)O(1+σ^2ε^{-2}+LΔ_f(1+σ/ε+τ)ε^{-2}), where the target is an expected squared gradient norm of at most ε2ε^2 and ττ bounds the feedback delay. We next study finite sums with nn components and obtain O(n+LΔf(n+min⁡{τ,n−1})ε−2)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.

PDF ↗

Models

Loading
EVIDENCE / COMPARISON

Benchmarks

Explore every benchmark

Loading

These charts contain model-linked results. The charts above also include unlinked source profiles. Compare scores within each evaluation. Model quality, usage, transparency and system performance measure different things.

Install TensorTrace