다중 그룹 평균 추정에서의 능동 학습을 위한 복잡도 측정 지표

우리는 다중 그룹 평균 추정(multi-group mean estimation) $d$-armed bandits에서의 능동 학습 (active learning)을 위한 extit{최대 위험 (max-risk)} 목적 함수를 연구합니다: 학습자는 최악의 불확실성 지표 $\max_{k\in[d]}σ_k^2/n_k$를 최소화하기 위해 $T$개의 샘플 예산을 $d$개의 그룹에 적응적으로 할당합니다. 여기서 $σ_k$는 arm $k$ 분포의 표준 편차이고, $n_k$는 arm $k$가 샘플링된 횟수입니다. 우리는 로컬 미니맥스 (local minimax) 프레임워크를 개발하고, 유한 분산을 가진 모든 가설 클래스 (hypothesis class)에 유효한 이 목적 함수에 대한 최초의 일반적인 하한 (lower bound)을 증명합니다. 이 하한은 난이도를 세 가지 직교하는 요소로 분리합니다: extit{예산 (budget)} 항, 불확실성이 arm들 사이에 얼마나 불균일하게 퍼져 있는지를 측정하는 extit{이분산성 (heteroscedasticity)} 지표, 그리고 모델 의존적 복잡도 측정 지표인 extit{분산 로컬 곡률 (Variance Local Curvature, VLC)}입니다. VLC는 가설 클래스 내부에서 분산의 국소적 변화가 얼마나 많은 정보를 생성하는지를 포착합니다. 매끄러운 클래스 (smooth classes)의 경우, VLC는 분산-피셔 정보량 (variance--Fisher information)의 재매개변수화 (reparametrization)이며, 일반적인 가족군에 대해 폐쇄형 (closed-form) 값을 가집니다. 사용 가능한 가장 강력한 상한 (upper bound)과 벤치마킹한 결과, 광범위한 영역에서 로그 인자 (logarithmic factors)를 제외하면 거의 최적에 가까움을 보여주었으며, 매우 이질적인 (heterogeneous) 사례에서의 체계적인 격차를 정확히 짚어냈습니다. 우리의 증명은 두 가지 핵심 요소를 도입합니다: 결정 공간 (decision space)에서의 손실 유도 $\ell_1$ 기하학 ($\ell_1$ geometry), 그리고 어려운 사례 구성을 명시적인 무작위 행렬 계산으로 축소하는 표현 기반 사례 생성기 (representation-based instance generator)입니다.