Lower bounds for non-convex stochastic optimization
Lower bounds for non-convex stochastic optimization
复制标题
DOI：
10.1007/s10107-022-01822-7
复制
发表时间：
2019-12
影响因子：
2.7
通讯作者：
Yossi Arjevani;Y. Carmon;John C. Duchi;Dylan J. Foster;N. Srebro;Blake E. Woodworth
中科院分区：
文献类型：
--
作者：
Yossi Arjevani;Y. Carmon;John C. Duchi;Dylan J. Foster;N. Srebro;Blake E. Woodworth
我们用随机一阶方法降低了寻找平稳点的复杂性(最多用梯度范数)。在一个研究得很好的模型中，算法通过查询一个有界方差的无偏随机梯度预言来访问光滑的、潜在的非凸函数，我们证明了(在最坏的情况下)任何算法都至少需要查询才能找到一个非平稳点。下界是紧的，并证明了随机梯度下降在该模型中是极小极大最优的。在一个更具限制性的模型中，噪声梯度估计满足均方光滑性，我们证明了查询的下界，建立了最近提出的方差减少技术的最优性。
We lower bound the complexity of finding-stationary points (with gradient norm at most) 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 leastqueries to find an-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 ofqueries, establishing the optimality of recently proposed variance reduction techniques.