Optimal-Point Variance Reduction For Bayesian Optimization With Regret Guarantee

기술 요약: 베이지안 최적화를 위한 최적 지점 분산 감소 기법의 회귀 보장

문제 정의

베이지안 최적화(Bayesian Optimization, BO)는 평가 비용이 많이 드는 블랙박스 함수를 최적화하기 위한 프레임워크이다. 엔트로피 탐색(Entropy Search, ES) 및 지식 구배(Knowledge Gradient, KG)와 같은 일보 앞을 내다보는(one-step lookahead) 방식들은 전역적 효용(global utility)을 고려함으로써 우수한 경험적 성능을 입증해 왔으나, 다음과 같은 두 가지 주요 한계점을 갖는다:

1. 계산적 난해함: 이들은 종종 복잡하고 계산 비용이 많이 드는 중첩 최적화나 (최적 입력 또는 최댓값에 대한 조건부 분포를 위한) 휴리스틱 근사에 의존한다.
2. 이론적 보장의 부재: 이러한 방법들의 실질적인 유효성에도 불구하고, 일보 앞을 내다보는 BO 방식에 대한 이론적 특성화는 여전히 미비하다. 구체적으로, 이 방법들에 대한 유한 샘플 회귀 보장(finite-sample regret guarantees)은 여전히 미해결 과제로 남아 있으며, 기존의 분석들은 (일반적으로 성립하지 않는) 사후 분산의 부가성(submodularity)과 같은 가정에 의존하는 경우가 많다.

방법론

본 논문은 **최적 지점 분산 감소(Optimal-Point Variance Reduction, OVR)**와 그 정규화 변형인 **정규화된 OVR(Regularized OVR, ROVR)**을 제안한다. 이들은 최적 입력 $x^*$에서의 사후 분산(또는 표준 편차)을 최소화하도록 설계된 일보 앞을 내다보는 BO 방식이다.

핵심 메커니즘

최대 정보량(mutual information)을 최대화하는 ES 기반 방식(조건부 분포를 위한 휴리스틱 근사가 필요함)과 달리, OVR은 최적 지점에서의 사후 표준 편차를 직접 목표로 한다. OVR의 획득 함수(Acquisition Function, AF)는 다음과 같이 정의된다:
$$\alpha_t(x) = \mathbb{E}_{x^*} [\sigma_t(x^* | x) \mid D_{t-1}]$$
여기서 $\sigma_t(x^* | x)$는 새로운 관측 $x$가 주어졌을 때 최적 지점 $x^*$에서의 사후 표준 편차이다.

주요 기술적 특징:

• 해석적 변환: 저자들은 관측값 $y_x$에 대한 기댓값을 해석적으로 제거할 수 있음을 보여주며, 이를 통해 AF를 오직 최적 지점 $x^*$에 대한 기댓값으로 단순화한다.
• 몬테카를로(MC) 근사: $x^*$의 분포는 다루기 어렵기 때문에, OVR은 MC 샘플링을 사용하여 기댓값을 근사한다. 이는 $M_t$개의 사후 경로 샘플 $g_t \sim p(f \mid D_{t-1})$를 생성하고, 각 경로를 최적화하여 샘플 최적점 $x^*_{t,m}$을 찾은 뒤, 다음과 같이 AF를 계산한다:
  $$\hat{\alpha}_t(x) = \frac{1}{M_t} \sum_{m=1}^{M_t} \sigma_t(x^*_{t,m} \mid x)$$
• 정규화(ROVR): 탐색(exploration)을 보장하고 이론적 수렴을 달성하기 위해, ROVR은 정규화 항을 도입한다:
  $$\hat{\alpha}_t(x) = \frac{1}{M_t} \sum_{m=1}^{M_t} \sigma_t(x^*_{t,m} \mid x) - c_t \sigma_{t-1}(x)$$
  여기서 $c_t \geq 0$은 정규화 파라미터이다. 이 항은 낮은 불확실성을 가진 입력을 억제하여, 불확실성이 높은 입력을 선택하도록 유도한다.

구현 세부 사항

• 사후 샘플링: 본 방법은 효율적인 근사 사후 경로 생성을 위해 경로 기반 조건화(pathwise conditioning)와 무작위 푸리에 특징(random Fourier feature) 근사(Wilson et al., 2020, 2021)를 사용한다.
• 휴리스틱 없음: PES, MES, 또는 JES와 달리, OVR은 최적 입력 또는 최댓값에 대한 조건부 분포를 위한 휴리스틱 근사를 요구하지 않는다.

주요 기여

본 논문의 주요 기여는 세 가지이다:

1. OVR 및 ROVR 제안: 저자들은 최적 입력에서의 사후 분산을 최소화하는 구현이 용이한 일보 앞을 내다보는 방법들을 소개한다. 이 방법들은 사후 샘플링과 MC 근사에만 의 rely하며, PES, MES, JES에서 요구되는 휴리스틱 근사를 피한다.
2. 균등 MC 추정 오차 경계: 본 논문은 입력 영역 전체에 대한 AF의 MC 추정에 대한 이론적 균등 오차 경계를 제공한다.
   • 이산 도메인(Discrete domains)의 경우: 오차 경계는 $O(\sqrt{\log(|X|/\delta)/M_t})$이다.
   • 연속 도메인(Continuous domains)의 경우: 커널의 립시츠 연속성 가정 하에, 오차 경계는 $O(\sqrt{d \log(M_t)/M_t})$이다. 이는 $M_t = \Omega(\log(t/\epsilon)/\epsilon^2)$개의 샘플이 $\epsilon$-정확도를 위해 충분함을 입증한다.
3. 회귀 보장(Regret Guarantee): 본 논문은 ROVR이 소멸하는 베이지안 기대 단순 회귀(Bayesian Expected Simple Regret, BSR) 상한을 달성함을 증명한다. 이 상한은 다른 BO 방법들의 기존 결과와 유사하다:
   $$\text{BSR}_T \leq \sqrt{\frac{C_1 \beta_T \gamma_T}{T}} + O\left(\frac{\beta_T^{1/2}}{T}\right) + O\left(\frac{1}{T c_T}\right) + O\left(\frac{1}{T} \sum_{t=1}^T \frac{\log M_t}{\sqrt{M_t} c_t}\right)$$
   여기서 $\gamma_T$는 최대 정보 이득이며, $\beta_T$는 도메인 크기와 매끄러움(smoothness)에 따라 결정된다.

실험 결과

저자들은 합성 함수, 벤치마크 함수(Ackley, Hartmann), 그리고 Olympus 프레임워크의 에뮬레이터를 사용하여 OVR 및 ROVR을 평가하였다.

• 성능: 다양한 노이즈 수준($\sigma^2 = 10^{-4}$ 및 $\sigma^2 = 1$)을 가진 합성 실험에서, OVR 및 ROVR은 EI, UCB, TS, PIMS, JES, MES를 포함한 최첨단(SOTA) 방법들과 대등하거나 이를 일관되게 능가하였다.
• 강건성: 휴리스틱 수정으로 인해 샘플 수가 증가함에 따라 지역 최적점에 빠지는 경향을 보이는 JES 및 MES와 달리, OVR 및 ROVR은 더 많은 MC 샘플과 함께 성능이 안정화되거나 개선되는 강건한 성능을 보여주었다.
• 비교: 이 방법들은 특히 일보 앞을 내다보는 전략들(MES, JES) 사이에서 우수한 성능을 보였으며, 이는 휴리스틱 근사 없는 분산 감소 접근법의 유효성을 입증한다.

의의 및 주장

본 논문은 OVR과 ROVR이 일보 앞을 내다보는 전략의 실질적인 효용성과 이론적 정당성 사이의 간극을 메운다고 주장한다.

• 이론적 진전: (흔히 위반되는) 부가성 가정에 의존하지 않고 소멸하는 회귀 상한을 제공함으로써, 본 연구는 BO의 이론적 문헌에 존재하는 중요한 공백을 해결한다.
• 실용적 유용성: 이 방법들은 사후 샘플링과 MC 근사만을 필요로 하여 계산적으로 효율적이며, 이는 KG나 ES 변형들과 같은 기존의 일보 앞을 내다보는 접근 방식보다 다루기 쉽다.
• 한계점: 저자들은 일보 앞을 내다보는 방법의 누적(cumulative) 회귀에 대한 분석은 여전히 미해결 과제로 남아 있다고 인정한다. 이는 UCB나 TS와 같은 밴딧 기반 알고리즘에 비해 순간적 회귀(instantaneous regret) 경계를 얻는 것이 어렵기 때문이다. 또한, 현재의 분석은 사후 샘플링 근사에서 발생하는 오차를 무시하며, 이는 향후 연구 과제로 남겨두었다.

요약하자면, 본 논문은 기존의 엔트로피 기반 접근 방식들이 겪는 휴리스틱 근사 문제를 피하면서, 소멸하는 단순 회귀를 달성하는 이론적으로 근거가 있고 계산적으로 다루기 쉬운 일보 앞을 내다보는 BO 방법을 제시한다.