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
May 8, 2026

Open-Ended Task Discovery via Bayesian Optimization

When applying Bayesian optimization (BO) to scientific workflow, a major yet often overlooked source of uncertainty is the task itself -- namely, what to optimize and how to evaluate it -- which can evolve as evidence accumulates. We introduce Generate-Select-Refine (GSR), a open-ended BO framework that alternates between task generation and task optimization. Starting from a user-provided seed task, GSR generates new tasks in a coarse-to-fine manner while a task-acquisition function schedules optimization. Asymptotically, it concentrates evaluations on the best task, incurring only logarithmic regret overhead relative to single-task BO. We apply GSR to new product development, chemical synthesis scaling, algorithm analysis, and patent repurposing, where it outperforms existing LLM-based optimizers.

Masaki Adachi, Yuta Suzuki, Juliusz Ziomek

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

Bayesian Optimization
AskPDF
Jun 1, 2026

Local Preferential Bayesian Optimization

Bayesian optimization (BO) is a popular and effective approach for tuning expensive, noisy experiments, but requires the formulation of an explicit objective function. Preferential BO (PBO) removes this requirement by learning from pairwise human feedback, yet existing methods struggle to efficiently optimize beyond low- and medium-dimensional problems due to their global search approaches. We address this limitation by developing a family of local PBO methods that transfer key ideas from high-dimensional BO to the preferential setting. In particular, we introduce local PBO methods which adapt trust-region and derivative-informed local search to pairwise preference feedback, where the latter exploits first- and second-order derivatives of the Laplace-approximated GP posterior. Our benchmark on GP sample paths, standard optimization benchmark functions, and policy-search tasks shows that local PBO methods are especially effective in high-dimensional and complex landscapes with steep optima. Compared with global preference-based baselines, they can substantially reduce cumulative regret, making them particularly useful for real-world preference-based optimization tasks such as policy search.

Johanna Menn, Miriam Kober, Paul Brunzema +2

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

Pairwise Preference LearningPairwise Preference EvaluationBayesian OptimizationLocal SearchSafe Bayesian OptimizationTrust-Region Optimization
AskPDF
Jun 5, 2026

Accelerating Multi-Objective Bayesian Optimisation via Predictive-Gradient Catalysts

This paper presents a general acceleration mechanism for multi-objective Bayesian optimisation (MOBO) that leverages Gaussian process predictive gradients as auxiliary signals. Rather than replacing existing Pareto-compliant acquisition functions, the proposed approach augments them with local stationarity information derived from surrogate-derived gradients, enabling faster convergence toward the global Pareto set under limited evaluation budgets. Two catalyst instantiations are investigated: an adaptive Multiple-Gradient Descent Algorithm-Based Catalyst (MGDA) and a predefined-weight variant that enables focused exploration when budgets are tight. Experiments on the DTLZ benchmark suite (using 2 objectives and 10 decision variables) show that predictive gradient catalysis can deliver significant acceleration compared to other acquisition functions (EHVI, AugTch, tMPoI, SAF) when surrogates are accurate, particularly for stationary problems.

Alma Rahat, Tinkle Chugh, Jonathan Fieldsend +1

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

Surrogate-Assisted OptimizationBayesian Optimization
AskPDF