Vi studerar problemet med att uppskatta parametrarna för en Gaussisk distribution när prover endast visas om de faller i vissa (okänd) uppsättning. Detta grundläggande problem i trunkerad statistik har lång historia går tillbaka till Galton, Lee, Pearson och Fisher. Nyligen utfört arbete av Daskalakis et al. (FOCS'18), ger den första effektiva algoritmen som fungerar för godtyckliga uppsättningar i hög dimension när uppsättningen är känd, men lämnar som ett öppet problem det mer utmanande och relevanta fallet av okänd trunkering uppsättning. Vårt huvudsakliga resultat är en beräknings- och prov effektiv algoritm för att uppskatta parametrarna hos Gaussian under godtyckliga okända trunkering uppsättningar vars prestanda sönderfaller med ett naturligt mått på komplexiteten i uppsättningen, nämligen dess Gaussiska yta. I synnerhet fungerar denna algoritm för stora familjer av uppsättningar, inklusive korsningar av halvrymder, polynomiska tröskelfunktioner och allmänna konvexa uppsättningar. Vi visar att vår algoritm noga fångar kompromissen mellan komplexiteten i uppsättningen och antalet prover som behövs för att lära sig parametrarna genom att ställa ut en uppsättning med liten Gaussian yta som det är information teoretiskt omöjligt att lära sig den sanna Gaussian med få prover.
Dessutom, för en beräkningseffektiv algoritm, kräver REF att trunkering uppsättningen har en konstant densitet i Gaussian utrymme.
Efficient Truncated Statistics with Unknown Truncation
{'venue': '2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS)', 'journal': '2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS)', 'mag_field_of_study': ['Computer Science', 'Mathematics']}