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 O(nε⁻²) from O(n²ε⁻²), 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.