On Global Joint Lower Bounds in Zeroth-Order Nonconvex Optimization

Yuxuan Xia, Xiao-Tong Yuan

Must the dimension and accuracy costs of zeroth-order optimization multiply? Global upper bounds for smooth stochastic nonconvex optimization scale as $O(d{\epsilon }^{-4})$, with both facto…