Detta papper behandlar stokastiska optimeringsproblem för en stor klass av objektiva funktioner, inklusive konvexa och kontinuerliga submodulära. Stochastic proximal gradient metoder har använts i stor utsträckning för att lösa sådana problem; dock är deras tillämplighet fortfarande begränsad när problemdimensionen är stor och projektionen på en konvex uppsättning är beräkning dyrt. Istället föreslås stokastiska villkorliga gradientalgoritmer som en alternativ lösning som förlitar sig på (i) Tillnärmelse av gradienter via en enkel genomsnittsteknik som kräver en enda stokastisk gradientbedömning per iteration; (ii) Lösa ett linjärt program för att beräkna nedstignings-/uppstigningsriktningen. Gradienten medelvärde teknik minskar bullret av gradient approximationer när tiden fortskrider, och ersätta projektion steg i proximala metoder med ett linjärt program minskar beräknings komplexiteten i varje iteration. Vi visar att under konvexitet och jämnhet antaganden, vår föreslagna stokastiska villkorad lutning metod konvergerar till det optimala objektiva funktionsvärdet med en sublinjär hastighet av O(1/t 1/3 ). Vidare, för en monoton och kontinuerlig DR-submodulär funktion och med förbehåll för en allmän konvex kroppsbegränsning, visar vi att vår föreslagna metod uppnår en (( (1 − 1/e)OPT − ) garanti (i förväntan) med O(1/ 3 ) stokastisk lutning beräkningar. Denna garanti matchar de kända hårdhetsresultaten och sluter gapet mellan deterministisk och stokastisk kontinuerlig submodulär maximering. Dessutom uppnår vi ((1/e)OPT − ) garanti efter drift på O(1/ 3 ) stokastiska gradienter för fallet att den objektiva funktionen är kontinuerlig DR-submodulär men icke-monoton och begränsningssatsen är en nedstängd konvex kropp. Genom att använda stokastisk kontinuerlig optimering som ett gränssnitt, ger vi också den första (1 − 1/e) tight approximation garanti för att maximera en monoton men stokastisk submodulär set funktion som omfattas av en allmän matrisrestriktion och (1/e) approximation garanti för icke-monoton fall. Numeriska experiment för både konvexa och submodulära inställningar tillhandahålls, och de illustrerar snabb konvergenstid för vår föreslagna stokastiska villkorade gradient metod i förhållande till alternativ.
Enligt vår kunskap är det första och enda arbete med en hastighet för den stokastiska CGM utan att öka batchstorlek är REF, som har komplexitet av O(1/ε 3 ).
Stochastic Conditional Gradient Methods: From Convex Minimization to Submodular Maximization
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}