Vi beskriver en allmän teknik som ger de första statistiska frågorna lägre gränser för en rad grundläggande högdimensionella inlärningsproblem som involverar Gaussiska distributioner. Våra huvudsakliga resultat är för problemen med (1) lärande Gaussian blandning modeller (GMMs), och (2) robust (agnostic) lärande av en enda okänd Gaussian distribution. För vart och ett av dessa problem visar vi ett super-polynomiskt gap mellan den (information-teoretiska) prov komplexiteten och den beräkningsmässiga komplexiteten hos någon statistisk frågesalgoritm för problemet. Statistiska Query-algoritmer (SQ) är en klass av algoritmer som endast får ifrågasätta förväntningar på distributionens funktioner snarare än få direkt tillgång till prover. Denna klass av algoritmer är ganska bred: ett brett spektrum av kända algoritmiska tekniker i maskininlärning är kända för att vara genomförbar med SQs. Dessutom, för de oövervakade inlärningsproblem som studeras i denna uppsats, alla kända algoritmer med icke-triviala prestanda garantier är SQ eller är lätt att implementera med SQs. Vår SQ lägre gräns för problem (1) matchas kvalitativt av kända inlärningsalgoritmer för GMMs. På en konceptuell nivå innebär detta resultat att – när det gäller SQ-algoritmer – den beräkningsmässiga komplexiteten hos lärande GMMs är i sig exponentiellt i dimensionen av det latenta rummet – även om det inte finns någon sådan informationsteoretisk barriär. Vår lägre gräns för problem (2) innebär att noggrannheten hos den robusta inlärningsalgoritmen i [29] är i huvudsak bästa möjliga bland alla polynom-tid SQ algoritmer. På den positiva sidan ger vi också en ny (SQ) inlärningsalgoritm för problem (2) att uppnå informationsteoretisk optimal noggrannhet, upp till en konstant faktor, vars körtid i huvudsak matchar vår lägre gräns. Vår algoritm bygger på en filtreringsteknik som generaliserar [29] som tar bort avvikelser baserade på högorder tensorer. Våra SQ nedre gränser uppnås genom en enhetlig momentmatching teknik som är användbar i andra sammanhang och kan vara av större intresse. Vår teknik ger nästan åtstramande lägre gränser för ett antal relaterade oövervakade skattningsproblem. Specifikt, för problemen med (3) robust kovariansuppskattning i spektral norm, och (4) robust gles medeluppskattning, etablerar vi en kvadratisk statistisk beräkningsavräkning för SQ-algoritmer, som matchar kända övre gränser. Slutligen kan vår teknik användas för att få tighta prov komplexitet lägre gränser för högdimensionella testproblem. Särskilt när det gäller det klassiska problemet med att kraftfullt testa ett okänt medelvärde (känd kovarians) Gaussian, innebär vår teknik ett informationsteoretiskt prov lägre bundet som skalar linjärt i dimensionen. Vårt urval lägre bundet matchar provet komplexiteten i motsvarande robust inlärningsproblem och separerar provet komplexitet robust testning från standard (non-robust) testning. Denna separation är förvånande, eftersom en sådan klyfta inte existerar för motsvarande inlärningsproblem.
Se REF för de senaste resultaten av beräkningskomplexa inlärningsblandningar av Gaussians.
Statistical Query Lower Bounds for Robust Estimation of High-Dimensional Gaussians and Gaussian Mixtures
{'venue': '2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS)', 'journal': '2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS)', 'mag_field_of_study': ['Computer Science', 'Mathematics']}