The Speed-Robustness Trade-Off for First-Order Methods with Additive Gradient Noise

Understand

We study the trade-off between convergence rate and sensitivity to stochastic additive gradient noise for first-order optimization methods.

• Ordinary Gradient Descent (GD) can be made fast-and-sensitive or slow-and-robust by increasing or decreasing the stepsize, respectively.
• However, it is not clear how such a trade-off can be navigated when working with accelerated methods such as Polyak's Heavy Ball (HB) or Nesterov's Fast Gradient (FG) methods.
• We consider two classes of functions: (1) strongly convex quadratics and (2) smooth strongly convex functions.