Cost-aware Stopping for Bayesian Optimization

Motivation

• Known: 기존 Bayesian optimization의 stopping rule은 크게 heuristic한 방식(고정 반복 수, 개선 정체 시 정지)과 이론적으로 뒷받침되지만 evaluation cost를 고려하지 않고 simple regret만 최적화하도록 설계된 방식(예: UCB-LCB 기반 regret bound rule)으로 나뉜다.
• Gap: 비용이 큰 상황에서 기존 stopping rule들은 불필요한 평가를 방지한다는 보장이 없으며, cost-aware acquisition function인 PBGI와 LogEIPC는 아직 adaptive stopping 세팅에서 연구된 바가 없다는 것이 연구 공백이다.
• Why: 비용을 고려한 stopping은 자동화된 머신러닝, 과학적 발견 등 실제 응용에서 평가 비용과 해의 질 사이의 트레이드오프를 관리하는 데 필수적이지만 실무적으로 충분히 탐구되지 않은 문제이며, 원칙적인 이론적 보장을 갖춘 규칙은 클라우드 컴퓨팅 비용 등 실질적 비용 절감에 직결된다.
• Approach: Pandora's Box 이론에 기반한 cost-aware stopping rule을 제안하고, 이를 expected improvement 설계 원리로도 확장하여 PBGI 및 LogEIPC acquisition function과 결합했을 때 성립하는 통합적이고 원칙적인 프레임워크를 제시한다.

Achievement

Figure 2. Cost-adjusted simple regret across acquisition-stopping

1. 새로운 cost-aware stopping rule 제안: Pandora's box 이론에서 유도된 adaptive stopping rule을 제시하며, 이는 expected improvement 설계 원리로도 자연스럽게 확장되어 고전적 세팅과 cost-aware 세팅 모두에 적용 가능한 통합 프레임워크를 구축했다.
2. 이론적 보장 확보: Theorem 3.2를 통해 제안한 stopping rule이 PBGI 또는 LogEIPC와 결합될 때 expected cost-adjusted regret에 대한 상한을 만족함을 증명했으며, 이는 Bayesian optimization의 adaptive stopping rule에 대한 최초의 이러한 유형의 이론적 보장이다.
3. 경험적 검증: synthetic task와 hyperparameter optimization, neural architecture size search를 포함한 실제 benchmark에서 다양한 acquisition-function–stopping-rule 조합을 체계적으로 비교하여, 제안한 stopping rule과 PBGI 또는 LogEIPC의 결합이 대체로 다른 조합과 대등하거나 더 우수한 cost-adjusted simple regret을 달성함을 보였다.

How

Figure 2. Cost-adjusted simple regret across acquisition-stopping

• PBGI acquisition function의 threshold 개념(expected improvement가 cost와 같아지는 지점 g)을 stopping 기준으로 확장하여, 남은 평가로부터 기대되는 개선이 cost 이하로 떨어지면 정지하는 규칙을 설계.
• 기존 EI 기반 stopping rule(Nguyen et al., 2017; Zhou et al., 2024)의 heuristic threshold를 evaluation cost per sample로 대체함으로써, cost-aware 세팅으로 원칙적으로 확장하고 PBGI stopping rule과 동등함을 증명.
• cost-per-sample 및 expected budget-constrained 두 가지 cost-aware Bayesian optimization 정식화(formulation) 모두에 stopping rule을 적용 가능하도록 설계.
• Theorem 3.2를 통해 제안된 stopping rule과 PBGI/LogEIPC acquisition function의 조합이 expected cost-adjusted simple regret에 대한 상한을 만족함을 이론적으로 증명.
• synthetic 함수, hyperparameter optimization, neural architecture size search 등 다양한 benchmark에서 PBGI, LogEIPC, LCB, TS 등 여러 acquisition function과 다양한 stopping rule(제안 규칙 포함)의 조합을 비교 실험.

Originality

• Pandora's Box decision principle과 PBGI acquisition function을 stopping 문제로 확장한 최초의 시도로, 기존에는 acquisition function 선택에만 활용되던 이론을 stopping rule 설계에 적용했다.
• 기존 EI 기반 stopping rule의 heuristic threshold 파라미터를 evaluation cost로 대체함으로써 별도의 튜닝 없이 원칙적인 threshold를 도출하고, 이를 PBGI stopping rule과 동치임을 증명하여 EI와 PBGI 두 설계 원리를 통합하는 이론적 연결고리를 제시했다.
• cost-adjusted simple regret에 대한 상한을 제공하는 최초의 adaptive stopping rule 이론적 보장을 제시했다는 점에서 독창적이다.

Limitation & Further Study

• KG(knowledge gradient)나 MES(max-value entropy search)처럼 value-of-information 또는 entropy search 원리에서 유도된 acquisition function은 본 논문의 stopping rule과 자연스럽게 결합되지 않으며, 각자의 맞춤형 stopping rule이 필요하다는 한계가 있다.
• 이론적 보장은 GP(Gaussian process) 기반 모델과 특정 acquisition function 조합(PBGI, LogEIPC)에 한정되어 있어, 다른 대리 모델이나 acquisition function으로의 일반화 가능성은 추가 연구가 필요하다.
• 비용 함수 c(x)가 알려져 있거나 관측 가능하다는 가정에 의존하는데, 실제로는 비용을 사전에 정확히 알기 어려운 상황이 많아 unknown cost 세팅에서의 성능 검증이 부족하다.
• 실험이 synthetic task와 제한된 benchmark(hyperparameter optimization, neural architecture size search)에 국한되어 있어, 더 다양한 실제 응용 도메인에서의 검증이 후속 연구로 필요하다.

Evaluation

총평: Bayesian optimization의 실용적이지만 이론적으로 미흡했던 cost-aware stopping 문제에 대해 Pandora's Box 이론에 기반한 원칙적 해법을 제시하고 이론적 보장까지 갖췄다는 점에서 견고하고 의미 있는 기여이며, 다양한 benchmark에서의 실증적 우수성도 함께 확인된 완성도 높은 연구이다.