Scalable Batch Bayesian Optimization Via Subspace Acquisition Functions

기술 요약: 부분 공간 획득 함수를 통한 확장 가능한 배치 베이지안 최적화

문제 정의

베이지안 최적화(Bayesian Optimization, BO)는 비용이 많이 드는 블랙박스 최적화 문제를 해결하기 위한 강력한 프레임워크입니다. 표준 BO는 한 번에 하나의 샘플 지점을 선택하는 순차적 방식을 사용하지만, 이 방식은 병렬 컴퓨팅 자원을 사용할 수 있을 때 비효율적입니다. 병렬성을 활용하기 위해서는 여러 샘플을 동시에 평가할 수 있는 배치 베이지안 최적화(Batch Bayesian Optimization) 알고리즘이 필요합니다.

그러나 기존의 배치 접근 방식은 배치 크기($q$)가 증가함에 따라 심각한 확장성 문제를 겪습니다:

• 다지점 기대 개선(Multi-point Expected Improvement, qEI): 이론적으로는 타당하지만, qEI를 최적화하는 것은 $d \times q$ 차원(여기서 $d$는 문제의 차원)의 탐색 공간을 포함합니다. $q$가 커짐에 따라 다변량 누적 분포 함수를 계산하는 비용이 증가하고 획득 함수를 최적화하는 난이도가 기하급級으로 높아져, qEI 및 그 변형들(예: FqEI, qLogEI)은 큰 배치 크기(일반적으로 $q > 10$)에서 실용적이지 못하게 됩니다.
• 휴리스틱 접근 방식 (예: Kriging Believer, Constant Liar, Local Penalization): 이러한 방법들은 배치 효과를 시뮬레이션하기 위해 "가짜" 지점이나 인위적인 페널티 함수에 의존하는 경우가 많습니다. 배치 크기가 증가함에 따라 이러한 인위적인 지점들의 축적이 가우시안 프로세스(GP) 모델의 정확도를 저하시켜, 잠재적으로 탐색 방향을 오도하고 최적화 효율을 떨어뜨릴 수 있습니다.
• 다중 목적 및 다중 모델 접근 방식: 여러 대리 모델을 훈련하거나 다중 목적 최적화 문제를 해결하는 방법들은 큰 배치 크기에서 잘 확장되지 않는 높은 계산 비용을 초래할 수 있습니다.

본 연구에서 다루는 핵심 과제는 차원의 저주나 모델 저하 없이 대규모 배치 평가를 위해 계산적으로 실행 가능하고 효과적인 배치 획득 전략을 설계하는 것입니다.

방법론

저자들은 기존의 획득 함수(특히 Expected Improvement를 포함하며, PI 및 UCB로도 적용 가능)를 무작위로 선택된 축 정렬 부분 공간(axis-aligned subspaces) 내에서 작동하도록 확장하는 **부분 공간 획득 함수(Subspace Acquisition Functions)**라는 새로운 접근 방식을 제안합니다.

핵심 개념: 부분 공간 기대 개선 (Subspace Expected Improvement, SSEI)

$q$개의 점을 전체 $d$차원 설계 공간에서 동시에 찾는 대신, 이 방법은 다음과 같이 수행합니다:

1. 부분 공간 선택: 축 정렬된 부분 공간들의 집합을 무작위로 선택합니다. $k$차원 축 정렬 부분 공간은 원래의 $d$개 차원 중 $k$개의 좌표를 선택하고 나머지 $d-k$개의 좌표를 현재 최적해($x_{min}$)의 값으로 고정함으로써 정의됩니다.
2. 국소 최적화: 각 선택된 부분 공간에 대해, 표준 획득 함수(예: EI)를 선택된 $k$개의 활성 변수에 대해서만 최적화합니다. 선택되지 않은 변수들은 $x_{min}$ 값으로 고정됩니다.
3. 배치 생성: 각 고유한 부분 공간에서 하나의 쿼리 지점을 선택합니다. 만약 요구되는 배치 크기 $q$가 사용 가능한 부분 공간의 수($N = 2^d - 1$)보다 크면, 부분 공간 다지점 기대 개선(Subspace Multi-Point Expected Improvement, SSqEI) 방식을 사용하여 단일 부분 공간 내에서 여러 점을 최적화합니다.

계산 프레임워크

제안된 알고리즘(Algorithm 1)은 다음과 같이 작동합니다:

• 초기화: 초기 샘플을 생성하고 GP 모델을 훈련합니다.
• 부분 공간 선택: 정수 $k \in [1, d]$를 무작위로 뽑은 다음, $k$개의 좌표 조합을 무작위로 선택하여 부분 공간을 형성합니다. 이는 모든 가능한 부분 공간을 열거하는 계산 비용을 피하기 위함입니다.
• 획득 최적화:
  • $q \le N$인 경우: $q$개의 서로 다른 부분 공간을 선택하고 각 부분 공간에서 하나의 점을 찾기 위해 표준 SSEI를 최적화합니다.
  • $q > N$인 경우: 가용한 $N$개의 부분 공간에 $q$개의 점을 분배합니다(SSqEI를 사용하여 단일 부분 공간 내에서 여러 점을 최적화).
• 평가: 생성된 $q$개의 점의 배치를 병렬로 평가합니다.
• 업데이트: 새로운 관측값으로 GP 모델을 업데이트하고 반복합니다.

획득 함수의 최적화 차원은 $d \times q$에서 약 $k \times 1$ (또는 SSqEI의 경우 $k \times q_i$)로 감소합니다. 여기서 기대 차원 $E[k] \approx d/2$입니다. 이는 획득 최적화의 복잡성을 크게 줄여줍니다.

주요 기여

1. 확장 가능한 배치 전략: 본 논문은 획득 함수 최적화의 지수적 복잡성을 피하면서, 배치를 독립적이거나 저차원인 부분 공간 최적화로 분리함으로써 대규모 배치 크기로 베이지안 최적화를 확장하는 방법을 소개합니다.
2. 단순성 및 범용성: 이 방식은 추가적인 하이퍼파라미터를 요구하지 않으며, 다양한 획득 함수(EI, PI, UCB에 적용 가능함을 입증)에 적용할 수 있습니다. 개념적으로 매우 단순합니다: "부분 공간을 추출하고, 국소적으로 최적화하며, 결합한다."
3. 차원에 대한 강건성: 현재의 최적해($x_{min}$)에 고정된 축 정렬 부분 공간 내에서 탐색을 제한함으로써, 이 방법은 무작위 부분 공간 선택을 통한 탐색(Exploration)과 국소 탐색(Exploitation) 사이의 균형을 자연스럽게 맞추며, 고차원 공간에서 특히 효과적입니다.

실험 결과

저자들은 제안된 방법(SSEI)을 60개의 합성 벤치마크 문제(GPMean, SumSquares, Rosenbrock 등)에 대해 차원 $d \in \{2, 4, 8, 10, 20, 30\}$ 및 배치 크기 $q \in \{1, 2, 4, 8, 16, 32, 64, 128\}$를 설정하여 10개의 최신 배치 알고리즘(qEI, qLogEI, FqEI, TuRBO, MSMR, MACE, PEI, EIMI, KB, Random Search 포함)과 비교 평가했습니다.

• 순차적 BO와의 성능 비교: $q=1$일 때, SSEI는 저차원 문제에서는 표준 EI와 유사한 성능을 보이지만, 고차원 문제($d \ge 8$)에서는 EI를 크게 능가합니다. 저자들은 이를 순차적 EI가 고차원에서 획득 함수를 최적화하는 데 어려움을 겪는 반면, SSEI의 국소 부분 공간 탐색이 획득 함수의 더 나은 지역 최적해를 찾아내기 때문이라고 설명합니다.
• 배치 크기에 따른 확장성:
  • 중소규모 배치 ($q \le 32$): SSEI는 함수 평가 횟수로 측정했을 때 다른 배치 방법들과 대등하거나 더 나은 성능을 유지하면서, 실제 실행 시간(Wall-clock time, 반복 횟수) 측면에서 거의 선형적인 속도 향상을 달와냅니다.
  • 대규모 배치 ($q = 128$): SSEI는 이 규모에서 실패하거나 성능이 크게 저하되는 qEI 변형들을 포함하여 모든 비교 대상 배치 알고리즘을 압도합니다. 제안된 방법은 더 빠르게 수렴하고 더 나은 최종 해를 찾습니다.
• 특정 알고리즘과의 비교:
  • vs. qEI/qLogEI/FqEI: SSEI는 $d$와 $q$가 증가함에 따라 $d \times q$ 차원의 저주를 피하기 때문에 이들보다 우수합니다.
  • vs. TuRBO: SSEI는 TuRBO와 경쟁력 있는 성능을 보이며, 저~중차원에서는 종종 TuRBO를 능가하고 고차원에서는 대등한 성능을 보입니다.
  • vs. 페널티 기반 방법 (PEI, EIMI, KB): SSEI는 배치 크기가 커짐에 따라 모델 저하를 겪는 이러한 방법들을 지속적으로 앞섭니다.
  • 범용성: 부분 공간 접근 방식은 PI(SSPI) 및 UCB(SSUCB)에도 성공적으로 적용되어, 각각의 다지점 대응물(qPI, qUCB)에 비해 유사한 성능 향상을 보여주었습니다.

의의 및 주장

본 논문은 제안된 부분 공간 획득 함수가 배치 베이지안 최적화를 위한 단순하고 효율적이며 확장 가능한 솔루션을 제공한다고 주장합니다. 주요 의의는 기존 방법들이 가진 계산적 병목 현상이나 정확도 저하 없이 대규모 병렬 컴퓨팅 자원(큰 $q$)을 사용할 수 있게 한다는 점에 있습니다.

저자들은 다음을 강조합니다:

• 이 방법은 획득 함수 최적화에서의 차원의 저주를 효과적으로 완화합니다.
• 무작위 부분 공간 선택(탐색)과 변수 고정(국소적 활용) 사이의 실용적인 절충안을 제공합니다.
• "플러그 앤 플레이(Plug-and-play)" 방식의 확장으로서 다양한 획득 함수에 적용 가능하며, 병렬 평가가 가능한 고비용 최적화 문제에서 특히 가치가 높습니다.

결론적으로, 여러 서로 다른 부분 공간에서 쿼리 지점을 선택하는 전략은 대규모 배치 베이지안 최적화를 위한 유망한 전략이며, 현재의 최첨단 방식들과 비교하여 수렴 속도와 해의 품질 면에서 상당한 개선을 제공한다는 것을 본 연구는 보여줍니다.