In many real-world scenarios, we need to optimize a system where the internal mechanics are hidden—a "black box." We can observe the output for a given input, but we cannot calculate a gradient. This is the domain of Zeroth-Order (ZO) optimization.
Traditionally, ZO methods relied on random direction sampling: perturbing the input in a random direction and seeing how the output changes. While computationally cheap per step, this approach is notoriously noisy. Recent research has shifted toward coordinate-wise gradient estimation, a strategy that trades higher per-iteration costs for significantly better stability, faster total convergence, and the ability to train deep neural networks without backpropagation.
The Precision of Coordinate Perturbations
The core intuition behind coordinate-wise estimation is a shift from stochasticity to determinism. Instead of a random "probe," the algorithm evaluates the function along every dimension of the decision space.
As Yujie Tang 0002 and Na Li explain in Distributed Zero-Order Algorithms for Nonconvex Multi-Agent Optimization, this approach constructs a gradient approximation by sequentially perturbing individual parameters. While this requires $O(d)$ function queries (where $d$ is the number of dimensions), the resulting gradient signal is far more accurate than random sampling.
This accuracy is not just a marginal improvement; it fundamentally changes the optimization dynamics. In Improved Zeroth-Order Variance Reduced Algorithms and Analysis for Nonconvex Optimization, Kaiyi Ji and colleagues demonstrate that the high precision of coordinate-wise estimators allows for significantly larger stepsizes. In the world of optimization, a larger stepsize means fewer iterations to reach the goal, often resulting in a lower total number of function evaluations despite the higher cost of each individual step.
Stability and Generalization
One of the most significant hurdles for ZO optimization has been its application to deep learning and high-dimensional spaces. Random perturbations introduce "noise" that scales poorly as the number of parameters increases.
Xinyue Liu and Bin Gu provide a theoretical foundation for why coordinate-wise methods succeed here in General Stability Analysis for Zeroth-Order Optimization Algorithms. They show that coordinate-wise estimation provides superior algorithmic stability because it avoids the "expansion factors" that typically degrade generalization in stochastic methods. This stability ensures that the model doesn't just fit the training data but generalizes well to unseen data, effectively closing the gap between black-box methods and standard gradient-based backpropagation.
Scaling to Deep Models
The practical breakthrough of this approach is most evident in the DeepZero framework, developed by Aochuan Chen, James Diffenderfer, and others (DeepZero: Scaling up Zeroth-Order Optimization for Deep Model Training).
DeepZero is the first framework to train deep neural networks from scratch using only function evaluations. It manages the $O(d)$ query cost through two clever mechanisms:
- Model Pruning: By reducing the number of active parameters, the number of required coordinate perturbations drops.
- Parallelization: Since each coordinate perturbation is independent, the evaluations can be distributed across multiple processors.
By using coordinate-wise estimation, DeepZero achieves a level of precision that randomized vector-wise methods cannot match in high-dimensional parameter spaces, allowing it to reach performance levels near those of traditional gradient-based training.
Combining with Variance Reduction
The effectiveness of coordinate-wise estimation is further amplified when combined with variance reduction techniques like SVRG and SAGA. Feihu Huang and Bin Gu introduced ZO-ProxSVRG and ZO-ProxSAGA in Faster Gradient-Free Proximal Stochastic Methods for Nonconvex Nonsmooth Optimization, achieving a fast $O(1/T)$ convergence rate.
Similarly, Hongchang Gao and Heng Huang show in Can Stochastic Zeroth-Order Frank-Wolfe Method Converge Faster for Non-Convex Problems? that for constrained problems, the stability of coordinate-wise updates is essential. It prevents the optimizer from oscillating wildly near the boundaries of the feasible region, a common failure mode for random-direction ZO methods.
Beyond Simple Coordinates
While the standard approach uses the canonical axes of the parameter space, the field is evolving toward "structured" directions. In A Structured Proximal Stochastic Variance Reduced Zeroth-order Algorithm, Marco Rando and Lorenzo Rosasco propose using orthogonal directions. This maintains the stability and low bias of coordinate-wise estimation while providing more flexibility in how the search space is explored, further accelerating convergence in non-convex and non-smooth landscapes.