# NeST-BO: Fast Local Bayesian Optimization via Newton-Step Targeting of Gradient and Hessian Information

arXiv: https://arxiv.org/abs/2510.05516 · HTML: https://mlsanity.com/paper/2510.05516/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 42 references that are in the map.
- First posted on arXiv 7 Oct 2025.

## Builds on (most cited first, 26 of 26)

- [GPyTorch: Blackbox Matrix-Matrix Gaussian Process Inference with GPU Acceleration](https://mlsanity.com/paper/1809.11165/) (2018)
- [Scalable Global Optimization via Local Bayesian Optimization](https://mlsanity.com/paper/1910.01739/) (2019)
- [SMAC3: A Versatile Bayesian Optimization Package for Hyperparameter Optimization](https://mlsanity.com/paper/2109.09831/) (2021)
- [Bayesian Optimization in a Billion Dimensions via Random Embeddings](https://mlsanity.com/paper/1301.1942/) (2013)
- [Unexpected Improvements to Expected Improvement for Bayesian Optimization](https://mlsanity.com/paper/2310.20708/) (2023)
- [High-Dimensional Bayesian Optimization with Sparse Axis-Aligned Subspaces](https://mlsanity.com/paper/2103.00349/) (2021)
- [Bayesian Optimization with Safety Constraints: Safe and Automatic Parameter Tuning in Robotics](https://mlsanity.com/paper/1602.04450/) (2016)
- [Batched Large-scale Bayesian Optimization in High-dimensional Spaces](https://mlsanity.com/paper/1706.01445/) (2017)
- [Re-Examining Linear Embeddings for High-Dimensional Bayesian Optimization](https://mlsanity.com/paper/2001.11659/) (2020)
- [Vanilla Bayesian Optimization Performs Great in High Dimensions](https://mlsanity.com/paper/2402.02229/) (2024)
- [Bayesian optimization for materials design](https://mlsanity.com/paper/1506.01349/) (2015)
- [Simple random search provides a competitive approach to reinforcement learning](https://mlsanity.com/paper/1803.07055/) (2018)
- [Joint Entropy Search for Maximally-Informed Bayesian Optimization](https://mlsanity.com/paper/2206.04771/) (2022)
- [Increasing the Scope as You Learn: Adaptive Bayesian Optimization in Nested Subspaces](https://mlsanity.com/paper/2304.11468/) (2023)
- [LassoBench: A High-Dimensional Hyperparameter Optimization Benchmark Suite for Lasso](https://mlsanity.com/paper/2111.02790/) (2021)
- [Local policy search with Bayesian optimization](https://mlsanity.com/paper/2106.11899/) (2021)
- [Standard Gaussian Process is All You Need for High-Dimensional Bayesian Optimization](https://mlsanity.com/paper/2402.02746/) (2024)
- [Local Bayesian optimization via maximizing probability of descent](https://mlsanity.com/paper/2210.11662/) (2022)
- [Global linear convergence of Newton's method without strong-convexity or Lipschitz gradients](https://mlsanity.com/paper/1806.00413/) (2018)
- [A Newton-CG Algorithm with Complexity Guarantees for Smooth Unconstrained Optimization](https://mlsanity.com/paper/1803.02924/) (2018)
- [The Behavior and Convergence of Local Bayesian Optimization](https://mlsanity.com/paper/2305.15572/) (2023)
- [Understanding High-Dimensional Bayesian Optimization](https://mlsanity.com/paper/2502.09198/) (2025)
- [High-Dimensional Gaussian Process Inference with Derivatives](https://mlsanity.com/paper/2102.07542/) (2021)
- [Fast Bayesian Optimization of Needle-in-a-Haystack Problems using Zooming Memory-Based Initialization (ZoMBI)](https://mlsanity.com/paper/2208.13771/) (2022)
- [Minimizing UCB: a Better Local Search Strategy in Local Bayesian Optimization](https://mlsanity.com/paper/2405.15285/) (2024)
- [Multi-Objective Bayesian Optimization for Networked Black-Box Systems: A Path to Greener Profits and Smarter Designs](https://mlsanity.com/paper/2502.14121/) (2025)

## Built on by (most cited first, 6 of 6)

- [BayeSQP: Bayesian Optimization through Sequential Quadratic Programming](https://mlsanity.com/paper/2602.03232/) (2026)
- [Rethinking Trust Region Bayesian Optimization in High Dimensions](https://mlsanity.com/paper/2604.22967/) (2026)
- [Local Constrained Bayesian Optimization](https://mlsanity.com/paper/2603.07965/) (2026)
- [An Efficient Spatial Branch-and-Bound Algorithm for Global Optimization of Gaussian Process Posterior Mean Functions](https://mlsanity.com/paper/2605.00855/) (2026)
- [Local Preferential Bayesian Optimization](https://mlsanity.com/paper/2606.02351/) (2026)
- [GRAPE: Gradient Refinement and Progress-Aware Exploitation for Query-Efficient High-Dimensional Bayesian Optimization](https://mlsanity.com/paper/2608.25116/) (2026)

## Abstract (arXiv)

Bayesian optimization (BO) is effective for expensive black-box problems but remains challenging in high dimensions. We propose NeST-BO, a curvature-aware local BO method that targets a (modified) Newton step by jointly learning gradient and Hessian information with Gaussian process (GP) surrogates, and selecting evaluations via a one-step lookahead bound on the Newton-step error. We show that this bound contracts with batch size, so NeST-BO drives the step error to zero; in well-behaved neighborhoods it recovers the fast local convergence behavior of inexact/modified Newton methods, while standard safeguards support global convergence to stationary points. To improve scaling with problem dimension, we optimize the acquisition in low-dimensional embedded subspaces (random or learned), reducing the dominant cost of learning curvature from O(d2) to O(m2) with m ll d while preserving step targeting. Across high-dimensional synthetic and real-world problems, including cases with thousands of variables and unknown active subspaces, NeST-BO consistently yields faster convergence and better final values than state-of-the-art local and high-dimensional BO baselines.