Post by Yifan Sun In comparison to past posts, this post is really about some (relatively) recent work by a bunch of people ([1],[2],[3] to name a few). I therefore tried to spend a lot less time detailing how these things work, as these authors have posted their own excellent blog posts and presentations; however, … Continue reading Convergence proofs IV: My journey with automatic proof generators
Tag: convergence rates
Newton’s method I: Quadratic convergence rate
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
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