Trading Adaptive Depth for Parallel Width in Prior-Guided Search

Automated machine-learning (AutoML) search consumes both evaluations and feedback rounds. When evaluations can run in parallel, waiting for feedback between batches can dominate elapsed time even when the total number of evaluations is unchanged. We study how much adaptive depth is needed to reach a target regret when each round can evaluate $b$ candidates in parallel. We characterize this tradeoff through the iso-regret frontier $b\mapsto N^{\star }(\epsilon ,b,\delta )$, which under regularity, coverage, and calibration conditions satisfies $N^{\star }(\epsilon ,b,\delta )=O\left(1+\frac{d_{\mathrm{eff}}\log (W/\epsilon )}{\log (b/{\nu }_{\mathrm{eff}})}\right)$. Here $d_{\mathrm{eff}}$ describes how rapidly near-optimal mass vanishes under a fixed reference prior, while ${\nu }_{\mathrm{eff}}$ summarizes losses in useful within-round coverage. The result gives a sufficient regime in which increasing parallel width can reduce the number of feedback rounds. Motivated by this characterization, we propose Prior-Weighted Bayesian Optimization (PWBO), which combines prior-weighted proposals, diversity-aware batch selection, and confidence-based elimination. In controlled synthetic experiments that vary prior quality and within-round coverage, the observed round counts follow the predicted reciprocal-log frontier, and the fitted difficulty parameter increases across priors as the theory predicts. We then study PWBO on a fully enumerated Avazu click-through-rate (CTR) pipeline testbed, where enumeration provides an exact reachable comparator while each search evaluation still requires model training. On this testbed, PWBO reaches the target in fewer feedback rounds than competing BO baselines.