arXiv:2611.19772v1 stat.ML

온라인 커널 회귀를 위한 폭이 최적에 가까운 순차 신뢰구간

Tight Sequential Confidence Intervals for Online Kernel Regression

Haichen Hu, David Simchi-Levi

제출 2026-11-17

한국어 초록

본 연구는 커널에 대한 최악의 경우를 기준으로 재생 커널 힐베르트 공간(RKHS) 원소의 온라인 신뢰구간에 대한 정밀한 최소최대 폭을 규명한다. 이는 Vakili 등의 2021년 미해결 문제를 처음 제시한 이산 시간 형태로 해결한다. 학습기는 적응적으로 선택한 점에서 $y_i=f(x_i)+\epsilon_i$를 관측한다. 이때 $\|f\|_{\mathcal H_k}\le B$이고 잡음은 독립·동일 분포의 $R$-부분 가우스 잡음이다. 학습기는 구간 $|f(x)-\mu_n(x)|\le\rho_n(\delta)\sigma_n(x)$를 보고한다. 여기서 $\mu_n$과 $\sigma_n$은 정규화 매개변수 $\lambda$를 갖는 대리 가우스 과정 모델의 사후 평균과 표준편차다. 고정 커널의 최소최대 신뢰구간 폭을 $\rho_n^*(\delta)$라 하자. 선형 커널과 주기적 소볼레프 커널의 합을 사용하면, 충분히 큰 모든 $n$과 모든 $\delta\in(0,1/4]$에 대해 $\rho_n^*(\delta)\asymp B+(R/\lambda)\sqrt{\gamma_n+\log(1/\delta)}$임을 보인다. 여기서 $\gamma_n$은 최대 정보 이득이며 $n$에 대해 다항식으로 증가한다. Lattimore(2023)에 기반해 고정된 2차원 영역에서 적응적 실험 설계를 구성한다. 가우스 잡음 아래에서 이 설계를 사용하면, 미리 정한 점의 정규화 오차가 일정한 확률로 $\Omega(B+(R/\lambda)\sqrt{\gamma_n})$이다. 따라서 커널과 온라인 설계에 대한 최악의 경우 신뢰구간 폭이 다항 로그 규모라는 추측은 성립하지 않는다.

원문 초록

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 $y_i=f(x_i)+\epsilon_i$ at adaptively chosen points, with $\|f\|_{\mathcal H_k}\le B$ and i.i.d. $R$-sub-Gaussian noise, and reports the interval $|f(x)-\mu_n(x)|\le\rho_n(\delta)\sigma_n(x)$, where $\mu_n$ and $\sigma_n$ are the posterior mean and standard deviation of a surrogate Gaussian process model with regularization parameter $\lambda$. Writing $\rho_n^*(\delta)$ 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 $n$, and all $\delta\in(0,1/4]$, $\rho_n^*(\delta)\asymp B+(R/\lambda)\sqrt{\gamma_n+\log(1/\delta)}$, where $\gamma_n$ is the maximal information gain and grows polynomially in $n$. 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 $\Omega(B+(R/\lambda)\sqrt{\gamma_n})$ with constant probability. This rules out the conjectured polylogarithmic width in the worst case over kernels and online designs.

제출 이력

확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.

  1. arXiv:2611.19772v1제출 시각 미확인

함께 살펴볼 논문

공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.

공통 태그로 연결된 공개 논문이 아직 없습니다.

토론

이 논문과 연결된 포럼 글이 아직 없습니다.