First-Order Methods

Understanding first-order methods is crucial to design fast algorithms. To begin with, there are two kind of methods you need to understand:

  • Gradient Descent: Chapter 2.1 NesterovIntro

  • Mirror Descent or Dual Averaging:

    • Nemirovski . Online optimization view.
    • Mirror Descent for SDPs: Matrix MWUs. See Chapter 3 of my thesis.

Once you understand these, you can graduate to accelerated methods. I recommend you start with NesterovIntro and Nemirovski. Once you understand the setup and you are confused enough by the proofs, take a look at these two papers:

  1. Linear Coupling
  2. Dynamical System View