Comparison to existing zeroth-order methods. As tab:convergencecomparison suggests, our sample complexity significantly outperforms that of [1]} and [2]}. But the sample complexity in [3]} outperforms our method, with a function evaluation complexity of \(\tilde{O}\left(\frac{d}{\epsilon ^2} \right)\) . However, a key limitation of their method is a requirement to use \(\Omega (d)\)  function evaluations to estimate the gradient at each iteration, which may not be practical in realistic applications when \(d\)  is large. Another limitation is that the method in [3]} requires checking if the gradient is small and adding a perturbation accordingly. In contrast, our method requires only the addition of an isotropic perturbative noise at each iteration, which is significantly more straightforward from an implementation perspective. Moreover, staying true to the spirit of zeroth-order algorithms, our method supports any number of function evaluations at each iteration between 1 to \(d\) .
