Broadly speaking, our proof shows that progress can be made both in iterations when the gradient is large (which we can define to be iterations \(t\)  where \(*{\nabla f(x_t)} \ge \epsilon \) ), and iterations when we are at an \(\epsilon \) -approximate saddle point (where progress may be made along the negative eigendirection of the Hessian matrix). While the approach is similar to the first-order case (e.g. [1]}), the zeroth-order setting brings forth several challenges which we explain below.
