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

We provide a novel computer-assisted technique for systematically analyzing\nfirst-order methods for optimization. In contrast with previous works, the\napproach is particularly suited for handling sublinear convergence rates and\nstochastic oracles. The technique relies on semidefinite programming and\npotential functions. It allows simultaneously obtaining worst-case guarantees\non the behavior of those algorithms, and assisting in choosing appropriate\nparameters for tuning their worst-case performances. The technique also\nbenefits from comfortable tightness guarantees, meaning that unsatisfactory\nresults can be improved only by changing the setting. We use the approach for\nanalyzing deterministic and stochastic first-order methods under different\nassumptions on the nature of the stochastic noise. Among others, we treat\nunstructured noise with bounded variance, different noise models arising in\nover-parametrized expectation minimization problems, and randomized\nblock-coordinate descent schemes.\n