Det har nyligen gjorts betydande arbete med teori och tillämpning av randomiserade algoritmer för koordinatnedstigning, med början i Nesterovs arbete [SIAM J. Optim., 22.2. 2012 ], som visade att en slumpmässig koordinat urval regel uppnår samma konvergens takt som Gauss-Southwell urval regel. Detta resultat tyder på att vi aldrig bör använda Gauss-Southwell regeln, eftersom det är typiskt mycket dyrare än slumpmässigt urval. De empiriska beteendena hos dessa algoritmer motsäger dock detta teoretiska resultat: i tillämpningar där beräkningskostnaderna för urvalsreglerna är jämförbara tenderar urvalsregeln Gauss-Southwell att prestera betydligt bättre än slumpmässiga koordinatval. Vi ger en enkel analys av Gauss-Southwell regeln visar att-utom i extrema fall-dess konvergens är snabbare än att välja slumpmässiga koordinater. Vi också (i) visar att exakt koordinatoptimering förbättrar konvergensen för vissa glesa problem, (ii) föreslå en Gauss-Southwell-Lipschitz regel som ger en ännu snabbare konvergens takt med tanke på kunskapen om Lipschitz konstanter av de partiella derivat, (iii) analysera effekten av ungefärliga Gauss-Southwell regler, och (iv) analysera proximal-gradient varianter av Gauss-Southwell regeln. Det har funnits ett stort intresse på senare tid för att tillämpa koordinatnedstigningsmetoder för att lösa storskaliga optimeringsproblem, med början i Nesterovs seminala arbete [2012], som gav den första globala konvergensanalysen för koordinatavslappningsmetoder för att minimera konvexa funktioner. Denna analys tyder på att välja en slumpmässig koordinat för att uppdatera ger samma prestanda som att välja den "bästa" koordinaten att uppdatera via dyrare Gauss-Southwell (GS) regel. (Nesterov föreslog också en mer smart randomiserad plan, som vi behandlar senare i detta dokument.) Detta resultat ger ett övertygande argument för att använda randomiserad koordinatnedstigning i sammanhang där GS-regeln är för dyr. Det tyder också på att det inte finns någon fördel med att använda GS-regeln i sammanhang där den är relativt billig. Men i dessa sammanhang, GS regel ofta betydligt överträffar randomiserade koordinat urval i praktiken. Detta tyder på att antingen analysen av GS inte är stram, eller att det finns en klass av funktioner för vilka GS-regeln är lika långsam som randomiserad koordinat nedstigning. Efter att ha diskuterat sammanhang där det är meningsfullt att använda koordinatnedstigning och GS-regeln besvarar vi denna teoretiska fråga genom att göra en noggrannare analys av GS-regeln (under starka konvexitets- och standardsantaganden) som ger samma hastighet som den randomiserade metoden för en begränsad klass av funktioner, men som annars är snabbare (och i vissa fall betydligt snabbare). Vi visar vidare att GS-metoden med exakt koordinatoptimering, jämfört med den vanliga konstanta stegvisa uppdateringen av koordinaten, har en märkbart snabbare takt för problem som uppfyller en viss gleshetsbegränsning (avsnitt 5). Vi tror att detta är det första resultatet som visar en teoretisk fördel med exakt koordinatoptimering; alla tidigare analyser visar att dessa strategier får samma hastighet som konstanta steg-storlek uppdateringar, även om exakt optimering tenderar att vara snabbare i praktiken. I avsnitt 6 föreslår vi dessutom en variant av GS-regeln som, i likhet med Nesterovs mer smarta slumpmässiga provtagningssystem, använder sig av kunskap om Lipschitz-konstanterna i de koordinatvisa gradienterna för att få en snabbare hastighet. Vi analyserar också ungefärliga GS-regler (avsnitt 7), som Nesterovs hastigheter visar att koordinatnedstigning kan vara snabbare än lutningsnedstigning i fall där, om vi optimerar n-variabler, kostnaden för att utföra n-koordinatuppdateringar liknar kostnaden för att utföra en fullständig gradient iteration. Detta innebär i huvudsak att koordinat nedstigning metoder är användbara för att minimera konvexa funktioner som kan uttryckas i en av följande två former: där x i är element i x, f är slät och billig, f ij är slät, G = {V, E} är en graf, och A är en matris. (Det antas att alla funktioner är konvexa.) 1 Familjen av funktioner h 1 inkluderar kärn maskininlärning problem såsom minst kvadrater, logistisk regression, lasso, och SVMs (när löst i dubbel form) [Hsieh et al., 2008]. Familj h 2 innehåller kvadratiska funktioner, grafbaserade etikettutbredning algoritmer för semiövervakad lärande [Bengio et al., 2006], och hitta de mest sannolika uppdrag i kontinuerlig parvis grafiska modeller [Rue och Held, 2005]. I allmänhet är GS-regeln för problem h 2 lika dyr som en fullständig gradientbedömning. G:s struktur möjliggör dock ofta ett effektivt genomförande av GS-regeln. Till exempel, om varje nod har som mest d grannar, kan vi spåra lutningarna av alla variabler och använda en max-heap struktur för att genomföra GS-regeln i O(d log n) tid [Meshi et al., 2012]. Detta liknar kostnaden för den randomiserade algoritmen om d  på grund av den genomsnittliga kostnaden för den randomiserade metoden beror på den genomsnittliga graden). Detta villkor är sant i en mängd olika tillämpningar. Till exempel, i rumslig statistik använder vi ofta tvådimensionella rutnätsstrukturerade grafer, där den maximala graden är fyra och den genomsnittliga graden är något mindre än 4. Som ett annat exempel, för att tillämpa grafbaserad märkning förökning på Facebook grafen (för att upptäcka spridningen av sjukdomar, till exempel), är det genomsnittliga antalet vänner runt 200 men ingen användare har mer än sju tusen vänner. 2 Det maximala antalet vänner skulle vara ännu mindre om vi avlägsnade kanter baserat på närhet. Ett icke-sparsivt exempel där GS är effektivt är kompletta grafer, eftersom den genomsnittliga graden och den maximala graden här är båda (n − 1). GS-regeln är således effektiv för att optimera täta kvadratiska funktioner. Å andra sidan kan GS vara mycket ineffektivt för stjärngrafer. Om varje kolumn av A har som mest c non-noles och varje rad har högst r non-noles, då för många anmärkningsvärda fall av problem h 1 kan vi genomföra GS-regeln i O(cr log n) tid genom att behålla Ax samt lutningen och igen med hjälp av en max-heap (se tillägg A). GS kommer således att vara effektivt om cr liknar antalet icke-nollor i A dividerat med n. Annars Dhillon et al. [2011] visar att vi kan approxima GS regeln för problem h 1 med ingen g i funktioner genom att lösa en närmaste granne problem. Deras analys av GS-regeln i det konvexa fallet ger dock samma konvergensgrad som erhålls genom slumpmässigt urval (även om den konstanta faktorn kan vara mindre med en faktor upp till n). Mer nyligen, Shrivastava och Li [2014] ger en allmän metod för att approximera GS-regeln för problem h 1 med ingen g i funktioner genom att skriva det som en maximal inre produkt sökproblem. Vi är intresserade av att lösa konvex optimering problem 1 Vi kan också överväga något mer allmänna fall som funktioner som definieras på hyper-kanter [Richtárik och Takáč, 2015], förutsatt att vi fortfarande kan utföra n koordinat uppdateringar för en liknande kostnad till en gradient utvärdering. 2 https://recordsetter.com/world-record/facebook-friends 2 där  en koordinatvis L-Lipschitz kontinuerlig, dvs. för varje i = 1,...., n, där e i är en vektor med en en i läge i och noll i alla andra positioner. För två-differentiable funktioner, är detta likvärdigt med antagandet att de diagonala elementen i hessian begränsas i magnitud av L. I kontrast, det typiska antagandet som används för gradient metoder är att  till är Den koordinat-descent metod med konstant steg-storlek är baserad på iteration Den randomiserade koordinat-urval regel väljer i k enhetligt från uppsättningen {1, 2,.., n}. Alternativt väljer GS-regeln koordinaten med den största riktningsderivatan. Under endera regeln, eftersom f är koordinatmässigt Lipschitz kontinuerlig, vi får följande bundna på de framsteg som görs av varje iteration: Vi fokuserar på fallet där f är μ-starkt konvex, vilket innebär att, för vissa positiva μ, vilket innebär att där x * är den optimala lösningen av (1). Denna gräns erhålls genom att minimera båda sidor av (3) med avseende på y. Konditionering på σ-fältet F k−1 genereras av sekvensen {x 0, x 1,. ., x k-1 }, och med förväntningar på båda sidor av (2), när i k väljs med enhetlig provtagning vi få Använda (4) och subtrahera f (x * ) från båda sidor, vi får Detta är ett specialfall av Nesterov [2012, Theorem 2] med α = 0 i sin notation.  Vi tänker nu på de framsteg som GS-regeln innebär. Genom definitionen av i k, Tillämpa denna ojämlikhet till (2), vi får som tillsammans med (4), innebär att detta är ett specialfall av Boyd och Vandenberghe [2004, § 9.4.3], betraktar GS-regeln som utför brantaste nedstigning i 1-normen. Även om detta är snabbare än vad som är känt för cykliskt koordinatval [Beck och Tetruashvili, 2013] och innehar deterministiskt snarare än i förväntan, är denna siffra densamma som den som anges i (5). Bristen på den befintliga GS-analysen är att för mycket går förlorat när vi använder ojämlikheten i (6). För att undvika behovet av att använda denna ojämlikhet, mäter vi istället stark konvexitet i 1-normen, dvs., som är analogen av (3). Minimera båda sidor med avseende på y, vi får som använder sig av konvex konjugat (och Vandenberghe, 2004, §3.3). Använda (8) i (2) och det faktum att ( ∞ för GS-regeln, vi får Det är uppenbart att om μ 1 = μ/n, då de hastigheter som underförs av (5) och (9) är identiska, men (9) är snabbare om μ 1 > μ/n. I bilaga B visar vi att relationen mellan μ och μ 1 kan erhållas genom förhållandet mellan de fyrkantiga normerna  och ·. I synnerhet har vi således, på en ytterlighet GS regeln får samma hastighet som enhetligt urval (μ 1  på μ/n). Vid den andra ytterligheten kan det dock vara snabbare än ett enhetligt urval med en faktor av n (μ 1 μ). Denna analys, att GS regeln endast får samma bundna som slumpmässiga urval i ett extremt fall, stöder bättre praktiskt beteende GS.  Vi illustrerar dessa två ytterligheter med det enkla exemplet på en kvadratisk funktion med en diagonal hessian Vi bevisar riktigheten av denna formel för μ 1 i bilaga C. Parametern μ 1 uppnår sin nedre gräns när alla λ i är lika, λ 1 = · · = λ n = α > 0, i vilket fall alltså enhetligt urval gör liksom GS-regeln om alla element i lutningen ändras i exakt samma takt. Detta är rimligt: under detta villkor finns det ingen uppenbar fördel med att välja koordinaten för att uppdatera på ett smart sätt. Intuitivt kan man förvänta sig att det gynnsamma fallet för Gauss-Southwell regeln skulle vara där en λ i är mycket större än de andra. I detta fall liknar emellertid μ 1 åter μ/n. För att uppnå den andra ytterligheten, anta att λ 1 = β och λ 2 = λ 3 = · · = λ n = α med α ≥ β. I detta fall har vi μ = β och om vi tar α → ∞, då har vi μ 1 → β, så μ 1 → μ. Detta fall är mycket mindre intuitivt; GS är n gånger snabbare än slumpmässig koordinat val om en del av lutningen förändras mycket långsammare än de andra. I det åtskiljbara kvadratiska fallet ovan ges μ 1 av det harmoniska medelvärdet av hessianens eigenvärden dividerat med n. Det harmoniska medelvärdet domineras av dess minsta värden, och det är därför som ha ett litet värde är ett anmärkningsvärt fall. Dessutom har det harmoniska medelvärdet delat med n en tolkning i termer av processer som "arbetar tillsammans" [Ferger, 1931]. Om varje λ i representerar den tid som varje process tar för att avsluta en uppgift (t.ex., stora värden av λ i motsvarar långsamma arbetare), är μ den tid som krävs av den snabbaste arbetaren för att slutföra uppgiften, och μ 1 är den tid som behövs för att slutföra uppgiften om alla processer fungerar tillsammans (och har oberoende effekter). Med hjälp av denna tolkning ger GS-regeln den största fördelen jämfört med slumpmässigt urval när det inte är effektivt att arbeta tillsammans, vilket innebär att om n-processerna fungerar tillsammans, då är uppgiften inte löst mycket snabbare än om den snabbaste arbetaren utförde uppgiften ensam. Detta ger en tolkning av det icke-intuitiva scenariot där GS ger störst nytta: om alla arbetstagare har samma effektivitet, löser de tillsammans problemet n gånger snabbare. På samma sätt, om det finns en långsam arbetare (stor λ i ), då problemet löses ungefär n gånger snabbare genom att arbeta tillsammans. Å andra sidan, om de flesta arbetstagare är långsamma (många stora λ i ), då arbetar tillsammans har liten nytta. Överväga standard linjär-prediction ram, där vi har inkluderat en snedvariabel β (ett exempel på problem h 1 ). Vanligtvis är regularisering parametern σ av snedvariabeln inställd på att vara mycket mindre än regularization parametern λ av de andra covariates, för att undvika fördomar mot en global förändring i prediktorn. Om man antar att det inte finns någon dold stark konvexitet i summan, har detta problem den struktur som beskrivs i föregående avsnitt (μ 1  på μ) där GS har den största fördelen över slumpmässigt urval. Betrakta den mer allmänna scenario där vi har en Lipschitz konstant L i för den partiella derivatan av f med avseende på varje koordinat i, och vi använder en koordinat-beroende steg-storlek vid varje iteration: Genom logiken av (2), i denna miljö vi har och därmed en konvergens av notera att L = max i {L i}, vi har således, konvergensen som baseras på L i kommer att vara snabbare, förutsatt att åtminstone en iteration väljer en i k med L i k < L. I värsta fall, dock (13) innehar med jämlikhet även om L i är distinkt, som vi kan behöva uppdatera en koordinat med L i = L på varje iteration. (Till exempel, överväga en separat funktion där alla utom en koordinat initieras till sitt optimala värde, och den återstående koordinaten har L i = L.) I Avsnitt 6, diskuterar vi urvalsregler som införlivar L i för att uppnå snabbare hastigheter när L i är distinkt, men först anser vi effekten av exakt koordinatoptimering på valet av L i k. För problem med funktioner i form h 1 och h 2, Vi kan ofta utföra exakt (eller numeriskt mycket exakt) koordinatoptimering, även om den objektiva funktionen inte är quadratic (t.ex., genom att använda en linesearch eller en sluten-form uppdatering). Observera att (12) fortfarande håller när du använder exakt koordinatoptimering snarare än att använda en stegstorlek på 1/L i k, som i detta fall vi har som motsvarar (11). I praktiken leder dock exakt koordinatoptimering till bättre prestanda. I detta avsnitt visar vi att användningen av GS-regeln resulterar i en konvergenshastighet som faktiskt är snabbare än (9) för problem med distinkt L i när funktionen är kvadratisk, eller när funktionen inte är kvadratisk men vi utför exakt koordinatoptimering. Den viktigaste egenskapen vi använder är att, efter att vi har utfört exakt koordinatoptimering, är vi garanterade att ha om inte x k+1 är den optimala lösningen. Därför väljer vi aldrig samma koordinat två gånger i rad, vilket garanterar att ojämlikhet (13) är strikt (med distinkt L i ) och exakt koordinatoptimering är snabbare. Vi noterar att förbättringen kan vara marginell, eftersom vi helt enkelt kan växla mellan de två största L i-värdena. Men, överväga att minimera h 2 när grafen är gles; efter uppdatering i k, är vi garanterade att ha i k f (x k+m ) = 0 för alla framtida iterationer (k + m) tills vi väljer en variabel i k+m-1 som är en granne till node i k i grafen. Således, om de två största L i inte är anslutna i grafen, GS kan inte helt enkelt alternera mellan de två största L i. Genom att använda denna egenskap, i bilaga D visar vi att GS-regeln med exakt koordinatoptimering för problem h 2 under en kedjestrukturerad graf har en konvergenshastighet av formen bland på varandra följande noder i, j, och k. Konsekvensen av detta resultat är att om de stora L i-värdena är mer än två kanter från varandra i grafen, då får vi en mycket bättre konvergenshastighet. Vi antar att för allmänna grafer, kan vi få en gräns som beror på det största värdet av ρ G 2 bland alla noder i och j ansluten av en väg av längd 1 eller 2. Observera att vi kan få liknande resultat för problem h 1, genom att bilda en graf som har en kant mellan noder i och j när motsvarande variabler är båda gemensamt icke-noll i minst en rad av A. Om L i är kända, Nesterov [2012] visade att vi kan få en snabbare konvergens genom provtagning proportionellt mot L i. Vi granskar detta resultat nedan och jämför det med GS-regeln, och föreslår sedan en förbättrad GS-regel för detta scenario. Även om vi i detta avsnitt kommer att anta att L i är kända, detta antagande kan mildras med hjälp av en backtracking förfarande [Nesterov, 2012, §6.1]. Tar förväntan på (11) under distribution p i = L i / n j=1 L j och fortsätter som tidigare, får vi L j är genomsnittet av Lipschitz konstanter. Detta visades av Leventhal och Lewis [2010] och är ett specialfall av Nesterov [2012, Theorem 2] med α = 1 i sin notation. Denna hastighet är snabbare än (5) för enhetlig provtagning om någon L i skiljer sig åt. Enligt vår analys kan denna kurs vara snabbare än (9) för GS-regeln. På den ena ytterligheten, om μ 1 = μ/n och någon L i skiljer sig, då detta Lipschitz provtagningsschema är snabbare än vår hastighet för GS. I samband med problemet i avsnitt 4.1 kan vi faktiskt göra Lipschitz provtagning snabbare än GS med en faktor på nästan n genom att göra en λ i mycket större än alla andra (återkalla att vår analys inte visar någon fördel för GS-regeln över slumpmässigt urval när endast en λ i är mycket större än de andra). Vid den andra ytterligheten, i vårt exempel från avsnitt 4.1 med många stora α och en liten β, GS och Lipschitz provtagningsfrekvensen är densamma när n = 2, med en hastighet av (1 − β/(α + β)). GS-hastigheten kommer dock att vara snabbare än provtagningsfrekvensen för Lipschitz för alla α > β när n > 2, eftersom provtagningsfrekvensen för Lipschitz är (1 − β/(n − 1)α + β)), vilket är långsammare än GS-hastigheten (1 − β/(α + (n − 1)β)). Eftersom varken Lipschitz provtagning eller GS dominerar den andra i allmänhet, är vi motiverade att överväga om snabbare regler är möjliga genom att kombinera de två tillvägagångssätten. Faktum är att vi får en snabbare hastighet genom att välja 7 i k som minimerar (11), vilket leder till den regel som vi kallar Gauss-Southwell-Lipschitz (GSL) regel. Efter ett liknande argument som avsnitt 4, men med användning av (11) i stället för punkt 2, får GSL-regeln en konvergenskvot där μL är den starka konvexitetskonstanten med avseende på normen Detta visas i bilaga E, och i bilaga F visar vi att GSL-regeln därför alltid är minst lika snabb som den snabbaste GS-regeln och Lipschitz-provtagningen. Det kan faktiskt vara mer än en faktor av n snabbare än att använda Lipschitz provtagning, medan det kan få en hastighet närmare den minsta L i, i stället för den maximala L i som den klassiska GS regeln beror på. En intressant egenskap hos GSL-regeln för kvadratiska funktioner är att det är den optimala myopiska koordinatuppdateringen. Det vill säga, om vi har ett orakel som kan välja koordinaten och den steg-storlek som minskar f med den största mängden, dvs., är detta likvärdigt med att använda GSL-regeln och uppdateringen i (10). Detta beror på att (11) håller med jämlikhet i det kvadratiska fallet, och valet α k = 1/L i k ger den optimala stegstorleken. Även om snabbare system kan vara möjliga med icke-myopiska strategier som skickligt väljer sekvensen av koordinater eller steg-storlekar, om vi bara kan utföra en iteration, då GSL regeln inte kan förbättras. [Bo och Sminchisescu, 2008] och lågrankade tensor approximationer [Li et al., 2015]. Med hjälp av ett argument som liknar (14) tillämpas även vår GSL-frekvens på MI-regeln, vilket förbättrar de befintliga gränserna för denna strategi. GSL-regeln är dock mycket billigare och kräver ingen särskild struktur (återkalla att vi kan uppskatta L i som vi går). Dhillon m.fl. [2011] diskutera en intressant koppling mellan GS-regeln och närmaste granne-sök (NNS) problem för mål för formen Detta är ett specialfall av h 1 med no g i funktioner, och dess lutning har den speciella formen där r(x) =  på (Ax). Vi använder symbolen r eftersom det är den kvarvarande vektorn (Ax − b) i specialfallet av minst kvadrater. För detta problem struktur GS regeln har formen där a i betecknar kolumn i av A för i = 1,..., n. Dhillon et al. [2011] föreslår en approximation av ovanstående argmax genom att lösa följande NNS-problem där i i intervallet (n + 1) till 2n avser negationen −(a i‐n ) i kolumnen (i − n) och om den valda i k är större än n återvänder vi (i − n). Vi kan motivera denna approximation med hjälp av logiken NNS beräknar alltså en approximation till GS-regeln som är partisk mot koordinater där en i är liten. Observera att denna formulering är likvärdig med GS-regeln i specialfallet att a i = 1 (eller någon annan konstant) för alla i. Shrivastava och Li [2014] mer nyligen har övervägt fallet där en i ≤ 1 och införlivar befogenheter hos en i i i NNS för att ge en bättre approximation. Ytterligare en intressant egenskap hos GSL-regeln är att vi ofta kan formulera den exakta GSL-regeln som ett normaliserat NNS-problem. Särskilt för problem (16) kommer Lipschitz-konstanterna ofta att ha formen L i = γ a i 2 för en viss positiv skalar γ. Till exempel har minst kvadrater γ = 1 och logistisk regression har γ = 0,25. När Lipschitz konstanter har denna form, kan vi beräkna den exakta GSL-regeln genom att lösa en normaliserad NNS-problem, Exaktheten i denna formel följer eftersom Således, formen av Lipschitz konstant smidigt avlägsnar fördomar mot mindre värden av ett i som blir introducerat när vi försöker formulera den klassiska GS-regeln som ett NNS-problem. Intressant nog behöver vi i denna miljö inte känna till γ för att genomföra GSL-regeln som ett NNS-problem. I många tillämpningar är den exakta GS-regeln för ineffektiv för att kunna användas praktiskt. En beräkningsmässigt billigare ungefärlig GS-regel kan dock finnas tillgänglig. Ungefärliga GS-regler under multiplikativa och additiva fel övervägdes av Dhillon et al. [2011] i det konvexa fallet, men i detta sammanhang liknar konvergenssatsen den som uppnås genom slumpmässigt urval. I detta avsnitt ger vi hastigheter beroende på μ 1 för ungefärliga GS-regler. I det multiplikativa felsystemet väljer den ungefärliga GS-regeln en i k som uppfyller för vissa k  på [0, 1). I denna regim, vår grundläggande bunden på framsteg (2) fortfarande innehar, som det definierades för alla i k. Vi kan införliva denna typ av fel i vår lägre gräns (8) för att erhålla Detta innebär en konvergensgrad av Således, konvergensen av metoden är nästan identisk med att använda den exakta GS-regeln för små k (och det bryts graciöst med k ). Detta är i motsats till att ha ett fel i lutningen [Friedlander och Schmidt, 2012], där felet måste minska till noll över tid. I det additiva felsystemet väljer den ungefärliga GS-regeln en i k som uppfyller vissa k ≥ 0. I bilaga G visar vi att enligt denna regel har vi där L 1 är Lipschitz-konstanten av  och f med avseende på 1-normen. Observera att L 1 kan vara betydligt större än L, så den andra delen av den maximala i A k är sannolikt den mindre delen om inte i är stora. Detta system är närmare fallet med ett fel i lutningen, eftersom k 10 måste minska till noll för att uppnå konvergens. Detta resultat innebär att ett tillräckligt villkor för algoritmen att erhålla en linjär konvergenshastighet är att felen k konvergerar till noll vid en linjär hastighet. Dessutom, om felen uppfyller k = O(ρ k ) för vissa ρ < (1 − μ 1 /L), då konvergensen av metoden är samma som om vi använde en exakt GS regel. Å andra sidan, om k inte minskar till noll, kan vi hamna upprepade gånger uppdatera samma fel koordinat och algoritmen kommer inte att konvergera (även om vi kan byta till den randomiserade metoden om detta upptäcks). En av de viktigaste motivationerna för återuppvaknandet av intresset för koordinat nedstigande metoder är deras prestanda på problem i form där f är slät och konvex och g i är konvex, men möjligen icke-smooth. Detta inkluderar problem med 1 -reglering, och optimering med lägre och / eller övre gränser på variablerna. I likhet med proximalgradientmetoder kan vi tillämpa den proximala operatören på koordinatuppdateringen, där Richtárik och Takáč [2014] med slumpmässiga koordinatval visar att denna metod har en konvergensgrad som liknar det icke-konsistenta/smooth-fallet. Det finns flera generaliseringar av GS-regeln till detta scenario. Här överväger vi tre möjligheter, som alla är likvärdiga med GS-regeln om g i inte är närvarande. För det första, GS-s regeln väljer koordinaten med den mest negativa riktning derivat. Denna strategi är populär för 1 -reglering [Shevade och Keerthi, 2003, Wu och Lange, 2008, Li och Osher, 2009 och i allmänhet ges av [se Bertsekas, 1999, §8.4] Emellertid kan längden på steget ( x k+1 - x k ) vara godtyckligt liten enligt detta val. I kontrast, GS-r regeln väljer den koordinat som maximerar längden på steg Yun, 2009, Dhillon et al., 2011], Denna regel är effektiv för bundna-konstruerade problem, men det ignorerar förändringen i den icke-smooth term. Slutligen, GS-q regeln maximerar framsteg antar en kvadratisk övre gräns på f [Tseng och Yun, 2009], Även om den minst intuitiva regeln, GS-q regeln verkar ha de bästa teoretiska egenskaper. Vidare, om vi använder L i stället för L i GS-q-regeln (som vi kallar GSL-q-strategin), då får vi GSL-regeln om g i 11 inte är närvarande. Däremot ger inte användningen av L i stället för L i GS-r-regeln (som vi kallar GSL-r-strategin) GSL-regeln som specialfall. I bilaga H visar vi att användningen av GS-q-regeln ger en konvergenshastighet där k avgränsas ovan av ett mått på g i:s icke-linjäritet längs möjliga koordinatuppdateringar gånger det omvända tillståndet μ 1 /L. Observera att k går till noll när k ökar och vi antar att ovanstående gräns faktiskt håller med k = 0. I bilaga H ger vi däremot också motexempel som visar att ovanstående sats inte håller med k = 0 för GS-s- eller GS-r-regeln, även om du ersätter minimivärdet med ett maximum. Således skulle varje gräns för GS-s eller GS-r regeln vara långsammare än den förväntade hastigheten vid slumpmässigt urval, medan GS-q regeln leder till en bättre gräns. Vi jämför först effektiviteten av olika koordinat urvalsregler på följande enkla fall av h 1. 2 -regulariserade gles minst kvadrater: Här anser vi problemet en instans av problem h 1. Vi sätter A till att vara en m by n matris med poster provtagna från en N (0, 1) distribution (med m = 1000 och n = 1000). Vi lade sedan till 1 till varje post (för att framkalla ett beroende mellan kolumner), multiplicerade varje kolumn med ett prov från N (0, 1) multiplicerat med tio (för att inducera olika Lipschitz konstanter över koordinaterna), och endast höll varje post av A icke-noll med sannolikhet 10 log(n)/n (en gleshetsnivå som tillåter Gauss-Southwell regeln att tillämpas med kostnad O(log 3 (n)). Vi sätter λ = 1 och b = Ax + e, där poster av x och e drogs från en N (0, 1) distribution. I denna inställning använde vi en stegstorlek på 1/L i för varje koordinat i, vilket motsvarar exakt koordinatoptimering. 2 -regulariserade gles logistisk regression: Här anser vi att problemet Vi ställer in en T i att vara raderna av A från föregående problem, och ställa in b = tecken(Ax), men slumpmässigt vända varje b i med sannolikhet 0,1. I den här inställningen jämförde vi med en stegstorlek på 1/L i med exakt koordinatoptimering. Överbestämda täta minsta kvadrater: Här ser vi problemet men, till skillnad från det tidigare fallet, ställer vi inte in element av A till noll och vi gör A har dimension 1000 av 100. Eftersom systemet är överbestämt, behöver det inte en explicit starkt konvex regularizer för att inducera global stark konvexitet. I detta fall innebär densitetsnivån att den exakta GS-regeln inte är effektiv. Därför använder vi en balltreestruktur [Omohundro, 1989] för att genomföra en effektiv ungefärlig GS-regel baserad på kopplingen till NNS-problemet upptäckt av Dhillon et al. Kommissionens genomförandeförordning (EU) nr 668/2014 av den 13 juni 2014 om tillämpningsföreskrifter för Europaparlamentets och rådets förordning (EU) nr 1151/2012 om kvalitetsordningar för jordbruksprodukter och livsmedel (EUT L 179, 19.6.2014, s. 1). Å andra sidan kan vi beräkna den exakta GSL-regeln för detta problem som ett NNS-problem som diskuteras i avsnitt 6.3. 1 -regularized underdefinierad gles minst kvadrater: Här anser vi att det icke-smooth problem Vi genererar A som vi gjorde för 2 -regularized gles minst kvadrater problem, utom med dimension 1000 av 10000. Detta problem är inte globalt starkt konvext, utan kommer att vara starkt konvext längs de dimensioner som inte är noll i den optimala lösningen. Vi ritar den objektiva funktionen (delad på dess ursprungliga värde) av koordinat nedstigning under olika urvalsregler i Figur 1. Även på dessa enkla dataset ser vi dramatiska skillnader i prestanda mellan de olika strategierna. GS-regeln överträffar i synnerhet det slumpmässiga urvalet av koordinater (och cykliskt urval) med stor marginal i samtliga fall. Lipschitz provtagningsstrategi kan minska denna klyfta, men den är fortfarande stor (även när en ungefärlig GS-regel används). Skillnaden mellan GS och slumpmässigt urval verkar vara mest dramatisk för 1 -regulariserade problemet; GS reglerna tenderar att fokusera på icke-noll variabler medan de flesta randomiserade / cykliska uppdateringar fokuserar på nollvariabler, som tenderar att inte flytta sig från noll. 3 Exakt koordinatoptimering och användning av GSL regeln verkar ge blygsamma men konsekventa förbättringar. De tre icke-smooth GS- * reglerna hade nästan identiska prestanda trots sina olika teoretiska egenskaper. GSL-q-regeln gav bättre prestanda än GS- *-reglerna, medan GSL-r-varianten fungerade sämre än till och med cykliska och slumpmässiga strategier. Vi fann det också möjligt att göra GS-s regeln fungerar dåligt genom att störa initiering bort från noll. Medan dessa experiment ritar prestanda i termer av antalet iterationer, i bilaga I visar vi att GS- * regler kan också vara fördelaktigt i fråga om körtid. Vi nästa överväga ett exempel på problem h 2, utför etikettutbredning för halvövervakad lärande i " två månar " dataset [Zhou et al., 2004]. Vi genererar 500 prover från denna datauppsättning, slumpvis märka fem punkter i data, och ansluta varje nod till sina fem närmaste grannar. Denna höga nivå av sparhet är typisk för grafbaserade metoder för halvövervakad inlärning, och gör det möjligt att genomföra den exakta Gauss-Southwell regeln effektivt. Vi använder det kvadratiska märkningskriteriet för Bengio et al. [2006], vilket möjliggör exakt koordinatoptimering och är normalt optimerad med cyklisk koordinatnedstigning. Vi ritar upp resultatet under olika urvalsregler i figur 2. Här ser vi att även cyklisk koordinat nedstigning överträffar randomiserad koordinat nedstigning, men att GS- och GSL-reglerna ger ännu bättre prestanda. Vi noterar att GS- och GSL-reglerna fungerar på samma sätt på detta problem eftersom Lipschitz-konstanterna inte varierar mycket. Det är uppenbart att GS-regeln inte är praktisk för alla problem där randomiserade metoder är tillämpliga. Icke desto mindre har vi visat att till och med ungefärliga GS-regler kan uppnå bättre konvergensnivåer än fullständigt randomiserade metoder. Vi har gett en liknande motivering för användningen av exakt koordinatoptimering, 3 För att minska kostnaden för GS-s-metoden i detta sammanhang, Shevade och Keerthi [2003] överväga en variant där vi först beräkna GS-s-regeln för icke-nollvariablerna och om ett element är tillräckligt stor då de inte anser nollvariabler. 14 och vi noterar att vårt argument också kan användas för att motivera användningen av exakt koordinatoptimering inom randomiserade koordinatnedstigningsmetoder (som används i våra experiment). Vi har också föreslagit den förbättrade GSL-regeln, och övervägt ungefärliga/proximala varianter. Vi förväntar oss att vår analys också gäller block uppdateringar genom att använda blandade normer · p,q, och kan användas för accelererade / parallella metoder [Fercoq och Richtárik, 2013], för primal-dual rates av dubbla koordinat uppstigning [Shalev-Shwartz och Zhang, 2013], för successiva prognosmetoder [Leventhal och Lewis, 2010], för att öka algoritmer [Rätsch et al., 2001], och för scenarier utan stark konvexitet under allmänna felgränser [Luo och Tseng, 1993].
Specifikt, ett konvext optimeringsproblem som minimerar en starkt konvex objektiv funktion ansågs i REF.
Coordinate Descent Converges Faster with the Gauss-Southwell Rule Than Random Selection
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}