I detta dokument fastställs en statistisk kontra beräkningsmässig kompromiss för att lösa ett grundläggande högdimensionellt maskininlärningsproblem via en grundläggande konvex avslappningsmetod. Specifikt anser vi Sparse Principal Component Analysis (Sparse PCA) problem, och familjen av Sum-of-Squares (SoS, aka Lasserre/Parillo) konvexa avkopplingar. Det var väl känt att i stor dimension p, en planterad k-sparse enhet vektor kan i princip detekteras med endast n  på k log p (Gaussian eller Bernoulli) prover, men alla effektiva (polynom tid) algoritmer kända kräver n  på k 2 log p prover. Det var också känt att denna quadratic gapet inte kan förbättras av de mest grundläggande semi-definite (SDP, aka spektral) avkoppling, motsvarande en grad-2 SoS algoritmer. Här bevisar vi att även grad-4 SOS algoritmer inte kan förbättra denna quadratic gap. Denna genomsnittliga-fall lägre bundet lägger till den lilla samlingen av hårdhet resulterar i maskininlärning för denna kraftfulla familj av konvexa avslappningsalgoritmer. Dessutom är vår design av ögonblick (eller "pseudo-förväntningar") för denna lägre gräns helt annorlunda än tidigare lägre gränser. Att fastställa lägre gränser för högre grad av SOS-algoritmer för är fortfarande ett utmanande problem. Modern maskininlärning och statistiska inferens problem är ofta högdimensionella, och det är mycket önskvärt att lösa dem med hjälp av mycket mindre prover än den omgivande dimensionen. Lyckligtvis vet vi ofta, eller antar, någon underliggande struktur av de objekt som söks, vilket möjliggör sådana besparingar i princip. Typiskt ett sådant antagande är att antalet verkliga grad av frihet är mycket mindre än dimensionen; exempel inkluderar gleshet begränsningar för vektorer, och låg rang för matriser och tensorer. Den största svårigheten som uppstår i nästan alla dessa problem är att medan information * teoretiskt det sökta svaret är närvarande (med hög sannolikhet) i ett litet antal prover, faktiskt computing (eller till och med approximation) det från dessa många prover är ett beräknings svårt problem. Det uttrycks ofta som en icke-konvex optimering program som är NP-hård i värsta fall, och till synes svårt även på slumpmässiga fall. Med tanke på denna situation, avslappnad formuleringar av sådana icke-konvexa program föreslogs, som kan lösas effektivt, men ibland för att uppnå korrekta resultat verkar kräva mycket mer prover än existentiella gränser ger. Detta fenomen har myntats den "statistiska kontra beräkningsmässiga kompromiss" av Chandrasekaran och Jordanien [CJ13], som motiverar och formaliserar ett ramverk för att studera det där effektiva algoritmer kommer från Sum-of-Squares familj av konvexa avkopplingar (som vi för närvarande ska diskutera). De ger också en detaljerad studie av denna kompromiss för den grundläggande de-bullering problem [Joh02, Don95, DJ98] i olika miljöer (vissa uppvisar kompromissen och andra som inte). Denna kompromiss observerades i andra praktiska maskininlärning problem, särskilt för Sparse PCA problem som kommer att vara vårt fokus, av Berthet och Rigollet [BR13a]. Som det visar sig, föreslogs studien av samma fenomen ännu tidigare i beräkningskomplex, främst från teoretiska motiv. Decatur, Goldreich och Ron [DGR97] initierar studien av "beräkningsprov komplexitet" för att studera statistiska kontra beräkning kompromisser i urvalsstorlek. I sin ram effektiva algoritmer är godtycklig polynom tid en, inte begränsad till någon särskild struktur som konvex avkopplingar. De påpekar till exempel att det inom ramen för Vapnik-Chervonkis och Valiants distributionsfria PAC-lärande ofta inte förekommer någon sådan kompromiss. Anledningen är att antalet prover i huvudsak bestäms (upp till logaritmiska faktorer, som vi mestadels kommer att ignorera här) av VC-dimensionen av den givna konceptklassen lärt, och dessutom, en "Occam algoritm" (som beräknar någon konsekvent hypotes) räcker för klassificering från dessa många prover. Så, i de många fall där effektivt hitta en hypotes som överensstämmer med data är möjligt, tillräckligt med prover för att lära är tillräckligt för att göra det effektivt! I detta dokument ges också exempel där detta inte är fallet när det gäller PAC-lärande, och sedan övergår man till en omfattande studie av möjliga kompromisser för att lära sig olika konceptklasser under den enhetliga fördelningen. Denna riktning vidareutvecklades av Servedio [Ser00]. Den snabba tillväxten av Big Data forskning, de olika problem som framgångsrikt attackeras av olika heuristik och försöken att hitta effektiva algoritmer med bevisbara garantier är ett växande område av interaktion mellan statistiker och maskininlärning forskare å ena sidan, och optimering och dataforskare å den andra. De avvägningar mellan provstorlek och beräknings komplexitet, som verkar vara närvarande för många sådana problem, återspeglar en märklig "konflikt" mellan dessa områden, som i den första mer data är goda nyheter, eftersom det tillåter mer exakt slutsats och förutsägelse, medan i den andra det är dåliga nyheter, eftersom en större indatastorlek är en källa till ökad komplexitet och ineffektivitet. Ännu viktigare, att förstå detta fenomen kan tjäna som en vägledning till utformningen av bättre algoritmer från både statistiska och beräkningsmässiga perspektiv, särskilt för problem där själva datainsamlingen är kostsam, och inte bara beräkning. En grundläggande fråga är alltså vilka problem som är en sådan avvägning, och att fastställa gränserna för vad som kan uppnås med effektiva metoder. Upprättandet av en kompromiss har två delar. Man måste bevisa en existentiell, information teoretisk övre gräns för antalet prover som behövs när effektivitet inte är en fråga, och sedan bevisa en beräkning lägre gräns på antalet prover för klassen av effektiva algoritmer till hands. Naturligtvis är det önskvärt att de nedre gränserna håller för en så bred klass av algoritmer som möjligt, och att den matchar den mest kända övre gränsen som uppnås av algoritmer från denna klass. Den mest allmänna, den beräkning komplexa ramen för [DGR97, Ser00] gör det möjligt
Grad fyra SOS nedre gränser för gles PCA i spikad covariance modell visades i REF.
Sum-of-Squares Lower Bounds for Sparse PCA
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}