Variance Reduction with Delayed Feedback for Non-Convex Optimization
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(√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.
Related
- Variance-reduced First-order Methods for Finite-sum Function Constrained Convex Optimization
- Distributed Zeroth-Order Composite Finite-Sum Optimization via Incremental Variance Reduction
- Variance Reduction for Decentralized Stochastic Optimization with Multiple Local Updates
- Lower Bounds for Stochastic First-Order Algorithms with Variance Reduction in Nonconvex--Concave Minimax Optimization
- Variance and volatility swap valuation with nonlinear liquidity-feedback stochastic volatility and regime switching
BibTeX
@misc{jiang2026variance,
title = {{Variance Reduction with Delayed Feedback for Non-Convex Optimization}},
author = {Wei Jiang and Dingzhi Yu and Zechao Li},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.28510},
eprint = {2610.28510},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.28510},
}
RIS
TY - UNPB
TI - Variance Reduction with Delayed Feedback for Non-Convex Optimization
AU - Wei Jiang
AU - Dingzhi Yu
AU - Zechao Li
PY - 2026
DA - 2026/10/20
PB - arXiv
DO - 10.48550/arxiv.2610.28510
UR - https://arxiv.org/abs/2610.28510
AB - 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(√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.
ER -