The Lingering of Gradients: How to Reuse Gradients over Time

First-order methods play a fundamental role in large-scale machine learning and optimization tasks. In most scenarios, the performance of a first-order method is represented by its convergence rate: the relationship between ε (the optimization error) versus T (the number of gradient computations). This is meaningful because in most applications, the time complexities for evaluating gradients at different points are of the same magnitude. In other words, the worse-case time complexities of first-order methods are usually proportional to a fixed parameter times T . In large-scale settings, however, if we have already spent time computing the (full) gradient at x, perhaps we can use such information to reduce the time complexity to compute full gradients at other points near x. We call this the "lingering" of gradients, because the gradient at x may be partially reused for future consideration, but will eventually fade away once we are far from x. Formally, consider the (finite-sum) stochastic convex minimization problem: { min