The next couple posts will focus on our favorite second order method: Newton's method. I've been going through them, partly as "review" (in quotes because I ended up learning a lot of new things) and partly to develop some intuition as to when acceleration-by-leveraging-second-ordery-info might actually help. This first post will be super short, and … Continue reading Newton’s method I: Quadratic convergence rate
Month: January 2021
Convergence proofs III: Continuous time interpretation
Post by Yifan Sun I have recently been caught up in the flurry of analyzing popular convex optimization problems as discretizations of continuous ODEs, with the objective of simplifying convergence analysis and constructing better methods. This "flurry" is by no means recent, with a somewhat "but we always knew this" vibe, and is by no … Continue reading Convergence proofs III: Continuous time interpretation
Convergence proofs II: (simple) estimate sequences
Post by Yifan Sun tl;dr: Estimate sequences are a very interesting way of isolating the problem of finding rates over a wide family of unconstrained problems, and can also be used to generate accelerated methods. However it's unclear whether they can easily be used on non-NAG-like methods, at least when restricted to quadratic functions. The … Continue reading Convergence proofs II: (simple) estimate sequences
Convergence proofs I: quadratic approximations
Post by Yifan Sun, Jan 8, 2021 Convergence proofs are the bane of every optimizer's existence. They are tricky, extremely long, and mostly unintuitive. Additionally, they tend to be tribal; there are "families" of convergence proof techniques that seem to cover a particular type of method under a particular class of functions, and while efforts … Continue reading Convergence proofs I: quadratic approximations