Lower bounds for non-convex stochastic optimization

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.

Automated summary

In this work, we establish lower bounds on the complexity of finding epsilon-stationary points using stochastic first-order methods. We prove that any algorithm accessing smooth, potentially non-convex functions through queries to an unbiased stochastic gradient oracle with bounded variance requires at least epsilon(-4) queries to find an epsilon-stationary point in the worst case. The tightness of the lower bound establishes the minimax optimality of stochastic gradient descent in this model. In a stricter model where the noisy gradient estimates satisfy a mean-squared smoothness property, we further prove a lower bound of epsilon(-3) queries, establishing the optimality of recently proposed variance reduction techniques.