Improving Dimension Dependence in Complexity Guarantees for Zeroth-Order Methods via Exponentially-Shifted Gaussian Smoothing

Smoothing-enabled zeroth-order (ZO) methods for nonsmooth convex stochastic optimization have assumed increasing relevance. A shortcoming of such schemes is the dimension dependence in the complexity guarantees, a concern that impedes truly large-scale implementations. We develop a novel exponentially-shifted Gaussian smoothing (esGS) gradient estimator by leveraging a simple change-of-variable argument. The moment bounds of the (esGS) estimator are characterized by a muted dependence on dimension. When the (esGS) estimator is incorporated within a ZO framework, the resulting iteration complexity bounds are reduced to <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\mathcal{O}(n\epsilon^{-2})$</tex> from <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\mathcal{O}(n^{2}\epsilon^{-2})$</tex>, the latter being the best available for the existing two-point estimator with Gaussian smoothing. More specifically, we provide asymptotic and rate statements for nonsmooth convex and strongly convex regimes. Preliminary comparisons with existing schemes appear promising.