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.

本文提供了一种新颖的计算机辅助技术，用于系统地分析面向优化的一阶方法，并且与以往的工作相比，该方法特别适用于处理次线性收敛率和随机预言机。该技术依赖于半定规划和潜力函数，并允许同时获得算法行为的最坏情况保证，并帮助选择适当的参数以调整其最坏情况表现。

随机一阶方法：通过潜力函数的非渐近和计算机辅助分析