Convergence Rates of Gaussian Process Thompson Sampling for Efficient Global Optimization
This paper studies noiseless efficient global optimization via Gaussian Process Thompson Sampling (GP-TS) in the frequentist RKHS setting. It proves that standard GP-TS suffers an intrinsic $\sqrt{\log N}$ simple-regret penalty for Mat\'ern kernels, yielding $O(N^{-\nu/d}\sqrt{\log N})$, and proposes Capped Thompson Sampling (GP-CTS), which achieves the minimax-optimal $\Theta(N^{-\nu/d})$ rate using a known RKHS norm bound. The analysis covers both discrete and continuous domains and is notable for matching upper and lower bounds in a non-bandit setting.
The paper delivers a tight and rigorous characterization of GP-TS convergence. For Mat\'ern kernels with smoothness $\nu$ in dimension $d$, it establishes a worst-case expected simple-regret upper bound of $O(N^{-\nu/d}\sqrt{\log N})$ for both discrete and continuous implementations. For a fixed one-dimensional Mat\'ern-$5/2$ kernel, it proves matching lower bounds of $\Omega(N^{-5/2}\sqrt{\log N})$, showing the logarithmic factor is intrinsic rather than an artifact. The proposed GP-CTS eliminates this factor to achieve the minimax-optimal $\Theta(N^{-\nu/d})$. The authors summarize their main algorithmic insight as: 'This modification successfully eliminates the logarithmic penalty and achieves the minimax-optimal rate $\Theta(N^{-\nu/d})$ for both discrete and continuous implementations.'
The lower-bound analysis in Section 4 is the standout contribution. By analyzing Gaussian derivative processes and constructing a quadratic-peaked objective with a flat plateau, the authors show that persistent overshoot on the suboptimal region can force GP-TS to miss the true maximizer. They explain that the mechanism is 'competition between Gaussian extremes on the suboptimal plateau and sampled values near the true maximizer.' On the positive side, the continuous-domain upper bound uses a nested-grid chaining argument (Lemma 3) to control exact posterior paths without restricting the algorithm to a finite grid, and the GP-CTS cap is cleanly derived from the deterministic RKHS inequality $|f(x)-\mu_n(x)|\le B s_n(x)$.
The negative result is narrower than the title suggests: the matching lower bound is proved only for a fixed one-dimensional Mat\'ern-$5/2$ kernel, and the authors concede that 'extending the logarithmic lower bounds beyond the present Mat\'ern parameters would clarify how widely the identified mechanism applies.' The GP-CTS fix, while theoretically optimal, requires a known valid RKHS norm upper bound $\overline{B}$ as extra algorithmic input; the paper notes that 'obtaining a valid norm upper bound without prior knowledge of the function class remains an additional challenge.' In addition, the continuous results assume exact posterior path sampling and exact global maximization, and the paper admits that 'practical implementations based on finite-dimensional sample-path approximations introduce additional sampling errors that are not covered by these results.'
Within the studied regime, the internal evidence is consistent: the upper and lower bounds coincide at $\Theta(N^{-5/2}\sqrt{\log N})$ for the specific Mat\'ern-$5/2$, $d=1$ case. The comparison to prior work is accurate: Table 1 contrasts the bounds with Takeno and Iwazaki [12] for GP-BTS, and the authors correctly claim that compared with previous noiseless GP-TS bounds, their 'results improve the logarithmic dependence when $1<\nu\le d$ and the polynomial convergence rate when $\nu>d$.' The minimax baseline for Mat\'ern kernels is appropriately drawn from Bull [1] and V\'azquez and Petit [14], confirming that GP-CTS attains the minimax rate.
Reproduction is entirely theoretical, with all proofs deferred to appendices (e.g., 'The complete proof is given in Appendix B.6'). Algorithms 1 and 2 are formally specified, but no code, data, or empirical validation is provided. The continuous results rest on idealized assumptions such as exact maximization of exact continuous posterior sample paths. Independent verification would require re-deriving the lengthy steps in the appendices, whose full text is truncated in the provided version.
Efficient global optimization aims to identify a global optimum of an expensive black-box function within a limited evaluation budget $N$. We investigate the convergence rates of Gaussian process Thompson sampling (GP-TS) under noiseless observations, assuming a fixed objective function in a reproducing kernel Hilbert space (RKHS). For Mat\'ern kernels with smoothness parameter $\nu$ in dimension $d$, we establish a worst-case expected simple-regret upper bound of $O(N^{-\nu/d}\sqrt{\log N})$ for both discrete GP-TS on sufficiently fine grids and its continuous counterpart. For the continuous implementation, we develop a nested-grid argument to control posterior sample paths over the entire domain. We further establish matching lower bounds of $\Omega(N^{-5/2}\sqrt{\log N})$ for both implementations under a fixed one-dimensional Mat\'ern-$5/2$ kernel, demonstrating that the logarithmic penalty is intrinsic to standard GP-TS in this setting. Motivated by this limitation, we propose Gaussian Process Capped Thompson Sampling (GP-CTS), which caps posterior sample paths using a valid RKHS norm upper bound while preserving optimism. This modification successfully eliminates the logarithmic penalty and achieves the minimax-optimal rate $\Theta(N^{-\nu/d})$ for both discrete and continuous implementations.
Pick a starting point or write your own. Challenges run in the background, so you can keep reading while the AI investigates.
No challenges yet. Disagree with the review? Ask the AI to revisit a specific claim.