The Minimax Risk in Testing Uniformity over Large Alphabets under Missing-Ball Alternatives

Technische Samenvatting: Het Minimax-risico bij het Testen van Uniformiteit over Grote Alfabetten onder Missing-Ball Alternatieven

Probleemformulering
Het artikel behandelt het probleem van het testen van de goedheid van aanpassing (goodness-of-fit) van categorische telgegevens aan een uniforme Poisson-verdeling tegen een klasse van alternatieven die worden gedefinieerd door de uitsluiting van een $\ell_p$-bal ($p \le 2$) met straal $\epsilon$ rond de uniforme snelheid-sequentie. De gegevens bestaan uit onafhankelijke Poisson-toevalsvariabelen $O_1, \dots, O_N$ met snelheden $nQ_i$, waarbij $N$ het aantal categorieën is en $n$ een schaalparameter die de totale verwachte telling controleert. De nulhypothese $H_0$ stelt een uniforme snelheid-vector $U = (1/N, \dots, 1/N)$ voor, terwijl de alternatieve hypothese $H(Q)$ snelheid-vectoren $Q$ omvat waarvoor $\|Q - U\|_p \ge \epsilon$ geldt.

De primaire focus ligt op het hoogdimensionale regime waar $N \gg n$ (specifiek $n = o(N)$), een setting waarin de klassieke chi-kwadraat-toets bekend staat als anders te gedragen dan in het laagdimensionale geval ($N = o(n)$). Het doel is om het minimax-risico $R^*(V_\epsilon)$ te karakteriseren, gedefinieerd als het infimum over alle toetsen van het supremum van de som van Type I- en Type II-fouten, naarmate zowel $N$ als $n$ naar oneindig gaan.

Methodologie
De analyse maakt gebruik van een minimax-kader dat wordt gereduceerd tot een Bayesiaanse setting. De auteurs stellen vast dat het minimax-risico asymptotisch equivalent is aan het minimax-Bayes-risico over een specifieke klasse van product-priors. De methodologie omvat verschillende belangrijke technische stappen:

1. Reductie naar Gestructureerde Subsets: De auteurs identificeren en sluiten eerst "gemakkelijke" alternatieven uit middels elementaire scheidingscondities gebaseerd op de som-, chi-kwadraat- en maximumstatistieken. Dit reduceert het probleem tot een subset van alternatieven $V_{\epsilon, \xi, r}$ waarbij de snelheden begrensd zijn en de $\ell_2$-afstand gecontroleerd wordt.
2. Lineaire Toetsstatistieken: De analyse richt zich op lineaire toetsstatistieken van de vorm $T_w = \sum_{m=0}^\infty w_m X_m$, waarbij $X_m$ het aantal categorieën met precies $m$ voorkomens is (de data-histogram).
3. Asymptotische Normaliteit: Een centrale technische bijdrage is het vaststellen van de uniforme asymptotische normaliteit van deze lineaire statistieken onder een klasse van priors. Dit maakt het mogelijk om het Bayesiaanse toetsingsprobleem te benaderen met een Gaussische verschuivings-experiment (Gaussian shift experiment).
4. Optimalisatie over Priors: De auteurs lossen een optimalisatieprobleem op over $N$-dimensionale sequenties om de "minst gunstige prior" (least favorable prior) te identificeren. Ze tonen aan dat de minst gunstige prior een product is van symmetrische twee-puntsverdelingen ondersteund op $\{1/N \pm \epsilon N^{-1/p}\}$.
5. Connectie met Signaaldetectie: De structuur van het resulterende optimalisatieprobleem wordt getoond analoog aan klassieke resultaten in signaaldetectie binnen Gaussische witte ruis.

Belangrijkste Bijdragen en Resultaten

• Karakterisering van het Minimax-risico: Het artikel leidt het asymptotische minimax-risico af voor het regime waar het risico convergeert naar een constante $c \in (0, 1)$. Het risico wordt gekarakteriseerd door de functie:
  $$\lim_{n,N \to \infty} R^*(V_\epsilon) = 2\Phi(-u_{\epsilon,n,N,p}/2)$$
  waarbij $\Phi$ de standaard normale cumulatieve verdelingsfunctie is en $u_{\epsilon,n,N,p}^2 = \frac{1}{2}\epsilon^4 n^2 N^{3-4/p}$.
  Dit resultaat biedt een karakterisering met een constante factor, waarmee verder wordt gegaan dan eerder werk dat slechts convergentie-ordes of steekproefcomplexiteit-schaalordes vaststelde.

• De Minimax-toets: De asymptotisch minimax-toets is een lineaire statistiek gebaseerd op de histogram-ordinaten met gewichten $w^*_m = g_{m, \lambda_0}(n\epsilon N^{-1/p})$, waarbij $g$ een gesymmetriseerde functie is afgeleid van de Poisson-waarschijnlijkheids-massafunctie.

  • In het limiet waar de verwachte telling per categorie $\lambda_0 = n/N \to 0$, vertrouwt de toets uitsluitend op "exclusieve botsingen" (categorieën met precies 2 voorkomens, $X_2$).
  • Voor grotere $\lambda_0$ gedraagt de toets zich vergelijkbaar met de chi-kwadraat-toets, maar met specifieke aanpassingen voor kleine tellingen.

• Prestaties van Bestaande Toetsen:

  • Chi-kwadraat-toets: Het artikel leidt het asymptotische risico van de chi-kwadraat-toets af onder de minst gunstige prior. Het toont aan dat, tenzij $n/N \to \infty$, de chi-kwadraat-toets het minimax-risico niet kan bereiken. De kloof wordt gekwantificeerd door een factor die een $\sqrt{n/(N+n)}$ bevat in het argument van de normale verdelingsfunctie.
  • Botsings-gebaseerde Toetsen: Toetsen gebaseerd op enkel botsingen (bijv. $X_2$) worden getoond als suboptimaal vergeleken met de volledige minimax-toets wanneer $\lambda_0$ niet verwaarloosbaar klein is, hoewel ze optimaal naderen wanneer $\lambda_0 \to 0$.

• Multinomiale Extensie: De auteurs beargumenteren dat het afgeleide Poisson minimax-risico ook het minimax-risico voor het vast-steekproefgrootte multinomiale model karakteriseert. Hoewel het Poisson-model dient als een bovengrens, claimt het artikel (verwijzend naar een begeleidende noot) dat de ondergrens ook voor het multinomiale geval geldt via conditionele centrale limietstellingen.

Betekenis
Het artikel claimt significant te zijn door een precieze, constante-factor karakterisering te bieden van het minimax-risico in hoogdimensionale uniformiteitstoetsing, een regime waar eerdere literatuur beperkt was tot orde-optimale resultaten. Door de exacte asymptotische risico en de bijbehorende minimax-toets te identificeren, maakt het werk vergelijkbare vergelijkingen mogelijk tussen diverse schatters (inclusclusief die gebaseerd op botsingen en chi-kwadraat-statistieken) die dezelfde steekproefcomplexiteit-schaalorde bereiken.

De resultaten verhelderen de beperkingen van de klassieke chi-kwadraat-toets in hoogdimensionale settings, waarbij wordt aangetoond dat de suboptimaliteit ervan niet louter een kalibratieprobleem is, maar een fundamentele beperking onder Poisson-sampling wanneer $n/N$ niet divergeert. Bovendien biedt de afleiding van de minst gunstige prior als een eenvoudige twee-puntsverdeling een concrete structurele verstandhouding van de "moeilijkste" alternatieven in deze klassen van problemen. De gepresenteerde empirische studies bevestigen dat de asymptotische risico-inschattingen accuraat zijn, zelfs in eindige steekproeven, en dat de voorgestelde minimax-toets zowel de chi-kwadraat- als de botsingsgebaseerde toetsen overtreft onder het minst gunstige alternatief.