Tighter Confidence Intervals under Without Replacement Sampling via Empirical Rate Functions

1. Problema e Contesto

Il lavoro affronta il problema fondamentale della costruzione di intervalli di confidenza (CI) per la media di una popolazione finita $\mu_N$ di $N$ valori $\{x_1, \dots, x_N\} \subset \Sigma$, basandosi su un campione casuale di dimensione $n$ estratto senza sostituzione (Without Replacement - WoR).

A differenza del campionamento con sostituzione (i.i.d.), il campionamento WoR presenta una caratteristica distintiva: l'incertezza sulla media della popolazione si riduce a zero man mano che $n$ si avvicina a $N$ (quando si osserva l'intera popolazione). Molti metodi classici (come l'intervallo di Hoeffding) non catturano questa proprietà, risultando troppo conservativi. L'obiettivo è derivare limiti inferiori fondamentali per la larghezza degli intervalli e proporre metodi che li raggiungano, sia per alfabeti finiti che continui.

2. Metodologia e Strumenti Teorici

L'approccio si basa su tre pilastri principali:

1. Identità di Accoppiamento (Bernoulli Coupling):
   Il cuore della metodologia è l'identità di accoppiamento di Hájek (Fatto 2.1). Questa identità stabilisce che la distribuzione empirica di un campione WoR può essere vista come la distribuzione empirica di un campione i.i.d. (Bernoulli) condizionato al fatto che la somma delle variabili bernoulliane sia esattamente $n$. Questo permette di utilizzare le tecniche di concentrazione standard per dati indipendenti per analizzare il caso WoR, introducendo un fattore di correzione legato alla probabilità binomiale.

2. Teoria delle Grandi Deviazioni (Large Deviations):
   Per gli alfabeti finiti, gli autori definiscono funzioni di tasso (rate functions) specifiche per il WoR, denotate come $J_+$ e $J_-$. Queste sono derivate dalla funzione di tasso $I(P, \beta, Q)$, che generalizza la divergenza di Kullback-Leibler per il campionamento senza sostituzione.
   $$I(P, \beta, Q) = d_{KL}(P \| Q) + \frac{1-\beta}{\beta} d_{KL}\left(\frac{Q-\beta P}{1-\beta} \bigg\| Q\right)$$
   dove $\beta = n/N$.

3. Ottimizzazione Convessa e Dualità:
   Per rendere computazionalmente fattibile la costruzione degli intervalli, viene derivata una formulazione duale delle funzioni di tasso inverse, riducendo il problema da una ottimizzazione su un semplicex di dimensione $|\Sigma|$ a un problema di ottimizzazione convessa in due dimensioni, indipendente dalla dimensione dell'alfabeto.

3. Contributi Chiave e Risultati

A. Alfabeti Finiti ($|\Sigma| = k < \infty$)

• Limite Inferiore Fondamentale (Teorema 3.4): Gli autori derivano un limite inferiore per la larghezza di qualsiasi intervallo di confidenza di livello $(1-\alpha_N)$ in un regime di "accuratezza moderata". La larghezza ottimale è caratterizzata dall'inverso delle funzioni di tasso WoR ($J_{\pm}^{-1}$).
• Nuovo Intervallo di Confidenza (Definizione 3.6): Viene proposto un nuovo CI basato sulle funzioni di tasso inverse empiriche. Gli estremi dell'intervallo sono definiti come:
  $$b_{\pm} = \inf/\sup \{ m : J_{\pm}(\hat{P}_n, \beta, m) \geq c_N/n \}$$
  dove $\hat{P}_n$ è la distribuzione empirica del campione.
• Ottimalità (Teorema 3.9): Si dimostra che, in certi regimi asintotici (per $N$ sufficientemente grande), la larghezza di questo nuovo CI corrisponde al limite inferiore fondamentale fino a costanti moltiplicative.
• Efficienza Computazionale (Teorema 3.11): Viene presentata una rappresentazione duale per $J_{\pm}$. Invece di ottimizzare su tutte le distribuzioni possibili, il problema si riduce a massimizzare una funzione concava su un dominio bidimensionale $(\lambda, \rho)$. Questo rende il calcolo dell'intervallo fattibile anche per grandi dimensioni dell'alfabeto.

B. Alfabeti Generali e Spazi di Banach

Poiché i risultati per alfabeti finiti possono essere troppo conservativi in pratica a causa delle approssimazioni combinatorie, gli autori estendono il lavoro a spazi continui utilizzando l'identità di accoppiamento.

• CI "Quasi Certi" per $\Sigma = [0, 1]$ (Sezione 3.3.1):
  Viene costruito un intervallo di confidenza che soddisfa una proprietà di copertura quasi certa (Naaman, 2016). A differenza degli intervalli non asintotici classici (che sono molto larghi) e degli intervalli asintotici basati sul CLT (che possono fallire infinite volte lungo un percorso), questo metodo garantisce che, con probabilità 1, l'intervallo contenga la vera media per tutti i $N$ sufficientemente grandi. Non richiede la conoscenza a priori del range delle osservazioni.
• CI per Spazi di Banach Lisce (Sezione 3.3.2):
  Per osservazioni in uno spazio di Banach $(2, D)$-liscio (che include gli spazi di Hilbert), viene proposto un CI non asintotico. Utilizzando l'identità di accoppiamento e disuguaglianze di concentrazione per somme di variabili indipendenti in spazi di Banach (Pinelis, 1994), si ottiene un intervallo più stretto rispetto ai metodi precedenti (es. Schneider, 2016).
  • Risultato Empirico: L'analisi numerica su dati MNIST (embedding della media del kernel) mostra che il nuovo metodo riduce la larghezza dell'intervallo rispetto a Schneider (2016) in modo significativo, specialmente per campioni di dimensioni moderate.

4. Significato e Impatto

Questo lavoro stabilisce nuove connessioni tra la stima sotto campionamento senza sostituzione e la teoria delle grandi deviazioni.

1. Teorico: Fornisce la prima caratterizzazione fondamentale della larghezza ottimale degli intervalli di confidenza WoR, identificando le funzioni di tasso inverse come la misura di complessità corretta.
2. Computazionale: La formulazione duale risolve il problema della complessità computazionale, rendendo gli intervalli ottimali calcolabili in pratica.
3. Pratico: I metodi proposti offrono intervalli più stretti (più informativi) rispetto agli standard attuali (Hoeffding-Serfling, Bernstein-Serfling, Betting-based), specialmente quando la frazione di campionamento $\beta$ è significativa o quando si lavora con spazi di funzioni complessi (come negli embedding di kernel).
4. Versatilità: Copre sia scenari a alfabeto finito (dove si ottiene l'ottimalità teorica) che scenari continui e spazi di Banach, offrendo soluzioni robuste per applicazioni come audit a rischio limitato, campionamento per sondaggi e inferenza Bayesiana scalabile (MCMC).

In sintesi, il paper sposta il paradigma dalla costruzione di intervalli basati su disuguaglianze di concentrazione generiche a una costruzione basata su funzioni di tasso empiriche ottimali, garantendo sia prestazioni teoriche superiori che efficienza computazionale.