Majority-of-Three is Optimal

Technische Zusammenfassung: Mehrheitsentscheidung aus drei Stimmen ist optimal

Problemstellung
Die Arbeit befasst sich mit dem zentralen Problem der Bestimmung der optimalen Stichprobenkomplexität für das PAC-Lernen im realisierbaren Fall (realizable setting). Während die Existenz optimaler Lerner durch Hanneke [Han16] (aufbauend auf Simon [Sim15]) etabliert wurde, sind die daraus resultierenden Algorithmen und ihre probabilistischen Analysen komplex. Ein spezifischer, elementarer Kandidat für einen optimalen Lerner ist die „Mehrheitsentscheidung aus drei“ (majority-of-three): Dabei wird eine Trainingsstichprobe in drei unabhängige Blöcke aufgeteilt, auf jedem Block ein konsistenter Klassifikator trainiert und die Mehrheitsentscheidung ausgegeben. Vorherige Arbeiten [AAHLZ24] bewiesen, dass diese Regel einen optimalen Erwartungswert und eine nahezu optimale PAC-Schranke (bis auf einen doppelt logarithmischen Faktor, $\log \log(\min\{n/d, 1/\delta\})$) erreicht. Die Autoren von [AAHLZ24] vermuteten, dass die Mehrheitsentscheidungs-Regel die optimale PAC-Schranke ohne diese zusätzlichen Faktoren erreicht. Diese Arbeit liefert einen Beweis für diese Vermutung.

Methodik
Der Beweis etabliert eine Hochwahrscheinlichkeit-Obere Schranke für den Fehler des Mehrheitsentscheidungs-Klassifikators $Maj(\hat{f}_1, \hat{f}_2, \hat{f}_3)$, wobei jeder $\hat{f}_i$ ein konsistenter Klassifikator ist, der auf einem unabhängigen Block $S_i$ der Größe $m = n/3$ trainiert wurde.

1. Reduktion auf Überlappungsmomente:
   Der Fehler der Mehrheitsentscheidung tritt nur auf, wenn mindestens zwei der drei Klassifikatoren einen Punkt $x$ falsch klassifizieren. Sei $E_i = \{x : \hat{f}_i(x) \neq f^\star(x)\}$ die Fehler Menge des $i$-ten Klassifikators, so ist der Gesamtfehler durch die Summe der paarweisen Schnittmengen beschränkt:
   $$\text{err}_P(Maj) \leq P(E_1 \cap E_2) + P(E_2 \cap E_3) + P(E_1 \cap E_3).$$
   Der Beweis konzentriert sich darauf, die $L_q$-Momente dieser Schnittmengenwahrscheinlichkeiten, speziell $\|P(E_1 \cap E_2)\|_{L_q}$, zu beschränken.

2. Zentrales technisches Werkzeug: Proposition 2.2:
   Der Kern des Arguments ist Proposition 2.2, die eine Momentenschranke für die Überlappung von Fehler Mengen aus zwei unabhängigen Stichproben $S$ und $T$ der Größe $m$ liefert. Für eine VC-Klasse $\mathcal{C}$ mit Dimension $d$ und einen deterministischen konsistenten Selektor $A$ (wobei $A(S) \cap S = \emptyset$), besagt die Proposition:
   $$\|P(A(S) \cap A(T))\|_{L_q} \leq 62400 \frac{d + q}{m}.$$
   Dieses Ergebnis ist analog zu Simons [Sim15] Überlappungsschätzung, bezieht sich jedoch auf unabhängige Stichproben statt auf verschachtelte (nested) Strukturen. Die Unabhängigkeit ist entscheidend, um die doppelt logarithmischen Faktoren zu vermeiden, die in früheren Analysen verschachtelter Strukturen vorkommen.

3. Rekursive Dekomposition und bedingte Wahrscheinlichkeiten:
   Um Proposition 2.2 zu beweisen, analysieren die Autoren das $q$-te Moment der Überlappung, indem sie $q$ unabhängige Testpunkte $X = (X_1, \dots, X_q)$ einführen. Das Moment wird als $\mathbb{E}_X [p_q(X)^2]$ umgeschrieben, wobei $p_q(X) = P(X \subseteq A(S))$.
   Unter Verwendung einer Kettenregel-Dekomposition wird $p_q(X)$ als Produkt bedingter Einschlusswahrscheinlichkeiten ausgedrückt:
   $$p_q(X) = \prod_{\ell=1}^q \alpha_{X_{<\ell}}(X_\ell), \quad \text{wobei } \alpha_{z}(x) = P(x \in A(S) \mid z \subseteq A(S)).$$
   Der Beweis stützt sich auf Lemma 3.1, eine Tail-Bound (Endwertschranke) für diese bedingten Wahrscheinlichkeiten. Es zeigt, dass für ein Konditionierungsereignis $E_z$ mit Wahrscheinlichkeit $p_z$ die Wahrscheinlichkeit, dass die bedingte Einschlusswahrscheinlichkeit $\alpha_z(X)$ einen Schwellenwert $a$ überschreitet, beschränkt ist durch:
   $$P(\alpha_z(X) > a) \leq \frac{160}{am} \left( d \log \frac{e}{a} + \log \frac{e}{p_z} \right).$$
   Diese Schranke kontrolliert die „Seltenheit“ des Konditionierungsereignisses, ohne den VC-Dimensions-Term aufzublähen.

4. Rekursives Argument:
   Die Autoren definieren ein gewichtetes Funktional $M_k$, das die quadrierten bedingten Wahrscheinlichkeiten und einen logarithmischen Term beinhaltet. Sie etablieren eine Rekursion $M_k \leq \frac{960}{m} M_{k-1}$. Die Iteration dieser Rekursion von $k=1$ bis $q$ liefert die gewünschte Schranke für das $q$-te Moment, welches dann mittels Markovs Ungleichheit mit $q = \lceil \log(1/\delta) \rceil$ in eine Hochwahrscheinlichkeit-Schranke überführt wird.

Wesentliche Beiträge und Ergebnisse

• Optimalitätsbeweis: Die Arbeit beweist, dass der Mehrheitsentscheidungs-Lerner (majority-of-three) die optimale Stichprobenkomplexität im realisierbaren PAC-Setting erreicht. Speziell gilt für jede Verteilung $P$, Zielfunktion $f^\star$ und Konfidenz $\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.$$
  Dies entspricht der klassischen unteren Schranke [EHKV89] bis auf eine universelle Konstante.
• Vereinfachung der Analyse: Der Beweis vereinfacht die algorithmische Struktur und die probabilistische Analyse früherer optimaler Lerner (wie Hannekes [Han16] und Larsens Bagging-Analyse [Lar23]). Er macht die Notwendigkeit komplexer verschachtelter Stichprobenstrukturen und der daraus resultierenden doppelt logarithmischen Faktoren hinfällig.
• Unabhängigkeit statt Verschachtelung: Die Arbeit zeigt auf, dass die Verwendung unabhängiger Blöcke (im Gegensatz zu verschachtelten Stichproben) eine sauberere Analyse ermöglicht, die die zuvor als notwendig erachteten $\log \log$-Faktoren vermeidet.

Bedeutung und Behauptungen
Die Autoren behaupten, dass dieses Ergebnis die Vermutung aus [AAHLZ24] bezüglich der Optimalität der Mehrheitsentscheidungs-Regel löst. Die Arbeit positioniert dies als eine signifikante Vereinfachung in der Theorie des PAC-Lernens und präsentiert das „einfachste Abstimmungsschema“, das nachweislich optimal ist. Der Beweis wird als kurz und in sich abgeschlossen beschrieben, wobei er auf eine neuartige rekursive Dekomposition bedingter Einschlusswahrscheinlichkeiten setzt, statt auf die komplexeren Konstruktionen früherer optimaler Lerner.

Die Arbeit enthält zudem einen Anhang, der die Verwendung von Large Language Models (LLMs) zur Vereinfachung des Beweises erläutert. Die Autoren merken an, dass der ursprüngliche Beweis länger war und vom Erstautor abgeleitet wurde, aber LLM-Unterstützung genutzt wurde, um alternative Argumente zu explorieren, was zur kürzeren rekursiven Form in der endgültigen Manuskriptfassung führte. Die mathematischen Ansprüche wurden von den Autoren verifiziert und formuliert.