The Lingering of Gradients: How to Reuse Gradients over Time
Classically, the time complexity of a first-order method is estimated by its number of gradient computations. In this paper, we study a more refined complexity by taking into account the "lingering" of gradients: once a gradient is computed at x k , the additional time to compute gradients at x k+1 , x k+2 , . . . may be reduced. We show how this improves the running time of gradient descent and SVRG. For instance, if the "additional time" scales linearly with respect to the traveled distance, then the "convergence rate" of gradient descent can be improved from 1/T to exp(−T
Summary: -------- The paper studies very lazy updates of stochastic gradients where one uses previous computed gradients instead of computing new ones. They justify such approach by introducing the notion of "lingering gradients", that they define properly. A theoretical approach is provided, assuming this new property, the authors propose a careful storage of previous gradients to exploit this property. Then experiments are made on a simpler method based on SVRG that, while loosing the theoretical properties previously proven, show strong improvements of their approach compared to classical ones.  Quality and clarity: -------------------- The paper is very well written. Motivation is clear and outline well carried on. The proofs are complicated but readable and correct (though I put below details that I''d like to be clarified). Such quality of paper offers the possibility to open discussions in conference.  Originality and significance: ----------------------------- The paper gives theoretical tools to tackle a heuristic that was interesting in practice and where they show real improvements. The storage of gradients using appropriate structure is original to me and may be worth disseminating.  Nevertheless, the original definition of lingering gradients seems quite unrealistic. The natural application of this framework is non-smooth optimization, where in some regions, the gradient indeed doesn't change. However characterizing how these regions smoothly change seems impossible. It seems to me that this lingering gradient is an approximation for very smooth functions (Lipschitz constant very small). -> Could the authors relate the approximate lingering property (up to a given epsilon) to the simple smoothness of the gradient in the experiments they do ? In other words can these Lipschitz constant be computed to understand better the approximation ?  Note that Holder smoothness of the function would also be interesting to relate the the beta exponent of their definition. It seems to me that in such cases it would be interesting to relate the proposed approach to approximate gradient methods that exploit the Holder smoothness see e.g. [Y. Nesterov 2013, Universal Gradient Methods for Convex Optimization Problems] but in a stochastic case.  Conclusion: ----------- Though I think the definition of lingering gradients is for the moment unrealistic, the proposed approach is an interesting step towards heuristics that use previous gradients in a lazy way. Overall the quality of the paper enables to open discussions in the conference that could be fruitful. Since the experiments part is particularly convincing, having the code available would definitely improve the paper (and so my overall appreciation).  Proof check: ------------ l 427: Precise that you used B_{k_i}(k_{t-1}-k_i) \subset B_{k_i}(k_t-k_i) because k_t > k_{t-1} l 461: Could you precise the terms hidden in the O ? l 490, Bounds on T_{time}: Detailing the inequalities would ease the reading. In particular I don't get the last inequality: form the assumptions we have log(m_S) > log(T)  Details: -------- l 117: the LP (2.1) is convex, the proposed formulation is therefore not a reduction to convex optimization but another smoothed formulation of the problem. l 490: Shouldn't it be m_S = \Omega(min(...,...)) without the \Theta ? l 490: In the case beta \in (0,1): erase additional parenthesis in the lower bound on m_S, correct m_s in m_S in the bound of T_{time}