Lower bounds for non-convex stochastic optimization

• 成果类型: Article
• 署名作者: Arjevani, Yossi; Carmon, Yair; Duchi, John C.; Foster, Dylan J.; Srebro, Nathan; Woodworth, Blake
• 署名单位: Hebrew University of Jerusalem; Tel Aviv University; Stanford University; Microsoft; Inria
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-022-01822-7
• 发表日期: 2023
• 页码: 165-214
• 关键词: oracle complexity; CONVERGENCE

摘要

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 meansquared smoothness property, we prove a lower bound of epsilon(-3) queries, establishing the optimality of recently proposed variance reduction techniques.