STREGO: A Scalable Implementation of a Trust-Region Framework for Noisy Bayesian Optimization

arXiv:2610.14338 · math.OC, cs.LG · Submitted 2026-10-09 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: I'm Tom.

Jane: And I'm Jane, here with Lu, Meng and our in-house large language model, Lalam.

Tom: Today's paper: "STREGO: A Scalable Implementation of a Trust-Region Framework for Noisy Bayesian Optimization".

Jane: The gist: STREGO, a scalable implementation of a trust-region Bayesian optimization framework, extends convergence guarantees to noisy function estimates and achieves competitive performance in high dimensions.

Tom: First, who's behind it and why it matters.

Title and authors: Tom: So, we're looking at this paper called STREGO: A Scalable Implementation of a Trust-Region Framework for Noisy Bayesian Optimization. The title itself is pretty long, but it tells you right away that they're dealing with two main things here: scaling and noise.

Jane: It sounds like they’re trying to take something that works for expensive blackbox problems, like TREGO, and make it work when you can't get perfectly accurate function values. That’s a big deal because in the real world, our measurements are always a little noisy or inaccurate.

Lu: They start by generalizing TREGO into this trust-region framework specifically designed for noisy Bayesian Optimization. The authors extend the convergence analysis to handle function estimates that are sufficiently accurate with sufficient high probability, which is crucial for making their theoretical guarantees hold up when you're dealing with stochastic oracle calls <ref:2610.14338#pg1>.

Meng: But they don't stop there; they propose STREGO as the actual scalable implementation of this framework. This suggests that the idea isn't just theoretical; it’s a concrete method to actually deploy in challenging settings, which is what I care about.

Lalam: The paper immediately sets up a structure where each phase alternates between global and local steps, and they decide when to accept a step based on some criteria <ref:2610.14338#pg1>. This structure helps manage the exploration versus exploitation trade-off in these complex scenarios.

Tom: Right, so we're talking about moving beyond just exact function values to dealing with noisy estimates, and they’ve built a framework around it called STREGO. It sounds like they are tackling the high-dimensional problem that often causes older methods to struggle <ref:2610.14338#pg1>.

Jane: Exactly. The main goal here is showing that this trust-region approach can maintain its convergence guarantees even when the function evaluations are noisy, and they aim for competitive performance in high dimensions, which is where things usually get really tough <ref:2610.14338#pg2>.

Lu: They’re addressing the deterioration of performance in high dimensions that TREGO tends to show, by introducing STREGO as a scalable method <ref:2610.14338#pg1>. The authors are showing how this framework can still be effective when the dimension d is large, typically d greater than or equal to twenty <ref:2610.14338#pg2>.

Meng: Scaling is a huge keyword for me because running these kinds of models at scale introduces massive computational costs, and if it doesn't scale well, it's just a paper that lives on a research server. So, what does STREGO actually do to make it scalable?

Lalam: STREGO achieves scalability by coupling a bi-objective global infill criterion with a purely exploitative local phase <ref:2610.14338#pg1>. This combination is key to their approach to balancing the search effort.

The paper's summary: Tom: So, the summary of STREGO explains that they’ve created a scalable implementation by linking two different parts: a global phase and a local phase. This isn't just one single acquisition function; it’s a two-pronged strategy for searching the space.

Jane: It sounds like the global phase is responsible for picking promising areas across the whole domain, while the local phase takes over once they get close to an area of interest. That separation seems smart for managing computational effort.

Lu: In their summary, the global phase selects candidates by solving a bi-objective problem based on two things: the posterior mean of a Gaussian process and the integrated variance reduction <ref:2610.14338#pg1>. This is different because they use this combined objective instead of just focusing on one measure.

Meng: The paper notes that this second objective, the integrated variance reduction, is designed so that it doesn't just favor points far from any data in high dimensions <ref:2610.14338#pg1>. That’s a specific mechanism they built in to avoid the "boundary issue" I mentioned earlier where traditional methods get stuck near edges.

Lalam: And then they have the local phase, which is purely exploitative; it minimizes the posterior mean of a second Gaussian process, trained only on points close to the incumbent <ref:2610.14338#pg1>. This means the model's focus adapts to that specific region rather than being stretched across the entire domain.

Tom: So, one part looks at where you should go next based on overall uncertainty reduction across the whole space, and another part zooms in very closely around where you are currently looking <ref:2610.14338#pg1>. That’s a sophisticated way to handle exploration versus exploitation.

Jane: It sounds like they are essentially saying, "First, let's find a good general direction using the global phase, then once we're in that promising neighborhood, let's use the local phase for high-precision refinement" <ref:2610.14338#pg1>.

Lu: That’s the core idea they are pushing with STREGO: a scalable implementation that combines these two distinct strategies effectively <ref:2610.14338#pg1>. It’s about making the search more robust to noise and better suited for high-dimensional problems.

Meng: For me, this dual objective thing is interesting because it seems to be a direct answer to how we can make the exploration strategy smarter when the underlying model is uncertain, which I see as a major hurdle in production models <ref:2610.14338#pg1>.

The paper's improvements: Tom: The paper points out several improvements they made to TREGO, and the most significant one seems to be how they adapted the trust-region approach for noisy BO <ref:2610.14338#pg1>. They extended the convergence analysis to noisy function estimates that are sufficiently accurate with sufficient high probability.

Jane: That extension of convergence guarantees under noise is pretty important because it means we have a more rigorous way to say that the method will actually converge, even when our evaluations aren't perfect <ref:2610.14338#pg1>.

Lu: They also propose two main improvements in their STREGO design. First, they use the bi-objective problem on the posterior mean and integrated variance reduction for the global phase <ref:2610.14338#pg1>. And second, their local phase minimizes a second Gaussian process trained only on points close to the incumbent <ref:2610.14338#pg1>.

Meng: The improvement in the local phase is what really catches my eye because they keep the training set small by restricting it to points within the trust region, so you don't get an explosion in fitting cost <ref:2610.14338#pg1>. That’s a practical constraint for deployment.

Lalam: Another improvement they highlight is the dual mechanism for unsuccessful local iterations, which distinguishes between certain and uncertain ones using parameters like "beta2" and "beta1" <ref:2610.14338#pg4>. This adds stability to the process when things get noisy or unpredictable.

Tom: So it’s not just about a new acquisition function; it’s about improving the underlying trust-region structure itself, making the method more robust against noise and dimension <ref:2610.14338#pg1>.

Jane: And they show this approach is competitive in high dimensions, which is what makes it really interesting for us right now. They are showing that you can still get good results even when the dimension goes up to one hundred <ref:2610.14338#pg2>.

Lu: The paper specifically shows that on synthetic problems, STREGO obtained the best mean solution quality in every configuration tested, from dimension four to one hundred with and without noise <ref:2610.14338#pg5>. That’s a very strong result for their proposed method on controlled benchmarks.

Meng: But I need to be careful there; synthetic problems are neat, but the real test is how this performs when we run it on actual engineering problems, and that's where we need the evidence <ref:2610.14338#pg5>.

Conclusion: Tom: So to wrap up on STREGO: the main implication is that a trust-region Bayesian optimization method can keep its convergence guarantees even with noisy evaluations and stay competitive in high dimensions <ref:2610.14338#pg1>. It seems like this dual strategy—global exploration based on overall uncertainty reduction and local exploitation around the incumbent—is what delivers the good performance <ref:2610.14338#pg5>.

Jane: I think what sticks is that the authors found this method works very well across both synthetic and real-world problems. They found it finds the best solution on Walker, Mopta08, and HalfCheetah, and even tied with TREGO on Swimmer <ref:2610.14338#pg5>.

Lu: And for the theoretical side, they’re showing that this approach maintains its convergence properties under these noisy conditions <ref:2610.14338#pg5>. It’s a solid piece of work demonstrating how to keep the mathematical guarantees intact while pushing performance in high dimensions <ref:2610.14338#pg5>.

Meng: From an engineering standpoint, I still have that computational cost at low dimension as a weakness, but the overall performance across the tested real-world problems is what tells me this is a viable method for production use <ref:2610.14338#pg5>.

Lalam: The paper on STREGO really solidifies the idea that by carefully structuring the global phase to rank candidates by how much uncertainty they remove over the whole domain, rather than just their own uncertainty, you get better results <ref:2610.14338#pg1>.

Tom: That’s a good summary of it. We’ve heard about STREGO and its design, its noisy convergence guarantees, and how it handles high dimensions across the board. We're ready to see what comes next in Bayesian optimization research <ref:2610.14338#pg5>.

Y. Diouane, I. El Hallaoui, M. Kadri, A. Lamghari

GERAD Department of Mathematics and Industrial Engineering at Polytechnique Montréal · Université du Québec – a Trois-Rivi⢆res

math.OC, cs.LG

Submitted: 2026-10-09

Updated: 2026-10-09

Code: https://github.com/Mayousk/STREGO

License: http://creativecommons.org/licenses/by-nc-sa/4.0/

Importance score: 83/100

The gist: The gist: STREGO, a scalable implementation of a trust-region Bayesian optimization framework, extends convergence guarantees to noisy function estimates and achieves competitive performance in high

Key concepts

Trust-Region Framework for Noisy BO: This framework extends Bayesian optimization to handle noisy function estimates. It structures the optimization into alternating global and local phases, deciding whether to accept a step based on trust regions, allowing it to maintain convergence guarantees even when function evaluations are inaccurate.
Global Phase Strategy: The global phase selects candidates by solving a bi-objective problem involving the posterior mean of a Gaussian process and integrated variance reduction (IVR). This means it prioritizes points that would reduce model uncertainty across the entire search space, rather than just focusing on local uncertainty at a single point.
Local Phase Strategy: The local phase is purely exploitative, minimizing the posterior mean of a second Gaussian process trained only on points close to the current best solution. This ensures that the model's lengthscales adapt specifically to the immediate region around the incumbent, making it highly efficient locally.
Integrated Variance Reduction (IVR): IVR is a metric used in the global phase to select candidates. It measures how much querying a specific point would reduce the overall uncertainty of the model across the entire domain, rather than just measuring uncertainty at that single query point.

Terminology

Bayesian Optimization — 1× in this paper · explained in 3 episodes

Summary

The gist: STREGO, a scalable implementation of a trust-region Bayesian optimization framework, extends convergence guarantees to noisy function estimates and achieves competitive performance in high dimensions.

General Framework and Noisy Convergence

The paper generalizes TREGO into a trust-region framework for noisy BO, extending the convergence analysis to noisy function estimates that are sufficiently accurate with sufficiently high probability. The framework allows each phase to consist of several consecutive EGO steps, with the structure alternating between global and local phases and deciding when a step is accepted. The convergence analysis is derived under assumptions requiring the objective function to be locally Lipschitz continuous rather than having a Lipschitz continuous gradient.

STREGO Implementation

STREGO introduces a scalable implementation that couples a bi-objective global infill criterion with a purely exploitative local phase. The global phase selects candidates by solving a bi-objective problem on the posterior mean of a Gaussian process and the integrated variance reduction. Unlike predictive variance, this second objective does not favor boundary points merely because they are far from the data. The local phase minimizes the posterior mean of a second Gaussian process, trained only on points close to the incumbent, so that its lengthscales adapt to this region rather than to the whole domain.

Global Phase Strategy

The global phase starts by building and training a GP on the entire DoE and solving a bi-objective problem based on the posterior information. The proposed bi-objective problem for the global phase is given by min x∈omega µ(x), −IVR(x). IVR measures how much querying x would reduce the uncertainty of the model over the entire domain omega, rather than just at x alone. The batch of G global candidates is generated by clustering the approximate Pareto set X P in the input space.

Local Phase Strategy

The local phase is purely exploitative, discarding variance and relying solely on the predictive mean inside the trust region. The local candidate x local k minimizes µ over the annulus defined by rmin δ ≤∥x − xinc∥ ≤ rmax δ. To keep fitting cost bounded, a relaxed local DoE X is used, trained only using points within the trust region.

Performance and Comparison

STREGO was tested on synthetic problems of dimension 4 to 100 and on real-world problems of dimension 16 to 124, with and without noise. A first experiment shows that, on three of the four synthetic functions tested, the integrated variance reduction generally leads to better solutions than the predictive variance. STREGO obtains the best mean solution quality in every configuration tested on synthetic problems. On four of the six real-world problems, STREGO finds the best solution, alone on three and tied with TREGO on the fourth. The performance comparison shows that STREGO obtains better final values than other solvers on Ackley, Alpine-01 and Rotated Rastrigin for d ranging from 4 to 100. On real-world problems, STREGO outperforms all other solvers on Walker and Mopta08, where it takes the lead early and ends at ≈ −800 and ≈ 262, respectively.

Conclusion

The results indicate that a trust-region BO method can keep its convergence guarantees with noisy evaluations and remain competitive in high dimension. The performance of STREGO seems largely due to two design choices: its global phase ranks candidates by the uncertainty they remove over the whole domain rather than by their own uncertainty, and its local phase fits its model only to the points near the incumbent. On synthetic problems, STREGO obtained the best mean solution quality in every configuration tested, from dimension 4 to 100, with and without noise. On real-world problems, STREGO found the best solution on Walker, Mopta08 and HalfCheetah and tied with TREGO on Swimmer. The weakness of STREGO is its computational cost at low dimension. Future research will be devoted to a cheaper way to solve the bi-objective problem of the global phase, the handling of categorical and integer variables, and the direct handling of blackbox constraints.

--- Page 1 ---

STREGO, a scalable implementation of a trust-region Bayesian optimization framework for noisy evaluations. The gist: STREGO, a scalable implementation of a trust-region Bayesian optimization framework, extends convergence guarantees to noisy function estimates and achieves competitive performance in high dimensions.

General Framework and Noisy Convergence

STREGO Implementation

STREGO introduces a scalable implementation that couples a bi-objective global infill criterion with a purely exploitative local phase. The global phase selects candidates by solving a bi-objective problem on the posterior mean of a Gaussian process and the integrated variance reduction. The local phase minimizes the posterior mean of a second Gaussian process, trained only on points close to the incumbent, so that its lengthscales adapt to this region rather than to the whole domain.

Conclusion

--- Page 2 ---

The objective function f: omega ⊆ R d → R is locally Lipschitz continuous and bounded from below but cannot be evaluated directly. Optimization algorithms have access only to a stochastic zeroth-order oracle fΘ(x), which returns a noisy observation of f(x) and depends on a random variable Θ with an unknown distribution. Expensive calls limit the number of evaluations, and Bayesian optimization (BO) is designed for this setting.

Preliminaries: EGO and TREGO

EGO [26] is an instance of the BO framework in which a GP surrogate is trained on a growing design of experiments (DoE) and the next candidate is selected by maximizing the EI infill criterion.

Improvements for AI systems

Improved convergence guarantees for Bayesian Optimization under noise by generalizing TREGO into a trust-region framework for noisy BO, which covers noisy function estimates that are sufficiently accurate with sufficiently high probability. This allows AI systems to maintain rigorous theoretical guarantees even when evaluations are stochastic, a critical feature for reliable deployment in real-world applications.
Scalable high-dimensional global exploration using the STREGO method's bi-objective problem, which minimizes the posterior mean of a Gaussian process and the integrated variance reduction. This allows AI systems to efficiently select candidates by balancing exploitation (mean) and exploration (IVR), preventing the boundary issue where traditional methods favor points far from data in high dimensions.
Adaptive local search refinement through an independent local model, as STREGO minimizes the posterior mean of a second Gaussian process, trained only on points close to the incumbent. This enables AI systems to achieve high-precision optimization within promising regions while keeping computational cost bounded by restricting the training set and adapting lengthscales to the local geometry.
Robust search strategies against noisy evaluations by employing a dual mechanism for unsuccessful local iterations, distinguishing between certain and uncertain ones using parameters like "β2 and β1." This enhances system stability by intelligently deciding whether to shrink the trust region aggressively or mildly based on the uncertainty of the noisy estimates.
Efficient batch-based global exploration through STREGO's global phase, which selects candidates by clustering points from a bi-objective Pareto set into a batch of G candidates. This allows AI systems to utilize parallel computing resources effectively, as evidenced by the comparison showing STREGO obtains the best mean solution quality in every configuration tested across synthetic benchmarks.
Enhanced performance on complex engineering problems through IVR as an uncertainty measure, which is shown to yield better results than predictive variance on functions like Ackley and Alpine-01. This allows AI systems to prioritize evaluations that improve the model where it matters for the search, not only at the candidate itself.
Superior performance on high-dimensional real-world problems by searching the full space rather than low-dimensional subspaces, as STREGO searches the full space, and demonstrating better results on problems like Walker and Mopta08 compared to solvers that restrict dimensionality.

Abstract

TREGO, a trust-region Bayesian optimization (BO) method for expensive blackbox problems, has convergence guarantees, but only for exact function values. In high dimension, its performance tends to deteriorate. This paper asks whether a trust-region BO method can be extended to handle noisy evaluations while being competitive in high dimension. We first generalize TREGO into a trust-region framework for noisy BO and extend its convergence analysis to noisy function estimates that are sufficiently accurate with sufficiently high probability. We then propose STREGO, a scalable implementation of this framework. Its global phase selects a batch of candidates by solving a bi-objective problem on the posterior mean of a Gaussian process and the integrated variance reduction. Unlike the predictive variance, this second objective does not favor boundary points merely because they are far from the data. Its local phase minimizes the posterior mean of a second Gaussian process, trained only on points close to the incumbent. STREGO is compared with TREGO, TURBO, BAXUS and NSMA-BO on synthetic and real-world problems of dimension 4 to 124, with and without noise. It gives the best average results in every synthetic setting tested and the best or tied-best solution on four of the six real-world problems. An implementation of STREGO is available at https://github.com/Mayousk/STREGO.