Abstract
Gradient-free/zeroth-order methods for black-box convex optimization have been extensively studied in the last decade with the main focus on oracle calls complexity. In this paper, besides the oracle complexity, we focus also on iteration complexity, and propose a generic approach that, based on optimal first-order methods, allows to obtain in a black-box fashion new zeroth-order algorithms for non-smooth convex optimization problems. Our approach not only leads to optimal oracle complexity, but also allows to obtain iteration complexity similar to first-order methods, which, in turn, allows to exploit parallel computations to accelerate the convergence of our algorithms. We also elaborate on extensions for stochastic optimization problems, saddle-point problems, and distributed optimization.
Introduction
In many real-world optimization scenarios—ranging from tuning complex physical simulators to crafting adversarial attacks against black-box neural networks—the underlying objective function's gradient is unavailable. In these "black-box" settings, practitioners must rely on zeroth-order optimization, where the algorithm only has access to function evaluations at specific points.
Historically, the primary metric for evaluating these algorithms has been oracle complexity: the total number of function evaluations required to reach a target accuracy. However, this focus often ignores iteration complexity: the number of sequential steps an algorithm must take. In an era of massive parallel computing, an algorithm that requires millions of sequential steps is often less practical than one that requires fewer steps but allows for many simultaneous evaluations per step. This paper introduces a generic "Smoothing Scheme" that bridges this gap, achieving optimal oracle complexity while drastically reducing iteration complexity for non-smooth convex problems.
The Smoothing Scheme: A Modular Framework
The proposed approach is a modular framework that transforms optimal first-order (gradient-based) algorithms designed for smooth problems into zeroth-order algorithms capable of handling non-smooth objectives. The process involves three core components:
- Randomized Smoothing: The non-smooth objective function is mathematically smoothed by averaging its values over a small, random neighborhood (typically a Euclidean ball). This creates a surrogate function that is differentiable.
- Stochastic Gradient Estimation: Since the true gradient of the smoothed function is still not directly accessible, the algorithm estimates it using a two-point finite difference. By querying the function at two points along a random direction sampled from a sphere, the algorithm generates an unbiased, low-variance gradient estimate.
- Black-Box Reduction: This gradient estimator is plugged into an existing, optimal first-order algorithm (such as the batched Accelerated Gradient method).
Because the underlying first-order algorithms support batching—processing multiple gradient estimates simultaneously—the resulting zeroth-order method can evaluate many random directions in parallel during a single sequential iteration.
Theoretical and Practical Insights
Complexity and Parallelization
A major theoretical contribution of this work is the proof that there is no necessary trade-off between oracle and iteration complexity. The proposed scheme achieves the theoretical lower bounds for both simultaneously: an iteration complexity of $O(d^{1/4}/\epsilon)$ and a total oracle complexity of $O(d/\epsilon^2)$, where $d$ is the dimension and $\epsilon$ is the target error. By pushing the computational burden into parallel batch evaluations, the wall-clock time for complex optimization tasks can be significantly reduced.
Experimental Validation
The authors validated the framework across diverse domains:
- Reinforcement Learning: In the OpenAI Gym Reacher-v2 environment, the zeroth-order method (using central finite differences) successfully matched the reward curve and performance of the ADAM optimizer, despite ADAM having access to exact gradients.
- Adversarial Attacks: The method was applied to generate adversarial examples for black-box image classifiers on the MNIST dataset.
- Convex Optimization: Using datasets from LibSVM (abalone and a9a), the authors demonstrated that for Robust Linear Regression and SVM classification, the zeroth-order approach converged nearly as fast as true gradient methods when the smoothing parameter was properly tuned.
Limitations and Future Directions
While the Smoothing Scheme is highly versatile, it does face certain constraints:
- Distributed Optimization: In decentralized distributed settings, the scheme currently loses a factor of $\sqrt{d}$ in communication rounds compared to state-of-the-art specialized methods.
- Numerical Stability: The choice of the smoothing parameter ($\gamma$) is critical. If $\gamma$ is too small, the distance between query points becomes negligible, leading to potential numerical instability due to machine precision limits.
- Future Extensions: Potential future work includes adapting the framework for adaptive gradient methods, exploring 1-sphere randomization to improve complexity bounds, and applying the scheme to more complex composite structures.
Conclusion
By treating first-order algorithms as a "black box" and providing a robust smoothing interface, this research provides a powerful tool for high-dimensional, non-smooth optimization. The ability to maintain optimal oracle complexity while enabling massive parallelization makes this approach particularly suited for modern, large-scale machine learning applications where time-to-solution is as critical as accuracy.
Summary updated