Zeroth Order Optimization on Bounded Domains

This direction is merged into another direction: zeroth-order gradient estimation (zeroth-order optimization). Its last version stays readable and citable here.

Version 1 of 115 papers21 conceptsfrozen 2026-10-04

In many real-world optimization problems, we don't have access to the gradient of a function. We might be tuning the hyperparameters of a complex simulation, optimizing a 3D mesh, or managing a marketing budget. In these "black-box" scenarios, we rely on zeroth-order optimization: we probe the function at various points and use the differences in the results to estimate which direction leads uphill.

However, a fundamental conflict arises when the "valid" space for our variables has strict boundaries.

The Boundary Problem

Standard zeroth-order methods estimate a gradient by adding a small amount of random noise (a perturbation) to the current position and checking the function value there. If you are in the middle of an infinite field, this works perfectly. But if you are standing at the very edge of a cliff—the boundary of your feasible set—half of your potential probes will land in mid-air where the function is undefined.

As Mohammad Pedramfar and colleagues note in A Unified Approach for Maximizing Continuous DR-submodular Functions, these exploratory queries falling outside the domain lead to invalid or missing information. This isn't just a mathematical nuisance; in engineering applications like those described by Shaocong Ma and Heng Huang in Riemannian Zeroth-Order Gradient Estimation with Structure-Preserving Metrics for Geodesically Incomplete Manifolds, taking a step outside the valid boundary can cause a simulation to crash or a geometric model to self-intersect.

Strategy 1: The Safety Buffer

The most straightforward way to handle boundaries is to never get too close to them. By "shrinking" the feasible set, we create a narrow buffer zone. We perform our optimization within this slightly smaller interior region, ensuring that even when we add exploratory noise, our probes remain within the original, true boundaries.

Ohad Shamir demonstrates in An Optimal Algorithm for Bandit and Zero-Order Convex Optimization with Two-Point Feedback that this shrinking approach can lead to optimal regret bounds for non-smooth functions. Similarly, Lin Chen 0003 and co-authors in Black Box Submodular Maximization: Discrete and Continuous Settings use a transformation that shrinks and translates the constraint set. This ensures the "sampling ball" used for gradient estimation stays entirely within the valid domain, allowing for consistent function evaluations even when the optimal solution lies exactly on the boundary.

Strategy 2: Geometry-Aware Perturbations

Shrinking the domain works well for simple boxes, but it becomes complex for more intricate shapes like the probability simplex (where all variables must be positive and sum to one).

Instead of using standard Gaussian noise and hoping it stays inside the lines, researchers have developed noise distributions that are "native" to the constraints. In A Note on Zeroth-Order Optimization on the Simplex, Tijana Zrnic and Eric Mazumdar propose using Dirichlet-distributed noise. Because the Dirichlet distribution naturally lives on the simplex, every single query point is guaranteed to be a valid probability distribution. This eliminates the need for complex post-hoc projections or corrections that often slow down convergence.

Strategy 3: Truncated Smoothing

A third approach is to adapt the noise distribution on the fly based on the distance to the nearest boundary. If you are far from the edge, you can use a wide, symmetric distribution. As you approach the edge, you "truncate" the distribution so it doesn't spill over.

In Online Convex Optimization with Memory and Limited Predictions, Lintao Ye and colleagues utilize truncated Gaussian smoothing. This technique generates exploratory perturbations that are strictly confined within the feasible set. By carefully weighting these truncated samples, the algorithm can still produce an unbiased estimate of the gradient, allowing zeroth-order methods to match the efficiency of first-order methods even in strictly constrained environments.

Why It Works

The core intuition across these papers is that gradient estimation is a sampling problem. In the absence of a formula for the gradient, we must "feel out" the local landscape. The research direction represented here moves away from "blind" sampling—which fails at the edges—toward "constrained" sampling. Whether by shrinking the playground, using geometry-specific distributions, or truncating the search, these methods ensure that every piece of information gathered is valid, leading to robust optimization in restricted spaces.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_zeroth_order_optimization_on_bounded_dom_2f2403f1,
  title = {Zeroth Order Optimization on Bounded Domains},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/zeroth-order-optimization-on-bounded-domains/rdr_2f2403f1474145a98e14abc23f5ac3ea},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_zeroth_order_optimization_on_bounded_dom_2f2403f1_v1,
  title = {Zeroth Order Optimization on Bounded Domains},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/zeroth-order-optimization-on-bounded-domains/rdr_2f2403f1474145a98e14abc23f5ac3ea/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}