The Physical Systems Behind Optimization Algorithms
We use differential equations based approaches to provide some physics insights into analyzing the dynamics of popular optimization algorithms in machine learning. In particular, we study gradient descent, proximal gradient descent, coordinate gradient descent, proximal coordinate gradient, and Newton's methods as well as their Nesterov's accelerated variants in a unified framework motivated by a natural connection of optimization algorithms to physical systems. Our analysis is applicable to more general algorithms and optimization problems beyond convexity and strong convexity, e.g. Polyak-Łojasiewicz and error bound conditions (possibly nonconvex).
1. Summary  This paper described the connection between various optimization algorithms for convex functions and similar variants and differential equations that describe physical systems. This work builds on previous work using differential equations to analyze optimization algorithms.   2. High level paper  I think the paper is a bit hard to read from Section 3 onward. Section 3 is packed with proofs of convergence for various types of functions, and new notation is frequently introduced. The contribution of the paper seems novel. And I think this work would be interesting to the optimization community.  3. High level technical  Overall I think the biggest things that could be improved are organization of the paper, and the clarity of the writing. Organization: I would spend more time explaining the proof steps in Section 3 and the general connection between optimization algorithms and physical dynamics in Section 5. I think the most interesting contribution of this paper is this optimization-physics connection. This paper will have a lot more impact if you take the time to deeply explain this connection, rather than go through the proofs of each convergence rate. For instance, it would be great to answer the questions: Why must the potential energy decrease for an algorithm to converge? Why is connection between the PL condition and Hooke's law important, or what insight does it give us? Why is the PL condition useful (I know that you cite [4] for examples, but I think you should include some to help with motivation). To have more space for all this I would move Section 4 to the appendix. And possibly move some proofs in Section 3 as well. Clarity: Right now Section 5 assumes a lot of background knowledge in physics. With the additional space I would describe these concepts in more detail, similar to Section 2. A few more specific comments that could improve clarity: - Lines 37-38: Could you be more specific when you say 'analyses rely heavily on algebraic tricks that are sometimes arguably mysterious to be understood'? This would better motivate the method. - Equations above 2.4 (Taylor expansion): Could you derive this quickly? - Line 115: Is it reasonable to require c -> c_0? Doesn't this mean that \eta = O(h) always? Is this reasonable? It would be good to discuss this. - Proof of Theorem 2.1: What does 0^+ mean? - Equation (3.1): How does Theorem 2.1 imply the bound? Do we assume that \gamma(0^+)=1 and f(X(0^+))=0, and do we ignore \gamma(t)? If so, then I see how Theorem 2.1 implies eq. (3.1), but otherwise I don't... - Line 177: It only implies this if m=0 or X^{..}=0, is this true?  4. Low level technical  - Line 1: 'differential equations based' -> 'differential equations-based' - Line 17: 'that achieves' -> 'that it achieves' - Line 39: 'recently attract' -> 'recently have attracted' - Line 45: 'are lack of link' -> 'lack a link' - Line 90: 'We starts with' -> 'We start with' - Line 124: I would remove the word 'mechanic' because this quantity is really the potential energy, as you describe below, and I think 'mechanic' creates confusion. - Line 156: 'independent on' -> 'independent of' - Line 167: 'strongly' -> 'strong' - Line 202: 'suffice' -> 'sufficient' - Line 270: 'As have been' -> 'As has been'  5. 1/2 sentence summary  Overall, while the paper is somewhat unclear, I think the novelty of the contribution, and its impact, justifies this paper being accepted.  Post-Rebuttal ---------------------- The authors do a very thorough job of addressing my review, but are slightly sloppy answering one of my questions: the response on lines 30-32 is a bit sloppy because: (a) they define t=kh in the paper, but in the response they say k=th, (b) in the response they say (x^{(k-1)} - x^{(k)}) = X(t + h) - X(t), but it must actually be equal to X(t - h) - X(t), furthermore, the initial equation (x^{(k-1)} - x^{(k)}) appears in none of the lines directly above equation (2.4) in the paper.  For me, I think this paper is worth accepting, but it is so dense that I think the authors need to move some of the proofs out of the main paper and into the supplementary to properly explain all of the concepts. Ultimately, because of their detailed response in the rebuttal, I still believe the paper should be accepted.