Stochastic first-order methods: non-asymptotic and computer-aided
  analyses via potential functions
  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. The technique also
benefits from comfortable tightness guarantees, meaning that unsatisfactory
results can be improved only by changing the setting. We use the approach for
analyzing deterministic and stochastic first-order methods under different
assumptions on the nature of the stochastic noise. Among others, we treat
unstructured noise with bounded variance, different noise models arising in
over-parametrized expectation minimization problems, and randomized
block-coordinate descent schemes.
