Stochastic first-order methods: non-asymptotic and computer-aided analyses via potential functions

Understand

We provide a novel computer-assisted technique for systematically analyzing first-order methods for optimization.

• In contrast with previous works, the approach is particularly suited for handling sublinear convergence rates and stochastic oracles.
• The technique relies on semidefinite programming and potential functions.
• It allows simultaneously obtaining worst-case guarantees on the behavior of those algorithms, and assisting in choosing appropriate parameters for tuning their worst-case performances.