In many real-world optimization problems, we lack access to the gradient of the objective function. In "bandit" settings—ranging from online advertising auctions to the fine-tuning of massive language models—we only observe a single scalar value: the loss or reward resulting from a specific action.
The challenge is to perform gradient-based optimization when we can only "probe" the function at one point at a time. This research direction focuses on one-point gradient estimation, a family of zeroth-order techniques that allow learners to approximate the geometry of a hidden cost surface using only these sparse, noisy evaluations.
The Intuition: Optimization in the Dark
Imagine standing on a hillside in total darkness. You want to reach the bottom (minimize the loss), but you cannot see the slope. However, you can measure your current altitude. To find which way to move, you could take a small step in a random direction $u$ and measure the altitude at that new spot. If the altitude is higher, you should probably move in the opposite direction of $u$; if it is lower, you should move toward $u$.
Mathematically, this is the core of the one-point estimator. As Ambuj Tewari and Ankan Saha demonstrate in Improved Regret Guarantees for Online Smooth Convex Optimization with Bandit Feedback, we can construct an unbiased estimate of the gradient of a smoothed version of our function $f$ by querying a single point $x + \delta u$, where $u$ is a random unit vector and $\delta$ is a small perturbation. The estimator typically takes the form: $$\hat{g} = \frac{d}{\delta} f(x + \delta u) u$$ where $d$ is the dimension of the space. Even though this estimate is extremely noisy, over many iterations, the average direction points toward the true gradient.
Halving the Cost of Exploration
While classic zeroth-order methods often require two evaluations (a "two-point" symmetric difference) to estimate a gradient, many modern applications cannot afford this. In FZOO: Fast Zeroth-Order Optimizer for Fine-Tuning Large Language Models towards Adam-Scale Speed, Sizhe Dang and Haishan Ye show that using a single perturbed loss calculation per step can achieve an 18x speedup over previous methods like MeZO. By calculating the difference between a perturbed loss and a baseline loss from a single forward pass, they maintain the memory efficiency of inference while reaching the convergence speeds of first-order optimizers like Adam.
This "frugal" approach to information is also vital in physical systems. Zhiyu He and Saverio Bolognani in Model-Free Nonlinear Feedback Optimization propose reusing historical data—comparing a new measurement to the previous iteration's result—to estimate gradients without needing extra probes. This is essential for hardware control where every measurement is costly or slow.
Navigating Constraints and Geometry
One-point estimation becomes more complex when the search space has boundaries. If you are at the edge of a feasible region, a random perturbation might take you outside the allowed area.
To solve this, Tijana Zrnic and Eric Mazumdar developed a specialized estimator for the probability simplex in A Note on Zeroth-Order Optimization on the Simplex. By using Dirichlet-distributed noise, they ensure all queries remain valid while still recovering the gradient's projection. Similarly, Mingrui Zhang and Hamed Hassani suggest optimizing over a "shrunken" subset of the constraint space in Online Continuous Submodular Maximization: From Full-Information to Bandit Feedback to provide a safety buffer for perturbations.
In more structured environments, like monotone games, Baoxiang Wang and Yaoliang Yu utilize ellipsoidal gradient estimation in Uncoupled and Convergent Learning in Monotone Games under Bandit Feedback. Instead of a simple sphere, they use a Dikin ellipsoid defined by a barrier function to adapt the exploration to the local geometry of the action space.
Handling Delay and Risk
The real world rarely provides clean, immediate feedback. In systems like ad auctions or network routing, the reward for an action might arrive with an unknown delay. Yuanyu Wan and Lijun Zhang have pioneered methods to handle this in Improved Regret for Bandit Convex Optimization with Delayed Feedback, showing that one-point estimates can still track moving targets even when the feedback loop is lagged.
Furthermore, optimization isn't always about the average case. In high-stakes fields like medicine, we care about the "tail risks." Adrian Rivera Cardoso and Huan Xu extended one-point estimation to risk-averse objectives in Risk-Averse Stochastic Convex Bandit. By perturbing actions and observing the resulting costs, they estimate the gradient of the Conditional Value at Risk (CVaR), allowing agents to avoid catastrophic outcomes even without knowing the underlying probability distributions.
Why It Works: The Power of Smoothing
The reason we can optimize with such limited information is that we aren't actually optimizing the original, potentially jagged function $f$. Instead, we are optimizing a smoothed surrogate $\hat{f}$.
By sampling a point in a neighborhood, we are effectively convolving the original function with a kernel (like a uniform ball or a Gaussian). This smoothing "fills in" the local details, creating a differentiable surface where a single point evaluation provides a valid, if noisy, directional hint. As demonstrated by Binbin Liu and Huan Liu in Online Newton Step Algorithm with Estimated Gradient, these noisy one-point estimates are even sufficient to construct second-order models of the loss surface, allowing for more aggressive updates that leverage the curvature of the objective.