아선형 노이즈 프로브를 이용한 온라인 볼록 최적화 (Online Convex Optimization with Sublinear Noisy

우리는 볼록 집합 $K o ext{R}^d$ 상에서의 온라인 볼록 최적화 (Online Convex Optimization, OCO)를 연구합니다. 각 라운드 $t$에서 학습자는 $x_t o K$를 선택한 후 볼록 손실 함수 $f_t:K o[0,1]$를 관찰하며, 사후적으로 가장 좋았던 고정된 결정에 대한 후회 (regret)를 최소화하는 것을 목표로 합니다. 우리는 최근의 두 가지 연구 흐름, 즉 전문가 설정 (experts setting)에서의 아선형 최적 전문가 쿼리 (sublinear best-expert queries)와 OCO에서 매 라운드 사용 가능한 쌍별 (pairwise, 비교 기반) 피드백을 일반화하는 통합된 프로빙 모델 (probing model)을 도입합니다. 우리의 프레임워크에서 학습자는 $k o T$개의 쌍별 프로브 (pairwise probes) 예산을 가집니다. 프로브가 수행되는 라운드에서 학습자는 두 점을 쿼리하여 어느 쪽의 손실이 더 작은지 학습할 수 있습니다. 우리의 주요 결과는 아선형(sublinear)이고 노이즈가 있는 프로브 예산만으로도 전체 피드백 OCO 체제에서 최악의 경우 후회 (worst-case regret)를 증명 가능하게 개선할 수 있음을 보여줍니다. $k$개의 $\delta$-노이즈 쌍별 프로브를 사용할 때, 우리는 다음과 같은 결과를 얻습니다: $\text{Reg}_T \le O\left(\min\left{\sqrt{dT\ln T},; \frac{dT\ln T}{k|1-2\delta|}\right}\right)$, 이는 $T$, $k$, $\delta$에 대해 ($T$의 로그 인자를 제외하고) 타이트 (tight)합니다. 특히 노이즈 파라미터 $\delta\in [0,1]$와 관련하여, 오라클 (oracle)의 응답이 동전 던지기(coin flip), 즉 $\delta$가 $\frac{1}{2}$에 가까워짐에 따라 후회 보장 (regret guarantee)은 부드럽게 저하됩니다. 동일한 기술을 $d$명의 전문가를 이용한 예측을 위한 유한한 $K$에 적용할 경우, 결과적인 속도 (rates)는 $d$를 포함한 모든 파라미터에 대해 완전히 타이트합니다. 우리의 분석은 분산 감소 효과 (variance reduction effect)를 통해 프로빙의 이점을 정량화하고, 연속적 지수 가중치 (Continuous Exponential Weights)의 2차 (분산 기반) 분석을 결합함으로써 OCO에서의 쌍별 프로빙에 대한 간결한 처리를 제공합니다.