Black-Box Reductions and Adaptive Gradient Methods for Nonconvex Optimization

Let $A$ be an online convex optimization algorithm with deterministic regret bound $\operatorname{Regret}_T(A)$. Let $f\colon\mathbb R^d\to\mathbb R$ be $\beta$-smooth, let $x_1$ satisfy $f(x_1)-f(x^\star)\leq M$, and suppose an oracle returns an unbiased stochastic gradient $\widetilde\nabla f(x)$ with

$$\mathbb E[\widetilde\nabla f(x)]=\nabla f(x),\qquad \mathbb E\|\widetilde\nabla f(x)-\nabla f(x)\|^2\leq\sigma^2.$$

Give a black-box reduction which, using $A$ and the oracle, produces $x_1,\ldots,x_T\in\mathbb R^d$ such that

$$\frac1T\sum_{t=1}^T\mathbb E\|\nabla f(x_t)\| \leq O\!\left(\sqrt{\frac{M\beta\,\operatorname{Regret}_T(A)}{T}}\right).$$

The dependence should allow adaptive regret guarantees, including their dimension dependence, to transfer to the stationarity rate.