Givna prover från en okänd distribution p och en beskrivning av en distribution q, är p och q nära eller långt? Denna fråga om "identitetstestning" har fått stor uppmärksamhet när det gäller testning om p och q är lika med eller långt i totalt variationsavstånd. Men i det senaste arbetet [VV11, ADK15, DP17] har följande frågor varit avgörande för att lösa problem vid distributionstester: • Alternativa avstånd: Kan vi testa om p och q är långt på andra avstånd, säger Hellinger? • Robusthet: Kan vi testa när p och q är nära, snarare än lika? Och i så fall, på vilka avstånd? Motiverade av dessa frågor, vi karakteriserar komplexiteten i distributionstester under en mängd olika avstånd, inklusive total variation, l2, Hellinger, Kullback-Leibler, och chi-squared. För varje par av avstånd d1 och d2 studerar vi komplexiteten av testning om p och q är nära i d1 jämfört med långt i d2, med fokus på att identifiera vilka problem tillåter starkt sublinjära testare (dvs. de med komplexitet O(n 1−γ ) för vissa γ > 0 där n är storleken på stödet för distributionerna p och q). Vi erbjuder matchande övre och nedre gränser för varje fall. Vi studerar också dessa frågor i det fall där vi bara har prover från q (ekvivalenstester), som visar kvalitativa skillnader från identitetstester i termer av när robusthet kan uppnås. Våra algoritmer faller in i det klassiska paradigmet av chi-squared statistik, men kräver avgörande förändringar för att hantera de utmaningar som införs av varje avstånd vi anser. Slutligen undersöker vi andra resultat på senare tid i ett försök att tjäna som referens för komplexiteten i olika distributionstestningsproblem.
Vid testning i andra distributionsavstånd gav REF karakteriseringar av urvalets komplexitet av identitetstester på en mängd olika avstånd förutom
Which Distribution Distances are Sublinearly Testable?
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}