技術要約：バギングはVCクラスを線形サンプル複雑度でロバストに学習する

問題設定

本論文は、テスト時における敵対的例（adversarial examples）に対してロバストな予測器を学習するという根本的な課題に取り組んでいる。インスタンス空間を $\mathcal{X}$、ラベル空間を $\mathcal{Y} = \{-1, 1\}$、および摂動写像 $U: \mathcal{X} \to 2^\mathcal{X}$ によって定義される敵対者を考える。目標は、未知の分布 $P$ に対して、以下の集団ロバストリスク（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}$ の学習に焦点を当てている。先行研究では、標準的なPAC学習の設定ではVCクラスは学習可能である一方、敵対的にロバストな学習においては重大な障壁があることが示されている。具体的には、Montasser, Hanneke, and Srebro [2019] は以下のことを示した：

1. プロパー学習（出力を $\mathcal{F}$ 内に限定すること）は、VC次元が1であるクラスであっても失敗する場合がある。
2. インプロパー学習は可能であるが、既知の最良のサンプル複雑度の境界は $d$ に対して指数関数的であった。
3. 既存のインプロパーなアルゴリズムは計算効率が悪く、$O(nd)$ 回のロバスト経験リスク最小化（RERM）オラクル呼び出しを必要とし、過大なオーバーヘッドを伴う。

中心となる問いは、サンプル効率的（$d$ に対して線形）かつオラクル効率的（RERMへの呼び出し回数が少ない）なアルゴリズムを設計できるかどうかである。

手法

著者は、バギング（ブートストラップ集約）とロバスト経験リスク最小化（RERM）を組み合わせた、シンプルなインプロパー学習アルゴリズムを提案している。

アルゴリズム（バギング・ロバストERM）

サイズ $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$ までのプレフィックスから、重複を許してサイズ $t$ のブートストラップ・データセット $S'_i$ を一様にサンプリングする。
   • 予測器 $\hat{f}_{S'_i} \in \mathcal{F}$ を得るために、RERMオラクルを $S'_i$ 上で実行する。
3. $N$ 個の予測器の多数決 $\text{MAJ}(\hat{f}_{S'_1}, \dots, \hat{f}_{S'_N})$ を出力する。

理論的アプローチ

解析は、従来のサンプル圧縮の議論とは異なる手法を用いている。代わりに、ロバストリスクに特化したリーブ・ワン・アウト（leave-one-out）解析を採用している：

1. RERMの分布： 著者は、ランダムな部分集合で訓練されたRERMによる誤差の分布を分析している。ランダムなテスト例 $(X, Y)$ と任意の摂動 $Z \in U(X)$ に対して、RERMが誤分類する割合の期待値が $\tilde{O}(d/n)$ と小さいことを証明している。
2. リーブ・ワン・アウト境界： この期待値を経験分布に適用することで、「フル・バギング」予測器（あらゆる可能なブートストラップの理想的な平均）のロバストリスクに関する境界を確立している。
3. スパース化（Sparsification）： フル・バギング予測器は計算量的に困難であるため、著者はモランとイェフダヨフ（Moran and Yehudayoff [2016]）の手法を用いて、独立した $N = O(d^\star)$ 個のブートストラップサンプルを用いて集約投票を近似する。このステップにより、オラクル複雑さが双対VC次元 $d^\star$ に直接結び付けられる。

主要な貢献と結果

1. 上界：線形サンプル複雑度

主要な結果（定理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)$ の計算オーバーヘッドしか発生しない。
• アグノスティック設定： この実現可能（realizable）な結果をアグノスティック設定からの還元（Montasser et al. [2019]）と組み合わせることで、サンプル複雑度 $\tilde{O}(\sqrt{d/n})$ およびオラクル複雑度 $O(d^\star \log n)$ を持つアグノスティック学習器を導出している。

2. 下界：双対VC次元の必要性

本論文は、オラクル複雑度における双対VC次元 $d^\star$ への依存性が回避不可能であることを証明している（定理2）。

• 結果： VC次元 $d$ と双対VC次元 $d^\star = 2^{d+1}-1$ を持つクラスが存在し、そのようなクラスでは、いくら訓練サンプルを提供しても、RERMオラクルへの呼び出しが $d^\star - 1$ 回未満である限り、いかなるアルゴリズムもロバストに学習できない。
• 示唆： 標準的なPAC学習では $O(\log n)$ または定数回のERM呼び出しで十分であるが、敵対的ロバスト学習には本質的に $\Omega(d^\star)$ 回のオラクルクエリが必要となる。これは、標準的な学習とロバストな学習の間の根本的な複雑さの分離を浮き彫りにしている。

3. 技術的特性

これらの結果は、Montasser, Hanneke, and Srebro [2022] によって提案された洗練された複雑度尺度 $\dim(\mathcal{F}, U)$ が $d$ によって抑えられることを意味しており、この尺度が大幅に大きくなり得るという予想を解決している。

意義と主張

本論文は、計算効率の高いロバストPAC学習のための「レシピ」を提供すると主張している。バギング・ヒューリスティックをRERMと組み合わせることで最適なサンプル複雑度を達成できることを示すことで、本研究は理論的なロバスト性と実用的なアルゴリズムの効率性の間の溝を埋めている。

本論文の貢献に関する主な主張は以下の通りである：

• 指数関数的な改善： $d$ に関するサンプル複雑度を指数関数的から線形へと移行させた。
• オラクル効率： オラクル呼び出しを $O(nd)$から$O(d^\star)$ へと削減し、RERMが計算量的に扱いやすいクラスにおいて、このアプローチを現実的なものにした。
• 根本的な限界： 双対VC次元が、標準的な学習におけるVC次元の役割とは対照的に、ロバスト学習におけるオラクル効率の正しい障壁であることを確立した。
• 実用的な関連性： アルゴリズムの並列可能性と、標準的なRERMオラクル（これらは実務で使用されている敵対的訓練のヒューリスティクスに対応する）への依存性は、これらの理論的な改善が現代のディープラーニングの文脈に直接適用可能であることを示唆している。

著者は、このアルゴリズムはインプロパー（出力が単一の関数 $\mathcal{F}$ ではなく多数決を出力する）であるが、これらの境界を達成するためにはこれが必要であると述べており、これはロバストな設定におけるプロパー学習とインプロパー学習の区別を反映している。本研究は、インプロパーな学習者を受け入れることで、双対VC次元を活用し、アルゴリズムの効率性と証明可能なロバスト性を統一している。