With this bound on \(*{W_{g_0}(t)}\) , we eventually prove in proposition:saddlepointfuncdecrease in appendix:saddlepointdecrease that our algorithm escapes any \(\epsilon -\) saddle point with constant probability and that the \(O(d)\)  term appearing in the square root term above will eventually lead to an \(O(d)\)  dependence in the sample complexityFor general \(1 \le m \le d\) , there will also be an \(O(1/m)\)  dependence in the sample complexity..
We note that the \(O(d)\)  dimension dependence matches that of the best-known existing upper bound for finding first-order stationary points in smooth nonconvex zeroth-order optimization [1]}, and has been conjectured to be the best possible dimension dependence for general smooth nonconvex zeroth-order optimization [2]}.
