betaFeedback

WorksMathematics

Tight Sequential Confidence Intervals for Online Kernel Regression

Abstract

We characterize, in the worst case over kernels, the sharp minimax width of online confidence intervals for elements of a reproducing kernel Hilbert space (RKHS). This resolves the open problem posed by Vakili et al. (2021) in its original discrete-time form. A learner observes yi=f(xi)+εiy_i=f(x_i)+ε_i at adaptively chosen points, with ∥f∥Hk≤B\|f\|_{\mathcal H_k}\le B and i.i.d. RR-sub-Gaussian noise, and reports the interval ∣f(x)−μn(x)∣≤ρn(δ)σn(x)|f(x)-μ_n(x)|\leρ_n(δ)σ_n(x), where μnμ_n and σnσ_n are the posterior mean and standard deviation of a surrogate Gaussian process model with regularization parameter λλ. Writing ρn∗(δ)ρ_n^*(δ) for the minimax confidence width for a fixed kernel, we show that, for the sum of a linear kernel and a periodic Sobolev kernel, all sufficiently large nn, and all δ∈(0,1/4]δ\in(0,1/4], ρn∗(δ)≍B+(R/λ)γn+log⁡(1/δ)ρ_n^*(δ)\asymp B+(R/λ)\sqrt{γ_n+\log(1/δ)}, where γnγ_n is the maximal information gain and grows polynomially in nn. Building on Lattimore (2023), we construct an adaptive design on a fixed two-dimensional domain for which, under Gaussian noise, the normalized error at a prespecified point is Ω(B+(R/λ)γn)Ω(B+(R/λ)\sqrt{γ_n}) with constant probability. This rules out the conjectured polylogarithmic width in the worst case over kernels and online designs.

Introduction

Kernel methods extend linear models to rich nonlinear function classes, and a large body of work studies online learning problems in which the unknown objective lies in a reproducing kernel Hilbert space (RKHS). Two prominent applications are kernelized bandits [44, 52, 7, 41, 50] and kernel-based reinforcement learning [59, 48, 47, 18].

In kernelized bandits and kernel-based reinforcement learning, surrogate Gaussian process (GP) models are often used to construct confidence intervals.

We observe an unknown function f∈Hkf \in\mathcal{H}_k on a compact domain X⊂Rd\mathcal{X} \subset\mathbb{R}^d through

yi=f(xi)+ϵi, i=1,…,n, ∥f∥Hk≤B,(1)y_i = f(x_i) + \epsilon_i,\ i = 1,\ldots,n,\ \|f\|_{\mathcal{H}_k} \le B, \tag*{(1)}

where kk is a known kernel and the noise terms ϵi\epsilon_i are i.i.d. RR-sub-Gaussian. The design is online, so xix_i may depend on the past observations {(xj,yj)}j<i\{(x_j,y_j)\}_{j<i}. Following Vakili et al. [51], let μn\mu_n and σn\sigma_n denote the posterior mean and standard deviation of a zero-mean surrogate GP with kernel kk and regularization parameter λ>0\lambda> 0. We seek the smallest width ρn(δ)\rho_n(\delta) such that, for every admissible ff, noise law, and online design, the following holds with probability at least 1−δ1-\delta.

∣f(x)−μn(x)∣≤ρn(δ)σn(x)for all x∈X.(2)|f(x)-\mu_n(x)| \le\rho_n(\delta)\sigma_n(x)\quad\text{for all }x\in\mathcal{X}. \tag*{(2)}

For offline designs independent of the noise, standard confidence bounds have only logarithmic dependence on nn under suitable kernel regularity conditions ([49 c]). In the online setting, self-normalized concentration gives the width ([2, 1, 7, 11])

ρn(δ)=B+Rλ2log⁡1δ+γn,\rho_n(\delta)=B+\frac{R}{\lambda}\sqrt{2\log\frac{1}{\delta}+\gamma_n},

where γn\gamma_n is the maximal information gain after nn observations. For kernels with polynomially decaying eigenvalues, including Matérn kernels, γn\gamma_n can grow polynomially in nn, making this width substantially larger than its offline counterpart ([50, 26]).

Over NN rounds, the standard analysis of the Gaussian process upper confidence bound (GP-UCB) algorithm gives regret O~(ρN(δ)NγN)\widetilde{O}(\rho_N(\delta)\sqrt{N\gamma_N}), which becomes O~(γNN)\widetilde{O}(\gamma_N\sqrt{N}) under the existing confidence width ([44, 7]). SupKernelUCB achieves O~(NγN)\widetilde{O}(\sqrt{N\gamma_N}) using offline confidence intervals ([52]). This gap motivates asking whether the γn\sqrt{\gamma_n} term in online confidence widths is necessary.

Vakili et al. [51] asked whether the γn\sqrt{\gamma_n} term in online confidence widths could be replaced by a term that is polylogarithmic in nn. The discrete-time lower bound for linear regression of Khamaru et al. [28] does not distinguish these rates, since γn\gamma_n grows only logarithmically in nn for fixed dimension. Lattimore [31] showed that this inflation is unavoidable in a continuous-time analogue, but explicitly mentioned that the corresponding discrete-time result remained unproved despite supporting simulations. Thus, the original question remained open for kernels with polynomially growing information gain:

What is the minimax optimal growth rate of the width ρn(δ)\rho_n(\delta) with nn? In particular, can the existing width be reduced by a factor of order γn\sqrt{\gamma_n}, up to logarithmic factors?

We resolve this question in its original discrete-time model, in the worst case over kernels. For each smoothness scale s>1/2s>1/2, we construct the sum of a linear kernel and a periodic Sobolev kernel of order ss on the fixed domain X=[−1,1]×[0,2π]⊂R2\mathcal{X}=[-1,1]\times[0,2\pi]\subset\mathbb{R}^2. For fB(a,b)=−Baf_B(a,b)=-Ba and i.i.d. N(0,R2)\mathcal{N}(0,R^2) noise, we construct, for each n≥n0(s,λ)n\ge n_0(s,\lambda), an online design such that, with probability at least 6/116/11,

∣fB(x0)−μn(x0)∣σn(x0)≳B+Rλ(nλ2)14s≳B+Rλγn.\frac{|f_B(x_0)-\mu_n(x_0)|}{\sigma_n(x_0)} \gtrsim B+\frac{R}{\lambda}\left(\frac{n}{\lambda^2}\right)^{\frac{1}{4s}}\gtrsim B+\frac{R}{\lambda}\sqrt{\gamma_n}.

where x0=(1,0)x_0=(1,0) is fixed before observing any data.

Let ρn∗(δ)\rho_n^*(\delta) denote the minimax confidence width of (2), defined in § 3. Combining this construction with the existing upper bound and a Gaussian tail lower bound for a deterministic design yields, for all n≥n0(s,λ)n \ge n_0(s,\lambda) and δ∈(0,1/4]\delta\in(0,1/4],

ρn∗(δ)≳B+Rλγn+log⁡1δ,γn≲(nλ2)12s\rho_n^*(\delta) \gtrsim B+\frac{R}{\lambda}\sqrt{\gamma_n+\log\frac{1}{\delta}},\qquad\gamma_n\lesssim\left(\frac{n}{\lambda^2}\right)^{\frac{1}{2s}}

where all comparison constants depend only on ss.

Since our kernel has input dimension d=2d=2 and polynomially growing information gain, the conjectured polylogarithmic width cannot hold for every kernel. Consequently, the gap in the standard GP-UCB regret analysis cannot be closed in general solely by tightening a confidence width that is valid for every kernel and online design and depends on the kernel only through γn\gamma_n and dd. Whether the γn\sqrt{\gamma_n} dependence can be improved for Matérn or squared exponential kernels remains open.

Notation: We write [n]={1,…,n}[n]=\{1,\ldots,n\} and use ∣J∣|J| for the cardinality of a finite set JJ. For a vector vv, ∥v∥2\|v\|_2 denotes its Euclidean norm. For a matrix AA, ∥A∥op\|A\|_{\mathrm{op}}, ∥A∥F\|A\|_F, and Tr⁡(A)\operatorname{Tr}(A) denote its operator norm, Frobenius norm, and trace, respectively. For symmetric matrices, A⪰A′A\succeq A' means that A−A′A-A' is positive semidefinite, and A≻0A\succ0 means that AA is positive definite. We use InI_n for the n×nn\times n identity matrix, 1n\mathbf{1}_n for the all-ones vector in Rn\mathbb{R}^n, and ⊗\otimes for the Kronecker product. For A∈Rn×nA\in\mathbb{R}^{n\times n} and J⊆[n]J\subseteq[n], AJA_J denotes the principal submatrix with rows and columns indexed by JJ. The notation N(μ,σ2)\mathcal{N}(\mu,\sigma^2) denotes the Gaussian distribution with mean μ\mu and variance σ2\sigma^2, and N(0,In)\mathcal{N}(0,I_n) denotes the standard Gaussian distribution on Rn\mathbb{R}^n. We use ⌊⋅⌋\lfloor\cdot\rfloor and ⌈⋅⌉\lceil\cdot\rceil for the floor and ceiling functions, and ii for the imaginary unit. For nonnegative quantities u,vu,v, we write u≳vu\gtrsim v if u≥cvu\ge cv and u≍vu\asymp v if cv≤u≤Cvcv\le u\le Cv, where c,C>0c,C>0 depend at most on the smoothness parameter ss, unless stated otherwise. The symbols O(⋅)O(\cdot) and Ω(⋅)\Omega(\cdot) have their usual asymptotic meanings as n→∞n\to\infty, and O~(⋅)\widetilde{O}(\cdot) hides polylogarithmic factors.

Literature Review

Kernelized bandits and Gaussian process optimization. Srinivas et al. [44] expressed GP-UCB regret through maximal information gain, with subsequent RKHS and contextual extensions [7, 29]. Lower bounds were established for the squared exponential and Matérn kernels [41, 4]. More recently, Ma and Scarlett [34] prove an Ω(NγN/log⁡N)\Omega(\sqrt{N\gamma_N/\log N}) expected regret lower bound for nonconstant continuous kernels on compact domains under Gaussian noise.

For the Matérn family, domain partitioning [25] and horizon-dependent regularization [56] yield sublinear regret. GP-UCB also admits improved guarantees in noise-free RKHS models and in the Bayesian setting [24 a], while regret lower bounds are available for specific exploration and regularization schedules [55, 57].

Related questions arise in kernel-based reinforcement learning [59, 48, 47]. For Sobolev RKHS reward and transition-density models, Hu and Simchi-Levi [18] characterize the minimax expected regret as a function of the number of episodes.

Self-normalized concentration and online confidence intervals. Confidence intervals and high-probability bounds are fundamental tools in probability and statistics. These include time-uniform confidence sequences for sequential data [15, 39] and uniform or pointwise bounds for stochastic processes [46, 10, 58, 19]. For online regression, self-normalized martingale inequalities [8, 9] underpin confidence ellipsoids for linear bandits and their Hilbert-space extensions [2, 1]. They yield online confidence bounds with a γn\sqrt{\gamma_n} dependence for kernel regression [7, 11, 56]. Recent work develops tighter kernel confidence bounds [12], dimension-free Bernstein-type inequalities [3], bounds without regularization penalties under additional covariate assumptions [6], and guarantees under kernel misspecification [35].

Maximal information gain. The maximal information gain was introduced by Srinivas et al. [44], with bounds for common kernels building on Seeger et al. [42]. Vakili et al. [50] bound it through the eigenvalue decay of the kernel, which gives γn=O~(nd/(2ν+d))\gamma_n = \tilde{O}(n^{d/(2\nu+d)}) for the Matérn-ν\nu kernel, and Janz et al. [26] determine its sharp order, up to constant factors, for the Matérn and squared exponential kernels. More broadly, effective dimension and eigenvalue decay control regret bounds in kernelized contextual bandits and online decision-making with functional regression [52, 60, 36, 20]. For our constructed kernel, we obtain matching information-gain bounds using Hadamard’s inequality for the upper bound and the spectrum of a repeated equispaced design for the lower bound.

Alternative approaches to kernelized bandits. In kernelized bandits, SupKernelUCB, batched elimination, and domain shrinking use staged or batched data collection to apply offline confidence bounds [52, 33, 40]. Related approaches combine experimental design with robust estimation [5], or use response-independent variance maximization to achieve near-optimal simple regret [49]. More recently, Takeno et al. [45] use data thinning under Gaussian noise to separate adaptive sampling from confidence interval construction, achieving near-optimal cumulative regret through phased elimination. RKHS regression can also serve as an estimation oracle within broader sequential decision-making frameworks. Such oracle-based approaches reduce contextual bandits to regression [13, 43, 21] and reinforcement learning to regression [38] (Hu et al. 2026).

The open problem and its partial answers. Vakili et al. [51] posed the question of tight online confidence intervals for RKHS elements. Lattimore [31] resolved its continuous-time version, with a lower bound for a direction that is not the feature vector of any point of the domain and on a domain that grows with nn, and left the discrete-time problem open. Khamaru et al. [28] carried out the discretization in finite dimension, where γn\sqrt{\gamma_n} and the rate dlog⁡n\sqrt{d\log n} coincide. On the regret side, Whitehouse et al. [56], who describe their result as a partial resolution of the open problem, show that GP-UCB attains sublinear regret for the Matérn family when the regularization parameter grows with the horizon. Our analysis establishes a discrete-time lower bound at a prespecified point of a fixed compact domain for a kernel with polynomially growing information gain. Together with the existing upper bound, this yields the sharp minimax characterization in Corollary 4.3.

Preliminaries

In this section, we formalize the statistical model and the criterion used throughout the paper. We first recall the RKHS model and the online design protocol, following the notation of Vakili et al. [51]. We then describe the surrogate GP model and the form of the confidence intervals, state the existing upper bound, and finally define the minimax confidence width.

Reproducing kernel Hilbert spaces. Let X⊂Rd\mathcal{X} \subset\mathbb{R}^{d} be a compact set and let k:X×X→Rk:\mathcal{X} \times\mathcal{X} \to\mathbb{R} be a continuous positive definite kernel. Let Hk\mathcal{H}_{k} denote the RKHS corresponding to kk, defined as the Hilbert space of functions on X\mathcal{X} equipped with an inner product ⟨⋅,⋅⟩Hk\langle\cdot,\cdot\rangle_{\mathcal{H}_{k}} that satisfies

k(⋅,x)∈Hk,⟨f,k(⋅,x)⟩Hk=f(x),∀x∈X, ∀f∈Hk.k(\cdot,x) \in\mathcal{H}_{k}, \quad\langle f,k(\cdot,x)\rangle_{\mathcal{H}_{k}} = f(x), \quad\forall x \in\mathcal{X},\ \forall f \in\mathcal{H}_{k}.

The second identity is the reproducing property. In particular, we have ∥k(⋅,x)∥Hk2=k(x,x)\lVert k(\cdot,x)\rVert_{\mathcal{H}_{k}}^{2}=k(x,x). Let {λm}m=1∞\{\lambda_{m}\}_{m=1}^{\infty} and {ϕm}m=1∞\{\phi_{m}\}_{m=1}^{\infty} denote the Mercer eigenvalues and eigenfeatures of kk with respect to a finite Borel measure whose support is X\mathcal{X}. By Mercer’s representation theorem [27], every f∈Hkf \in\mathcal{H}_{k} can be written as

f(x)=∑m=1∞wmλm1/2ϕm(x),∥f∥Hk=∥w∥ℓ2,(3)f(x)=\sum_{m=1}^{\infty}w_{m}\lambda_{m}^{1/2}\phi_{m}(x),\quad\lVert f\rVert_{\mathcal{H}_{k}}=\lVert w\rVert_{\ell_{2}}, \tag*{(3)}

so the decay of the eigenvalues λm\lambda_{m} measures the size of the function class. We use two examples below. The linear kernel k(x,x′)=xTx′k(x,x')=x^{\mathsf{T}}x' has at most dd nonzero eigenvalues, and its RKHS consists of linear functions. A kernel on the circle of the form ∑l≥1αlcos⁡(l(b−b′))\sum_{l\geq1}\alpha_{l}\cos(l(b-b')), with αl≥0\alpha_{l}\geq0 and ∑l≥1αl<∞\sum_{l\geq1}\alpha_{l}<\infty, has the trigonometric functions as eigenfeatures, and its eigenvalues are proportional to the weights αl\alpha_{l}, each with multiplicity two.

Observation model and online designs. A learner collects noisy observations {(xi,yi)}i=1n\{(x_{i},y_{i})\}_{i=1}^{n} of an unknown objective function f∈Hkf\in\mathcal{H}_{k}, where

yi=f(xi)+ϵi,i∈[n].y_{i}=f(x_{i})+\epsilon_{i},\quad i\in[n].

This is the standard observation model for kernelized bandits [44, 7]. Following Vakili et al. [51], we impose the following assumption.

Assumption 3.1. The RKHS norm of ff is bounded as ∥f∥Hk≤B\lVert f\rVert_{\mathcal{H}_{k}}\leq B, for some B>0B>0. Moreover, the noise terms are i.i.d. sub-Gaussian random variables, i.e., for some R>0R>0, E[exp⁡(ηϵi)]≤exp⁡(η2R2/2)\mathbb{E}[\exp(\eta\epsilon_{i})]\leq\exp(\eta^{2}R^{2}/2) for all η∈R\eta\in\mathbb{R} and all $i\geq 1.

In online learning problems, as pointed out by Vakili et al. [51], the observation points are collected sequentially: the point xi+1x_{i+1} is determined after all the values {(xj,yj)}j=1i\{(x_{j},y_{j})\}_{j=1}^{i} are revealed. This is in contrast to an offline design, where the points are fixed in advance.

Definition 3.2. (i) Online setting. Define the filtration

Fi:=σ(x1,…,xi+1,ϵ1,…,ϵi),i≥0.\mathcal{F}_{i}:=\sigma(x_{1},\ldots,x_{i+1},\epsilon_{1},\ldots,\epsilon_{i}),\quad i\geq0.

For each i≥1i\geq1, xix_{i} is Fi−1\mathcal{F}_{i-1}-measurable. The noise ϵi\epsilon_{i} is Fi\mathcal{F}_{i}-measurable and is independent of Fi−1\mathcal{F}_{i-1}.

(ii) Offline setting. The design sequence (xi)i≥1(x_{i})_{i\geq1} is independent of the noise sequence (ϵi)i≥1(\epsilon_{i})_{i\geq1}.

We make two additions to part (i) explicit. First, we include the sigma algebra F0=σ(x1)\mathcal{F}_0 = \sigma(x_1), which is needed for x1x_1. Second, we state the independence of ϵi\epsilon_i from Fi−1\mathcal{F}_{i-1}, which is implicit in Vakili et al. [51]: it holds whenever xix_i is a measurable function of the past observations {(xj,yj)}j<i\{(x_j,y_j)\}_{j<i} and of randomization that is independent of the noise. When only nn rounds are considered, we impose these conditions for i∈[n]i \in[n]. We refer to a sequence {xi}i=1n\{x_i\}_{i=1}^n that satisfies part (i) as an online design.

Surrogate GP model

A standard approach in kernelized regression employs a zero-mean surrogate GP model f^\widehat{f} with covariance kernel kk, using its posterior mean to estimate ff and its posterior standard deviation to quantify uncertainty ([44, 7, 49]). GP model f^\widehat{f} with kernel kk provides a surrogate posterior mean μn(x)=E[f^(x)∣{(xi,yi)}i=1n]\mu_n(x) = \mathbb{E}[\widehat{f}(x) \mid\{(x_i,y_i)\}_{i=1}^n] and a surrogate posterior variance σn2(x)=E[(f^(x)−μn(x))2∣{(xi,yi)}i=1n]\sigma_n^2(x) = \mathbb{E}[(\widehat{f}(x)-\mu_n(x))^2 \mid\{(x_i,y_i)\}_{i=1}^n]. It is well known that

μn(x)=zn⊤(x)yn,σn2(x)=k(x,x)−kn⊤(x)(λ2In+Kn)−1kn(x),(4)\mu_n(x) = z_n^\top(x)y_n,\quad\sigma_n^2(x) = k(x,x)-k_n^\top(x)(\lambda^2 I_n+K_n)^{-1}k_n(x), \tag*{(4)}

where kn(x)=[k(x,x1),k(x,x2),…,k(x,xn)]⊤k_n(x) = [k(x,x_1), k(x,x_2),\ldots,k(x,x_n)]^\top, KnK_n is the kernel matrix [Kn]i,j=k(xi,xj)[K_n]_{i,j}=k(x_i,x_j), zn(x)=(λ2In+Kn)−1kn(x)z_n(x)=(\lambda^2 I_n+K_n)^{-1}k_n(x), and λ>0\lambda>0 is a regularization parameter. yn=[y1,y2,…,yn]⊤y_n=[y_1,y_2,\ldots,y_n]^\top denotes the vector of observations. The posterior mean μn\mu_n coincides with the kernel ridge regression estimate with penalty λ2\lambda^2. The GP model is only a surrogate: the objective function ff is a fixed element of Hk\mathcal{H}_k, and the noise need not be Gaussian.

Confidence intervals and the existing bound

A confidence interval for ff takes the form

∣f(x)−μn(x)∣≤ρn(δ)σn(x)for all x∈X,with probability at least 1−δ,(5)|f(x)-\mu_n(x)|\leq\rho_n(\delta)\sigma_n(x)\quad\text{for all }x\in\mathcal{X},\quad\text{with probability at least }1-\delta, \tag*{(5)}

and we refer to ρn(δ)\rho_n(\delta) as its width.

In the online setting, we use the maximal information gain

γn:=sup⁡(x1,…,xn)∈Xnlog⁡det⁡(In+λ−2Kn).(6)\gamma_n := \sup_{(x_1,\ldots,x_n)\in\mathcal{X}^n}\log\det\left(I_n+\lambda^{-2}K_n\right). \tag*{(6)}

This quantity is closely related to the effective dimension of the kernel ([44, 52]). It is the normalized form of the definition in the open problem ([51]), since

log⁡det⁡(In+λ−2Kn)=log⁡det⁡(λ2In+Kn)−nlog⁡(λ2).\log\det\left(I_n+\lambda^{-2}K_n\right)=\log\det\left(\lambda^2I_n+K_n\right)-n\log(\lambda^2).

The two definitions, therefore, have the same maximizing designs and agree in value when λ=1\lambda=1. For the linear kernel, we have γn=O(dlog⁡n)\gamma_n=O(d\log n), whereas γn\gamma_n can grow polynomially in nn for kernels whose Mercer eigenvalues decay polynomially ([50, 26]).

Several works study online confidence bounds for kernel regression ([1, 7, 51, 56]). We state the bound for any fixed λ>0\lambda>0 in our notation.

Theorem 3.3 (Chowdhury and Gopalan [7]; Durand et al. [11]). Let kk be a continuous positive definite kernel on a compact set X⊂Rd\mathcal{X}\subset\mathbb{R}^d. Under Assumption 3.1, in the online design setting of Definition 3.2, for any δ∈(0,1)\delta\in(0,1), with probability at least $1-\delta,wehaveforall, we have for alln\geq 1

and all x∈Xx \in\mathcal{X} that

∣f(x)−μn(x)∣≤(B+Rλ2log⁡1δ+γn)σn(x).(7)|f(x)-\mu_n(x)| \le\left(B+\frac{R}{\lambda}\sqrt{2\log\frac{1}{\delta}}+\gamma_n\right)\sigma_n(x). \tag*{(7)}

Theorem 3.3 holds for every kernel and every online design.

The minimax confidence width. To provide the minimax lower bound, we first define the notion of minimax confidence width. We call a pair (f,P)(f,\mathbb{P}), consisting of an objective function ff and a joint law P\mathbb{P} of the design and the noise {(xi,ϵi)}i=1n\{(x_i,\epsilon_i)\}_{i=1}^n, an instance, and we write Pn(B,R)\mathcal{P}_n(B,R) for the collection of all instances that satisfy Assumption 3.1 and the online design condition in Definition 3.2. We define the minimax confidence width by

ρn∗(δ):=inf⁡{ρ≥0: sup⁡(f,P)∈Pn(B,R)P(∃x∈X:∣f(x)−μn(x)∣>ρσn(x))≤δ}.(8)\rho_n^*(\delta) := \inf\left\{\rho\ge0:\ \sup_{(f,\mathbb{P})\in\mathcal{P}_n(B,R)}\mathbb{P}\left(\exists x\in\mathcal{X}: |f(x)-\mu_n(x)|>\rho\sigma_n(x)\right)\le\delta\right\}. \tag*{(8)}

The quantity ρn∗(δ)\rho_n^*(\delta) depends on the kernel, the domain, and (B,R,λ)(B,R,\lambda), which we suppress in the notation. The event in (8) is measurable, because ff, μn\mu_n, and σn\sigma_n are continuous in xx and X\mathcal{X} is separable. The supremum takes the worst-case failure probability over the objective function, the noise distribution, and the online design. The design may depend on nn, BB, RR, and λ\lambda. The outer infimum selects the smallest width with worst-case failure probability at most δ\delta.

Theorem 3.3 gives

ρn∗(δ)≤B+Rλ2log⁡(1/δ)+γn\rho_n^*(\delta) \le B+\frac{R}{\lambda}\sqrt{2\log(1/\delta)+\gamma_n}

for every kernel and every nn. The open problem Vakili et al. [51] asks how ρn∗(δ)\rho_n^*(\delta) grows with nn, and in particular whether the γn\sqrt{\gamma_n} dependence can be improved.

The Sharp Minimax Confidence Width

In this section, we provide our theoretical guarantees on the sharp minimax confidence width. We first specify the kernel and the online design of the hard instance and establish a lower bound for online confidence intervals. Our additive Fourier kernel and adaptive sampling rule are partially motivated by the construction of Lattimore [31]. We then combine this result with the existing upper bound of Theorem 3.3 to obtain a sharp characterization of the minimax confidence width, and we record the resulting answer to the open problem.

The hard kernel. Fix a smoothness parameter s>1/2s>1/2. Define the 2π2\pi-periodic function

χ(ϑ):=∑l=1∞αlcos⁡(lϑ).\chi(\vartheta) := \sum_{l=1}^{\infty}\alpha_l\cos(l\vartheta).

Let ζ(u):=∑m=1∞m−u\zeta(u):=\sum_{m=1}^{\infty}m^{-u} for u≥1u\ge1 denote the Riemann zeta function. The weights are αl:=l−2s/ζ(2s)\alpha_l:=l^{-2s}/\zeta(2s) for l≥1l\ge1, so ∑l≥1αl=1\sum_{l\ge1}\alpha_l=1.

Using the Fourier representation of periodic RKHS kernels in Krieg and Vybrál [30], we define the normalized periodic Sobolev kernel of order ss on [0,2π][0,2\pi] by

ks∘(b,b′):=χ(b−b′).(9)k_s^\circ(b,b') := \chi(b-b'). \tag*{(9)}

The normalization gives ks∘(b,b)=χ(0)=1k_s^\circ(b,b)=\chi(0)=1. Under the uniform distribution on [0,2π][0,2\pi], the eigenfunctions are 2cos⁡(lb)\sqrt{2}\cos(lb) and 2sin⁡(lb)\sqrt{2}\sin(lb) for l≥1l \ge1, each with eigenvalue αl/2\alpha_l/2. The associated RKHS is the mean-zero periodic Sobolev space of order ss [53, 30].

Our second kernel is the linear kernel on [−1,1][-1,1], given by

k2(a,a′):=aa′,a,a′∈[−1,1].k_2(a,a') := aa',\quad a,a' \in[-1,1].

For the hard instance, we take the domain X:=[−1,1]×[0,2π]⊂R2\mathcal{X}:=[-1,1]\times[0,2\pi]\subset\mathbb{R}^2 and combine the two kernels to obtain

k((a,b),(a′,b′)):=k2(a,a′)+ks∘(b,b′).(10)k\big((a,b),(a',b')\big):=k_2(a,a')+k_s^\circ(b,b'). \tag*{(10)}

The constructed kernel satisfies the following property.

Proposition 4.1. The kernel kk in (10) is continuous and positive definite, with k((a,b),(a,b))=1+a2≤2k((a,b),(a,b))=1+a^2\le2. Under the uniform probability measure on X\mathcal{X}, its nonzero Mercer eigenvalues consist of one copy of 1/31/3 and two copies of αl/2\alpha_l/2 for each l≥1l\ge1. When listed in nonincreasing order with multiplicity, these eigenvalues satisfy λm≍m−2s\lambda_m\asymp m^{-2s}.

The proof is given in Appendix § 7.

Data generation. Fix n≥40n\ge40, set fB(a,b):=−Baf_B(a,b):=-Ba, and let q:=⌊n/20⌋q:=\lfloor n/20\rfloor. Before sampling, we fix the second coordinates by visiting qq equally spaced points in the same order for 20 passes, then using 0 for the remaining rounds.

b(r−1)q+j:=2π(j−1)qfor r∈[20], j∈[q],bi:=0 for 20q<i≤n.(11)b_{(r-1)q+j}:=\frac{2\pi(j-1)}{q}\quad\text{for }r\in[20],\ j\in[q],\quad b_i:=0\text{ for }20q<i\le n. \tag*{(11)}

From these coordinates, we form Kn∘:=[ks∘(bi,bj)]i,j∈[n]K_n^\circ:=[k_s^\circ(b_i,b_j)]_{i,j\in[n]} and compute the inverse and the LDLTLDL^\mathsf{T} factorization of the regularized kernel matrix.

G:=(λ2In+Kn∘)−1,λ2In+Kn∘=LDLT,(12)G:=(\lambda^2I_n+K_n^\circ)^{-1},\quad\lambda^2I_n+K_n^\circ=LDL^\mathsf{T}, \tag*{(12)}

where LL is unit lower triangular and DD is diagonal with positive entries. Set

En:=Tr⁡(G)−∑i=1n1Dii,κ:=En−1/2.(13)E_n:=\operatorname{Tr}(G)-\sum_{i=1}^{n}\frac{1}{D_{ii}},\quad\kappa:=E_n^{-1/2}. \tag*{(13)}

The repeated visit to b1b_1 ensures En>0E_n>0, as shown in the proof of Theorem 4.2.

In round i∈[n]i\in[n], take bib_i from (11) and choose xix_i using the past residuals yj+Baˉjy_j+B\bar a_j, j<ij<i.

ai:=−κR∑j<iLij(yj+Baˉj),aˉi:=max⁡{−1,min⁡{1,ai}},xi:=(aˉi,bi).(14)a_i:=-\frac{\kappa}{R}\sum_{j<i}L_{ij}(y_j+B\bar a_j),\quad\bar a_i:=\max\{-1,\min\{1,a_i\}\},\quad x_i:=(\bar a_i,b_i). \tag*{(14)}

We then observe yi=fB(xi)+ϵi=−Baˉi+ϵiy_i=f_B(x_i)+\epsilon_i=-B\bar a_i+\epsilon_i, where ϵi∼N(0,R2)\epsilon_i\sim\mathcal{N}(0,R^2) is independent of the past. We evaluate the confidence interval at the fixed point x0:=(1,0)x_0:=(1,0).

Theorem 4.2 (Lower bound for online confidence intervals). Fix s>1/2s > 1/2 and B,R,λ>0B, R, \lambda> 0. Consider the kernel (10), the objective function fB(a,b)=−Baf_B(a,b) = -Ba, i.i.d. noise ϵi∼N(0,R2)\epsilon_i \sim\mathcal{N}(0,R^2), and the online design (4.3–4.6). There exist constants cs,cs′>0c_s, c'_s > 0 depending only on ss and an integer n0=n0(s,λ)≥λ2n_0 = n_0(s,\lambda) \ge\lambda^2 such that, for every n≥n0n \ge n_0, with probability at least 6/116/11,

∣fB(x0)−μn(x0)∣σn(x0)≥cs[B+Rλ(nλ2)14s]≥cs′(B+Rλγn).\frac{\lvert f_B(x_0) - \mu_n(x_0)\rvert}{\sigma_n(x_0)} \ge c_s\left[B + \frac{R}{\lambda}\left(\frac{n}{\lambda^2}\right)^{\frac{1}{4s}}\right] \ge c'_s\left(B + \frac{R}{\lambda}\sqrt{\gamma_n}\right).

Moreover, for every n≥n0n \ge n_0, the maximal information gain of the kernel (10) satisfies γn≍(n/λ2)1/(2s)\gamma_n \asymp(n/\lambda^2)^{1/(2s)}, with comparison constants depending only on ss.

Consequently, for every δ∈(0,1/2]\delta\in(0,1/2] and n≥n0n \ge n_0, every deterministic width ρn(δ)\rho_n(\delta) for which (5) holds for this instance satisfies

ρn(δ)≥cs′(B+Rλγn).\rho_n(\delta) \ge c'_s\left(B + \frac{R}{\lambda}\sqrt{\gamma_n}\right).

Combining the upper bound in Theorem 3.3 and the lower bound in Theorem 4.2 with a Gaussian tail lower bound for a deterministic design gives the sharp minimax confidence width.

Corollary 4.3 (Sharp minimax confidence width). Fix s>1/2s > 1/2 and λ>0\lambda> 0, and consider the kernel (10). Let n0=n0(s,λ)n_0 = n_0(s,\lambda) be as in Theorem 4.2. For all n≥n0n \ge n_0, B,R>0B, R > 0, and δ∈(0,1/4]\delta\in(0,1/4], we have

ρn∗(δ)≍B+Rλγn+log⁡1δ.\rho_n^*(\delta) \asymp B + \frac{R}{\lambda}\sqrt{\gamma_n + \log\frac{1}{\delta}}.

with comparison constants depending only on ss.

For fixed ss, BB, RR, λ\lambda and δ∈(0,1/4]\delta\in(0,1/4], the minimax width for our d=2d = 2 kernel grows as n1/(4s)n^{1/(4s)}, with the lower bound holding even at the prespecified point x0x_0. Therefore, we resolve the open problem posed by Vakili et al. [51] in the worst case over kernels in discrete time.

Discussion

This paper resolves, in the worst case over kernels, the open problem on tight online confidence intervals for RKHS elements posed by Vakili et al. [51], in the discrete-time model in which it was stated. We use the existing upper bound and establish a matching lower bound. In particular, for the additive kernel (10), combining our lower bound with the existing self-normalized upper bound (Abbasi-Yadkori [1]; Chowdhury and Gopalan [7]; Durand et al. [11]) yields

ρn∗(δ)≍B+Rλγn+log⁡1δ.\rho_n^*(\delta) \asymp B + \frac{R}{\lambda}\sqrt{\gamma_n + \log\frac{1}{\delta}}.

for all sufficiently large nn and all δ∈(0,1/4]\delta\in(0,1/4]. Our discrete-time analysis shows that, for intervals of the form (5) and in the worst case over kernels and online designs, this inflation is an unavoidable statistical obstruction rather than an artifact of a particular concentration inequality or proof technique. Thus, the γn\sqrt{\gamma_n} dependence of the existing confidence width is unavoidable in general, ruling out the conjectured polylogarithmic width. It is also consistent with the fact that the known order-optimal algorithms for kernelized bandits rely on batching or elimination, which control the dependence between the design and the noise, rather than on a sharper online interval.

Several directions follow from this characterization. The most immediate task is to determine the minimax confidence width for specific kernel families. Our lower bound uses an additive linear component, and the online design steers the estimate of its coefficient. It remains open whether a Matérn or squared exponential kernel alone exhibits the same inflation at a point [26]. A second direction is the regret of GP-UCB with a fixed regularization parameter, for which our result does not exclude a design-specific analysis. A third direction is a lower bound over all estimators, as in the Bayes-risk bound of Lattimore [31] and the minimax bound of Khamaru et al. [28], and over all interval constructions, for a fixed kernel with polynomially growing information gain. Finally, a natural direction is to construct data-driven widths that adapt to the realized design while maintaining coverage. On the hard instance of Theorem 4.2, any data-dependent interval μn(x0)±ρ^n(δ)σn(x0)\mu_n(x_0) \pm\widehat{\rho}_n(\delta)\sigma_n(x_0) with coverage at least 1−δ1-\delta must satisfy ρ^n(δ)≥cs′[B+(R/λ)γn]\widehat{\rho}_n(\delta) \ge c'_s[B+(R/\lambda)\sqrt{\gamma_n}] with probability at least 6/11−δ6/11-\delta, for every n≥n0n \ge n_0. Wild refitting and related resampling methods provide tools for evaluating excess risk and prediction error [54, 21, 17, 37]. An open question is whether these ideas can be adapted to pointwise confidence intervals under adaptive sampling. We leave the investigation of these directions to future work.

Useful Mathematical Tools

We collect the concentration inequality and matrix formulas used below.

Lemma A.1 (Laurent–Massart inequality, Laurent and Massart [32]). Let ξ∼N(0,In)\xi\sim\mathcal{N}(0,I_n) and let A∈Rn×nA \in\mathbb{R}^{n \times n} be symmetric and positive semidefinite. For every t>0t > 0,

P(ξTAξ>tr⁡(A)+2∥A∥Ft+2∥A∥opt)≤e−t,\mathbb{P}\left(\xi^{\mathsf{T}} A \xi> \operatorname{tr}(A) + 2\lVert A\rVert_F\sqrt{t} + 2\lVert A\rVert_{\mathrm{op}}t\right) \le e^{-t},
P(ξTAξ<tr⁡(A)−2∥A∥Ft)≤e−t.\mathbb{P}\left(\xi^{\mathsf{T}} A \xi< \operatorname{tr}(A) - 2\lVert A\rVert_F\sqrt{t}\right) \le e^{-t}.

Lemma A.2 (Rank-one updates, Horn and Johnson [14]). Let A∈Rn×nA \in\mathbb{R}^{n \times n} be symmetric positive definite and u∈Rnu \in\mathbb{R}^n. Then

(A+uuT)−1=A−1−A−1uuTA−11+uTA−1u,(A + uu^{\mathsf{T}})^{-1} = A^{-1} - \frac{A^{-1}uu^{\mathsf{T}}A^{-1}}{1 + u^{\mathsf{T}}A^{-1}u},
det⁡(A+uuT)=det⁡(A)(1+uTA−1u).\det(A + uu^{\mathsf{T}}) = \det(A)(1 + u^{\mathsf{T}}A^{-1}u).

Lemma A.3 (Schur complements, Horn and Johnson [14]). Let A=(PqqTr)∈Rn×nA = \begin{pmatrix} P & q \\ q^{\mathsf{T}} & r \end{pmatrix} \in\mathbb{R}^{n \times n} be symmetric positive definite. Its Schur complement r−qTP−1qr - q^{\mathsf{T}}P^{-1}q is positive, and

det⁡A=det⁡P(r−qTP−1q),(A−1)nn=(r−qTP−1q)−1.\det A = \det P\left(r - q^{\mathsf{T}}P^{-1}q\right), \qquad(A^{-1})_{nn} = \left(r - q^{\mathsf{T}}P^{-1}q\right)^{-1}.

For n=1n = 1, the empty determinant and quadratic form are interpreted as one and zero, respectively.

Lemma A.4 (Determinant identities and bounds, Horn and Johnson [14]). For Ψ∈Rn×m\Psi\in\mathbb{R}^{n \times m}, Sylvester’s determinant identity gives

det⁡(In+ΨΨT)=det⁡(Im+ΨTΨ).\det(I_n + \Psi\Psi^{\mathsf{T}}) = \det(I_m + \Psi^{\mathsf{T}}\Psi).

For every symmetric positive definite A∈Rm×mA \in\mathbb{R}^{m \times m}, Hadamard’s inequality gives

det⁡A≤∏j=1mAjj.\det A \le\prod_{j=1}^{m} A_{jj}.

Properties of the Hard Kernel

Proof of Proposition 4.1. Since s>1/2s > 1/2, the weights satisfy ∑l≥1αl=1\sum_{l \ge1} \alpha_l = 1. The Fourier series defining χ\chi therefore converges uniformly, so ks∘k_s^\circ and the additive kernel kk are continuous. Define

e0(a,b):=3 a,el,c(a,b):=2cos⁡(lb),el,s(a,b):=2sin⁡(lb),l≥1.e_0(a,b) := \sqrt{3}\,a,\qquad e_{l,c}(a,b) := \sqrt{2}\cos(lb),\qquad e_{l,s}(a,b) := \sqrt{2}\sin(lb),\quad l \ge1.

The cosine difference identity gives the uniformly convergent expansion

k(x,x′)=13e0(x)e0(x′)+∑l=1∞αl2{el,c(x)el,c(x′)+el,s(x)el,s(x′)}.k(x,x') = \frac{1}{3}e_0(x)e_0(x') + \sum_{l=1}^{\infty}\frac{\alpha_l}{2}\left\{e_{l,c}(x)e_{l,c}(x') + e_{l,s}(x)e_{l,s}(x')\right\}.

Each feature product is a positive semidefinite rank-one kernel, and all its coefficients are positive. We conclude that kk is positive definite. Setting x=x′=(a,b)x = x' = (a,b) and using cos⁡2(lb)+sin⁡2(lb)=1\cos^2(lb) + \sin^2(lb) = 1 yields k(x,x)=a2+∑l≥1αl=1+a2≤2k(x,x)=a^2+\sum_{l\geq1}\alpha_l=1+a^2\leq2.

Under the uniform probability measure on X\mathcal{X}, the functions e0,el,c,el,se_0,e_{l,c},e_{l,s} form an orthonormal family. The trigonometric functions are orthonormal under the uniform measure on [0,2π][0,2\pi]. The first coordinate is independent of the second, with mean zero and second moment 1/31/3. Integrating the kernel expansion against each of these functions gives eigenvalue 1/31/3 for e0e_0 and αl/2\alpha_l/2 for both el,ce_{l,c} and el,se_{l,s}. The integral operator vanishes on the orthogonal complement of their closed span, so these are all its nonzero eigenvalues.

The periodic eigenvalues in nonincreasing order are λ~m=(2ζ(2s))−1⌈m/2⌉−2s\widetilde{\lambda}_m=(2\zeta(2s))^{-1}\lceil m/2\rceil^{-2s}. After inserting the single eigenvalue 1/31/3, the ordered sequence satisfies λ~m≤λm≤λ~m−1\widetilde{\lambda}_m\leq\lambda_m\leq\widetilde{\lambda}_{m-1} for m≥2m\geq2. Since λ~m≍m−2s\widetilde{\lambda}_m\asymp m^{-2s}, we obtain the claimed decay.

Proof of the Lower Bound

Fix a positive semidefinite kernel k∘k^\circ on [0,2π][0,2\pi] with k∘(b,b)≤1k^\circ(b,b)\leq1, a deterministic sequence b1,…,bnb_1,\ldots,b_n, and a test point x0=(1,b0)x_0=(1,b_0) with b0∈[0,2π]b_0\in[0,2\pi]. We use the additive kernel k((a,b),(a′,b′))=aa′+k∘(b,b′)k((a,b),(a',b'))=aa'+k^\circ(b,b') and the response model yi=fB(xi)+ϵiy_i=f_B(x_i)+\epsilon_i with fB(a,b)=−Baf_B(a,b)=-Ba and i.i.d. ϵi∼N(0,R2)\epsilon_i\sim\mathcal{N}(0,R^2). Write Kn∘=[k∘(bi,bj)]i,j∈[n]K_n^\circ=[k^\circ(b_i,b_j)]_{i,j\in[n]} and define G,L,D,EnG,L,D,E_n as in (12) and (13). For J⊆[n]J\subseteq[n], let kJ∘(b)=(k∘(b,bj))j∈Jk_J^\circ(b)=(k^\circ(b,b_j))_{j\in J} and let KJ∘K_J^\circ be the corresponding principal submatrix of Kn∘K_n^\circ. The posterior variance for the k∘k^\circ component based on JJ is

vJ(b):=k∘(b,b)−kJ∘(b)T(λ2I∣J∣+KJ∘)−1kJ∘(b),v∅(b):=k∘(b,b).v_J(b):=k^\circ(b,b)-k_J^\circ(b)^\mathsf{T}(\lambda^2 I_{|J|}+K_J^\circ)^{-1}k_J^\circ(b),\qquad v_\varnothing(b):=k^\circ(b,b).

Write v<i=v[i−1]v_{<i}=v_{[i-1]} and v−i=v[n]∖{i}v_{-i}=v_{[n]\setminus\{i\}}.

Whenever En>0E_n>0, set κ=En−1/2\kappa=E_n^{-1/2} and use the design (14). The residual yi+Baˉiy_i+B\bar{a}_i equals ϵi\epsilon_i for every realization, including when aia_i is clipped. Thus the vector ξ\xi with coordinates ξi=(yi+Baˉi)/R=ϵi/R\xi_i=(y_i+B\bar{a}_i)/R=\epsilon_i/R has law N(0,In)\mathcal{N}(0,I_n). The offset vector before clipping is

a~:=(In−L)ξ,a=κa~.\widetilde{a}:=(I_n-L)\xi,\qquad a=\kappa\widetilde{a}.

Indeed, In−LI_n-L is strictly lower triangular, so ai=−κ∑j<iLijξja_i=-\kappa\sum_{j<i}L_{ij}\xi_j depends only on past residuals. The actual point is xi=(aˉi,bi)x_i=(\bar{a}_i,b_i).

The posterior error at the test point

For vectors a,ξ∈Rna,\xi\in\mathbb{R}^n, define

Γ:=aTGξ,Q:=aTGa,θ:=k[n]∘(b0)TGa,ψ:=k[n]∘(b0)TGξ.\Gamma:=a^\mathsf{T}G\xi,\quad Q:=a^\mathsf{T}Ga,\quad\theta:=k^\circ_{[n]}(b_0)^\mathsf{T}Ga,\quad\psi:=k^\circ_{[n]}(b_0)^\mathsf{T}G\xi.

Lemma C.1. Suppose that a∈[−1,1]na\in[-1,1]^n, xi=(ai,bi)x_i=(a_i,b_i), and yn=Rξ−Bay_n=R\xi-Ba. Then

μn(x0)−fB(x0)=(1−θ)(B+RΓ)1+Q+Rψ,\mu_n(x_0)-f_B(x_0)=\frac{(1-\theta)(B+R\Gamma)}{1+Q}+R\psi,
σn2(x0)=(1−θ)21+Q+v[n](b0).\sigma_n^2(x_0)=\frac{(1-\theta)^2}{1+Q}+v_{[n]}(b_0).

Proof of Lemma C.1. Let h=k[n]∘(b0)h=k^\circ_{[n]}(b_0). The additive kernel gives Kn=Kn∘+aaTK_n=K_n^\circ+aa^\mathsf{T}, $k_n(x_0)=a+h, and k(x0,x0)=1+k∘(b0,b0)k(x_0,x_0)=1+k^\circ(b_0,b_0). Since G≻0G \succ0, we have 1+Q≥11+Q\ge1. Applying Lemma A.2, we obtain

A:=(λ2In+Kn)−1=G−Gaa⊤G1+Q.A := (\lambda^2 I_n+K_n)^{-1}=G-\frac{Gaa^\top G}{1+Q}.

Using this inverse, we obtain (a+h)⊤Aa=(Q+θ)/(1+Q)(a+h)^\top Aa=(Q+\theta)/(1+Q) and

(a+h)⊤Aξ=Γ+ψ−(Q+θ)Γ1+Q=(1−θ)Γ1+Q+ψ.(a+h)^\top A\xi=\Gamma+\psi-\frac{(Q+\theta)\Gamma}{1+Q}=\frac{(1-\theta)\Gamma}{1+Q}+\psi.

Substituting yn=Rξ−Bay_n=R\xi-Ba into (4) and subtracting fB(x0)=−Bf_B(x_0)=-B yields the claimed error. For the variance, we obtain

σn2(x0)=v[n](b0)+1−Q−2θ+(Q+θ)21+Q=v[n](b0)+(1−θ)21+Q.\sigma_n^2(x_0)=v_{[n]}(b_0)+1-Q-2\theta+\frac{(Q+\theta)^2}{1+Q}=v_{[n]}(b_0)+\frac{(1-\theta)^2}{1+Q}.

Cholesky identities and Gaussian bounds

Lemma C.2. For J⊆J′⊆[n]J\subseteq J'\subseteq[n] and b∈[0,2π]b\in[0,2\pi], we have 0≤vJ′(b)≤vJ(b)≤k∘(b,b)0\le v_{J'}(b)\le v_J(b)\le k^\circ(b,b). For each i∈[n]i\in[n],

Dii=λ2+v<i(bi)≥λ2,Gii=1λ2+v−i(bi).(15)D_{ii}=\lambda^2+v_{<i}(b_i)\ge\lambda^2,\qquad G_{ii}=\frac{1}{\lambda^2+v_{-i}(b_i)}. \tag*{(15)}

Consequently,

En=∑i=1n[1λ2+v−i(bi)−1λ2+v<i(bi)]=1λ2∑i=1n[v<i(bi)λ2+v<i(bi)−v−i(bi)λ2+v−i(bi)],(16)E_n=\sum_{i=1}^{n}\left[\frac{1}{\lambda^2+v_{-i}(b_i)}-\frac{1}{\lambda^2+v_{<i}(b_i)}\right]=\frac{1}{\lambda^2}\sum_{i=1}^{n}\left[\frac{v_{<i}(b_i)}{\lambda^2+v_{<i}(b_i)}-\frac{v_{-i}(b_i)}{\lambda^2+v_{-i}(b_i)}\right], \tag*{(16)}

with every summand nonnegative.

Proof of Lemma C.2. Completing the square, we obtain

vJ(b)=min⁡z∈R∣J∣[k∘(b,b)−2z⊤kJ∘(b)+z⊤(λ2I∣J∣+KJ∘)z].v_J(b)=\min_{z\in\mathbb{R}^{|J|}}\left[k^\circ(b,b)-2z^\top k_J^\circ(b)+z^\top(\lambda^2 I_{|J|}+K_J^\circ)z\right].

The expression is nonnegative by positive semidefiniteness of the Gram matrix on the points in JJ and bb. Extending zz by zero on J′∖JJ'\setminus J shows vJ′(b)≤vJ(b)v_{J'}(b)\le v_J(b). The choice z=0z=0 gives vJ(b)≤k∘(b,b)v_J(b)\le k^\circ(b,b).

The leading ii by ii principal submatrix of LDL⊤LDL^\top has determinant ∏j≤iDjj\prod_{j\le i}D_{jj} because LL is unit lower triangular. Taking the ratio of the leading determinants of orders ii and i−1i-1 gives DiiD_{ii}, with the empty determinant interpreted as one. Applying Lemma A.3 to that leading submatrix, we evaluate this ratio as λ2+v<i(bi)\lambda^2+v_{<i}(b_i). Applying the same lemma to the full matrix after moving index ii to the last position gives Gii=(λ2+v−i(bi))−1G_{ii}=(\lambda^2+v_{-i}(b_i))^{-1}. Substituting both identities into (13) gives the first sum in (C.2), whose summands are nonnegative since v−i(bi)≤v<i(bi)v_{-i}(b_i)\le v_{<i}(b_i). Rewriting λ2/(λ2+v)=1−v/(λ2+v)\lambda^2/(\lambda^2+v)=1-v/(\lambda^2+v) gives the second sum.

Define H:=D−1/2L−1H := D^{-1/2}L^{-1} and M:=H−D−1/2M := H-D^{-1/2}. For ξ∼N(0,In)\xi\sim N(0,I_n), write

u:=Mξ,W:=∥u∥22,Z:=∑i=1nuiDii−1/2ξi.u := M\xi,\quad W := \lVert u\rVert_2^2,\quad Z := \sum_{i=1}^{n}u_iD_{ii}^{-1/2}\xi_i.

Lemma C.3. The matrix MM is strictly lower triangular, so uiu_i depends only on ξ1,…,ξi−1\xi_1,\ldots,\xi_{i-1}. For the offset vector a=κ(In−L)ξa=\kappa(I_n-L)\xi,

Γ=κ(W+Z),Q=κ2W,E[W]=∥M∥F2=En.\Gamma=\kappa(W+Z),\quad Q=\kappa^2W,\quad\mathbb{E}[W]=\lVert M\rVert_F^2=E_n.

Proof of Lemma C.3. Since L−1L^{-1} is unit lower triangular, M=D−1/2(L−1−In)M=D^{-1/2}(L^{-1}-I_n) is strictly lower triangular. We have G=HTHG=H^{\mathsf T}H and

Ha=κu,Hξ=u+D−1/2ξ.Ha=\kappa u,\quad H\xi=u+D^{-1/2}\xi.

We pair HaHa with HξH\xi and with itself to obtain the identities for Γ\Gamma and QQ. Since E[ξξT]=In\mathbb{E}[\xi\xi^{\mathsf T}]=I_n, we have E[W]=∥M∥F2\mathbb{E}[W]=\lVert M\rVert_F^2. The strictly lower triangular part MM and the diagonal part D−1/2D^{-1/2} of HH are orthogonal under the Frobenius inner product. Therefore,

∥M∥F2=∥H∥F2−∑i=1nDii−1=Tr⁡(G)−∑i=1nDii−1=En.\lVert M\rVert_F^2=\lVert H\rVert_F^2-\sum_{i=1}^{n}D_{ii}^{-1}=\operatorname{Tr}(G)-\sum_{i=1}^{n}D_{ii}^{-1}=E_n.

□

Lemma C.4. For the offset vector before clipping, each a~i\tilde a_i, ψ\psi, and θ\theta is centered Gaussian, with

Var⁡(a~i)≤1λ2,Var⁡(ψ)≤1λ2,Var⁡(θ)≤4κ2λ2.(17)\operatorname{Var}(\tilde a_i)\le\frac{1}{\lambda^2},\quad\operatorname{Var}(\psi)\le\frac{1}{\lambda^2},\quad\operatorname{Var}(\theta)\le\frac{4\kappa^2}{\lambda^2}. \tag*{(17)}

Moreover,

∥MTM∥op≤4λ2,∥MTM∥F2≤4Enλ2,∑i=1nui2Dii≤Wλ2.(18)\lVert M^{\mathsf T}M\rVert_{\mathrm{op}}\le\frac{4}{\lambda^2},\quad\lVert M^{\mathsf T}M\rVert_F^2\le\frac{4E_n}{\lambda^2},\quad\sum_{i=1}^{n}\frac{u_i^2}{D_{ii}}\le\frac{W}{\lambda^2}. \tag*{(18)}

Proof of Lemma C.4. The three scalars in (C.3) are deterministic linear functions of ξ\xi. To bound the variance of a~i\tilde a_i, use (C.1) and the diagonal of LDLTLDL^{\mathsf T} to obtain

λ2Var⁡(a~i)=λ2∑j<iLij2≤∑j<iDjjLij2=k∘(bi,bi)−v<i(bi)≤1.\lambda^2\operatorname{Var}(\tilde a_i)=\lambda^2\sum_{j<i}L_{ij}^2\le\sum_{j<i}D_{jj}L_{ij}^2=k^\circ(b_i,b_i)-v_{<i}(b_i)\le1.

Since Kn∘⪰0K_n^\circ\succeq0, we have ∥H∥op2=∥G∥op≤λ−2\lVert H\rVert_{\mathrm{op}}^2=\lVert G\rVert_{\mathrm{op}}\le\lambda^{-2}. Combining this estimate with Dii≥λ2D_{ii}\ge\lambda^2 gives

∥M∥op≤∥H∥op+∥D−1/2∥op≤2/λ.\lVert M\rVert_{\mathrm{op}}\le\lVert H\rVert_{\mathrm{op}}+\lVert D^{-1/2}\rVert_{\mathrm{op}}\le2/\lambda.

Let h=k[n]∘(b0)h=k^\circ_{[n]}(b_0). Then ∥Hh∥22=hTGh=k∘(b0,b0)−v[n](b0)≤1\lVert Hh\rVert_2^2=h^{\mathsf T}Gh=k^\circ(b_0,b_0)-v_{[n]}(b_0)\le1. Using G=HTHG=H^{\mathsf T}H and Ha=κMξHa=\kappa M\xi, we obtain

Var⁡(ψ)=∥HTHh∥22≤λ−2,Var⁡(θ)=κ2∥MTHh∥22≤4κ2λ−2.\operatorname{Var}(\psi)=\lVert H^{\mathsf T}Hh\rVert_2^2\le\lambda^{-2},\quad\operatorname{Var}(\theta)=\kappa^2\lVert M^{\mathsf T}Hh\rVert_2^2\le4\kappa^2\lambda^{-2}.

Finally, since MTMM^{\mathsf T}M is positive semidefinite,

∥MTM∥F2≤∥MTM∥opTr⁡(MTM)≤4Enλ2,\lVert M^{\mathsf T}M\rVert_F^2\le\lVert M^{\mathsf T}M\rVert_{\mathrm{op}}\operatorname{Tr}(M^{\mathsf T}M)\le\frac{4E_n}{\lambda^2},

where the last inequality uses Lemma C.3 and the operator bound for MM. The last bound in (C.4) follows from Dii≥λ2D_{ii} \ge\lambda^2 and W=∑iui2W = \sum_i u_i^2.

A probability bound for the normalized error

Lemma C.5. Fix δ0∈(0,1/5)\delta_0 \in(0,1/5) and suppose that

En≥E(λ,δ0,n):=max⁡{6272λ2log⁡2δ0,2λ2log⁡2nδ0}.(19)E_n \ge E(\lambda,\delta_0,n) := \max\left\{\frac{6272}{\lambda^2}\log\frac{2}{\delta_0},\frac{2}{\lambda^2}\log\frac{2n}{\delta_0}\right\}. \tag*{(19)}

Under the design (14), with probability at least 1−5δ01-5\delta_0,

∣fB(x0)−μn(x0)∣σn(x0)≥4B213+REn9408,σn2(x0)≥221.(20)\frac{|f_B(x_0)-\mu_n(x_0)|}{\sigma_n(x_0)} \ge\frac{4B}{21\sqrt{3}}+R\sqrt{\frac{E_n}{9408}}, \qquad\sigma_n^2(x_0)\ge\frac{2}{21}. \tag*{(20)}

Proof of Lemma C.5. Set t=log⁡(2/δ0)t=\log(2/\delta_0). The quadratic form W=ξTMTMξW=\xi^\mathsf{T}M^\mathsf{T}M\xi has mean EnE_n. Applying Lemma A.1 to MTMM^\mathsf{T}M, we obtain, with probability at least 1−2e−t=1−δ01-2e^{-t}=1-\delta_0,

∣W−En∣≤2∥MTM∥Ft+2∥MTM∥optt≤4λEnt+8tλ2≤5En8.|W-E_n| \le2\|M^\mathsf{T}M\|_F\sqrt{t}+2\|M^\mathsf{T}M\|_{\mathrm{opt}}t \le\frac{4}{\lambda}\sqrt{E_nt}+\frac{8t}{\lambda^2}\le\frac{5E_n}{8}.

Here the norm bounds are from Lemma C.4, and En≥64t/λ2E_n\ge64t/\lambda^2 makes the last two terms at most En/2E_n/2 and En/8E_n/8. Denote the resulting event 3En/8≤W≤13En/83E_n/8\le W\le13E_n/8 by AWA_W.

For the martingale term, let Gi=σ(ξ1,…,ξi)\mathcal{G}_i=\sigma(\xi_1,\ldots,\xi_i) and νi=uiDii−1/2\nu_i=u_iD_{ii}^{-1/2}. The coefficient νi\nu_i is Gi−1\mathcal{G}_{i-1}-measurable by Lemma C.3, and ξi\xi_i is standard Gaussian independent of Gi−1\mathcal{G}_{i-1}. For each sign r∈{−1,1}r\in\{-1,1\}, let

Xi(r):=exp⁡(rλ22∑j≤iνjξj−λ48∑j≤iνj2),X0(r)=1.X_i^{(r)}:=\exp\left(\frac{r\lambda^2}{2}\sum_{j\le i}\nu_j\xi_j-\frac{\lambda^4}{8}\sum_{j\le i}\nu_j^2\right),\qquad X_0^{(r)}=1.

Conditional on Gi−1\mathcal{G}_{i-1}, the Gaussian moment generating function gives E[exp⁡(rλ2νiξi/2−λ4νi2/8)∣Gi−1]=1\mathbb{E}[\exp(r\lambda^2\nu_i\xi_i/2-\lambda^4\nu_i^2/8)\mid\mathcal{G}_{i-1}]=1. By nonnegativity and induction, each Xi(r)X_i^{(r)} is integrable with mean one and E[Xi(r)∣Gi−1]=Xi−1(r)\mathbb{E}[X_i^{(r)}\mid\mathcal{G}_{i-1}]=X_{i-1}^{(r)}. On AW∩{∣Z∣>W/2}A_W\cap\{|Z|>W/2\}, the sign rr of ZZ satisfies

log⁡Xn(r)≥λ2W4−λ4W8λ2=λ2W8≥3λ2En64,\log X_n^{(r)}\ge\frac{\lambda^2W}{4}-\frac{\lambda^4W}{8\lambda^2}=\frac{\lambda^2W}{8}\ge\frac{3\lambda^2E_n}{64},

where we used ∑iνi2≤W/λ2\sum_i\nu_i^2\le W/\lambda^2 from (C.4). Applying Markov’s inequality for both signs gives

P(AW∩{∣Z∣>W/2})≤2e−3λ2En/64≤δ0\mathbb{P}\left(A_W\cap\{|Z|>W/2\}\right)\le2e^{-3\lambda^2E_n/64}\le\delta_0

by (C.5).

Using the Gaussian variance bounds in (C.3) and κ2=En−1\kappa^2=E_n^{-1}, we obtain

P(∣θ∣>1/2)≤2e−λ2En/32≤δ0,\mathbb{P}(|\theta|>1/2)\le2e^{-\lambda^2E_n/32}\le\delta_0,
P(∣ψ∣>λ−12t)≤2e−t=δ0,\mathbb{P}(|\psi|>\lambda^{-1}\sqrt{2t})\le2e^{-t}=\delta_0,
P(max⁡i∈[n]∣ai∣>1)≤2ne−λ2En/2≤δ0.\mathbb{P}\left(\max_{i\in[n]}|a_i|>1\right)\le2ne^{-\lambda^2E_n/2}\le\delta_0.

The last line uses Var⁡(ai)≤1/(λ2En)\operatorname{Var}(a_i) \le1/(\lambda^2 E_n) and a union bound. The first and last lines use the two terms of (C.5), respectively.

Together these bounds give an event of probability at least 1−5δ01-5\delta_0 on which AWA_W holds, ∣Z∣≤W/2|Z| \le W/2, ∣θ∣≤1/2|\theta| \le1/2, ∣ψ∣≤λ−12t|\psi| \le\lambda^{-1}\sqrt{2t}, and no offset is clipped. On this event the raw response vector is yn=Rξ−Bay_n = R\xi- Ba, so Lemma C.1 applies to the realized design. By Lemma C.3, we have

1+Q=1+WEn∈[11/8,21/8],Γ≥κW/2≥3En/16.1+Q=1+\frac{W}{E_n}\in[11/8,21/8],\qquad\Gamma\ge\kappa W/2\ge3\sqrt{E_n}/16.

The threshold gives ∣ψ∣≤λ−12t≤En/56|\psi|\le\lambda^{-1}\sqrt{2t}\le\sqrt{E_n}/56. Since 1−θ∈[1/2,3/2]1-\theta\in[1/2,3/2], the signed posterior error satisfies

μn(x0)−fB(x0)≥421(B+3REn16)−R∣ψ∣≥4B21+REn56.\mu_n(x_0)-f_B(x_0)\ge\frac{4}{21}\left(B+\frac{3R\sqrt{E_n}}{16}\right)-R|\psi|\ge\frac{4B}{21}+\frac{R\sqrt{E_n}}{56}.

Using 0≤v[n](b0)≤10\le v_{[n]}(b_0)\le1 in the variance identity, we obtain

221≤σn2(x0)≤(3/2)211/8+1=2911<3.\frac{2}{21}\le\sigma_n^2(x_0)\le\frac{(3/2)^2}{11/8}+1=\frac{29}{11}<3.

Dividing the error bound by σn(x0)\sigma_n(x_0) and using 562⋅3=940856^2\cdot3=9408 proves (C.6).

Spectral estimates for the cyclic design

Lemma C.6. Let k∘=ks∘k^\circ=k_s^\circ with s>1/2s>1/2, and let q≥2q\ge2 and p≥3p\ge3 be integers with n≥pqn\ge pq. Suppose that

b(r−1)q+j=2π(j−1)q,r∈[p], j∈[q],b_{(r-1)q+j}=\frac{2\pi(j-1)}{q},\qquad r\in[p],\ j\in[q],

with arbitrary bi∈[0,2π]b_i\in[0,2\pi] for pq<i≤npq<i\le n. Let ω0,…,ωq−1\omega_0,\ldots,\omega_{q-1} be the eigenvalues of Kq∘:=[ks∘(bj,bj′)]j,j′∈[q]K_q^\circ:=\left[k_s^\circ(b_j,b_{j'})\right]_{j,j'\in[q]}, and let Hp−1:=∑r=1p−11/rH_{p-1}:=\sum_{r=1}^{p-1}1/r. Then

λ2En≥Hp−1−116∣{l:ωl≥λ2}∣,∣{l:ωl≥λ2}∣≥min⁡{q−1,⌊(q2ζ(2s)λ2)1/(2s)⌋}.\lambda^2E_n\ge\frac{H_{p-1}-1}{16}\left|\{l:\omega_l\ge\lambda^2\}\right|,\qquad\left|\{l:\omega_l\ge\lambda^2\}\right|\ge\min\left\{q-1,\left\lfloor\left(\frac{q}{2\zeta(2s)\lambda^2}\right)^{1/(2s)}\right\rfloor\right\}.

Proof of Lemma C.6. Since [Kq∘]j,j′=χ(2π(j−j′)/q)\left[K_q^\circ\right]_{j,j'}=\chi(2\pi(j-j')/q), the matrix Kq∘K_q^\circ is circulant. Let JJ consist of rr complete passes. Ordering the indices of JJ by pass gives KJ∘=1r1rT⊗Kq∘K_J^\circ=\mathbf{1}_r\mathbf{1}_r^{\mathsf T}\otimes K_q^\circ and kJ∘(bj)=1r⊗Kq∘ejk_J^\circ(b_j)=\mathbf{1}_r\otimes K_q^\circ e_j, where eje_j is the jj-th standard basis vector. Since (1r1rT)1r=r1r(\mathbf{1}_r\mathbf{1}_r^{\mathsf T})\mathbf{1}_r=r\mathbf{1}_r, we have

(λ2Irq+KJ∘)−1kJ∘(bj)=1r⊗(λ2Iq+rKq∘)−1Kq∘ej.(\lambda^2 I_{rq}+K_J^\circ)^{-1}k_J^\circ(b_j)=\mathbf{1}_r\otimes(\lambda^2 I_q+rK_q^\circ)^{-1}K_q^\circ e_j.

Using this identity in the posterior variance and simplifying gives

vJ(bj)=[λ2Kq∘(λ2Iq+rKq∘)−1]jj=λ2q∑l=0q−1ωlλ2+rωl=:λ2βr.(21)v_J(b_j)=\left[\lambda^2K_q^\circ(\lambda^2I_q+rK_q^\circ)^{-1}\right]_{jj}=\frac{\lambda^2}{q}\sum_{l=0}^{q-1}\frac{\omega_l}{\lambda^2+r\omega_l}=:\lambda^2\beta_r. \tag*{(21)}

The second equality uses the constant diagonal of the circulant matrix in brackets. Since each ωl≥0\omega_l\ge0, βr\beta_r is nonincreasing in rr, with 0≤βr≤β1≤10\le\beta_r\le\beta_1\le1.

For i=(r−1)q+ji=(r-1)q+j with r≤p−1r\le p-1, the observations before ii are contained in the first rr passes, and those with indices other than ii include all p−1p-1 passes other than pass rr. Monotonicity from Lemma C.2 and (C.7) therefore give v≺i(bi)≥λ2βrv_{\prec i}(b_i) \ge\lambda^2\beta_r and v−i(bi)≤λ2βp−1v_{-i}(b_i) \le\lambda^2\beta_{p-1}. The ii-th summand of λ2En\lambda^2 E_n in (C.2) is thus at least

βr1+βr−βp−11+βp−1=βr−βp−1(1+βr)(1+βp−1)≥βr−βp−14.\frac{\beta_r}{1+\beta_r}-\frac{\beta_{p-1}}{1+\beta_{p-1}}=\frac{\beta_r-\beta_{p-1}}{(1+\beta_r)(1+\beta_{p-1})}\ge\frac{\beta_r-\beta_{p-1}}{4}.

All other summands are nonnegative by Lemma C.2. Summing over the first p−1p-1 passes and substituting the eigenvalue formula for βr\beta_r gives

λ2En≥q4∑r=1p−1(βr−βp−1)=14∑l=0q−1∑r=1p−1(p−1−r)ωl2(λ2+rωl)(λ2+(p−1)ωl).\lambda^2 E_n\ge\frac{q}{4}\sum_{r=1}^{p-1}(\beta_r-\beta_{p-1})=\frac{1}{4}\sum_{l=0}^{q-1}\sum_{r=1}^{p-1}\frac{(p-1-r)\omega_l^2}{(\lambda^2+r\omega_l)(\lambda^2+(p-1)\omega_l)}.

For ωl≥λ2\omega_l\ge\lambda^2, the denominator is at most 4r(p−1)ωl24r(p-1)\omega_l^2. Keeping those terms, we obtain

λ2En≥116∑l: ωl≥λ2∑r=1p−1(1r−1p−1)=Hp−1−116∣{l:ωl≥λ2}∣.\lambda^2 E_n\ge\frac{1}{16}\sum_{l:\,\omega_l\ge\lambda^2}\sum_{r=1}^{p-1}\left(\frac{1}{r}-\frac{1}{p-1}\right)=\frac{H_{p-1}-1}{16}\left|\left\{l:\omega_l\ge\lambda^2\right\}\right|.

To count the eigenvalues above the threshold, we take the discrete Fourier transform of χ\chi on the grid. Its absolutely convergent Fourier series has coefficient α∣m∣/2\alpha_{|m|}/2 at each frequency m≠0m\ne0, and ∑j=0q−1e2πij(m−l)/q\sum_{j=0}^{q-1}e^{2\pi ij(m-l)/q} equals qq when m≡l(modq)m\equiv l\pmod q and zero otherwise. Hence

ωl=∑j=0q−1χ(2πj/q)e−2πijl/q=q2∑m≠0m≡l(mod⁡ q)α∣m∣.\omega_l=\sum_{j=0}^{q-1}\chi(2\pi j/q)e^{-2\pi ijl/q}=\frac{q}{2}\sum_{\substack{m\ne0\\m\equiv l\;(\operatorname{mod}\ q)}}\alpha_{|m|}.

Keeping m=lm=l for 1≤l≤q−11\le l\le q-1 gives ωl≥q/(2ζ(2s)l2s)\omega_l\ge q/(2\zeta(2s)l^{2s}). Thus every l∈{1,…,q−1}l\in\{1,\ldots,q-1\} with l≤(q/(2ζ(2s)λ2))1/(2s)l\le(q/(2\zeta(2s)\lambda^2))^{1/(2s)} contributes to the count.

Lemma C.7. Consider the kernel (10) with s>1/2s>1/2. For all n≥1n\ge1 and λ>0\lambda>0, let ln:=⌈(n/(ζ(2s)λ2))1/(2s)⌉l_n:=\left\lceil(n/(\zeta(2s)\lambda^2))^{1/(2s)}\right\rceil and Cs:=2(2s+log⁡2+1/(2s−1))C_s:=2(2s+\log2+1/(2s-1)). Then

γn≤log⁡(1+nλ2)+Csln\gamma_n\le\log\left(1+\frac{n}{\lambda^2}\right)+C_sl_n
≤log⁡(1+nλ2)+Cs{(nλ2)1/(2s)+1}.\le\log\left(1+\frac{n}{\lambda^2}\right)+C_s\left\{\left(\frac{n}{\lambda^2}\right)^{1/(2s)}+1\right\}.

For every deterministic sequence b1,…,bn∈[0,2π]b_1,\ldots,b_n\in[0,2\pi], we also have

γn≥log⁡det⁡(In+λ−2Kn∘)≥λ2En.\gamma_n\ge\log\det(I_n+\lambda^{-2}K_n^\circ)\ge\lambda^2E_n.

Proof of Lemma C.7. For arbitrary xi=(ai,bi)∈Xx_i=(a_i,b_i)\in\mathcal{X}, write a=(a1,…,an)⊤a=(a_1,\ldots,a_n)^\top, so Kn=Kn∘+aa⊤K_n=K_n^\circ+aa^\top. Lemma A.2 and (In+λ−2Kn∘)−1⪯In(I_n+\lambda^{-2}K_n^\circ)^{-1}\preceq I_n give

det⁡(In+λ−2Kn)=det⁡(In+λ−2Kn∘){1+λ−2a⊤(In+λ−2Kn∘)−1a}≤det⁡(In+λ−2Kn∘)(1+nλ2),\begin{aligned} \det(I_n+\lambda^{-2}K_n)=\det(I_n+\lambda^{-2}K_n^\circ)\left\{1+\lambda^{-2}a^\top(I_n+\lambda^{-2}K_n^\circ)^{-1}a\right\} \\ &\le\det(I_n+\lambda^{-2}K_n^\circ)\left(1+\frac{n}{\lambda^2}\right), \end{aligned}

where we used ∥a∥22≤n\lVert a\rVert_2^2\le n. Let Ψm∈Rn×2m\Psi_m \in\mathbb{R}^{n \times2m} have columns (αlcos⁡(lbi))i=1n\left(\sqrt{\alpha_l}\cos(lb_i)\right)_{i=1}^{n} and (αlsin⁡(lbi))i=1n\left(\sqrt{\alpha_l}\sin(lb_i)\right)_{i=1}^{n} for l∈[m]l \in[m]. Applying the two parts of Lemma A.4, we obtain

log⁡det⁡(In+λ−2ΨmΨm⊤)=log⁡det⁡(I2m+λ−2Ψm⊤Ψm)≤2∑l=1mlog⁡(1+nαl/λ2).\log\det(I_n+\lambda^{-2}\Psi_m\Psi_m^\top)=\log\det(I_{2m}+\lambda^{-2}\Psi_m^\top\Psi_m)\leq2\sum_{l=1}^{m}\log(1+n\alpha_l/\lambda^2).

Here the two diagonal entries indexed by ll are at most 1+nαl/λ21+n\alpha_l/\lambda^2. The Fourier series converges absolutely, so ΨmΨm⊤→Kn∘\Psi_m\Psi_m^\top\to K_n^\circ entrywise. Passing to the limit gives

log⁡det⁡(In+λ−2Kn∘)≤2∑l=1∞log⁡(1+nαl/λ2).(22)\log\det(I_n+\lambda^{-2}K_n^\circ)\leq2\sum_{l=1}^{\infty}\log(1+n\alpha_l/\lambda^2). \tag*{(22)}

Since nαl/λ2≤(ln/l)2sn\alpha_l/\lambda^2\leq(l_n/l)^{2s}, we compare this series with the integral of the decreasing function t↦log⁡(1+(ln/t)2s)t\mapsto\log(1+(l_n/t)^{2s}) over (0,∞)(0,\infty). Rescaling by lnl_n gives

∑l=1∞log⁡(1+nαl/λ2)≤ln∫0∞log⁡(1+u−2s) du≤ln(∫01(log⁡2−2slog⁡u) du+∫1∞u−2s du)=ln(2s+log⁡2+12s−1).\begin{aligned} \sum_{l=1}^{\infty}\log(1+n\alpha_l/\lambda^2)\leq l_n\int_0^\infty\log(1+u^{-2s})\,du \\ &\leq l_n\left(\int_0^1(\log2-2s\log u)\,du+\int_1^\infty u^{-2s}\,du\right) \\ &= l_n\left(2s+\log2+\frac{1}{2s-1}\right). \end{aligned}

Combining (C.8) with the determinant estimate for the linear coordinate and taking the supremum over x1,…,xnx_1,\ldots,x_n gives the first upper bound. The second follows from ln≤(n/λ2)1/(2s)+1l_n\leq(n/\lambda^2)^{1/(2s)}+1.

For the lower bound, take xi=(0,bi)x_i=(0,b_i) so that Kn=Kn∘K_n=K_n^\circ. By (6), the factorization (12), and (C.1), we have

γn≥log⁡det⁡(In+λ−2Kn∘)=∑i=1nlog⁡Diiλ2=∑i=1nlog⁡(1+v<i(bi)λ2)≥∑i=1nv<i(bi)λ2+v<i(bi)≥λ2En.\begin{aligned} \gamma_n\geq\log\det(I_n+\lambda^{-2}K_n^\circ)=\sum_{i=1}^{n}\log\frac{D_{ii}}{\lambda^2} \\ &=\sum_{i=1}^{n}\log\left(1+\frac{v_{<i}(b_i)}{\lambda^2}\right)\geq\sum_{i=1}^{n}\frac{v_{<i}(b_i)}{\lambda^2+v_{<i}(b_i)}\geq\lambda^2E_n. \end{aligned}

We used log⁡(1+u)≥u/(1+u)\log(1+u)\geq u/(1+u) for u≥0u\geq0 and the representation (C.2) with nonnegative subtracted terms.

Proof of the lower-bound theorem

Proof of Theorem 4.2. We first verify that the construction is an admissible instance. The kernel sections at (1,0)(1,0) and (−1,0)(-1,0) differ by the function (a,b)↦2a(a,b)\mapsto2a, and their squared distance in Hk\mathcal{H}_k is 2+2−2⋅0=42+2-2\cdot0=4. Thus,

fB=−B2{k(⋅,(1,0))−k(⋅,(−1,0))},∥fB∥Hk=B.f_B=-\frac{B}{2}\{k(\cdot,(1,0))-k(\cdot,(-1,0))\},\qquad\|f_B\|_{\mathcal{H}_k}=B.

The Gaussian noise is RR-sub-Gaussian, and the residual yj+Baˉj=ϵjy_j+B\bar a_j=\epsilon_j is available after round jj. Hence the rule (14) selects xix_i from past observations, and clipping ensures xi∈Xx_i\in\mathcal{X}.

The scaling κ\kappa is well defined for every n≥40n\geq40. Indeed, the second pass repeats b1b_1, so Lemma C.2 gives

v−1(b1)≤v{q+1}(b1)=1−1λ2+1<1=v<1(b1).v_{-1}(b_1) \le v_{\{q+1\}}(b_1) = 1-\frac{1}{\lambda^2+1} < 1 = v_{<1}(b_1).

The first summand of EnE_n in (C.2) is therefore positive, and all other summands are nonnegative.

We now lower bound EnE_n. Apply Lemma C.6 with p=20p=20 and q=⌊n/20⌋q=\lfloor n/20\rfloor. Since H19>7/2H_{19}>7/2,

λ2En≥532min⁡{q−1,⌊Tq⌋},Tq:=(q2ζ(2s)λ2)1/(2s).\lambda^2 E_n \ge\frac{5}{32}\min\{q-1,\lfloor T_q\rfloor\}, \qquad T_q:=\left(\frac{q}{2\zeta(2s)\lambda^2}\right)^{1/(2s)}.

For fixed s>1/2s>1/2 and λ>0\lambda>0, we have Tq→∞T_q\to\infty and Tq/q→0T_q/q\to0. Choose an integer n1=n1(s,λ)≥max⁡{40,λ2}n_1=n_1(s,\lambda)\ge\max\{40,\lambda^2\} such that 2≤Tq≤q2\le T_q\le q for all n≥n1n\ge n_1. Then ⌊Tq⌋≥Tq/2\lfloor T_q\rfloor\ge T_q/2 and q−1≥q/2≥Tq/2q-1\ge q/2\ge T_q/2. Using q≥n/40q\ge n/40, we obtain

En≥564λ2(n80ζ(2s)λ2)1/(2s)=cˉsλ2(nλ2)1/(2s),cˉs:=564{80ζ(2s)}−1/(2s).(23)E_n\ge\frac{5}{64\lambda^2}\left(\frac{n}{80\zeta(2s)\lambda^2}\right)^{1/(2s)} =\frac{\bar c_s}{\lambda^2}\left(\frac{n}{\lambda^2}\right)^{1/(2s)},\qquad\bar c_s:=\frac{5}{64}\{80\zeta(2s)\}^{-1/(2s)}. \tag*{(23)}

The right-hand side grows polynomially in nn, whereas E(λ,1/11,n)E(\lambda,1/11,n) in (C.5) grows logarithmically. We may therefore increase n1n_1 to an integer n2=n2(s,λ)n_2=n_2(s,\lambda) such that En≥E(λ,1/11,n)E_n\ge E(\lambda,1/11,n) for every n≥n2n\ge n_2. Applying Lemma C.5 with δ0=1/11\delta_0=1/11, we obtain, for each such nn, with probability at least 6/116/11,

∣fB(x0)−μn(x0)∣σn(x0)≥4B213+REn9408≥cs[B+Rλ(nλ2)1/(4s)],(24)\frac{|f_B(x_0)-\mu_n(x_0)|}{\sigma_n(x_0)} \ge\frac{4B}{21\sqrt{3}}+R\sqrt{\frac{E_n}{9408}} \ge c_s\left[B+\frac{R}{\lambda}\left(\frac{n}{\lambda^2}\right)^{1/(4s)}\right], \tag*{(24)}

where cs:=min⁡{4/(213),cˉs/9408}>0c_s:=\min\{4/(21\sqrt{3}),\sqrt{\bar c_s/9408}\}>0. The same event satisfies σn2(x0)≥2/21\sigma_n^2(x_0)\ge2/21.

To express this bound in terms of information gain, let CsC_s be the constant in Lemma C.7. There is an integer n3=n3(s,λ)n_3=n_3(s,\lambda) such that, for all n≥n3n\ge n_3, (n/λ2)1/(2s)≥max⁡{1,log⁡(1+n/λ2)}(n/\lambda^2)^{1/(2s)}\ge\max\{1,\log(1+n/\lambda^2)\}. The upper bound in that lemma then gives

γn≤(1+2Cs)(nλ2)1/(2s).(25)\gamma_n\le(1+2C_s)\left(\frac{n}{\lambda^2}\right)^{1/(2s)}. \tag*{(25)}

Its lower bound and (C.9) show that, for n≥n0:=max⁡{n2,n3}n\ge n_0:=\max\{n_2,n_3\},

cˉs(nλ2)1/(2s)≤γn≤(1+2Cs)(nλ2)1/(2s).(26)\bar c_s\left(\frac{n}{\lambda^2}\right)^{1/(2s)} \le\gamma_n\le(1+2C_s)\left(\frac{n}{\lambda^2}\right)^{1/(2s)}. \tag*{(26)}

In particular, n0≥λ2n_0\ge\lambda^2, and both comparison constants depend only on ss. Set cs′:=cs/1+2Csc'_s:=c_s/\sqrt{1+2C_s}. Combining (C.10) and (C.11), on the same event, we have

∣fB(x0)−μn(x0)∣σn(x0)≥cs[B+Rλ(nλ2)1/(4s)]≥cs′(B+Rλγn).\frac{|f_B(x_0)-\mu_n(x_0)|}{\sigma_n(x_0)} \ge c_s\left[B+\frac{R}{\lambda}\left(\frac{n}{\lambda^2}\right)^{1/(4s)}\right] \ge c'_s\left(B+\frac{R}{\lambda}\sqrt{\gamma_n}\right).

Fix δ∈(0,1/2]\delta\in(0,1/2] and let ρn(δ)\rho_n(\delta) be a deterministic width that gives coverage at least 1−δ1-\delta for this instance. If ρn(δ)<cs′(B+(R/λ)γn)\rho_n(\delta)<c'_s(B+(R/\lambda)\sqrt{\gamma_n}), then coverage fails at x0x_0 throughout the event just constructed, whose probability is at least 6/11>δ6/11>\delta. This contradiction proves the claimed width bound.

For a data-dependent width with coverage at least 1−δ1-\delta on this instance, the coverage event intersects our lower-bound event with probability at least 6/11−δ6/11-\delta. On that intersection the width is at least cs′(B+(R/λ)γn)c'_s(B+(R/\lambda)\sqrt{\gamma_n}), which gives the claim used in § 5.

Proof of the Minimax Characterization

The dependence on the confidence level follows from an elementary Gaussian tail bound.

Lemma D.1. Let g∼N(0,1)g\sim\mathcal{N}(0,1). For every τ≥0\tau\ge0,

P(∣g∣>τ)≥12e−τ2.\mathbb{P}(|g|>\tau)\ge\frac{1}{2}e^{-\tau^2}.

Proof of Lemma D.1. Let g′g' be an independent copy of gg. Since [−τ,τ]2[-\tau,\tau]^2 is contained in the disk of radius 2τ\sqrt{2}\tau,

P(∣g∣≤τ)2=P(∣g∣≤τ, ∣g′∣≤τ)≤P(g2+g′2≤2τ2)=1−e−τ2.\mathbb{P}(|g|\le\tau)^2=\mathbb{P}(|g|\le\tau,\ |g'|\le\tau)\le\mathbb{P}(g^2+g'^2\le2\tau^2)=1-e^{-\tau^2}.

Here g2+g′2g^2+g'^2 has the exponential distribution with mean 2. Taking the complement and using 1−u≤1−u/2\sqrt{1-u}\le1-u/2 for u∈[0,1]u\in[0,1], we obtain

P(∣g∣>τ)≥1−1−e−τ2≥12e−τ2.\mathbb{P}(|g|>\tau)\ge1-\sqrt{1-e^{-\tau^2}}\ge\frac{1}{2}e^{-\tau^2}.

:::

Proof of Corollary 4.3. Fix n≥n0(s,λ)n\ge n_0(s,\lambda), B,R>0B,R>0, and δ∈(0,1/4]\delta\in(0,1/4]. Call a deterministic width ρ≥0\rho\ge0 valid if the supremum of failure probabilities in (8) is at most δ\delta. Theorem 3.3 supplies such a width and gives

ρn∗(δ)≤B+Rλ2log⁡1δ+γn≤2(B+Rλγn+log⁡1δ).\rho_n^*(\delta)\le B+\frac{R}{\lambda}\sqrt{2\log\frac{1}{\delta}+\gamma_n}\le\sqrt{2}\left(B+\frac{R}{\lambda}\sqrt{\gamma_n+\log\frac{1}{\delta}}\right).

Every valid width must cover the hard instance of Theorem 4.2. Since δ≤1/4<6/11\delta\le1/4<6/11, its constant-probability lower bound forces every such width to satisfy ρ≥cs′[B+(R/λ)γn]\rho\ge c'_s[B+(R/\lambda)\sqrt{\gamma_n}]. Taking the infimum over valid widths, we obtain

ρn∗(δ)≥cs′(B+Rλγn).\rho_n^*(\delta)\ge c'_s\left(B+\frac{R}{\lambda}\sqrt{\gamma_n}\right).

To obtain the confidence-level term, consider the deterministic design xi=x‡:=(0,0)x_i=x_{\ddagger}:=(0,0) for all i∈[n]i\in[n], with f≡0f\equiv0 and i.i.d. noise ϵi∼N(0,R2)\epsilon_i\sim\mathcal{N}(0,R^2). This is an instance in Pn(B,R)\mathcal{P}_n(B,R). Since k(x‡,x‡)=1k(x_{\ddagger},x_{\ddagger})=1, its kernel matrix and test vector are Kn=1n1nTK_n=\mathbf{1}_n\mathbf{1}_n^{\mathsf{T}} and kn(x‡)=1nk_n(x_{\ddagger})=\mathbf{1}_n. The identity (λ2In+Kn)1n=(λ2+n)1n(\lambda^2 I_n+K_n)\mathbf{1}_n=(\lambda^2+n)\mathbf{1}_n and (4) yield

μn(x‡)=∑i=1nϵiλ2+n,σn2(x‡)=λ2λ2+n.\mu_n(x_{\ddagger})=\frac{\sum_{i=1}^{n}\epsilon_i}{\lambda^2+n},\qquad\sigma_n^2(x_{\ddagger})=\frac{\lambda^2}{\lambda^2+n}.

Consequently,

f(x†)−μn(x†)σn(x†)=−∑i=1nϵiλλ2+n∼N(0,ςn2),ςn2:=R2nλ2(λ2+n)≥R22λ2.\frac{f(x_{\dagger})-\mu_n(x_{\dagger})}{\sigma_n(x_{\dagger})}=-\frac{\sum_{i=1}^{n}\epsilon_i}{\lambda\sqrt{\lambda^2+n}}\sim\mathcal{N}(0,\varsigma_n^2),\quad\varsigma_n^2:=\frac{R^2n}{\lambda^2(\lambda^2+n)}\ge\frac{R^2}{2\lambda^2}.

where n≥n0≥λ2n\ge n_0\ge\lambda^2. A valid width has failure probability at most δ\delta at x†x_{\dagger}. Applying Lemma D.1, we therefore find

δ≥P(∣g∣>ρςn)≥12exp⁡(−ρ2ςn2),g∼N(0,1).\delta\ge\mathbb{P}\left(|g|>\frac{\rho}{\varsigma_n}\right)\ge\frac{1}{2}\exp\left(-\frac{\rho^2}{\varsigma_n^2}\right),\quad g\sim\mathcal{N}(0,1).

Since δ≤1/4\delta\le1/4, we have log⁡(1/(2δ))≥12log⁡(1/δ)\log(1/(2\delta))\ge\frac{1}{2}\log(1/\delta), and hence

ρ2≥ςn2log⁡12δ≥R24λ2log⁡1δ.\rho^2\ge\varsigma_n^2\log\frac{1}{2\delta}\ge\frac{R^2}{4\lambda^2}\log\frac{1}{\delta}.

This holds for every valid ρ\rho, so ρn∗(δ)≥(R/(2λ))log⁡(1/δ)\rho_n^*(\delta)\ge(R/(2\lambda))\sqrt{\log(1/\delta)}.

Set cs:=12min⁡{cs′,1/2}c_s:=\frac{1}{2}\min\{c_s',1/2\}. By taking the average of the two lower bounds, we obtain

ρn∗(δ)≥12[cs′(B+Rλγn)+R2λlog⁡1δ]≥cs[B+Rλ(γn+log⁡1δ)]≥cs(B+Rλγn+log⁡1δ).\begin{aligned} \rho_n^*(\delta)\ge\frac{1}{2}\left[c_s'\left(B+\frac{R}{\lambda}\sqrt{\gamma_n}\right)+\frac{R}{2\lambda}\sqrt{\log\frac{1}{\delta}}\right] \\ &\ge c_s\left[B+\frac{R}{\lambda}\left(\sqrt{\gamma_n}+\sqrt{\log\frac{1}{\delta}}\right)\right] \\ &\ge c_s\left(B+\frac{R}{\lambda}\sqrt{\gamma_n+\log\frac{1}{\delta}}\right). \end{aligned}

Together with the upper bound, this proves the claimed comparison, with constants depending only on ss.

References

  1. [1]Yasin Abbasi-Yadkori. Online Learning for Linearly Parametrized Control Problems. PhD thesis, University of Alberta, 2013.
  2. [2]Yasin Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. In Advances in Neural Information Processing Systems, volume 24, pages 2312–2320, 2011.
  3. [3]Arya Akhavan, Amitis Shidani, Alex Ayoub, and David Janz. Bernstein-type dimension-free concentration for self-normalised martingales. arXiv preprint arXiv:2507.20982, 2025.arxiv.org/abs/2507.20982
  4. [4]Xu Cai and Jonathan Scarlett. On lower bounds for standard and robust Gaussian process bandit optimization. In Proceedings of the 38th International Conference on Machine Learning, 2021.arxiv.org/abs/2008.08757
  5. [5]Romain Camilleri, Julian Katz-Samuels, and Kevin Jamieson. High-dimensional experimental design and kernel bandits. In Proceedings of the 38th International Conference on Machine Learning, 2021.arxiv.org/abs/2105.05806
  6. [6]Fan Chen, Jian Qian, Alexander Rakhlin, and Nikita Zhivotovskiy. Self-normalized martingales and uniform regret bounds for linear regression. arXiv preprint arXiv:2605.01628, 2026.arxiv.org/abs/2605.01628
  7. [7]Sayak Ray Chowdhury and Aditya Gopalan. On kernelized multi-armed bandits. In Proceedings of the 34th International Conference on Machine Learning, pages 844–853, 2017.
  8. [8]Victor H. de la Peña, Michael J. Klass, and Tze Leung Lai. Self-normalized processes: exponential inequalities, moment bounds and iterated logarithm laws. The Annals of Probability, 32(3A): 1902–1933, 2004.
  9. [9]Victor H. de la Peña, Tze Leung Lai, and Qi-Man Shao. Self-Normalized Processes: Limit Theory and Statistical Applications. Springer, 2009.
  10. [10]Sjoerd Dirksen. Tail bounds via generic chaining. Electronic Journal of Probability, 20(53):1–29, 2015.arxiv.org/abs/1309.3522
  11. [11]Audrey Durand, Odalric-Am­brym Maillard, and Joelle Pineau. Streaming kernel regression with provably adaptive mean, variance, and regularization. Journal of Machine Learning Research, 19(17):1–34, 2018.arxiv.org/abs/1708.00768
  12. [12]Hamish Flynn and David Reeb. Tighter confidence bounds for sequential kernel regression. arXiv preprint arXiv:2403.12732, 2024.arxiv.org/abs/2403.12732
  13. [13]Dylan Foster and Alexander Rakhlin. Beyond UCB: Optimal and efficient contextual bandits with regression oracles. In Proceedings of the 37th International Conference on Machine Learning, pages 3199–3210, 2020.arxiv.org/abs/2002.04926
  14. [14]Roger A. Horn and Charles R. Johnson. Matrix Analysis. Cambridge University Press, second edition, 2012.
  15. [15]Steven R. Howard, Aaditya Ramdas, Jon McAuliffe, and Jasjeet Sekhon. Time-uniform, nonparametric, nonasymptotic confidence sequences. The Annals of Statistics, 49(2):1055–1080, 2021.DOI
  16. [17]Haichen Hu and David Simchi-Levi. Interleaved resampling and refitting: Data and compute-efficient evaluation of black-box predictors. arXiv preprint arXiv:2603.14218, 2026a.arxiv.org/abs/2603.14218
  17. [18]Haichen Hu and David Simchi-Levi. Minimax regret for Sobolev kernel-based reinforcement learning. arXiv preprint arXiv:2610.34045, 2026b.arxiv.org/abs/2610.34045
  18. [19]Haichen Hu and David Simchi-Levi. Simultaneous pointwise majorization for mixed tail processes with applications in Gaussian chaos and ergodic diffusions. arXiv preprint arXiv:2609.01576, 2026c.arxiv.org/abs/2609.01576
  19. [20]Haichen Hu, Rui Ai, Stephen Bates, and David Simchi-Levi. Contextual online decision making with infinite-dimensional functional regression. In Proceedings of the 42nd International Conference on Machine Learning, 2025a.arxiv.org/abs/2501.18359
  20. [21]Haichen Hu, David Simchi-Levi, and Navid Azizan. Eluder-dimension-free regret for stage-wise constrained contextual bandits via offline regression. arXiv preprint arXiv:2505.07101, 2025b.arxiv.org/abs/2505.07101
  21. [24]Shogo Iwazaki. Gaussian process upper confidence bound achieves nearly optimal regret in noise-free Gaussian process bandits. In Advances in Neural Information Processing Systems, volume 38, 2025b.
  22. [25]David Janz, David Burt, and Javier González. Bandit optimisation of functions in the Matérn kernel RKHS. In Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics, 2020.arxiv.org/abs/2001.10396
  23. [26]David Janz, Arya Akhavan, and Alexandre B. Tsybakov. Maximum effective dimension and information gain. arXiv preprint arXiv:2608.24450, 2026.arxiv.org/abs/2608.24450
  24. [27]Motonobu Kanagawa, Philipp Hennig, Dino Sejdinovic, and Bharath K. Sriperumbudur. Gaussian processes and kernel methods: A review on connections and equivalences. arXiv preprint arXiv:1807.02582, 2018.arxiv.org/abs/1807.02582
  25. [28]Koulik Khamaru, Yash Deshpande, Tor Lattimore, Lester Mackey, and Martin J. Wainwright. Near-optimal inference in adaptive linear regression. arXiv preprint arXiv:2107.02266v3, 2023.arxiv.org/abs/2107.02266
  26. [29]Andreas Krause and Cheng Soon Ong. Contextual Gaussian process bandit optimization. In Advances in Neural Information Processing Systems, volume 24, pages 2447–2455, 2011.
  27. [30]David Krieg and Jan Vybíral. New lower bounds for the integration of periodic functions. Journal of Fourier Analysis and Applications, 29:41, 2023. doi: 10.1007/s00041-023-10021-7.DOI
  28. [31]Tor Lattimore. A lower bound for linear and kernel regression with adaptive covariates. In Proceedings of Thirty Sixth Conference on Learning Theory, volume 195 of Proceedings of Machine Learning Research, pages 2095–2113. PMLR, 2023.
  29. [32]Béatrice Laurent and Pascal Massart. Adaptive estimation of a quadratic functional by model selection. The Annals of Statistics, 28(5):1302–1338, 2000.
  30. [33]Zihan Li and Jonathan Scarlett. Gaussian process bandit optimization with few batches. In Proceedings of the 25th International Conference on Artificial Intelligence and Statistics, 2022.arxiv.org/abs/2110.07788
  31. [34]Chenkai Ma and Jonathan Scarlett. A general Ω̃(√(T/Tγ)) lower bound for kernel bandits. arXiv preprint arXiv:2610.11082, 2026.
  32. [35]Davide Maran and Csaba Szepesvári. Sharper guarantees for misspecified kernelized bandit optimization. arXiv preprint arXiv:2605.05967, 2026.arxiv.org/abs/2605.05967
  33. [36]Gergely Neu, Julia Olkhovskaya, and Sattar Vakili. Adversarial contextual bandits go kernelized. In Proceedings of the 35th International Conference on Algorithmic Learning Theory, volume 237 of Proceedings of Machine Learning Research, pages 907–929. PMLR, 2024. URL https://proceedings.mlr.press/v237/neu24a.html.arxiv.org/abs/2310.01609
  34. [37]Yijin Ni and Xiaoming Huo. Upper confidence bounds for the prediction error of kernel ridge regression via Gaussian refitting. arXiv preprint arXiv:2607.28846, 2026.arxiv.org/abs/2607.28846
  35. [38]Jian Qian, Haichen Hu, and David Simchi-Levi. Offline oracle-efficient learning for contextual MDPs via layerwise exploration-exploitation tradeoff. arXiv preprint arXiv:2405.17796, 2024.arxiv.org/abs/2405.17796
  36. [39]J. Jon Ryu and Gregory W. Wornell. Gambling-based confidence sequences for bounded random vectors. In Proceedings of the 41st International Conference on Machine Learning, 2024.arxiv.org/abs/2402.03683
  37. [40]Sudeep Salgia, Sattar Vakili, and Qing Zhao. A domain-shrinking based Bayesian optimization algorithm with order-optimal regret performance. In Advances in Neural Information Processing Systems, volume 34, 2021.arxiv.org/abs/2010.13997
  38. [41]Jonathan Scarlett, Ilija Bogunovic, and Volkan Cevher. Lower bounds on regret for noisy Gaussian process bandit optimization. In Proceedings of the 2017 Conference on Learning Theory, volume 65 of Proceedings of Machine Learning Research, pages 1723–1742. PMLR, 2017.arxiv.org/abs/1706.00090
  39. [42]Matthias W. Seeger, Sham M. Kakade, and Dean P. Foster. Information consistency of nonparametric Gaussian process methods. IEEE Transactions on Information Theory, 54(5):2376–2382, 2008.DOI
  40. [43]David Simchi-Levi and Yunzong Xu. Bypassing the monster: A faster and simpler optimal algorithm for contextual bandits under realizability. Mathematics of Operations Research, 2021.
  41. [44]Niranjan Srinivas, Andreas Krause, Sham Kakade, and Matthias Seeger. Gaussian process optimization in the bandit setting: No regret and experimental design. In Proceedings of the 27th International Conference on Machine Learning, pages 1015–1022, 2010.DOI
  42. [45]Shion Takeno, Shogo Iwazaki, and Ichiro Takeuchi. Near-optimal regret bounds for UCB-style Gaussian process bandits via data thinning. arXiv preprint arXiv:2610.28136, 2026.arxiv.org/abs/2610.28136
  43. [46]Michel Talagrand. The Generic Chaining: Upper and Lower Bounds of Stochastic Processes. Springer Monographs in Mathematics. Springer, 2005.DOI
  44. [47]Sattar Vakili. Open problem: Order optimal regret bounds for kernel-based reinforcement learning. In Proceedings of Thirty Seventh Conference on Learning Theory, volume 247 of Proceedings of Machine Learning Research. PMLR, 2024.arxiv.org/abs/2406.15250
  45. [48]Sattar Vakili and Julia Olkhovskaya. Kernelized reinforcement learning with order optimal regret bounds. In Advances in Neural Information Processing Systems, volume 36, 2023.arxiv.org/abs/2306.07745
  46. [49]Sattar Vakili, Nacime Bouziani, Sepehr Jalali, Alberto Bernacchia, and Da-shan Shiu. Optimal order simple regret for Gaussian process bandits. In Advances in Neural Information Processing Systems, volume 34, 2021a.arxiv.org/abs/2108.09262
  47. [50]Sattar Vakili, Kia Khezeli, and Victor Picheny. On information gain and regret bounds in Gaussian process bandits. In Proceedings of the 24th International Conference on Artificial Intelligence and Statistics, pages 82–90, 2021b.arxiv.org/abs/2009.06966
  48. [51]Sattar Vakili, Jonathan Scarlett, and Tara Javidi. Open problem: Tight online confidence intervals for RKHS elements. In Proceedings of Thirty Fourth Conference on Learning Theory, volume 134 of Proceedings of Machine Learning Research, pages 4647–4652. PMLR, 2021c.arxiv.org/abs/2110.15458
  49. [52]Michal Valko, Nathan Korda, Rémi Munos, Ilias Flaounas, and Nello Cristianini. Finite-time analysis of kernelised contextual bandits. In Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence, pages 654–663, 2013.arxiv.org/abs/1309.6869
  50. [53]Grace Wahba. Spline Models for Observational Data. SIAM, 1990.
  51. [54]Martin J. Wainwright. Wild refitting for black box prediction. arXiv preprint arXiv:2506.21460, 2025.arxiv.org/abs/2506.21460
  52. [55]Wenjia Wang and Xiaowei Zhang. On the suboptimality of GP-UCB under polynomial effective optimism. arXiv preprint arXiv:2312.01386v2, 2026.arxiv.org/abs/2312.01386
  53. [56]Justin Whitehouse, Aaditya Ramdas, and Zhiwei Steven Wu. On the sublinear regret of GP-UCB. In Advances in Neural Information Processing Systems, volume 36, 2023.arxiv.org/abs/2307.07539
  54. [57]Yunbei Xu. Bellman-sufficient information complexity. arXiv preprint arXiv:2606.11171, 2026a.arxiv.org/abs/2606.11171
  55. [58]Yunbei Xu. Pointwise complexity for gaussian fields: Upper envelopes, algorithmic lower bounds, and separation. arXiv preprint arXiv:2606.07931, 2026b.arxiv.org/abs/2606.07931
  56. [59]Zhuoran Yang, Chi Jin, Zhaoran Wang, Mengdi Wang, and Michael I. Jordan. Provably efficient reinforcement learning with kernel and neural function approximations. In Advances in Neural Information Processing Systems, volume 33, 2020.
  57. [60]Houssam Zenati, Alberto Bietti, Eustache Diemert, Julien Mairal, Matthieu Martin, and Pierre Gaillard. Efficient kernelized UCB for contextual bandits. In Proceedings of the 25th International Conference on Artificial Intelligence and Statistics, volume 151 of Proceedings of Machine Learning Research, pages 5689–5720. PMLR, 2022. URL https://proceedings.mlr.press/v151/zenati22a.html.arxiv.org/abs/2202.05638

Paper details

vlnc:W_34gbayvz
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents