The Approximation Ratio for the Risk of Myopic Bayesian Active Learning for Linear Regression

기술적 요약: 선형 회귀를 위한 탐욕적 베이지안 능동 학습의 리스크에 대한 근사 비율

문제 정의
본 연구는 예산 제약 조건 하에서 베이지안 선형 회귀를 위한 최적의 데이터 선택이라는 근본적인 문제를 다룹로다. 구체적으로, $n$개의 후보 입력 벡터 집합 $V = \{v_i\}_{i=1}^n \subset \mathbb{R}^d$와 사전 정밀도 행렬(prior precision matrix) $\Lambda$가 주어졌을 때, 사후 파라미터 추정 리스크를 최소화하는 크기 $k$의 부분 집합 $S$를 선택하는 것이 목표입니다. 리스크는 사후 공분산 행렬의 트레이스(trace)로 정의됩니다:
$$f(S) := \text{tr}\left( \left( \Lambda + \sum_{i \in S} v_i v_i^\top \right)^{-1} \right)$$
능동 학습(active learning)의 맥락에서, 이는 알고리즘이 장기적인 계획 대신 일보 앞을 내다보는 최적의 선택으로 대체하여 즉각적인 리스크 감소를 최소화하는 "마이오픽(myopic, 근시안적)" 설정에 해당합니다. 이 집합 함수를 최적화하는 것은 NP-hard이지만, 그리디(greedy) 알고리즘은 매 단계에서 가장 큰 리스크 감소를 가져오는 점을 반복적으로 추가하는 표준적인 휴리스틱으로 사용됩니다.

방법론 및 이론적 프레임워크
본 논문은 분석의 초점을 기존 연구들이 다루었던 '리스크 감소량'에서 리스크 함수의 '역수(reciprocal)'인 $F_{\text{reciprocal}}(S) = 1/f(S)$로 전환함으로써 그리디 알고리즘의 성능을 분석합니다.

1. 근사 서브모듈성(Approximate Submodularity): 저자들은 $F_{\text{reciprocal}}$이 근사적으로 서브모듈(submodular)임을 입증합니다. 이들은 Das와 Kempe [2018]가 도입한 서브모듈성 비율($\gamma$) 개념을 활용합니다. 리스크 감소 함수의 서브모듈성을 제한했던 기존 분석들과 달리, 본 연구는 역수 리스크의 서브모듈성 비율에 대한 하한을 도출합니다.
2. 핵심 파라미터 (MILS): 본 연구의 핵심적인 기여는 **최대 초기 레버리지 스코어(Maximum Initial Leverage Score, MILS)**라는 문제 의존적 파라미터를 식별한 것입니다. 이는 다음과 같이 정의됩니다:
   $$h_{\max} = \max_{i \in [n]} v_i^\top \Lambda^{-1} v_i$$
   저자들은 역수 리스크의 서브모듈성 비율이 $(1 + h_{\max})^{-1}$에 의해 제한됨을 증명합니다.
3. 근사 보장(Approximation Guarantee): 도출된 서브모듈성 비율과 근사적으로 서브모듈인 함수의 그리디 최대화에 관한 기존 이론적 결과들을 결합하여, 최적의 리스크 대비 그리디 알고리즘의 리스크에 대한 상한을 도출합니다.

주요 기여 및 결과

• 최초의 상수 계수 리스크 보장: 본 논문은 A-최적(A-optimal) 및 V-최적(V-optimal) 실험 설계에서 그리디 알고리즘이 달성하는 리스크 자체(리스크 감소량이 아닌)에 대한 최초의 상수 계수 근사 보장을 제공합니다. 근사 비율은 다음과 같이 증명되었습니다:
  $$\frac{f(S_{\text{greedy}})}{f(S^*)} \leq h_{\max} + \frac{1}{1 - 1/e} \approx h_{\max} + 1.582$$
  이 결과는 그리디 알고리즘의 성능이 최대 초기 레버리지 스코어에 선형적으로 비례함을 보여줍니다.

• 경계의 타이트함(Tightness of the Bound): 저자들은 하다마르 행렬(Hadamard matrices)을 이용한 명시적인 문제 사례 군을 구성하여 도출된 경계가 절대 상수 범위 내에서 타이트함을 입증합니다. 그리디 알고리즘의 리스크가 최적의 리스크보다 약 $h_{\max}$ 배만큼 더 커지는 사례가 존재함을 보여줌으로써, $h_{\max}$에 대한 의존성이 분석의 부산물이 아니라 필수적인 것임을 확인했습니다.

• 기존 경계의 한계: 수치 시뮬레이션을 통해, 본 논문은 리스크 감소(예: Bian et al. [2017], Chamon and Ribeiro [2017])에 기반한 기존의 근사 보장들이, 특히 초기 리스크 $f(\emptyset)$가 큰 경우 적은 예산에서도 무용해질(vacuous, 유용한 하한을 제공하지 못함) 수 있음을 보여줍니다. 반면, 새로운 경계는 유효한 정보를 유지합니다.

의의 및 주장
본 논문은 마이오픽 능동 학습에 대한 이론적 이해의 중요한 간극을 메웠다고 주장합니다. 그리디 알고리즘이 최적의 리스크 감소량의 상수 비율을 달라는 것은 잘 알려져 있지만, 그리디 알고리즘이 최종 리스크 자체에 대해 상수 계수 근사를 달성하는지는 이전에는 알려져 있지 않았습니다.

저자들은 거의 모든 실용적인 베이지안 능동 학습 알고리즘이 다단계 계획의 복잡성을 피하기 위해 마이오픽(일보 앞을 내다보는) 계획에 의존한다는 점에서, 이 결과가 능동 학습에 있어 근본적이라고 주장합니다. 본 연구는 베이지안 선형 회귀의 경우, 이러한 마이오픽 전략이 최대 초기 레버리지 스코어가 작을 때 충분히 계획된 전략만큼이나 잘 작동한다는 최초의 이론적 보증을 제공합니다. 저자들은 이 연구를 적응적 선택(adaptive selection)이 오프라인 선택(offline selection)과 동일하지 않은 다른 모델들에 대한 향후 분석의 토대로 제시합니다.