arXiv:2610.11082v1 stat.ML

커널 밴딧(Kernel Bandits)에 대한 일반적인 $\widetildeΩ(\sqrt{Tγ_T})$ 하한

A General $\widetildeΩ(\sqrt{T γ_T})$ Lower Bound for Kernel Bandits

Chenkai Ma, Jonathan Scarlett

제출 2026-10-08

한국어 초록

커널 밴딧(kernel bandit) 문제는 주어진 재생 커널 힐베르트 공간(Reproducing Kernel Hilbert Space, RKHS)에서 유계 노름(bounded norm)을 갖는 미지의 함수를 잡음이 있는 피드백(noisy feedback)을 통해 순차적으로 최적화하는 문제이다. 커널 밴딧의 후회(regret) 분석에서 중심이 되는 양은 최대 정보 획득량(maximum information gain) $γ_T$이다. 특히, 기존에 알려진 가장 좋은 상한(upper bound)은 로그 항(log factor)을 제외하면 $\sqrt{Tγ_T}$로 스케일링되며, 제곱 지수(squared exponential) 커널과 마테른(Matérn) 커널과 같은 특정 커널에 대해서는 이와 거의 일치하는 하한(lower bound)이 도출되어 왔다. 그러나 일반적인 커널에 대한 하한은 부족하여, 어느 정도의 일반성에서 상한이 근사 최적(near-optimal)인지가 불분명하다. 본 논문에서는 콤팩트 정의역(compact domain) 상의 비상수 연속 커널(non-constant continuous kernel)에 대해 일반적인 $Ω(\sqrt{Tγ_T/\log T})$ 미니맥스 후회 하한을 수립하여, 매우 일반적인 의미에서 (로그 항 범위 내에서의) 근사 최적성을 입증한다. 우리는 이 하한에 나타나는 로그 항이 일반적으로는 피할 수 없음을 보이지만, 특정 조건 하에서는 이를 제거할 수 있음을 보인다. 특히 우리의 결과는 $ν\in (0,2)$인 마테른-$ν$(Matérn-$ν$) 커널, $γ\in (0,2)$인 $γ$-지수(γ-exponential) 커널, 그리고 특정 조각별 다항식(piecewise-polynomial) 커널에 대해 미니맥스 최적 스케일링이 (상수 인자 범위 내에서) 정확히 $Θ(\sqrt{Tγ_T})$임을 함의한다.

원문 초록

The kernel bandit problem consists of sequentially optimizing an unknown function with noisy feedback, where the function has bounded norm in a given Reproducing Kernel Hilbert Space (RKHS). A central quantity in the regret analysis of kernel bandits is the maximum information gain $γ_T$. In particular, the best existing upper bounds scale as $\sqrt{Tγ_T}$ up to log factors, and nearly-matching lower bounds have been derived for specific kernels such as squared exponential and Matérn. However, lower bounds for general kernels are lacking, thus making it unclear in what generality the upper bounds are near-optimal. In this paper, we establish a general $Ω(\sqrt{Tγ_T/\log T})$ minimax regret lower bound for non-constant continuous kernels on compact domains, establishing near-optimality (within log factors) in a very general sense. We show that the log factor appearing in this bound is unavoidable in general, but that it can be removed under certain conditions. Among other things, our findings imply that the minimax-optimal scaling is exactly $Θ(\sqrt{Tγ_T})$ (i.e., within constant factors) for the Matérn-$ν$ kernel with $ν\in (0,2)$, $γ$-exponential kernel with $γ\in (0,2)$, and certain piecewise-polynomial kernels.

제출 이력

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

  1. arXiv:2610.11082v1

함께 살펴볼 논문

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

arXiv:2602.07144v3cs.LG공통 태그 Bayesian Optimization, Gaussian Processes, regret bounds

BONSAI: 자연스러운 단순성과 해석 가능성을 갖춘 베이즈 최적화

BONSAI: Bayesian Optimization with Natural Simplicity and Interpretability

베이즈 최적화(Bayesian optimization, BO)는 블랙박스 함수의 표본 효율적 최적화(sample-efficient optimization)를 위해 널리 사용되는 기법입니다. 많은 응용 분야에서 튜닝 대상 파라미터는 정교하게 설계된 기본 설정(default configuration)과 함께 제공되며, 실무자들은 꼭 필요한 경우에만 이 기본값에서 벗어나기를 원합니다. 그러나 표준 BO는 기본값으로부터의 편차를 최소화하는 것을 목표로 하지 않으며, 실제로는 중요도가 낮은 파라미터를 탐색 공간의 경계로 밀어내는 경우가 많습니다. 이는 중요 변경사항과 무의미한 변경사항을 구분하기 어렵게 만들고, 최적화 목적함수에 관련 운영 고려사항이 누락되었을 때 추천된 설정을 검토하는 부담을 가중시킵니다. 본 논문에서는 획득 가치(acquisition value)의 손실(loss)을 명시적으로 제어하면서 기본 설정 대비 영향력이 적은 편차를 가지치기(pruning)하는 기본값 인식(default-aware) BO 정책인 BONSAI를 소개합니다. BONSAI는 기대 개선량(expected improvement)과 상한 신뢰 구간(GP-UCB)을 포함한 다양한 획득 함수(acquisition function)와 호환됩니다. 우리는 BONSAI에 의해 발생하는 후회(regret)의 이론적 상계를 제시하여, 적절한 조건 하에서 기본 GP-UCB의 무후회(no-regret) 특성을 유지하면서 무관한 변경사항을 제거함을 증명합니다. 다양한 실제 응용 전반에 걸쳐, BONSAI가 실행 시간(wall time)에 거의 영향을 주지 않으면서 경쟁력 있는 최적화 성능을 유지함과 동시에 추천 설정에서 기본값이 아닌 파라미터의 수를 실질적으로 줄임을 실험적으로 확인했습니다. BONSAI의 후보 생성 비용은 표준 BO 대비 평균 1.5배에 불과하여, 기존 희소(sparse) BO 기법들의 7~34배와 대비됩니다.

arXiv:2606.00956v2cs.LG공통 태그 Bayesian Optimization, Gaussian Processes, regret bounds

1단계 룩어헤드 베이지안 최적화의 리그렛 보장을 향하여

Towards Regret Guarantees for One-Step Lookahead Bayesian Optimization

본 논문에서는 1단계 룩어헤드(one-step lookahead) 베이지안 최적화(BO) 기법의 이론적 보장을 연구한다. 엔트로피 탐색(entropy search)과 같은 1단계 룩어헤드 BO 기법들의 실증적 유효성은 광범위하게 연구되어 왔으나, 이러한 기법들은 계산적으로 다루기 힘든 근사에 의존하는 경우가 많으며 리그렛(regret) 보장은 여전히 충분히 개발되지 않은 상태이다. 이에 따라 본 논문에서는 사후 표본추출(posterior sampling)과 몬테카를로 근사만을 필요로 하는 1단계 룩어헤드 BO 기법인 최적점 분산 감소(OVR)를 분석한다. 연구진은 획득 함수(acquisition function) 계산 시 입력 도메인 전반에 대한 균일한 몬테카를로 추정 오차 한계를 도출한다. 나아가 탐험을 촉진하도록 약간 수정한 정규화된 OVR이 점근적으로 0으로 수렴하는 베이지안 기대 단순 리그렛 상한을 달성함을 보인다. 마지막으로 수치 실험을 통해 OVR 및 정규화된 OVR의 성능을 검증한다.

arXiv:2605.09454v3stat.ML공통 태그 Bayesian Optimization, Multi-Armed Bandits, regret bounds

단일 인덱스 밴딧의 최적 후회

Optimal Regret for Single Index Bandits

우리는 보상이 알 수 없는 보상 함수를 통해 고차원 컨텍스트의 알 수 없는 1차원 투영(projection)에 의존하는 $\textit{단일 인덱스 밴딧}$(single-index bandit) 문제를 연구한다. 이 모델은 선형 및 일반화 선형 밴딧을 비모수적(nonparametric) 설정으로 확장하며, 보상 함수가 사전에 알려지지 않은 경우에 특히 적합하다. 단조(monotone) 보상 함수에 대한 최적 후회(regret) 보장은 알려져 있으나, 일반적인 비단조(non-monotone) 경우는 여전히 잘 이해되지 않으며, 현재까지 알려진 최선의 상한은 $\tilde{\mathcal{O}}(T^{3/4})$이다(보상 함수에 대한 표준 유계성 및 립시츠(Lipschitz) 가정 하에서 [Kang et al., 2025]). 우리는 일반 단일 인덱스 밴딧의 최적 후회를 확립함으로써 이 격차를 해소한다. 우리는 Zoomed Single Index Bandit with Upper Confidence Bound($\texttt{ZoomSIB-UCB}$)라는 간단한 2단계 알고리즘을 제안한다. 이 알고리즘은 먼저 정규화된 스타인(Stein) 추정량을 통해 투영 방향을 추정하고, 이산화(discretization)를 통해 문제를 1차원 밴딧으로 축소한 후 UCB를 적용한다. 이 접근법은 $\tilde{\mathcal{O}}(T^{2/3})$의 후회를 달성하며, 추가적인 가정 없이 기존 연구를 크게 개선한다. 우리는 또한 $\tilde{\Omega}(T^{2/3})$의 일치하는 미니맥스 하한을 증명하여 상한이 본질적으로 타이트함을 보인다. 상한과 하한을 종합하면 단일 인덱스 밴딧에서 후회에 대한 정밀한 특성화를 제공한다. 더불어, 실험 결과는 우리 접근법의 효과성과 강인성을 추가로 입증한다.

arXiv:2607.03184v1cs.CV공통 태그 Bayesian Optimization, Gaussian Processes, Multi-Armed Bandits

BVS: 세밀한 지각을 위한 멀티모달 대규모 언어 모델 기반 베이지안 시각 탐색

BVS: Bayesian Visual Search with Multimodal Large Language Model for Fine-grained Perception

멀티모달 대규모 언어 모델(MLLM)은 인상적인 범용 능력을 보여주지만, 초고해상도(UHR) 이미지에서의 세밀한 지각, 특히 복잡한 장면 속 작은 객체 인식에는 어려움을 겪는다. 기존 방법들은 딜레마에 직면해 있다: 비효율적인 사전 정보 없는 스캐닝에 의존하거나, 초기 모델 편향을 수정하는 사후 보정이 부재한 정적 사전 정보 기반 휴리스틱에 의존한다. 이를 해결하기 위해, 우리는 지각을 연속적인 공간-스케일 다양체(manifold)에 대한 전역 최적화 문제로 정식화하는 프레임워크인 BVS(Bayesian Visual Search)를 제안한다. 구체적으로, BVS는 사전 안내와 사후 보정을 연결한다: MLLM의 조기 중단 어텐션 롤아웃을 활용하여 추론 인식 사전 정보를 구성하는 한편, 스케일 인식 비정상 커널과 GP-UCB를 적용하여 반복적인 지역 관찰을 통해 사전 정보의 노이즈를 동적으로 수정하고 누락된 정보를 복원한다. 우리는 준선형 후회 한계(sub-linear regret bounds)를 통해 이론적 보장을 제공하며, 광범위한 실험을 통해 BVS가 정확도와 효율성 간의 우수한 균형으로 최신 기준선을 크게 능가함을 입증한다.

arXiv:2603.09276v2stat.ML공통 태그 Bayesian Optimization, Gaussian Processes, regret bounds

베이지안 최적화를 위한 톰슨 샘플링의 후회 경계에 대하여

On Regret Bounds of Thompson Sampling for Bayesian Optimization

우리는 목적 함수가 GP(가우시안 프로세스)의 샘플 경로라는 가정 하에 널리 사용되는 베이지안 최적화 방법인 가우시안 프로세스 톰슨 샘플링(GP-TS)을 연구합니다. 고확률 및 기대 후회 경계가 확립된 GP 상위 신뢰 구간(GP-UCB)과 비교할 때, GP-TS에 대한 대부분의 분석은 기대 후회로 제한되어 있습니다. 또한, 관대한 후회(Lenient regret)와 개선된 누적 후회 상한에 대한 GP-UCB의 최근 분석이 GP-TS에 적용될 수 있는지 여부는 여전히 불분명합니다. 이러한 공백을 메우기 위해, 본 논문은 다음과 같은 여러 후회 경계를 제시합니다: (i) GP-TS가 확률 $δ$로 $1/δ$에 대한 다항식 의존성을 겪는다는 것을 시사하는 GP-TS의 후회 하한, (ii) $δ$에 대한 개선된 후회 상한을 직접적으로 시사하는 누적 후회의 2차 모멘트 상한, (iii) 기대 관대한 후회 상한, 그리고 (iv) 시간 지평 $T$에 대한 개선된 누적 후회 상한. 아울러, 우리는 $T$에 대한 개선된 후회 상한을 얻기 위해 최근 분석의 필요 조건을 완화한 것을 포함하여 여러 유용한 보조정리를 제공합니다.

토론

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