Majority-of-Three is Optimal

技術要約：3分の多数決（Majority-of-Three）の最適性

問題設定
本論文は、実現可能な設定（realizable setting）におけるPAC学習の最適なサンプル複雑性を決定するという中心的な問題に取り組んでいる。Hanneke [Han16]（Simon [Sim15] の研究に基づき）によって最適学習器の存在は確立されているが、その結果得られるアルゴリズムと確率的解析は複雑である。具体的かつ初等的な最適学習器の候補として、「3分の多数決（majority-of-three）」ルールがある。これは、訓練サンプルを3つの独立したブロックに分割し、各ブロックに対して一貫した分類器（consistent classifier）を学習させ、その多数決を出力するというものである。先行研究 [AAHLZ24] は、このルールが期待値において最適（optimal）な境界を達成し、また（二重対数因子 $\log \log(\min\{n/d, 1/\delta\})$ を除いて）準最適なPAC境界を達成することを証明した。[AAHLZ24] の著者らは、多数決ルールがこれらの余分な因子なしに最適なPAC境界を達成するという予想を立てた。本論文は、この予想の証明を提供する。

手法
本証明は、サイズ $m = n/3$ の独立したブロック $S_i$ で学習された一貫した分類器 $\hat{f}_i$ に対する、多数決分類器 $Maj(\hat{f}_1, \hat{f}_2, \hat{f}_3)$ の誤差の、高確率上界を確立するものである。

1. 重複モーメントへの還元（Reduction to Overlap Moments）:
   多数決の誤差は、少なくとも2つの分類器が点 $x$ を誤分類する場合にのみ発生する。$i$ 番目の分類器の誤差集合を $E_i = \{x : \hat{f}_i(x) \neq f^\star(x)\}$ とすると、総誤差は以下のペアワイズな積集合の和によって抑えられる：
   $$\text{err}_P(Maj) \leq P(E_1 \cap E_2) + P(E_2 \cap E_3) + P(E_1 \cap E_3).$$
   証明では、これらの積集合確率の $L_q$ モーメント、具体的には $\|P(E_1 \cap E_2)\|_{L_q}$ の評価に焦点を当てる。

2. 主要な技術的ツール：命題 2.2（Proposition 2.2）:
   議論の核となるのは、サイズ $m$ の2つの独立したサンプル $S$ と $T$ から生じる誤差集合の重なりに関するモーメント境界を与える命題 2.2である。VC次元 $d$ を持つVCクラス $\mathcal{C}$ と、決定論的一貫性選択子（deterministic consistent selector）$A$（ただし $A(S) \cap S = \emptyset$）に対し、この命題は以下を述べる：
   $$\|P(A(S) \cap A(T))\|_{L_q} \leq 62400 \frac{d + q}{m}.$$
   この結果は、Simon [Sim15] の重なり推定に類似しているが、入れ子状（nested）の構造ではなく、独立したサンプルに適用される。この独立性は、従来の入れ子構造の解析に見られた二重対数因子を回避するために極めて重要である。

3. 再帰的分解と条件付き確率（Recursive Decomposition and Conditional Probabilities）:
   命題 2.2 を証明するために、著者らは $q$ 個の独立したテスト点 $X = (X_1, \dots, X_q)$ を導入することで、重なりの $q$ 次モーメントを分析する。モーメントは $\mathbb{E}_X [p_q(X)^2]$ と書き換えられる。ここで $p_q(X) = P(X \subseteq A(S))$ である。
   連鎖律による分解を用いて、$p_q(X)$ は条件付き包含確率の積として表現される：
   $$p_q(X) = \prod_{\ell=1}^q \alpha_{X_{<\ell}}(X_\ell), \quad \text{ここで } \alpha_{z}(x) = P(x \in A(S) \mid z \subseteq A(S)).$$
   証明は、これらの条件付き確率の裾（tail）に関する境界である補題 3.1に依拠している。これは、条件付きイベント $E_z$（確率 $p_z$）に対し、条件付き包含確率 $\alpha_z(X)$ が閾値 $a$ を超える確率が以下で抑えられることを示している：
   $$P(\alpha_z(X) > a) \leq \frac{160}{am} \left( d \log \frac{e}{a} + \log \frac{e}{p_z} \right).$$
   この境界は、VC次元の項を膨張させることなく、条件付きイベントの「希少性」を制御する。

4. 再帰的議論（Recursive Argument）:
   著者らは、二乗された条件付き確率と対数項を含む重み付き関数 $M_k$ を定義する。彼らは $M_k \leq \frac{960}{m} M_{k-1}$ という再帰式を確立する。この再帰を $k=1$ から $q$ まで反復することで、目的の $q$ 次モーメントの境界が得られ、その後、 $q = \lceil \log(1/\delta) \rceil$ としたときのマルコフの不等量を用いて高確率境界へと変換される。

主要な貢献と結果

• 最適性の証明: 本論文は、実現可能なPAC設定において、多数決の3のルールが最適なサンプル複雑性を達成することを証明している。具体的には、任意の分布 $P$、ターゲット $f^\star$、および信頼度 $\delta$ に対し、以下が成立する：
  $$P\left( \text{err}_P(Maj(\hat{f}_1, \hat{f}_2, \hat{f}_3)) \leq 107 \frac{d + \log(1/\delta)}{n} \right) \geq 1 - \delta.$$
  これは、普遍的な定数を除いて、古典的な下界 [EHKV89] と一致する。
• 解析の簡素化: 本証明は、先行する最適学習器（Hanneke [Han16] や Larsen のバギング解析 [Lar23] など）のアルゴリズム構造と確率的解析を簡素化する。これらは、複雑な入れ子状のサンプル構造と、それに伴う二重対数因子の必要性を排除している。
• 入れ子から独立へ: 本研究は、独立したブロックを使用すること（入れ子状のサンプルではなく）が、従来の分析で必要と考えられていた $\log \log$ 因子を回避し、より明快な解析を可能にすることを実証している。

意義と主張
著者らは、この結果が [AAHLZ24] における多数決の3のルールの最適性に関する予想を解決したと主張している。本論文は、これをPAC学習理論における重要な簡略化として位置づけており、証明可能に最適な「最も単純な投票スキーム」を提供している。証明は短く自己完結的であり、先行する最適学習器のより複雑な構成ではなく、条件付き包含確率の新しい再帰的分解に依拠している。

また、本論文には、証明を簡素化するために大規模言語モデル（LLM）を使用した詳細が付録に含まれている。著者らは、初期の証明はより長く、第一著者によって導出されたものであるが、LLMによる支援を用いて代替的な議論を探索し、最終的な原稿に提示されているような、より短い再帰的な形式に至ったと述べている。数学的な主張は著者らによって検証され、記述されている。