Deterministic Zeroth-Order Mirror Descent via Vector Fields with A Posteriori Certification

Technical Summary: Deterministic Zeroth-Order Mirror Descent via Vector Fields with A Posteriori Certification

1. Problem Statement
The paper addresses the challenge of performing deterministic, zeroth-order (derivative-free) optimization in moderate dimensions, specifically for objectives where gradients are unavailable, prohibitively expensive, or numerically unstable to compute (e.g., matrix functions involving log-determinants or quantum relative entropy). While standard Mirror Descent (MD) offers geometry-aware optimization via Bregman divergences, it traditionally relies on exact gradients. Existing deterministic derivative-free optimization (DFO) methods (e.g., direct search, trust-region models) typically operate in Euclidean geometry and focus on stationarity measures rather than last-iterate function value guarantees. Conversely, randomized zeroth-order methods provide expectation-based bounds but lack the reproducibility and run-wise certification required for safety-critical or auditable applications. The core problem is to develop a deterministic zeroth-order framework that preserves Bregman geometry, utilizes only function values, and provides explicit, verifiable last-iterate convergence guarantees.

2. Methodology
The authors propose a generalized $\Omega$-driven Mirror Descent framework. Instead of using the gradient $\nabla f(x)$, the algorithm employs a general vector field $\Omega(x)$ constructed deterministically from function values.

• Generalized Update Rule: The update maps the primal iterate $x_j$ to the dual space via $\theta_j = \nabla \Phi(x_j)$, performs a step $\theta_{j+1} = \theta_j - \eta_j \Omega(x_j)$, and maps back to the primal space $x_{j+1} = (\nabla \Phi)^{-1}(\theta_{j+1})$.
• A Posteriori Certification: The analysis relies on a trajectory-wise relative smoothness condition (Equation 2.5): $\eta_j D_{f,\Omega}(x_{j+1} \| x_j) \leq D_\Phi(x_{j+1} \| x_j)$. Unlike global assumptions, this condition is checked along the realized iterates. If satisfied, it yields explicit last-iterate guarantees.
• Punctured-Neighborhood Generalized Star-Convexity: To handle the approximation error inherent in zeroth-order oracles, the paper introduces a relaxed star-convexity condition. It requires $\langle \Omega(x), x - x^* \rangle \geq f(x) - f(x^*)$ to hold only outside a small neighborhood $U$ of the minimizer $x^*$. This isolates an explicit "error floor" determined by the resolution of the zeroth-order oracle.
• Deterministic Instantiation: The framework is instantiated using deterministic central finite differences in moderate dimensions. The vector field $\Omega(x)$ is constructed using $2d$ off-center function evaluations (plus one reusable center value).
• Robust Conic Dominance: A key technical contribution is the proof that the finite-difference vector field satisfies the required star-convexity condition outside a specific set $V_{\epsilon, c}$. This is achieved by formulating the problem as a robust conic dominance design problem, ensuring a single scaled proxy direction dominates all admissible true directions over a circular cone of uncertainty.

3. Key Contributions

• Unified Framework: The paper establishes a general template for $\Omega$-driven mirror descent that subsumes various information-geometric algorithms (including generalized Blahut–Arimoto updates) and deterministic finite-difference schemes.
• Trajectory-Wise Certification: It provides a mechanism for run-wise, verifiable certificates. If the relative smoothness inequality holds along a specific trajectory, the algorithm guarantees a specific last-iterate function value bound, independent of global smoothness assumptions.
• Explicit Error Floor Analysis: For deterministic finite differences, the authors derive a "rate-plus-floor" convergence bound. The error decays as $O(1/t)$ outside a resolution-dependent neighborhood, with the error floor explicitly characterized by the finite-difference step size $\epsilon$ and the condition number of the problem.
• Geometric Connection: The work reveals a hidden geometric structure linking Bregman telescoping identities, deterministic certification, and robust conic geometry (specifically second-order cone duality) in the context of zeroth-order optimization.

4. Main Results

• Theorem 2.1 & 2.3: Under the trajectory-wise relative smoothness condition and punctured-neighborhood generalized star-convexity, the algorithm guarantees:
  $$f(x_t) - f(x^*) \leq \max \left( \frac{D_\Phi(x^* \| x_1)}{\sum_{j=1}^{t-1} \eta_j}, \max_{x \in U} (f(x) - f(x^*)) \right)$$
  This bound separates the convergence rate (driven by the Bregman divergence and step sizes) from the approximation error (driven by the neighborhood $U$).
• Theorem 6.4 & Corollary 6.6: When instantiated with deterministic central finite differences, the exceptional set $V_{\epsilon, c}$ is shown to be contained within a Euclidean ball of radius proportional to $\epsilon\sqrt{d}$. This yields a concrete bound where the error floor is determined by the objective variation within this $\epsilon$-neighborhood.
• Feasibility (Theorem 5.1): The paper proves that for sufficiently small step sizes, the trajectory-wise relative smoothness condition is always feasible, justifying the use of certificate-driven line search.

5. Significance and Claims
The paper claims to bridge a gap between deterministic zeroth-order optimization and geometry-aware mirror descent. Its primary significance lies in:

1. Determinism and Verifiability: Providing a framework suitable for applications requiring reproducibility and auditability (e.g., scientific computing, safety-critical design), where stochastic methods are insufficient.
2. Geometric Flexibility: Extending the benefits of Bregman geometry (crucial for problems with simplex, entropy, or positive-definite constraints) to settings where gradients are unavailable.
3. Theoretical Insight: Demonstrating that for zeroth-order mirror descent, the critical structural assumption for last-iterate guarantees is not classical convexity per se, but a punctured-neighborhood generalized star-convexity condition. This condition naturally accommodates the resolution limits of finite-difference approximations.
4. Methodological Shift: Moving the focus from global assumptions to a posteriori, trajectory-wise certificates, allowing practitioners to verify convergence guarantees based on the actual run data rather than worst-case theoretical bounds.

The authors position this work as a complement to existing DFO traditions, offering a specific interface where Bregman geometry is preserved, and providing the first trajectory-wise, verifiable mirror-descent-style certificate for last-iterate function values under function-value-only oracles.