We lower bound the complexity of finding $\epsilon$-stationary points (with
gradient norm at most $\epsilon$) using stochastic first-order methods. In a
well-studied model where algorithms access smooth, potentially non-convex
functions through queries to an unbiased stochastic gradient oracle with
bounded variance, we prove that (in the worst case) any algorithm requires at
least $\epsilon^{-4}$ queries to find an $\epsilon$ stationary point. The lower
bound is tight, and establishes that stochastic gradient descent is minimax
optimal in this model. In a more restrictive model where the noisy gradient
estimates satisfy a mean-squared smoothness property, we prove a lower bound of
$\epsilon^{-3}$ queries, establishing the optimality of recently proposed
variance reduction techniques.

采用随机一阶方法找到梯度范数不超过 ε 的 ε- 稳定点的复杂度下界，使用具有有界方差的无偏随机梯度预言机访问光滑但可能非凸函数的一种模型，证明任何算法在最坏情况下需要至少 ε^-4 个查询才能找到 ε- 稳定点。对于噪声梯度估计满足均方光滑性质的更严格模型，我们证明了 ε^ -3 个查询的下界，建立了最近提出的方差缩减技术的最优性。