기술 요약: 배깅은 VC 클래스를 선형 샘플 복잡도로 강건하게 학습한다

문제 정의

본 논문은 테스트 시점에 적대적 예제(adversarial examples)에 대해 강건한 예측기를 학습하는 근본적인 과제를 다룬다. 인스턴스 공간 $\mathcal{X}$, 레이블 공간 $\mathcal{Y} = \{-1, 1\}$, 그리고 섭동 맵(perturbation map) $U: \mathcal{X} \to 2^\mathcal{X}$로 정의된 적대자를 고려할 때, 목표는 다음의 모집단 강건 리스크(population robust risk)를 최소화하는 예측기 $\hat{f}$를 학습하는 것이다:
$$R_U(\hat{f}; P) = \mathbb{E}_{(X,Y) \sim P} \left[ \sup_{Z \in U(X)} \mathbb{1}\{\hat{f}(Z) \neq Y\} \right]$$
여기서 $P$는 $\mathcal{X} \times \mathcal{Y}$ 상의 미지의 분포이다.

본 논문은 유한한 베이퍼닉-체르보넨키스(VC) 차원 $d$를 갖는 함수 클래스 $\mathcal{F}$의 학습 가능성에 초점을 맞춘다. 기존 연구들은 VC 클래스가 표준 PAC 설정에서는 학습 가능하지만, 적대적으로 강건한 학습에서는 상당한 난관에 봉착한다는 점을 밝혀냈다. 구체적으로, Montasser, Hanneke, Srebro [2019]는 다음과 같은 사실을 보여주었다:

1. 고유 학습(Proper learning) (출력을 $\mathcal{F}$ 내로 제한하는 것)은 VC 차원이 1인 클래스에 대해서도 실패할 수 있다.
2. **부적절 학습(Improper learning)**은 가능하지만, 알려진 최선의 샘플 복잡도 상한은 $d$에 대해 지수적이다.
3. 기존의 부적절 알고리즘들은 $O(nd)$번의 강건 경험적 위험 최소화(Robust Empirical Risk Minimization, RERM) 오라클 호출을 요구하며, 이는 과도한 오버헤드를 동반하여 계산 효율성이 떨어진다.

핵심 질문은 샘플 효율적( $d$에 대해 선형)이면서 동시에 오라클 효율적(RERM 호출 횟수가 적은)인 알고리즘을 설계할 수 있는가 하는 점이다.

방법론

저자는 **배깅(Bagging, Bootstrap Aggregation)**과 **강건 경험적 위험 최소화(RERM)**를 결합한 단순한 부적절 학습 알고리즘을 제안한다.

알고리즘 (Bagging Robust ERMs)

크기가 $n$인 훈련 세트 $S$, 신뢰 매개변수 $\delta$, 그리고 RERM 오라클 $\hat{f}$가 주어졌을 때:

1. 부트스트랩 샘플의 개수 $N = O(d^\star + \log(1/\delta))$를 설정한다. 여기서 $d^\star$는 클래스 $\mathcal{F}$의 **이중 VC 차원(dual VC dimension)**이다.
2. 각 $i \in \{1, \dots, N\}$에 대하여:
   • 특정 범위 $J_n = \{n/4, \dots, n-1\}$에서 무작위 크기 $t$를 선택한다.
   • $S$의 길이 $t$인 접두사(prefix)로부터 중복 허용 추출(with replacement)을 통해 크기가 $t$인 부트스트랩 데이터셋 $S'_i$를 샘플링한다.
   • RERM 오라클을 $S'_i$에 실행하여 예측기 $\hat{f}_{S'_i} \in \mathcal{F}$를 얻는다.
3. $N$개 예측기의 다수결(majority vote)인 $\text{MAJ}(\hat{f}_{S'_1}, \dots, \hat{f}_{S'_N})$을 출력한다.

이론적 접근 방식

분석은 기존의 샘플 압축(sample-compression) 논의와는 다른 방향으로 전개된다. 대신, 강건 리스크에 맞춤화된 리브-원-아웃(leave-one-out) 분석을 채택한다:

1. RERMs에 대한 분포: 저자는 무작위 부분 집합에서 학습된 RERM들의 오류 분포를 분석한다. 이들은 임의의 테스트 예시 $(X, Y)$와 임의의 섭동 $Z \in U(X)$에 대해, RERM들이 $Z$를 오분류하는 비율이 기대값 측면에서 작음($\tilde{O}(d/n)$)을 증명한다.
2. 리브-원-아웃 경계: 이 기댓값을 경험적 분포에 적용함으로써, "전체 배깅(full bagging)" 예측기(모든 가능한 부트스트랩의 이상적인 평균)에 대한 강건 리스크 경계를 설정한다.
3. 희소화(Sparsification): 전체 배킹 예측기는 다루기 까다로우므로, 저자는 $N = O(d^\star)$개의 독립적인 부트스트랩 샘플만을 사용하여 집계 투표를 근사하는 희소화 기법(Moran and Yehudayoff [2016])을 사용한다. 이 단계는 오라클 복잡도를 이중 VC 차원 $d^\star$와 직접 연결한다.

주요 기여 및 결과

1. 상한(Upper Bound): 선형 샘플 복잡도

주요 결과(정리 1)는 VC 클래스가 VC 차원 $d$에 대해 선형인 샘플 복잡도를 갖는 적대적 강건 학습이 가능하다는 것을 확립한다.

• 샘플 복잡도: $O(d/\epsilon + \frac{1}{\epsilon}\log(1/\delta))$. 이는 기존의 $O(\exp(d))$ 상한에 비해 지수적인 개선을 제공한다.
• 오라클 복잡도: 알고리즘은 $N = O(d^\star)$번의 RERM 오라클 호출을 수행한다.
• 계산 효율성: 알고리즘은 병렬 처리가 가능하며(기존의 부스팅 기반 접근법과 달리), $O(d^\star n)$의 계산 오버헤드만을 발생시킨다.
• 애그노스틱(Agnostic) 설정: 이 실현 가능한(realizable) 결과를 애그노스틱 설정으로부터의 환원(reduction) 방식(Montasser et al. [2019])과 결래하여, 저자는 샘플 복잡도 $\tilde{O}(\sqrt{d/n})$ 및 오라클 복잡도 $O(d^\star \log n)$을 갖는 애그노스틱 학습기를 도출한다.

2. 하한(Lower Bound): 이중 VC 차원의 필연성

본 논문은 오라클 복잡도에서 이중 VC 차원 $d^\star$에 대한 의존성이 피할 수 없음을 증명한다(정리 2).

• 결과: VC 차원이 $d$이고 이중 VC 차원이 $d^\star = 2^{d+1}-1$인 클래스들이 존재하며, 이러한 클래스들에 대해서는 아무리 많은 훈련 샘플이 주어지더라도 RERM 오라클을 $d^\star - 1$번 미만으로 호출하는 모든 알고리즘은 강건하게 학습하는 데 실패한다.
• 시사점: $O(\log n)$ 또는 상수 번의 ERM 호출만으로 충분한 고전적 PAC 학습과 달리, 적대적 강건 학습은 본질적으로 $\Omega(d^\star)$의 오라클 쿼리를 요구한다. 이는 표준 학습과 강건 학습의 복잡도 사이의 근본적인 차이를 강조한다.

3. 기술적 특성

이 결과들은 Montasser, Hanneke, Srebro [2022]가 제안한 정교한 복잡도 척도 $\dim(\mathcal{F}, U)$가 $d$에 의해 유계(bounded)되어 있음을 시사하며, 이 척도가 훨씬 더 클 수 있다는 가설을 해결한다.

의의 및 주장

본 논문은 계산적으로 효율적인 강건 PAC 학습을 위한 "레시피"를 제공한다고 주장한다. 단순한 배깅 휴리스틱과 RERM을 결합함으로써 최적의 샘플 복잡도를 달성할 수 있음을 보여줌으로써, 본 연구는 이론적 강건성과 실제적인 알고리즘 효율성 사이의 간극을 메운다.

논문의 기여에 관한 주요 주장은 다음과 같다:

• 지수적 개선: $d$에 대한 샘플 복잡도를 지수적에서 선형으로 전환하였다.
• 오라클 효율성: 오라클 호출을 $O(nd)$에서$O(d^\star)$로 줄여, RERM이 계산적으로 다루기 쉬운 클래스들에 대해 접근 가능하게 만들었다.
• 근본적 한계: 이중 VC 차원이 표준 학습에서의 VC 차원과 대조되는, 오라클 효율성을 결정짓는 올바른 장벽임을 확립하였다.
• 실용적 관련성: 알고리즘의 병렬 가능성과 표준 RERM 오라클(실제 현장에서 사용되는 적대적 훈련 휴리스틱에 대응함)에 대한 의존성은 이러한 이론적 개선이 현대 딥러닝 문맥에 직접 적용될 수 있음을 시사한다.

저자는 비록 알고리즘이 부적절 학습(improper learner)이지만(단일 함수가 아닌 다수결을 출력하므로), 이를 통해 이러한 상한을 달성하는 것이 필수적이라고 언급하며, 이는 강건한 설정에서의 고유 학습과 부적절 학습의 구분을 반영한다. 이 연구는 이중 VC 차원을 활용하여 부적절 학습자를 수용함으로써 알고리즘 효율성과 증명 가능한 강건성을 통합한다.