Beyond Worst-Case Analysis in Stochastic Approximation: Moment Estimation Improves Instance Complexity

Abstract

We study oracle complexity of gradient based methods for stochastic approximation problems. Though in many settings optimal algorithms and tight lower bounds are known for such problems, these optimal algorithms do not achieve the best performance when used in practice. We address this theory-practice gap by focusing on