Tighter Confidence Intervals under Without Replacement Sampling via Empirical Rate Functions

1. Problemstellung

Das Paper adressiert das fundamentale Problem der Konstruktion von Konfidenzintervallen (CIs) für den Populationsmittelwert $\mu_N$ einer endlichen Population $X_N = \{x_1, \dots, x_N\} \subset \Sigma$, basierend auf einer Stichprobe der Größe $n$, die ohne Zurücklegen (Without Replacement, WoR) gezogen wurde.

Im Gegensatz zum klassischen i.i.d.-Fall (mit Zurücklegen) weist das WoR-Sampling eine inhärente Eigenschaft auf: Die Unsicherheit über den Populationsmittelwert geht gegen Null, sobald die Stichprobengröße $n$ die Populationsgröße $N$ erreicht ($n \to N$). Viele bestehende Methoden (wie der klassische Hoeffding-Intervall) erfassen diese Eigenschaft nicht adäquat und liefern zu breite Intervalle, insbesondere wenn $n$ einen signifikanten Anteil von $N$ ausmacht.

Das Ziel ist es, Konfidenzintervalle zu entwickeln, die:

1. Eine garantierte Abdeckungswahrscheinlichkeit von $1-\alpha$ bieten (nicht-asymptotisch).
2. Die Breite des Intervalls fundamental minimieren, indem sie die spezifischen Eigenschaften des WoR-Samplings nutzen.
3. Für verschiedene Alphabet-Typen (endlich, kontinuierlich, Banach-Räume) anwendbar sind.

2. Methodik und theoretische Grundlagen

Die Autoren stützen ihre Herangehensweise auf zwei Hauptpfeiler:

A. Bernoulli-Kopplung (Bernoulli Coupling)

Ein zentrales Werkzeug ist die Identität von Hájek (1960), die das WoR-Sampling mit einer einfacheren i.i.d.-Bernoulli-Stichprobe verbindet.

• Idee: Eine WoR-Stichprobe $X_n$ aus einer Population $X_N$ hat dieselbe Verteilung wie eine i.i.d.-Bernoulli-Stichprobe $J_i \sim \text{Bernoulli}(\beta)$ (mit $\beta = n/N$), bedingt darauf, dass die Summe der Bernoulli-Variablen genau $n$ ergibt ($S_{N,J} = n$).
• Nutzen: Dies erlaubt die Anwendung von Konzentrationsungleichungen für unabhängige Daten (i.i.d.) auf das WoR-Problem, wobei ein Korrekturfaktor (basierend auf der Wahrscheinlichkeit $P(S_{N,J}=n)$) hinzugefügt wird.

B. Große Abweichungen (Large Deviations Theory)

Für den Fall eines endlichen Alphabets ($|\Sigma| = k < \infty$) nutzen die Autoren die Theorie der großen Abweichungen.

• Rate-Funktion: Sie definieren eine spezifische WoR-Rate-Funktion $I(P, \beta, Q)$, die analog zur relativen Entropie (KL-Divergenz) im i.i.d.-Fall ist, aber die Struktur des WoR-Samplings berücksichtigt.
• Inverse Rate-Funktionen: Die optimale Breite eines Konfidenzintervalls wird durch die Inverse dieser Rate-Funktionen bestimmt.

3. Schlüsselbeiträge und Ergebnisse

A. Fundamentale Untergrenze für endliche Alphabete

Für den Fall endlicher Alphabete leiten die Autoren eine informationstheoretische Untergrenze für die Breite jedes Konfidenzintervalls ab (Theorem 3.4).

• Ergebnis: Die Breite eines jeden Intervalls mit Abdeckungswahrscheinlichkeit $1-\alpha_N$ muss mindestens proportional zur Differenz der inversen WoR-Rate-Funktionen $J_+^{-1}$ und $J_-^{-1}$ sein.
• Regime: Dies gilt im sogenannten „moderate accuracy"-Regime, wo $\log(1/\alpha_N)$ groß genug ist im Vergleich zu $(k+1)\log N$.

B. Ein neues, nahezu optimales Konfidenzintervall

Basierend auf der Untergrenze schlagen die Autoren ein neues CI vor (Definition 3.6), das auf empirischen inversen Rate-Funktionen basiert.

• Konstruktion: Die Intervallgrenzen werden durch Invertieren der empirischen Rate-Funktion $J(\hat{P}_n, \beta, m)$ bestimmt, wobei $\hat{P}_n$ die empirische Verteilung der Stichprobe ist.
• Optimalität: Theorem 3.9 zeigt, dass die Breite dieses neuen CIs in bestimmten asymptotischen Regimes die informationstheoretische Untergrenze bis auf Konstanten erreicht.
• Berechenbarkeit (Dualität): Da die direkte Optimierung über den WahrscheinlichkeitsSimplex bei großen Alphabeten rechenintensiv ist, leiten die Autoren eine duale Formulierung (Theorem 3.11) ab. Diese reduziert das Problem auf ein zweidimensionales konvexes Optimierungsproblem, das unabhängig von der Alphabetgröße $|\Sigma|$ ist und somit effizient lösbar ist.

C. Erweiterungen auf allgemeine Alphabete

Da die oben genannte Methode auf endliche Alphabete beschränkt ist, entwickeln die Autoren zwei weitere CIs unter Verwendung der Bernoulli-Kopplung:

1. „Fast sichere" CIs für $\Sigma = [0, 1]$ (Section 3.3.1):

   • Sie konstruieren ein Intervall, das eine stärkere Garantie als asymptotische CLT-basierte Intervalle bietet, aber flexibler ist als strikte nicht-asymptotische Intervalle (wie Hoeffding-Serfling).
   • Unter bestimmten Bedingungen (Assumption 3.15) wird gezeigt, dass das Intervall den wahren Mittelwert nur endlich oft verfehlt (fast sichere Abdeckung).

2. CIs für glatte Banach-Räume (Section 3.3.2):

   • Für Daten in einem $(2, D)$-glatten Banach-Raum (z. B. RKHS für Kernel-Einbettungen) wird ein einfaches, nicht-asymptotisches CI entwickelt.
   • Vergleich: Dieses Intervall ist enger als das bestehende CI von Schneider (2016), insbesondere in moderaten Stichprobengrößen und Parametern. Die Verbesserung wird durch die Nutzung der Kopplung und moderner Konzentrationsungleichungen für Banach-Räume (Pinelis) erreicht.

4. Signifikanz und Anwendungen

• Theoretischer Fortschritt: Das Paper stellt eine direkte Verbindung zwischen der Schätzung unter WoR-Sampling und der Theorie der großen Abweichungen her. Es identifiziert die inverse WoR-Rate-Funktion als die fundamentale Komplexitätsgröße für die CI-Breite.
• Praktische Relevanz:
  • Risikobegrenzte Audits (Risk-Limiting Audits): WoR-Sampling ist hier Standard; engere CIs bedeuten effizientere Audits.
  • Bayesianische Inferenz & MCMC: Subsampling-Methoden profitieren von genaueren Schätzungen.
  • Kernel-Methode: Die Anwendung auf glatte Banach-Räume ist direkt relevant für Kernel-Mean-Embeddings (z. B. zur Vergleich von Verteilungen), wie im MNIST-Experiment demonstriert.
• Recheneffizienz: Die duale Formulierung macht die Berechnung der optimalen CIs auch für große Alphabetgrößen praktikabel.

Zusammenfassung

Shekhar und Ramdas liefern einen umfassenden theoretischen Rahmen für Konfidenzintervalle beim Sampling ohne Zurücklegen. Sie beweisen, dass die optimale Intervallbreite durch inverse Rate-Funktionen bestimmt wird, schlagen ein neues, nahezu optimales Verfahren für endliche Alphabete vor (mit effizienter dualer Berechnung) und erweitern die Ergebnisse auf kontinuierliche und Banach-Raum-Szenarien mittels einer Bernoulli-Kopplung. Die vorgeschlagenen Methoden sind sowohl theoretisch fundiert als auch empirisch überlegen im Vergleich zu bestehenden Ansätzen wie Hoeffding-Serfling oder Schneider (2016).