PaperlayerView exact revision on arXiv

Source-linked AI summary

GRAPE: Gradient Refinement and Progress-Aware Exploitation for Query-Efficient High-Dimensional Bayesian Optimization

Richard Cornelius Suwandi, Feng Yin

arXiv:2608.25116v1cs.LGcs.AIstat.ML

TL;DR

High-dimensional Bayesian optimization can favor directions that are likely to descend but yield little improvement. GRAPE refines the local gradient posterior, then chooses directions by expected conditional decrease, achieving strong query efficiency and theoretical convergence guarantees.

  • Problem

    Descent probability can favor safe directions with negligible improvement, while high-dimensional Bayesian optimization becomes difficult as search-space volume grows exponentially.

  • Method

    GRAPE first sharpens the local gradient posterior with a closed-form acquisition, then selects update directions by maximizing expected decrease conditional on descent.

  • Results

    GRAPE achieves an average 5.4× speedup on black-box adversarial attacks and outperforms the second-best method by 3.8 log-units on LLM prompt optimization.

  • Takeaways & Limitations

    Gradient refinement monotonically reduces local uncertainty, while progress-aware directions converge to true steepest descent as the posterior sharpens.

  • Takeaways & Limitations

    GRAPE is sensitive to initialization and may become trapped in suboptimal basins on poor starting points or highly multimodal landscapes.

Abstract

from arXiv · show

Optimizing expensive, high-dimensional black-box functions remains a central challenge in modern machine learning and scientific discovery. While local Bayesian optimization mitigates the curse of dimensionality, existing techniques often prioritize the probability of descent over the magnitude of progress. This leads to overly conservative steps that yield negligible improvement, wasting queries on directions that are nearly certain to descend but offer little decrease. We introduce Gradient Refinement and Progress-Aware Exploitation (GRAPE), a two-stage framework that first sharpens the local gradient posterior via a closed-form acquisition function, then selects update directions by maximizing the expected decrease conditional on descent. Theoretical analysis proves that this gradient refinement stage monotonically minimizes local uncertainty and that the progress-aware direction converges to true steepest descent as the posterior sharpens. Empirically, GRAPE demonstrates superior query efficiency across high-dimensional tasks: in black-box adversarial attacks, it achieves an average 5.4$\times$ speedup over baselines, and on large language model prompt optimization tasks, it outperforms the second best method by a reduction of 3.8 log-units in the final average regret.

1 Introduction

High-dimensional Bayesian optimization becomes difficult as limited budgets leave surrogates uncertain across exponentially expanding domains. GRAPE addresses a limitation of descent-probability criteria by refining the local gradient posterior and selecting directions for expected progress.

  • Motivation: Bayesian optimization uses probabilistic surrogates and acquisition functions to select queries for expensive black-box objectives.Gaussian processes commonly provide the surrogate, balancing exploration and exploitation.
  • Motivation: High-dimensional BO suffers because fixed evaluation budgets cover a vanishingly small fraction of the exponentially expanding search space.Surrogate uncertainty and global acquisition optimization also become increasingly difficult.
  • Motivation: Gradient-aware local BO uses function evaluations to refine GP gradient posteriors, providing local descent guidance without explicit gradient observations.This local strategy is especially valuable when exploring the full high-dimensional domain is prohibitive.
  • Motivation: Descent probability can favor nearly certain but negligible decreases while overlooking less certain directions with substantially greater potential improvement.GRAPE targets this mismatch between certainty of descent and magnitude of progress.
  • Contribution: GRAPE first sharpens the local gradient posterior with a closed-form acquisition, then maximizes expected decrease conditional on descent.This two-stage design separates gradient refinement from progress-aware exploitation.
  • Contribution: GRAPE's refinement monotonically minimizes local uncertainty, while its progress-aware direction converges to true steepest descent as the posterior sharpens.These are the framework's stated theoretical guarantees.

2 Related Work

High-dimensional BO methods manage complexity through structural assumptions, local modeling, or gradient-aware criteria. GRAPE instead changes the exploitation criterion to expected conditional decrease while retaining local gradient refinement and remaining compatible with hybrid global strategies.

  • High-dimensional BO: Random embeddings and sparse axis-aligned models reduce effective search complexity through low-intrinsic-dimension or sparse-coordinate assumptions.Their effectiveness depends on whether those structural assumptions match the objective.
  • Local modeling: TURBO concentrates evaluations in adaptive trust regions, expanding after successful steps and contracting after failures, with restarts for poor basins.Gradient-aware methods similarly emphasize local modeling but use GP derivative guidance instead of trust-region success rules.
  • Vanilla BO: Recent vanilla BO methods improve high-dimensional performance through dimension-aware length-scale priors, kernel choices, or length-scale initialization.The reported behavior remains sensitive to kernel and initialization choices.
  • Gradient-aware methods: GIBO, MPD, MINUCB, and NEST-BO differ in whether they minimize gradient uncertainty, maximize descent probability, optimize confidence bounds, or jointly pursue related local criteria.These methods provide the closest gradient-aware local comparisons for GRAPE.
  • GRAPE distinction: GRAPE ranks directions by expected decrease conditional on descent while greedily reducing uncertainty in the gradient used for ranking.It requires only function evaluations and first-order GP derivatives, rather than second-order information.
  • Hybrid optimization: GRAPE can serve as the local component of hybrid global optimization schemes that alternate BO acquisitions with local optimization or trust-region steps.This positioning addresses settings where global coverage is required.

3 Preliminaries

The paper formulates costly noisy black-box local minimization and uses Gaussian processes to model both objective values and latent gradients. Candidate directions are evaluated through the posterior probability that their directional derivative is negative, motivating a progress-aware alternative.

  • Problem Setting: The objective is a continuous black-box function on a compact domain, and the goal is local minimization from a starting point.The local neighborhood restricts optimization to targeted search near the current iterate.
  • Problem Setting: Queries return noisy function values, while gradients are unavailable and evaluations are costly.The optimizer must decide both where to gather information and how to move using it.
  • Gaussian-process model: A GP posterior supplies objective predictions and uncertainty, which acquisition functions use to balance promising and uncertain evaluation points.The observation model includes Gaussian noise with variance σ2.
  • Gradient posterior: Differentiating a sufficiently smooth GP yields a joint Gaussian belief over function values and partial derivatives, so function evaluations can inform local gradients.The posterior mean µx estimates the local gradient and Σx quantifies its uncertainty.
  • Local BO: Local BO methods generally refine derivative beliefs before choosing a descent step, with GIBO using the posterior mean gradient and MINUCB using a confidence-bound objective.This establishes the two-stage framework within which GRAPE operates.
  • Descent probability: For a unit direction v, the directional derivative is Gaussian, and local descent occurs when this scalar derivative is negative.Its posterior descent probability therefore depends on the projected gradient belief.
  • Descent probability: MPD maximizes posterior descent probability, accounting for both estimated slope and uncertainty rather than using only the posterior mean.GRAPE retains this directional posterior while arguing that probability alone does not ensure sample-efficient progress.

4 Proposed Method

GRAPE combines progress-aware exploitation with gradient refinement in a two-stage local BO loop. It replaces descent-probability-only ranking with expected conditional decrease and uses a closed-form acquisition to sharpen the gradient posterior before moving.

  • Progress-aware exploitation: Descent probability depends only on standardized directional mean γv = µv/σv, making it invariant to positive rescaling of mean and uncertainty.Consequently, directions with identical standardized scores can have very different expected slopes.
  • Progress-aware exploitation: Two directions with (µ1, σ1) = (−2, 1) and (µ2, σ2) = (−0.2, 0.1) share descent probability Φ(2) ≈0.977 despite conditional expected decreases of ≈2.05 and ≈0.21.The example exposes the magnitude information missing from descent probability.
  • Progress-aware exploitation: GRAPE ranks unit directions by expected decrease conditional on descent, using a score defined from the standardized directional mean and standard normal PDF/CDF.The closed form follows from the mean of a lower-truncated Gaussian.
  • Progress-aware exploitation: The progress-aware score approaches the posterior mean slope under highly certain descent, assigns no value to certain ascent, and favors high variance near γv ≈0.This combines magnitude, descent probability, and an implicit exploration effect.
  • Gradient Refinement: Because diffuse gradient posteriors can make progress rankings unreliable, GRAPE spends a short evaluation budget sharpening local gradient covariance before moving.This refinement is performed at the current iterate.
  • Gradient Refinement: The refinement acquisition selects auxiliary locations by expected one-step reduction in total gradient variance, using the covariance after augmenting the dataset with a noisy query.The candidate query is chosen before its outcome is observed.
  • Gradient Refinement: For a GP, the refinement acquisition is independent of the unobserved function value and therefore has a closed form.It can be optimized deterministically without Monte Carlo sampling.
  • GRAPE loop: The two-stage loop first selects refinement queries and then moves along the direction of maximum expected progress under the refined posterior.Initialization uses random queries before repeated refinement and exploitation iterations.

5 Theoretical Analysis

GRAPE’s analysis shows that gradient refinement monotonically contracts local gradient uncertainty, while progress-aware exploitation approaches normalized steepest descent as the posterior becomes sharp and consistent. Together, the stages form a principled approximation to first-order optimization under the stated regularity assumptions.

  • Notation and Assumptions: The analysis studies whether refinement reduces local gradient uncertainty and whether exploitation recovers the correct direction as uncertainty vanishes.It assumes a convex compact domain, an RKHS objective, and standard kernel and iterate regularity conditions.
  • Gradient Uncertainty Reduction: Under the stated assumptions, gradient refinement cannot increase the posterior gradient covariance trace.The expected trace after observing a query equals the current trace minus the refinement acquisition, with equality only when the posterior cross-covariance gradient vanishes.
  • Gradient Uncertainty Reduction: Selecting the location with maximum refinement acquisition is greedily optimal and makes repeated refinement monotonically decrease Tr(Σx).The acquisition equals the expected one-step reduction in total gradient variance.
  • Asymptotic Descent Direction: As Tr(Σx) → 0 and µx → ∇f(x), the progress-aware direction converges to normalized steepest descent.The result requires ∇f(x) ≠ 0 and follows from the limiting progress score over unit directions.
  • Interpretation: The two stages are complementary: refinement improves the gradient posterior, enabling exploitation to rank directions increasingly reliably and asymptotically match a gradient oracle.The paper reports empirical validation of both theorems in Appendix F.

6 Experiments

GRAPE is evaluated on high-dimensional adversarial attacks and discrete LLM prompt optimization, using query efficiency and regret as primary measures. It outperforms competing global and local methods, with especially strong gains as dimensionality increases.

  • Benchmarks: GRAPE is evaluated on black-box adversarial attacks and BoLT prompt-optimization tasks spanning embedding dimensions 128–768.The attack benchmarks use MNIST and CIFAR-10, while prompt optimization uses a discrete pool of 5,014 prompts.
  • Evaluation metrics: Attack evaluation measures queries to first success and attack success rate under a fixed query budget, where fewer queries and higher success rates are better.The success-rate curves show how quickly methods accumulate successful attacks as query budgets increase.
  • Adversarial attacks: GRAPE reaches successful adversarial attacks with substantially fewer queries than every baseline, while all pairwise comparisons are statistically significant.On CIFAR-10, VBO and Random require 7.5× and 9.4× as many queries, NEST-BO requires 3.3× more on both datasets, and other first-order methods require 3.8–4.7× more.
  • Adversarial attacks: Figure 2 shows GRAPE reaching the highest attack success rate earliest under a fixed budget of 2000 queries, with the advantage particularly pronounced on CIFAR-10.NEST-BO follows GRAPE, ahead of the other local methods.
  • LLM prompt optimization: On prompt optimization, global methods and random search plateau early, first-order local methods and TURBO reach mid-tier plateaus, and GRAPE and NEST-BO enter the deep low-regret region below −10.GRAPE descends sooner and finishes with the lowest regret at every embedding dimension.
  • LLM prompt optimization: At d = 128, GRAPE and NEST-BO achieve similar final regret, whereas at d = 768 GRAPE achieves roughly 3 additional log-units of improvement.The widening gap is attributed in the paper to NEST-BO’s increasingly data-hungry d × d Hessian posterior relative to GRAPE’s first-order gradient posterior.

7 Conclusion

GRAPE combines gradient refinement with progress-aware exploitation for query-efficient high-dimensional local BO, supported by theoretical guarantees and strong empirical results. The discussion identifies local initialization, curvature, and GP inference costs as remaining constraints.

  • Conclusion: GRAPE couples closed-form gradient refinement with expected-decrease exploitation conditional on descent.The two stages sharpen the local gradient posterior and restore progress magnitude to directional selection.
  • Conclusion: Gradient refinement monotonically reduces local gradient uncertainty, while the progress-aware direction converges to true steepest descent as the posterior sharpens.
  • Conclusion: 5.4× average speedup over baselines is achieved on black-box adversarial attacks, while LLM prompt optimization improves final average regret by 3.8 log-units versus the second-best method.
  • Limitations: Poor initialization or highly multimodal landscapes can trap this purely local method in suboptimal basins.Trust-region restarts and local–global switching are identified as possible escape mechanisms requiring budget allocation.
  • Limitations: The progress-aware score assumes local linearization is adequate, while exact GP inference scales cubically with the dataset size per outer iteration.High curvature may make truncated-Gaussian conditional-decrease estimates inaccurate, and growing budgets make inference a bottleneck.

A Ablation Study

The ablation isolates gradient refinement and progress-aware exploitation across adversarial attacks and prompt optimization, using matched protocols and shared GP modeling. The results indicate that progress-aware exploitation contributes more, while refinement adds consistent value when paired with it.

  • Ablation design: The ablation compares MPD, MPD-Refine, GRAPE-RandExp, and full GRAPE, with each hybrid changing one stage under matched protocols.
  • Evaluation: The four variants are evaluated on black-box adversarial attacks and LLM prompt optimization tasks.
  • Variants: MPD-Refine combines gradient refinement with MPD exploitation, whereas GRAPE-RandExp combines random exploration with progress-aware exploitation.
  • Results: MPD-Refine yields only a modest improvement over MPD, while GRAPE-RandExp closes much of the gap to full GRAPE across all three benchmarks.
  • Results: The direction score is the more impactful design choice, though refinement provides a smaller, consistent benefit when Stage 2 uses conditional progress.Conditional progress uses both µx and Σx rather than descent probability alone.
  • Protocols: All methods use the same Matérn-5/2 GP and marginal-likelihood training protocol, with common initial points and evaluation budgets.

B.6 Compute Resources

The sensitivity study sweeps one hyperparameter at a time around GRAPE’s defaults on MNIST and PO-128 while holding other settings fixed. The results place most defaults in reasonably flat regions, with step size most sensitive.

  • Protocol: The study sweeps one hyperparameter at a time around the defaults on MNIST and PO-128, holding other settings fixed.
  • Overall sensitivity: Table 4 is consistent with defaults that lie in a reasonably flat region.
  • Exploration: τexplore = 1 is the clear under-refinement failure case, while values in {3, 5, 10} change MNIST queries by only a few dozen evaluations.
  • Exploitation: The exploitation cap shows nearly indistinguishable behavior at 30 and 50 once early stopping dominates.
  • Step size: Step size η is the most sensitive setting: 0.01 is too conservative and 0.2 overshoots, while 0.05 and 0.1 remain close.
  • Threshold: τthresh values near 5 × 10−3 behave similarly, whereas 5 × 10−2 truncates exploitation early and hurts prompt-opt regret.

D Kernel Robustness: Matérn vs. SE

Kernel robustness compares GRAPE under ARD Matérn-5/2 and squared-exponential kernels using the same MLE protocol. The squared-exponential swap worsens both reported metrics but does not overturn method rankings on MNIST and PO-128.

  • Setup: The robustness study reruns GRAPE and MPD with an ARD squared-exponential kernel under the same MLE fitting protocol used for the main Matérn-5/2 results.
  • Kernel comparison: Switching from Matérn-5/2 to squared-exponential worsens both methods on both metrics, consistent with high-dimensional squared-exponential fragility.
  • Results: GRAPE’s MNIST query count rises from 216 to 268 under the kernel swap.
  • Results: PO-128 final regret worsens by roughly 1.7 log-units when GRAPE switches from Matérn-5/2 to squared-exponential.
  • Results: The method ranking remains unchanged on MNIST and PO-128, so the main-paper comparison is not overturned by the kernel swap.
  • Theory checks: The synthetic checks use a smooth quadratic in d=2 and report mean ± standard deviation over 10 random seeds while testing the theoretical claims.

F.2 Theorem 2: Convergence to Steepest Descent

Theorem 2 predicts that the progress-aware direction approaches true steepest descent as the gradient posterior concentrates, and experiments confirm this convergence. The angle to steepest descent decreases toward zero as gradient uncertainty shrinks.

  • As Tr(Σx) →0 and µx →∇f(x), the progress-aware direction v⋆ converges to true steepest descent vsd.
  • Theorem 2 is tested by perturbing the analytic gradient mean and shrinking an anisotropic covariance toward zero.
  • Total gradient uncertainty Tr(Σx) decreases monotonically under greedy αref refinement at a fixed interior point.
  • The angle ∠(v⋆, vsd) decays toward zero as the posterior concentrates, agreeing with Theorem 2.

G Full Proof of Theorem 2

The proof establishes convergence of progress-aware exploitation to normalized steepest descent by showing pointwise and uniform convergence of its score, followed by argmax convergence and uniqueness. The surrounding analysis also characterizes the score as conditional decrease rather than descent probability alone.

  • Proof of Theorem 2: Under Tr(Σx) →0 and µx →∇f(x), directional means converge to v⊤∇f(x) and directional uncertainties vanish.
  • Proof of Theorem 2: Uniform convergence of J(v) over the unit sphere permits convergence of its maximizers through the Berge Maximum Theorem.
  • Proof of Theorem 2: Because the limiting score is uniquely maximized by −∇f(x)/∥∇f(x)∥, the progress-aware direction converges to normalized steepest descent.
  • Score decomposition: P(v) is homogeneous in directional scale, so it measures conditional decrease magnitude rather than a dimensionless probability.
  • Score decomposition: Progress-aware exploitation maximizes conditional decrease P(v), while MPD maximizes descent probability and unconditional expected descent maximizes their product.
  • Score decomposition: Maximizing either probability or conditional magnitude alone is generally not equivalent to maximizing their probability-weighted product.

J.4 Worked Example: Scale Blindness and Ranking Disagreement

The worked example shows that descent probability can be blind to slope magnitude and can rank a nearly certain but tiny decrease above a less certain, larger-tailed direction. Progress-aware exploitation instead selects the larger conditional decrease, while the product criterion also favors it.

  • Scale blindness: Two directions with γu = γw = −5 receive identical descent probabilities despite conditional magnitudes differing by orders of magnitude.
  • Ranking disagreement: Probability-only ranking can prefer a nearly certain but tiny direction, whereas progress-aware exploitation favors a direction with larger conditional decrease.
  • Ranking disagreement: The unconditional expected descent values are 0.01 for v1 and approximately 0.20 for v2, so the product criterion also prefers v2.
  • Relation to EI: Progress-aware exploitation retains the conditional-magnitude factor of EI but applies it to directional derivatives and uses it after local gradient refinement.
  • Optimization: The sphere-constrained progress-aware score has no general closed form and is optimized with projected gradient ascent, random restarts, and warm-starting.
Loading 2608.25116v1…