Rennala MVR: Improved Time Complexity for Parallel Stochastic Optimization via Momentum Variance Reduction

In heterogeneous clusters, elapsed time is often more informative than iteration complexity. We ask whether momentum variance reduction can improve the time complexity of Rennala SGD, a time-optimal parallel method for smooth nonconvex stochastic optimization. We propose Rennala MVR and, under expected similarity, derive oracle- and time-complexity upper bounds together with a time lower bound for zero-respecting algorithms. For equal worker speeds, the optimized time bound matches this lower bound up to universal constants; time-aware tuning of the momentum parameter can also yield a strict improvement over Rennala SGD. Experiments with the exact method on a controlled nonconvex stochastic benchmark support the predicted dependence on expected similarity and the time-aware choice of the momentum parameter, while complementary neural-network experiments with a practical inexact variant show similar empirical gains.