Saddle point escape in stochastic gradient descent (SGD). In practice, only stochastic gradient estimators are available in many problems. While SGD may converge to local maxima in worst-case scenarios [1]}, under assumptions such as bounded variance or subGaussian noise, there have been many works that have studied the problem of saddle point escape in SGD [2]}, [3]}, [4]}, [5]}, [6]}. The best existing rate (without considering momentum/variance reduction techniques) appears to belong to that of [7]}, which converges to \(\epsilon \) -second order stationary points using \(\tilde{O}(1/\epsilon ^{3.5})\)  stochastic gradients. While zeroth-order gradient estimators may also be viewed as stochastic gradients, they typically do not satisfy the bounded/subGaussian noise assumptions that are assumed in these works, making a direct comparison inappropriate. Escaping saddle point via momentum methods in SGD has also been studied [8]}, [9]}; while we do not consider incorporating momentum in our works, this may be interesting future work. A number of papers has also considered the specialized setting of escaping saddle points in nonconvex finite-sum optimization [10]}, [11]}, with many considering the case where variance-reduction is used [12]}, [13]}. While the finite-sum problem is quite different from our problem, the variance reduction approach considered in these works may be a relevant future direction. The saddle point escape problem has also been studied in other specific settings such as compressed optimization [14]}, distributed optimization [15]}, or in the overparameterization case [16]}.
