cs.LGAug 25, 2026

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

Authors: Richard Cornelius Suwandi, Feng Yin

Organizations: School of Artificial Intelligence The Chinese University of Hong Kong, Shenzhen Shenzhen, China

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

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.

Figures & tables

Figure 1: One outer iteration of GRAPE . (a) Nearby queries sharpen a wide prior descent belief into a narrower posterior (Theorem 1 ). (b) Candidate directions are ranked by their expected progress.
 MNIST ( d=784d=784 )CIFAR-10 ( d=1024d=1024 )
Method# of queriesRatio# of queriesRatio
Random1971±498∗1971\pm 498^{*}9.1×9.1\times3222±662∗3222\pm 662^{*}9.4×9.4\times
VBO1589±271∗1589\pm 271^{*}7.4×7.4\times2563±436∗2563\pm 436^{*}7.5×7.5\times
D-LogEI1381±222∗1381\pm 222^{*}6.4×6.4\times2114±372∗2114\pm 372^{*}6.2×6.2\times
TuRBO1143±192∗1143\pm 192^{*}5.3×5.3\times1239±191∗1239\pm 191^{*}3.6×3.6\times
GIBO981±184∗981\pm 184^{*}4.5×4.5\times1613±271∗1613\pm 271^{*}4.7×4.7\times
Table 1: Average number of queries ( ↓\downarrow ) ±\pm standard deviation required for a successful attack, across 10 independent runs. Ratio is each method’s query count divided by that of GRAPE (higher is worse). ∗ indicates that GRAPE requires significantly fewer queries than the marked baseline under a paired Wilcoxon signed-rank test ( p<0.05p<0.05 ).
Figure 2: Attack success rate ( ↑\uparrow ) versus number of queries on 5050 randomly selected images from MNIST ( d=784d=784 ) and CIFAR-10 ( d=1024d=1024 ).
Figure 3: Log simple regret ( ↓\downarrow ) versus BO iteration on BoLT prompt-optimization tasks PO-128–PO-768. Shaded regions denote one standard deviation over 10 seeds.
Appendix figures & tables7 assets

Supplementary material from the paper’s appendix.

Appendix

VariantMNIST (#Q ↓\downarrow )PO-128 ( ℓT↓\ell_{T}\downarrow )PO-768 ( ℓT↓\ell_{T}\downarrow )
MPD (baseline)827±128827\pm 128−7.1±1.2-7.1\pm 1.2−5.9±1.4-5.9\pm 1.4
MPD -Refine741±119741\pm 119−7.8±1.3-7.8\pm 1.3−6.6±1.5-6.6\pm 1.5
GRAPE -RandExp371±68371\pm 68−11.8±1.6-11.8\pm 1.6−12.6±1.7-12.6\pm 1.7
GRAPE (full)216±42\mathbf{216\pm 42}−13.9±1.3\mathbf{-13.9\pm 1.3}−15.7±1.5\mathbf{-15.7\pm 1.5}
Appendix
Table 2: Ablation of gradient refinement vs. progress-aware exploitation (mean ±\pm std over 1010 runs). Lower is better. MPD and full GRAPE match the main-paper settings; each hybrid changes one stage.
ParameterValue
Refinement budget τexplore\tau_{\mathrm{explore}}55
Exploitation budget τexploit\tau_{\mathrm{exploit}}3030 (max)
Step size η\eta0.1⋅diam(X)0.1\cdot\mathrm{diam}(\mathcal{X})
Early-stop threshold τthresh\tau_{\mathrm{thresh}}5×10−35\times 10^{-3}
Direction restarts1010 (with warm start)
Refinement candidates NcandN_{\mathrm{cand}}100100 (uniform in X\mathcal{X} )
Appendix
Table 3: Hyperparameters for GRAPE .
HyperparameterValueMNIST (#Q ↓\downarrow )PO-128 ( ℓT↓\ell_{T}\downarrow )
τexplore\tau_{\mathrm{explore}}11287±61287\pm 61−11.4±1.5-11.4\pm 1.5
33238±49238\pm 49−13.1±1.4-13.1\pm 1.4
55 (default)216±42\mathbf{216\pm 42}−13.9±1.3\mathbf{-13.9\pm 1.3}
1010241±51241\pm 51−14.0±1.4-14.0\pm 1.4
τexploit\tau_{\mathrm{exploit}} (max)1010268±58268\pm 58−12.1±1.6-12.1\pm 1.6
2020229±47229\pm 47−13.4±1.4-13.4\pm 1.4
Appendix
Table 4: One-at-a-time sensitivity of GRAPE on MNIST and PO-128 (mean ±\pm std over 1010 runs). Default rows match Table 3 and are bolded within each block.
MethodKernelMNIST (#Q ↓\downarrow )PO-128 ( ℓT↓\ell_{T}\downarrow )
GRAPEMatérn- 5/25/2 (default)216±42\mathbf{216\pm 42}−13.9±1.3\mathbf{-13.9\pm 1.3}
GRAPESE / RBF268±58268\pm 58−12.2±1.6-12.2\pm 1.6
MPDMatérn- 5/25/2827±128827\pm 128−7.1±1.2-7.1\pm 1.2
MPDSE / RBF961±151961\pm 151−5.9±1.5-5.9\pm 1.5
Appendix
Table 5: Kernel robustness: Matérn- 5/25/2 vs. squared-exponential (mean ±\pm std over 1010 runs). Lower is better.
 MNISTPO-128
MethodTotal (s)Opt. / iter (s)Total (s)Opt. / iter (s)
GRAPE94±1794\pm 170.41±0.070.41\pm 0.0788±1388\pm 130.37±0.060.37\pm 0.06
NeST-BO1370±2401370\pm 2401.91±0.241.91\pm 0.24421±47421\pm 471.98±0.271.98\pm 0.27
MPD251±41251\pm 410.30±0.050.30\pm 0.0569±1169\pm 110.27±0.050.27\pm 0.05
MinUCB420±70420\pm 700.47±0.080.47\pm 0.0897±1497\pm 140.42±0.070.42\pm 0.07
GIBO355±60355\pm 600.36±0.060.36\pm 0.0681±1281\pm 120.33±0.060.33\pm 0.06
Appendix
Table 6: Wall-clock timing (mean ±\pm std over 1010 runs). “Opt. / iter” is surrogate fit plus acquisition / direction optimization, excluding black-box queries. MNIST totals accumulate this overhead over the queries-to-success from the main text; PO-128 totals use a fixed budget T=200T{=}200 . NeST-BO incurs additional Hessian-related cost; VBO / D-LogEI pay for global multi-start acquisition over the full domain. GRAPE ’s overhead is dominated by GP refits and candidate scoring of αref\alpha_{\mathrm{ref}} / projected gradient ascent for P\mathcal{P} .
Figure 4: Empirical validation of Theorem 1 . Total gradient uncertainty \Tr(Σx)\Tr(\boldsymbol{\Sigma}_{\mathbf{x}}) at a fixed interior point decreases monotonically under greedy αref\alpha_{\mathrm{ref}} refinement (mean ±\pm std over 1010 seeds).
Figure 5: Empirical validation of Theorem 2 . Angle between the progress-aware direction v⋆\mathbf{v}^{\star} and true steepest descent vsd\mathbf{v}_{\mathrm{sd}} decreases toward zero as \Tr(Σx)→0\Tr(\boldsymbol{\Sigma}_{\mathbf{x}})\to 0 and μx→∇f(x)\boldsymbol{\mu}_{\mathbf{x}}\to\nabla f(\mathbf{x}) (mean ±\pm std over 1010 seeds).
More in this topic

Bayesian Optimization

Bayesian optimization uses probabilistic models and sequential experiments to find strong solutions when evaluating a black-box objective is costly.

See all 247 papers

Explore similar work

CardsList

  1. Open-Ended Task Discovery via Bayesian Optimization

    May 8, 2026Masaki Adachi, Yuta Suzuki, Juliusz ZiomekBayesian Optimization

    Lattice Lab · Toyota Motor Corporation · Machine Learning Research Group +1

  2. Local Preferential Bayesian Optimization

    Jun 1, 2026Johanna Menn, Miriam Kober, Paul Brunzema +2Pairwise Preference LearningPairwise Preference Evaluation

    Institute for Data Science in Mechanical Engineering, RWTH Aachen University, Aachen, Germany · Department of Clinical Research, University of Bern, Bern, Switzerland · Center for Reproducible Science and Research Synthesis, University of Zurich, Zurich, Switzerland +1

  3. Accelerating Multi-Objective Bayesian Optimisation via Predictive-Gradient Catalysts

    Jun 5, 2026Alma Rahat, Tinkle Chugh, Jonathan Fieldsend +1Surrogate-Assisted OptimizationBayesian Optimization

    Loughborough University, Loughborough, LE11 3TU, U.K. · University of Exeter, Exeter EX4 4QD, U.K. · The University of Manchester, Manchester M15 6PB, U.K.