In traditional optimization, we rely on gradients—the "slope" of a function—to guide us toward a minimum. However, in many real-world scenarios, the gradient is either impossible to calculate (a "black box" system) or the function is so "jagged" (non-smooth) that gradients become unreliable. This is where zeroth-order (gradient-free) optimization steps in, using only function evaluations to find the optimal path.
The challenge is that these evaluations are rarely perfect. While most algorithms assume "nice" random noise that cancels out over time, recent research focuses on a much harder problem: adversarial noise. This is noise that is biased, non-zero-mean, or even intentionally designed to mislead the optimizer.
The Intuition of Gradient Estimation
To move without a gradient, we must estimate one. The most common approach is to sample the function at one or more points near our current position and use the difference in values to approximate the slope.
Pavel Dvurechensky, Alexander Gasnikov, and their colleagues in An Accelerated Method for Derivative-Free Smooth Stochastic Convex Optimization demonstrate that by using a two-point feedback mechanism, we can achieve convergence rates that are only a factor of $\sqrt{n}$ (where $n$ is the dimension) slower than gradient-based methods.
The core intuition is that even if the function evaluations are corrupted by bounded adversarial noise, the algorithm can still identify the general "downhill" direction. As long as the noise level remains below a certain threshold relative to the desired accuracy, the optimizer will converge to a stable neighborhood of the optimal solution.
The Geometry of Robustness
Not all ways of sampling the function are equal. Researchers have found that the choice of "randomization" (how we pick the directions to sample) significantly impacts how well the algorithm handles noise.
In Gradient-Free Federated Learning Methods with $l_1$ and $l_2$-Randomization, Aleksandr Lobanov and Darina Dvinskikh show that $l_1$-randomization (sampling from a simplex or using the $l_1$-norm) often provides better stability than $l_2$ (spherical) alternatives in high-dimensional, noisy environments. Similarly, Arya Akhavan and Alexandre B. Tsybakov leverage $l_1$ randomization in Gradient-free optimization of highly smooth functions to derive tighter bounds for functions that are "highly smooth," proving that zeroth-order methods can remain robust even when noise is "almost adversarial."
Matching First-Order Resilience
A surprising result in this field is that lacking a gradient doesn't necessarily make you more vulnerable to noise. Nikita Kornilov and Alexander Gasnikov show in Accelerated Zeroth-order Method for Non-Smooth Stochastic Convex Optimization Problem with Infinite Variance that by using gradient clipping, zeroth-order methods can tolerate the same level of adversarial noise as first-order methods.
This is particularly important when dealing with "heavy-tailed" noise—errors so extreme they have infinite variance. By clipping the estimated gradients, the algorithm prevents a single corrupted evaluation from throwing the entire optimization process off track.
Saddle Points and Overparameterization
The frontier of this research extends to complex landscapes like saddle points (common in GANs and game theory) and overparameterized models (where there are more parameters than data points).
In Gradient-free algorithm for saddle point problems under overparametrization, Ekaterina Statkevich and her team introduce ZOS-SEG, an algorithm that approximates gradients to solve minimax problems. They find that in overparameterized settings, these methods can actually reach lower "error floors" than in purely stochastic environments, even when faced with deterministic adversarial noise.
However, a recurring theme across these papers—including Gradient-Free Optimization for Non-Smooth Saddle Point Problems under Adversarial Noise—is that our current theoretical bounds for noise tolerance are not yet "tight." We know these algorithms are robust, but we are still discovering the absolute limits of how much adversarial interference they can survive before they break.
Why It Works
The success of these methods rests on three pillars:
- Redundancy: By sampling multiple points or using high-order smoothness (as explored by Georgii Bychkov in AZO-SGD-HS), the algorithm gathers enough information to "see through" the noise.
- Proximal Geometry: Using non-Euclidean setups (like Mirror Descent) allows the algorithm to adapt to the specific geometry of the problem, making it less sensitive to perturbations in certain directions.
- Dynamic Adaptation: In time-varying environments, such as tracking moving agents, P.S. Sarma and Ketan Rajawat show in Tracking Moving Agents via Inexact Online Gradient Descent that online frameworks can maintain stability even when sensor data is intentionally corrupted.