PaperlayerView exact revision on arXiv

Source-linked AI summary

Adaptively Incorporating Directional Hints into Zeroth-Order Optimization

Alexander Ryabchenko, Jian Qian, Wenlong Mou

arXiv:2609.08277v1cs.LGmath.OC

TL;DR

Zeroth-order optimization needs to exploit directional hints without becoming biased when those hints are inaccurate. CV-ZOD uses a control-variate estimator to adapt to hint quality, with an oracle rate interpolating between first-order and zeroth-order regimes and a practical version matching it up to logarithmic factors. Experiments on simulation-based scientific tasks show speedups over zeroth-order methods and lower final error than biased guided methods.

  • Problem

    Zeroth-order optimization must operate on non-convex objectives when gradients are unavailable or prohibitively expensive, while directional hints may be inaccurate and bias existing guided estimators.

  • Method

    CV-ZOD refines the classical zeroth-order estimator with a control variate based on a directional-hint reference vector, preserving the smoothed-gradient expectation while reducing variance.

  • Results

    CV-ZOD’s oracle rate interpolates between first-order O(1/T) and zeroth-order O(d/T), while its practical variant matches the adaptive guarantee up to logarithmic factors and uses O(k + log T) queries per iteration.

  • Takeaways & Limitations

    CV-ZOD uses directional hints without changing estimator bias, supporting robust progress across hint qualities and improving results over existing zeroth-order and biased guided methods in scientific tasks.

  • Takeaways & Limitations

    The framework currently processes one low-dimensional hint subspace per iteration; aggregating multiple surrogate gradients can increase k and query costs, and large-scale language-model settings remain an open test.

Abstract

from arXiv · show

We study zeroth-order optimization of non-convex functions with the aid of directional hints, which are cheap but potentially inaccurate approximations of the true gradient direction, given by linear subspaces at each iteration. To leverage these hints adaptively while maintaining robustness to their quality, we introduce Control-Variate Zeroth-Order Descent (CV-ZOD), a new framework that refines the classical zeroth-order gradient estimator with a control variate that can be set based on the directional hints. We first show that the oracle algorithm that optimally sets the reference vector and step size at each iteration achieves a convergence rate that interpolates between the first-order $O(1/T)$ rate and the zeroth-order $O(d/T)$ rate, depending on the quality of the hints along the trajectory. We then develop a practical variant of CV-ZOD that achieves the same oracle guarantee up to logarithmic factors, without any prior knowledge of the hint quality. We validate the method empirically on simulation-based scientific optimization tasks, demonstrating sustained progress on non-convex landscapes where zeroth-order descent is slower and existing guided methods stall as guidance deteriorates.

1 Introduction

The paper addresses non-convex optimization when gradients are unavailable by adaptively using potentially inaccurate directional hints. CV-ZOD preserves unbiasedness while interpolating between first-order and zeroth-order convergence, and its practical variant extends this guarantee without prior hint-quality knowledge.

  • Motivation: Zeroth-order methods rely on function evaluations when gradients are unavailable or prohibitively expensive, but their convergence typically worsens with dimension d.Relevant settings include simulator-based scientific optimization and black-box machine-learning applications.
  • Motivation: Directional hints can accelerate early progress when aligned with the gradient, yet blindly following them introduces bias and can limit convergence.Ignoring hints instead returns to standard dimension-dependent zeroth-order optimization.
  • CV-ZOD framework: CV-ZOD uses a control-variate estimator whose reference vector reduces variance while remaining unbiased for the smoothed gradient.The oracle reference vector is obtained by projecting the true gradient onto the hint subspace.
  • CV-ZOD framework: The oracle CV-ZOD algorithm interpolates between O(1/T) with well-aligned hints and O(d/T) with uninformative hints.The optimal stepsize and projected-gradient reference determine this interpolation.
  • Adaptive method: The adaptive zeroth-order variant matches the oracle guarantee up to logarithmic factors using O(k + log T) queries per iteration and no prior hint-quality knowledge.It estimates the oracle quantities using only function evaluations.
  • Empirical validation: On fluid-dynamics and computational-chemistry tasks, CV-ZOD achieves significant speedup over zeroth-order baselines and lower final error than biased guided methods.The experiments use cheap surrogate models to generate directional hints.

2 Problem Setting

The problem setting considers iterative optimization with only function-value access and a low-dimensional subspace hint revealed at each iteration. Performance is evaluated through expected output stationarity, while hints may be adaptive but must satisfy non-anticipation.

  • Objective and assumptions: The objective is an unconstrained minimization problem for a differentiable function f: R^d → R with dimension d.The setting assumes f is B-Lipschitz and L-smooth.
  • Interaction model: At each iteration, the algorithm receives a low-dimensional linear subspace hint and accesses the objective only through scalar function evaluations.It then issues zeroth-order queries and selects the next iterate.
  • Interaction model: The algorithm runs for T iterations from an arbitrary initialization and returns an output point based on the collected information.Every descent step size α_t is strictly positive.
  • Evaluation: Performance is measured by the expected squared gradient norm at the output point, including randomness from the algorithm and hint generation.The expectation covers all randomness affecting the returned point.
  • Hint model: Hint subspaces may be deterministic, random, or adaptively chosen, provided each hint depends only on information available before the iteration’s internal randomness.This is expressed through a non-anticipation condition.
  • Hint quality: Hint quality is quantified by the principal angle between the hint subspace and the current gradient, measuring how much of that gradient the subspace captures.Convergence guarantees depend on the realized angle sequence along the trajectory rather than a worst-case bound.

3 Control-Variate Framework for Zeroth-Order Descent

CV-ZOD uses a control-variate estimator that remains unbiased for the smoothed gradient while reducing variance according to reference-vector accuracy. Its convergence interpolates between zeroth- and first-order rates as directional hints improve, and its practical adaptive version requires no prior hint-quality knowledge.

  • Control-variate estimator: The classical zeroth-order estimator incurs a d-factor because isotropic exploration probes all directions equally.CV-ZOD targets this exploration cost by using directional information in the reference vector.
  • Control-variate estimator: CV-ZOD estimates the residual gradient after subtracting a reference vector, then adds the reference back through a zero-mean control variate.This preserves the smoothed-gradient expectation while reducing variance when the reference approximates the true gradient.
  • Descent scheme: At each iteration, CV-ZOD selects a reference vector and step size, samples an independent Gaussian direction, and updates the iterate with the control-variate estimator.The output is sampled from iterates with probabilities proportional to their step sizes.
  • Descent scheme: The convergence guarantee is governed by the balance between step-size variance costs and descent credit, under smoothness, Lipschitz, dimension, and step-size conditions.The theorem provides a high-probability guarantee for bounded reference vectors and conditionally fresh Gaussian directions.
  • Convergence guarantee: O(1/T) is recovered when reference vectors match the gradient, whereas uninformative references recover O(d/T), up to logarithmic factors.The general rate depends on reference quality along the trajectory and therefore interpolates between these regimes.
  • Directional hints: For a hint subspace, the oracle reference is the gradient projection and the locally optimal step size depends on the hint angle.These choices are locally optimal given the current iterate and subspace but depend on the unknown gradient; function-evaluation estimates achieve the adaptive guarantee up to logarithmic factors.

4 Main Results: Adaptive Convergence from Directional Hints

The adaptive CV-ZOD instantiation estimates hint-subspace gradients and gradient norms from function evaluations to choose reference vectors and step sizes. Its convergence rate interpolates between O(1/T) and O(d/T), while query overhead is O(k + log T) per iteration.

  • Adaptive estimation: The practical method estimates the projected gradient with k + 1 function queries using finite differences along an orthonormal basis of the hint subspace.The projection guarantee is deterministic under L-smoothness and requires no concentration argument or logarithmic oversampling.
  • Adaptive estimation: Gradient norms and orthogonal-gradient norms are estimated by averaging Gaussian probes to support adaptive step-size selection.These estimates provide constant-factor approximations with logarithmic probe counts under the stated probability condition.
  • Adaptive guarantees: The adaptive step size tracks the oracle step size within a constant factor while preserving control of the descent balance.The resulting construction substitutes estimated reference vectors and step sizes into the main convergence theorem.
  • Adaptive guarantees: The convergence rate interpolates between O(1/T) and O(d/T) according to hint-subspace alignment along the realized trajectory.The cumulative oracle step size governs the rate, and the guarantee matches the locally optimal rate up to logarithmic factors.
  • Query complexity: The adaptive algorithm uses O(k + log T) additional queries per iteration beyond the single control-variate gradient query.Batching the control-variate estimator by b directions can reduce estimator variance by a factor of b, up to Gaussian-smoothing bias.

5 Simulations

CV-ZOD is evaluated on fluid inverse problems and molecular geometry optimization using cheap differentiable surrogates for directional hints. It adapts across changing hint quality, outperforming unguided or biased alternatives in the reported simulations.

  • Tasks and setup: The experiments use a fluid inverse problem and molecular geometry optimization, with expensive objectives queried zeroth-order and surrogate gradients defining rank-one hint subspaces.The comparisons include classical ZOD without hints and GES with biased guided estimation.
  • Fluid inverse problem: The fluid experiment uses d = 8192, a 16-query iteration budget, 15 paired seeds, and 100 optimization steps.CV-ZOD allocates 12 queries to the control-variate update, 2 to gradient projection, and 2 to norm estimates.
  • Fluid inverse problem: As surrogate alignment deteriorates in the fluid task, GES plateaus and SurGD loses early gains, whereas CV-ZOD reaches the lowest final objective.Early in optimization, CV-ZOD descends at a rate comparable to GES and surrogate descent.
  • Molecular geometry optimization: In molecular optimization, CV-ZOD and GES outperform unguided ZOD, while CV-ZOD achieves a similar energy reduction to SurGD and outperforms GES.The result is averaged over ten paired runs across efavirenz, adenosine, and benzylpenicillin.

6 Discussion and Future Work

CV-ZOD incorporates directional hints through an unbiased control-variate estimator, so hint quality affects variance rather than estimator bias. Its adaptive rule matches the oracle rate up to logarithmic factors without prior alignment knowledge, while larger-scale validation remains open.

  • Discussion: CV-ZOD uses control-variate gradient estimation so directional hints affect estimator variance, not bias.The framework therefore preserves an unbiased estimator for the smoothed gradient across reference vectors.
  • Discussion: The adaptive step-size rule matches the oracle convergence rate up to logarithmic factors without prior knowledge of hint alignment.It uses only O(k + log T) queries per iteration.
  • Future Work: The framework currently handles one low-dimensional hint subspace per iteration, while aggregating multiple surrogate gradients can increase k and query requirements.The paper identifies adaptive aggregation of a fixed number of surrogates as an open question.
  • Future Work: Validation in large-scale settings such as memory-efficient fine-tuning or language-model prompt optimization remains an important direction for future work.These settings naturally provide surrogate gradients from smaller or distilled models.

A Prior Work on Zeroth-Order Optimization with Directional Hints

Prior guided zeroth-order methods modify the search distribution to exploit directional hints, but this introduces anisotropic bias and incompatible scales across guided and orthogonal directions. CV-ZOD instead remains unbiased, enabling a single-scale adaptive step-size treatment.

  • Guided Evolutionary Strategies: GES replaces isotropic perturbations with anisotropic perturbations that allocate more variance to the hint subspace while preserving total variance.Its parameter γ interpolates between isotropic exploration and exploration entirely supported on the hint subspace.
  • Guided Evolutionary Strategies: Anisotropic exploration introduces bias by applying different gains to gradient components in S and S⊥.The component in S can be amplified by a factor of order d/k.
  • Guided Evolutionary Strategies: This bias creates a step-size dilemma: stability along S makes the step overly conservative on S⊥, while tuning for S⊥ makes it too aggressive along S.The resulting optimization geometry is not robust when hint alignment varies across iterations.
  • Prior-Guided Random Gradient-Free Methods: PRGF uses a single-vector hint and assumes directional derivatives rather than zeroth-order function feedback.Its estimator also applies different effective gains to the S and S⊥ gradient components.
  • Summary: CV-ZOD remains unbiased for every reference vector, so its step size controls residual variance through one scale rather than two biased component scales.This property enables the adaptive tuning developed in the paper.

B Ablations of the Discount Factor and Query Allocation

The ablation varies discount factors and query allocations for the fluid task, showing that performance depends on preserving enough queries for control-variate updates. The strongest displayed configuration uses balanced allocation toward updates and γdisc = 0.7.

  • Ablation Setup: The sweep compares γdisc values {0, 0.6, 0.7, 0.8, 0.9} across query allocations 12/2/2, 7/7/2, and 2/12/2.The allocations are update / norm / projection queries.
  • Ablation Setup: Table 1 reports final fluid objective means and standard deviations over 15 paired seeds, with columns ordered as update, norm, and projection queries.Lower final objective is better.
  • Results: 0.01363 reduces the mean final objective from 0.07635 under γdisc = 0 to 0.01363 under γdisc = 0.7 with the 12/2/2 allocation.All 15 runs finish below 0.020 in that configuration.
  • Results: Every displayed positive discount factor beats ZOD in mean final objective for the 12/2/2 and 7/7/2 allocations.Increasing norm-estimation queries to 12 leaves only two update directions and produces much poorer results throughout the sweep.

C.1 Proof of Lemma 3.3

Lemma 3.3 establishes that the control-variate estimator is unbiased for the smoothed gradient and provides a mean-squared estimation-error bound. The proof invokes smoothness and Gaussian expectation facts.

  • Lemma 3.3: For every x and reference vector m, the expected control-variate estimator equals the smoothed gradient ∇fτ(x).This is the lemma’s unbiasedness statement.
  • Lemma 3.3: The lemma also bounds the estimator’s mean-squared error.The proof derives the bound by expanding the estimation error.
  • Proof: The proof uses L-smoothness and two stated expectation facts to justify the error bound.The unbiasedness follows from Lemma 3.2 and Fact E.1.

C.2 Proof of Theorem 3.4

The proof establishes Theorem 3.4 by combining Gaussian-direction concentration, a descent inequality, and martingale control under bounded reference vectors and capped step sizes.

  • Assumptions: Theorem 3.4 assumes fresh conditionally standard Gaussian directions and uniformly bounded reference vectors.The theorem requires maxt∈[T]∥mt∥≤2B almost surely.
  • Conclusion: Combining the concentration event with the martingale event yields the theorem’s high-probability guarantee under the stated step-size and dimension conditions.The combined event has probability at least 1−3δ/4, which is at least 1−δ.
  • Descent decomposition: The descent analysis separates the accumulated martingale term from the quadratic variation and telescopes the smoothness inequality across iterations.The proof defines MT as the accumulated stochastic term and QT as the weighted squared-estimator-error term.
  • Concentration events: Gaussian norm and inner-product tail bounds, followed by a union bound, produce a simultaneous high-probability event over all iterations.Choosing ℓ=log(12T/δ) gives total failure probability at most δ/4.
  • Martingale control: The estimator error is centered conditionally on the pre-sampling information, enabling martingale concentration for the accumulated stochastic term.The proof applies a Hanson–Wright-based moment-generating-function bound to the centered degree-two Gaussian polynomial.

D Proof of Theorem 4.4

The proof of Theorem 4.4 combines subspace-based estimation guarantees with Theorem 3.4, controlling local optimality, balance, smoothing error, and failure events.

  • Theorem conditions: Theorem 4.4 analyzes Algorithm 1 with logarithmic confidence parameters, logarithmically many samples, and a smoothing radius constrained by dimension and horizon.The theorem assumes d≥log(2T^2), N=⌈C log(2T)⌉, and a stated upper bound on τ.
  • High-probability control: A high-probability event simultaneously provides local optimality and balance control for all iterations, while Lemma 4.1 supplies deterministic bounds.The event from Lemma 4.3 is combined with the deterministic estimate before applying Theorem 3.4.
  • Applying the core theorem: Theorem 3.4 is applicable because the algorithm’s step sizes satisfy αt≤1/(γL), and its bound is substituted into the descent argument.The proof uses γ=C0 log(2T^2) and then drops remaining negative descent credits when summing over t.
  • Expectation step: The expectation argument absorbs smoothing and failure-event contributions using the assumed τ bound and the scaling of γ and A*T.The proof concludes after using γ=O(log(2T)) and A*T≤T/L.
  • Supporting lemmas: Lemma 4.1 supplies the deterministic subspace-based reference-vector guarantee used in the theorem’s proof.Its proof expresses the projected gradient through an orthonormal basis and applies smoothness.

D.2 Proofs of Lemmas 4.2 and 4.3

The proofs of Lemmas 4.2 and 4.3 establish concentration for subspace gradient estimates and convert it into simultaneous balance and step-size controls.

  • Lemma 4.2: Lemma 4.2 gives a high-probability norm-estimation guarantee for any point, linear subspace, smoothing radius, and sufficiently large sample count.The sample requirement is logarithmic in the inverse failure probability.
  • Lemma 4.2: The proof of Lemma 4.2 concentrates the squared Gaussian projections around the gradient norm and combines the resulting events by a union bound.The nonzero-gradient case uses independent chi-square variables and Laurent–Massart concentration.
  • Lemma 4.3: Lemma 4.3 defines an error scale proportional to τ^2L^2(d^2+log^2(2NT/δ)) and provides simultaneous controls over all iterations.The lemma specifies a fallback αt when its denominator is zero.
  • Lemma 4.3: The resulting subspace-estimation error is bounded by a descent-dependent term plus c0τ^2(d^3+d log^2(2NT/δ)).This bound is the form used later to control the adaptive step sizes.
  • Proof strategy: The proof derives the lemma by conditioning the estimation calls, applying concentration with failure probability δ/(2T), and union-bounding across 2T calls.The resulting event holds simultaneously for every iteration.
Loading 2609.08277v1…