How Many Initial Points Does Bayesian Optimization Need?

• URL: http://arxiv.org/abs/2607.04356v1
• Date: Sun, 05 Jul 2026 15:22:53 GMT
• Title: How Many Initial Points Does Bayesian Optimization Need?
• Abstract summary: We show that total cost of evaluations is U-shaped in $n_$, i.e., a practitioner wastes resources by selecting either too low or too high a value of $n_$.<n>We attribute this U-shape to the known boundary issue of variance-driven BO: BO burns early budget on corners of the hypercube before turning inward.
• Score: 2.738648582869357
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Bayesian Optimization (BO) generally begins with an initialization phase: a batch of $n_0$ uninformed evaluations. The choice of $n_0$ remains largely heuristic, and we empirically observe that the total cost (random initial points plus BO iterations needed to find the global optimum) is U-shaped in $n_0$, i.e., a practitioner wastes resources by selecting either too low or too high a value of $n_0$. We find this tradeoff persists across MLE, Bayesian MCMC, and exact GP hyperparameters, as well as across acquisition functions. Toward the latter, Thompson Sampling appears an exception, with both total cost and simple regret essentially $n_0$-agnostic, though higher in our experiments. We attribute this U-shape to the known boundary issue of variance-driven BO: BO burns early budget on corners of the hypercube before turning inward. We demonstrate this effect using a 3D BO trajectory where the exact hyperparameters are known. We conclude with practical recommendations: use multi-step lookahead BO where possible; otherwise use Thompson Sampling when $n_0$ cannot be tuned, and a generously large $n_0$ when it can.

Related papers

• Best-of-Majority: Minimax-Optimal Strategy for Pass@$k$ Inference Scaling [54.50689440956967]
  LLM inference often generates a batch of candidates for a prompt and selects one via strategies like majority voting or Best-of-N (BoN)<n>We propose Best-of-Majority (BoM) with a pivotal step that restricts the candidates to the responses with high frequency in the $N$ samples before selecting the top-$k$ rewards.<n>Unlike majority voting and BoN, BoM has a key advantage: unlike majority voting and BoN, its performance does not degrade when increasing $N$.
  arXiv  Detail & Related papers  (2025-10-03T17:35:45Z)
• Bayesian Optimization from Human Feedback: Near-Optimal Regret Bounds [20.024434010891433]
  We refer to this problem as Bayesian Optimization from Human Feedback (HF), which differs from the best actions from a reduced feedback model.<n>The objective is to identify the best action using a limited preference framework.<n>In other words, the same number of preferential emerging samples as scalar-valued samples is sufficient to find a nearly optimal solution.
  arXiv  Detail & Related papers  (2025-05-29T17:17:29Z)
• Near-optimal Regret Using Policy Optimization in Online MDPs with Aggregate Bandit Feedback [49.84060509296641]
  We study online finite-horizon Markov Decision Processes with adversarially changing loss and aggregate bandit feedback (a.k.a full-bandit)<n>Under this type of feedback, the agent observes only the total loss incurred over the entire trajectory, rather than the individual losses at each intermediate step within the trajectory.<n>We introduce the first Policy Optimization algorithms for this setting.
  arXiv  Detail & Related papers  (2025-02-06T12:03:24Z)
• Beyond likelihood ratio bias: Nested multi-time-scale stochastic approximation for likelihood-free parameter estimation [49.78792404811239]
  We study inference in simulation-based models where the analytical form of the likelihood is unknown.<n>We use a ratio-free nested multi-time-scale approximation (SA) method that simultaneously tracks the score and drives the parameter update.<n>We show that our algorithm can eliminate the original bias $Obig(sqrtfrac1Nbig)$ and accelerate the convergence rate from $Obig(beta_k+sqrtfracalpha_kNbig)$.
  arXiv  Detail & Related papers  (2024-11-20T02:46:15Z)
• (Accelerated) Noise-adaptive Stochastic Heavy-Ball Momentum [7.095058159492494]
  Heavy ball momentum (SHB) is commonly used to train machine learning models, and often provides empirical results over gradient descent.<n>We show that SHB can attain an accelerated mini-batch size when the mini-batch size is larger than a threshold $b*$ that on the condition number $kappa2$.
  arXiv  Detail & Related papers  (2024-01-12T18:17:28Z)
• Kernelized Normalizing Constant Estimation: Bridging Bayesian Quadrature and Bayesian Optimization [51.533164528799084]
  We show that to estimate the normalizing constant within a small relative error, the level of difficulty depends on the value of $lambda$. We find that this pattern holds true even when the function evaluations are noisy.
  arXiv  Detail & Related papers  (2024-01-11T07:45:09Z)
• $\pi$BO: Augmenting Acquisition Functions with User Beliefs for Bayesian Optimization [40.30019289383378]
  We propose $pi$BO, an acquisition function generalization which incorporates prior beliefs about the location of the optimum. In contrast to previous approaches, $pi$BO is conceptually simple and can easily be integrated with existing libraries and many acquisition functions. We also demonstrate that $pi$BO improves on the state-of-the-art performance for a popular deep learning task, with a 12.5 $times$ time-to-accuracy speedup over prominent BO approaches.
  arXiv  Detail & Related papers  (2022-04-23T11:07:13Z)
• Approximate Function Evaluation via Multi-Armed Bandits [51.146684847667125]
  We study the problem of estimating the value of a known smooth function $f$ at an unknown point $boldsymbolmu in mathbbRn$, where each component $mu_i$ can be sampled via a noisy oracle. We design an instance-adaptive algorithm that learns to sample according to the importance of each coordinate, and with probability at least $1-delta$ returns an $epsilon$ accurate estimate of $f(boldsymbolmu)$.
  arXiv  Detail & Related papers  (2022-03-18T18:50:52Z)
• Bayesian Optimistic Optimisation with Exponentially Decaying Regret [58.02542541410322]
  The current practical BO algorithms have regret bounds ranging from $mathcalO(fraclogNsqrtN)$ to $mathcal O(e-sqrtN)$, where $N$ is the number of evaluations. This paper explores the possibility of improving the regret bound in the noiseless setting by intertwining concepts from BO and tree-based optimistic optimisation. We propose the BOO algorithm, a first practical approach which can achieve an exponential regret bound with order $mathcal O(N-sqrt
  arXiv  Detail & Related papers  (2021-05-10T13:07:44Z)
• Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits with Linear Payoff Functions [53.77572276969548]
  We show that the C$2$UCB algorithm has the optimal regret bound $tildeO(dsqrtkT + dk)$ for the partition matroid constraints. For general constraints, we propose an algorithm that modifies the reward estimates of arms in the C$2$UCB algorithm.
  arXiv  Detail & Related papers  (2021-01-20T04:29:18Z)
• MOTS: Minimax Optimal Thompson Sampling [89.2370817955411]
  It has remained an open problem whether Thompson sampling can match the minimax lower bound $Omega(sqrtKT)$ for $K$-armed bandit problems. We propose a variant of Thompson sampling called MOTS that adaptively clips the sampling instance of the chosen arm at each time step. We prove that this simple variant of Thompson sampling achieves the minimax optimal regret bound $O(sqrtKT)$ for finite time horizon $T$, as well as the optimal regret bound for Gaussian rewards when $T$ approaches infinity.
  arXiv  Detail & Related papers  (2020-03-03T21:24:39Z)

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.