I denna artikel beskriver och analyserar vi sublinear-tid approximation algoritmer för vissa optimeringsproblem som uppstår i maskininlärning, såsom utbildning linjära clasfiers och hitta minimala omslutande bollar. Våra algoritmer kan utökas till vissa kärnorade versioner av dessa problem, såsom SVDD, hård marginal SVM och L 2 -SVM, för vilka sublinjära tidsalgoritmer inte var kända tidigare. Dessa nya algoritmer använder en kombination av en ny provtagningsteknik och en ny multiplikativ uppdateringsalgoritm. Vi ger lägre gränser som visar körtiden för många av våra algoritmer att vara nästan bästa möjliga i enhet-kostnad RAM-modellen. De tidsgränser som ges för våra algoritmer, utom Las Vegas, är under antagande av konstant felsannolikhet; för utdatagarantier som håller med sannolikhet 1 − δ, bör våra gränser multipliceras med log(n/δ). Tidsgränser kräver också antagandet att indata lagras på ett sådant sätt att en given post A i, j kan återvinnas i konstant tid. Detta kan göras genom att till exempel hålla varje rad A i A som ett haschbord. (Enkelt hålla posterna i raden i sorterad ordning efter kolumnnummer är också tillräckligt, ådrar sig en O(log d) overhead i körtid för binär sökning.) Formell beskrivning: Klassificering. I det linjära klassificeringsproblemet ges eleven en uppsättning n-märkta exempel i form av d-dimensionella vektorer, bestående av ingångsmatrisen A. Etiketterna består av en vektor y  till {+1, −1} n. Målet är att hitta en separerande hyperplane, det vill säga en normal vektor x i enheten Euclidean boll B sådan att för alla i, y(i) · A i x ≥ 0; här y(i) betecknar i'th koordinat av y. Som nämnts, Vi kommer att anta hela att A i B för alla i... [n], där allmänt [m] betecknar uppsättningen av heltal {1, 2,..., m}. Som standard kan vi anta att etiketterna y(i) är alla 1, genom att ta A i ← −A i för alla i med y(i) = −1. Den approximativa versionen av linjär klassificering är att hitta en vektor x ε  på B som är en ε-ungefärlig lösning, det vill säga (1) Den optimala för denna formulering erhålls när x = 1, utom när ingen separation hyperplane finns, och sedan den optimala x är nollvektorn. Observera att min i A i x = min p till p Ax, där R n är enheten simplex { p  till R n p i ≥ 0, i p i = 1}. Således kan vi betrakta det optimala som resultatet av ett spel för att bestämma p Ax, mellan en minimator välja p  på, och en maximerare välja x  på B, vilket ger där denna optimala σ kallas marginalen. Från standard dualitet resultat, σ är också den optimala av den dubbla problemet min p på max x och B p Ax, och de optimala vektorerna p * och x * är samma för båda problemen. Den klassiska Perceptron Algoritmen returnerar en ε-ungefärlig lösning till detta problem i 1 ε 2 iterationer, och total tid O(ε −2 M). 2 För givet ε-värde (0, 1) tar vår nya algoritm O(ε −2 (n + d)log n) log(n/δ)) tid att returnera en ε-ungefärlig lösning med sannolikhet minst 1 − δ. Dessutom visar vi att detta är optimalt i enhetskostnad RAM-modellen, upp till polylogaritmiska faktorer. Formell beskrivning: Minsta omslutningskula (MEB). MEB problemet är att hitta den minsta Euclidean bollen i R d som innehåller raderna i A. Det är ett specialfall av Quadratic Programmering (QP) i enheten simplex, nämligen att hitta min p på p + p AA p, där b är en n-vektor. Detta förhållande, och generaliseringen av vår MEB algoritm till QP i simplex, diskuteras i Avsnitt 3.3; för mer allmän bakgrund om QP i simplex, och relaterade problem, se till exempel Clarkson [2008].
Clarkson och Al. REF presenterar sublinjär-tid (i storleken på inmatningen) approximationsalgoritmer för vissa optimeringsproblem såsom utbildning linjära klassificeringar (t.ex., perceptron) och hitta MEB.
Sublinear optimization for machine learning
{'venue': 'JACM', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}