Adjusted Expected Improvement for Cumulative Regret Minimization in Noisy Bayesian Optimization

• URL: http://arxiv.org/abs/2205.04901v3
• Date: Thu, 03 Oct 2024 16:17:50 GMT
• Title: Adjusted Expected Improvement for Cumulative Regret Minimization in Noisy Bayesian Optimization
• Abstract summary: We adapt the expected improvement function for better performance under cumulative regret. A novel quantity called the evaluation cost is compared against the acquisition function. We establish a high-probability regret upper bound of EIC based on the maximum information gain.
• Score: 37.99915557191065
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The expected improvement (EI) is one of the most popular acquisition functions for Bayesian optimization (BO) and has demonstrated good empirical performances in many applications for the minimization of simple regret. However, under the evaluation metric of cumulative regret, the performance of EI may not be competitive, and its existing theoretical regret upper bound still has room for improvement. To adapt the EI for better performance under cumulative regret, we introduce a novel quantity called the evaluation cost which is compared against the acquisition function, and with this, develop the expected improvement-cost (EIC) algorithm. In each iteration of EIC, a new point with the largest acquisition function value is sampled, only if that value exceeds its evaluation cost. If none meets this criteria, the current best point is resampled. This evaluation cost quantifies the potential downside of sampling a point, which is important under the cumulative regret metric as the objective function value in every iteration affects the performance measure. We establish in theory a high-probability regret upper bound of EIC based on the maximum information gain, which is tighter than the bound of existing EI-based algorithms. It is also comparable to the regret bound of other popular BO algorithms such as Thompson sampling (GP-TS) and upper confidence bound (GP-UCB). We further perform experiments to illustrate the improvement of EIC over several popular BO algorithms.

Related papers

• LambdaRankIC: Directly Optimizing Rank IC for Financial Prediction [8.50639201265868]
  In financial predictions, the performance of machine learning models is often assessed by Rank IC.<n>We propose LambdaRankIC, a novel learning-to-rank approach that directly optimize Rank IC.<n>We evaluate the proposed approach on both simulated and real-world financial data.
  arXiv  Detail & Related papers  (2026-05-01T08:24:59Z)
• Expected Improvement via Gradient Norms [2.542957206389996]
  Expected Improvement (EI) is known to be overly exploitative and can converge to suboptimal stationary points.<n>We propose Expected Improvement via Gradient Norms (EI-GN), a novel acquisition function that applies the improvement principle to a gradient-aware auxiliary objective.<n>EI-GN relies on gradient observations used to learn gradient-enhanced surrogate models that enable principled gradient inference from function evaluations.
  arXiv  Detail & Related papers  (2026-01-29T07:37:13Z)
• Robust Bayesian Optimization via Tempered Posteriors [1.6042394978941517]
  We develop a robust GP-based BO via tempered posterior updates to mitigate overconfidence under local misspecifications.<n>We show that tempering yields sharper worst-case regret guarantees than the standard posterior $(=1)$, with the most favorable guarantees occurring near the classical EI choice.
  arXiv  Detail & Related papers  (2026-01-11T23:34:24Z)
• Principled Algorithms for Optimizing Generalized Metrics in Binary Classification [53.604375124674796]
  We introduce principled algorithms for optimizing generalized metrics, supported by $H$-consistency and finite-sample generalization bounds.<n>Our approach reformulates metric optimization as a generalized cost-sensitive learning problem.<n>We develop new algorithms, METRO, with strong theoretical performance guarantees.
  arXiv  Detail & Related papers  (2025-12-29T01:33:42Z)
• Cost-aware Stopping for Bayesian Optimization [53.34052774820105]
  We propose a cost-aware stopping rule for Bayesian optimization that adapts to varying evaluation costs and is free of tuning.<n>We prove a theoretical guarantee bounding the expected cumulative evaluation cost incurred by our stopping rule when paired with state-of-the-art acquisition functions.
  arXiv  Detail & Related papers  (2025-07-16T17:54:14Z)
• Minimax Optimal Reinforcement Learning with Quasi-Optimism [9.410437324336275]
  We introduce EQO (Exploration via Quasi-Optimism) as a new type of reinforcement learning algorithm. It avoids reliance on empirical variances and employs a simple bonus term proportional to the inverse of the state-action visit count. It consistently outperforms existing algorithms in both regret performance and computational efficiency.
  arXiv  Detail & Related papers  (2025-03-02T09:32:06Z)
• Every Call is Precious: Global Optimization of Black-Box Functions with Unknown Lipschitz Constants [72.47160195925056]
  We introduce Call Precious (P), a novel approach for global optimization of Lipschitz continuous functions. P eliminates the need to estimate the Lipschitz constant, thereby minimizing additional function. EC guarantees no-regret performance for evaluation budgets.
  arXiv  Detail & Related papers  (2025-02-06T18:34:40Z)
• $i$REPO: $i$mplicit Reward Pairwise Difference based Empirical Preference Optimization [12.266207199002604]
  Large Language Models (LLM) can sometimes produce outputs that deviate from human expectations. We propose a novel framework named $i$REPO, which utilizes implicit Reward pairwise difference regression for Empirical Preference Optimization. We show that $i$REPO effectively achieves self-alignment using soft-label, self-generated responses and the logit of empirical AI annotators.
  arXiv  Detail & Related papers  (2024-05-24T05:42:11Z)
• Lower-Left Partial AUC: An Effective and Efficient Optimization Metric for Recommendation [52.45394284415614]
  We propose a new optimization metric, Lower-Left Partial AUC (LLPAUC), which is computationally efficient like AUC but strongly correlates with Top-K ranking metrics. LLPAUC considers only the partial area under the ROC curve in the Lower-Left corner to push the optimization focus on Top-K.
  arXiv  Detail & Related papers  (2024-02-29T13:58:33Z)
• Unexpected Improvements to Expected Improvement for Bayesian Optimization [23.207497480389208]
  We propose LogEI, a new family of acquisition functions whose members either have identical or approximately equal optima as their canonical counterparts, but are substantially easier to optimize numerically. Our empirical results show that members of the LogEI family of acquisition functions substantially improve on the optimization performance of their canonical counterparts and surprisingly, are on par with or exceed the performance of recent state-of-the-art acquisition functions.
  arXiv  Detail & Related papers  (2023-10-31T17:59:56Z)
• High-dimensional Contextual Bandit Problem without Sparsity [8.782204980889077]
  We propose an explore-then-commit (EtC) algorithm to address this problem and examine its performance. We derive the optimal rate of the ETC algorithm in terms of $T$ and show that this rate can be achieved by balancing exploration and exploitation. We introduce an adaptive explore-then-commit (AEtC) algorithm that adaptively finds the optimal balance.
  arXiv  Detail & Related papers  (2023-06-19T15:29:32Z)
• Optimizing Two-way Partial AUC with an End-to-end Framework [154.47590401735323]
  Area Under the ROC Curve (AUC) is a crucial metric for machine learning. Recent work shows that the TPAUC is essentially inconsistent with the existing Partial AUC metrics. We present the first trial in this paper to optimize this new metric.
  arXiv  Detail & Related papers  (2022-06-23T12:21:30Z)
• Regret Bounds for Expected Improvement Algorithms in Gaussian Process Bandit Optimization [63.8557841188626]
  The expected improvement (EI) algorithm is one of the most popular strategies for optimization under uncertainty. We propose a variant of EI with a standard incumbent defined via the GP predictive mean. We show that our algorithm converges, and achieves a cumulative regret bound of $mathcal O(gamma_TsqrtT)$.
  arXiv  Detail & Related papers  (2022-03-15T13:17:53Z)
• Rectified Max-Value Entropy Search for Bayesian Optimization [54.26984662139516]
  We develop a rectified MES acquisition function based on the notion of mutual information. As a result, RMES shows a consistent improvement over MES in several synthetic function benchmarks and real-world optimization problems.
  arXiv  Detail & Related papers  (2022-02-28T08:11:02Z)
• SnAKe: Bayesian Optimization with Pathwise Exploration [9.807656882149319]
  We consider a novel setting where the expense of evaluating the function can increase significantly when making large input changes between iterations. This paper investigates the problem and introduces 'Sequential Bayesian Optimization via Adaptive Connecting Samples' (SnAKe) It provides a solution by considering future queries and preemptively building optimization paths that minimize input costs.
  arXiv  Detail & Related papers  (2022-01-31T19:42:56Z)
• Momentum Accelerates the Convergence of Stochastic AUPRC Maximization [80.8226518642952]
  We study optimization of areas under precision-recall curves (AUPRC), which is widely used for imbalanced tasks. We develop novel momentum methods with a better iteration of $O (1/epsilon4)$ for finding an $epsilon$stationary solution. We also design a novel family of adaptive methods with the same complexity of $O (1/epsilon4)$, which enjoy faster convergence in practice.
  arXiv  Detail & Related papers  (2021-07-02T16:21:52Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.