Adaptive Variance Reduction without Knowing Oracle Smoothness
The paper proposes one variance-reduction method that adapts across average smoothness, standard smoothness, and noiseless optimization without knowing the constants.
Given a gradient budget, the authors use a two-phase setup: first comparing independent gradients and switching to normalized momentum when their difference crosses a threshold. That phase supplies a candidate guarantee and bounds the expected function gap before variance reduction starts. The stated rates are \(O(T^{-1/3})\) for average smoothness, \(O(T^{-1/4})\) for standard smoothness, and \(O(T^{-1/2})\) without noise. For unknown \(T\), they add a two-path method with logarithmic factors in the stochastic cases. ArXiv · AI/CL/LG's note
Given a gradient budget, the authors use a two-phase setup: first comparing independent gradients and switching to normalized momentum when their difference crosses a threshold. That phase supplies a candidate guarantee and bounds the expected function gap before variance reduction starts. The stated rates are \(O(T^{-1/3})\) for average smoothness, \(O(T^{-1/4})\) for standard smoothness, and \(O(T^{-1/2})\) without noise. For unknown \(T\), they add a two-path method with logarithmic factors in the stochastic cases. ArXiv · AI/CL/LG's note
score 4