Second, the noise in the zeroth-order estimator also makes the analysis around \(\epsilon -\) approximate saddle points challenging because the concentration properties of the noise is hard to characterize. While intuitively a more noisy estimator should facilitate escape from saddle point, without a concentration bound on the noise, the noise may behave in unpredictable ways that prevent escape from the saddle region. Previous analysis of saddle point escape using stochastic estimators typically requires these estimators to satisfy subGaussian properties [1]}, [2]}, which zeroth-order estimators do not satisfy. We overcome this issue by showing that while the zeroth-order estimators considered in our paper are merely subExponential and not subGaussian, we can leverage the fact that they are the product of subGaussian vectors to derive a tight concentration bound on the vector sums of such estimators.
