However, the analysis of efficient saddle point escape for stochastic gradient methods is often more complicated. In general, the behavior of the stochastic gradient near the saddle point can be difficult to characterize; thus, to reliably evade saddle points using stochastic gradients with high probability, an additional isotropic perturbation at each iteration is often still required [1]}. Even when additional perturbation is not required, strong concentration assumptions are typically made on the stochastic gradients being used, such as subGaussianity, boundedness of the variance or a bounded gradient estimator [2]}, [3]}, [4]}, [5]}, [6]}, [7]}, creating an analytical issue when such idealized assumptions fail to hold. Indeed, common zeroth order estimators, such as two-point estimators [8]}, are not subGaussian, and can have unbounded variance. For instance, for two-point zeroth-order finite-difference gradient estimators, it can be shown that the variance of the estimator is on the order of \(\Omega (d *{\nabla f(x)}^2)\)  [8]}, with both a dependence on the problem dimension \(d\)  as well as on norm of the gradient, which can be unbounded. Due to these properties (non-subGaussianity and unboundedness), it is tricky to bound the effect of such zeroth-order estimators and establish tight concentration inequalities that facilitate escape near saddle points. In addition, the large variance of the zeroth-order estimator is also an issue away from saddles when the gradient is large. While this is not an issue to show function improvement in expectation (which existing zeroth order works showing first-order stationarity have focused on), as we discuss later, this becomes an issue when guaranteeing high probability bounds.
