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

We study the trade-off between convergence rate and sensitivity to stochastic\nadditive gradient noise for first-order optimization methods. Ordinary Gradient\nDescent (GD) can be made fast-and-sensitive or slow-and-robust by increasing or\ndecreasing the stepsize, respectively. However, it is not clear how such a\ntrade-off can be navigated when working with accelerated methods such as\nPolyak's Heavy Ball (HB) or Nesterov's Fast Gradient (FG) methods. We consider\nthree classes of functions: (1) smooth strongly convex quadratics, (2) smooth\nstrongly convex functions, and (3) functions that satisfy the\nPolyak-Lojasiewicz property and have one-sided Lipschitz gradients. For each\nfunction class, we present a tractable way to compute the convergence rate and\nsensitivity to additive gradient noise for a broad family of first-order\nmethods, and we present algorithm designs that trade off these competing\nperformance metrics. Each design consists of a simple analytic update rule with\ntwo states of memory, similar to HB and FG. Moreover, each design has a scalar\ntuning parameter that explicitly trades off convergence rate and sensitivity to\nadditive gradient noise. We numerically validate the performance of our designs\nby comparing their convergence rate and sensitivity to those of many other\nalgorithms, and through simulations on Nesterov's "bad function".\n

Paper

Similar papers

© 2026 NYSGPT2525 LLC