First-Order Methods

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