Intuitively, the above result shows that if little function value improvement has been made, then the algorithm's iterates have not moved much, such that it remains approximately in a saddle region if it started out in a saddle region. Building on this technical result, we next prove that each time we are near the saddle point, there is a constant probability of making significant function value decrease. We briefly provide a high-level proof outline below. In our proof, we introduce a coupling argument connecting two closely-related sequences both starting from the saddle, differing only in the sign of their perturbative term along the minimum eigendirection of the saddle. Specifically, when function decrease from a saddle is not sufficiently large, due to the earlier technical result, we know that the coupled sequences will remain within a radius \(\phi \)  of the original saddle for a large number (which we will denote as \(T_s\) ) of iterations. We then utilize this fact to show that the difference of the coupled sequences will (with some constant probability) grow exponentially large, eventually moving out of their specified radius \(\phi \)  within \(T_s\)  iterations, leading to a contradiction. We note that while our proof approach is not new (see e.g. [1]}), the application to the zeroth-order setting poses significant technical challenges, which we explain in the discussion following our next result, lemma:saddledifftermexpression. lemma:saddledifftermexpression formally introduces the coupling we have mentioned, setting the stage for the rest of our arguments. For notational convenience, in this section, unless otherwise specified, we will often assume that the initial iterate \(x_0\)  is an \(\epsilon \) -saddle point.
