Onlineoptimering har varit ett framgångsrikt ramverk för att lösa storskaliga problem under beräkningsbegränsningar och partiell information. Nuvarande metoder för online-konvex optimering kräver antingen en projektion eller exakt gradientberäkning vid varje steg, vilka båda kan vara oöverkomligt dyra för storskaliga tillämpningar. Samtidigt finns det en växande trend av icke konvex optimering i maskininlärning gemenskap och ett behov av online-metoder. Kontinuerliga DR-submodulära funktioner, som uppvisar ett naturligt minskande returtillstånd, har nyligen föreslagits som en bred klass av icke-konvexa funktioner som kan optimeras effektivt. Även om online-metoder har införts, lider de av liknande problem. I detta arbete föreslår vi Meta-Frank-Wolfe, den första online projektionfri algoritm som använder stokastiska gradient uppskattningar. Algoritmen bygger på en noggrann provtagning av gradienter i varje omgång och uppnår den optimala O ( ε T ) motstående ånger gräns för konvex och kontinuerlig submodulär optimering. Vi föreslår också One-Shot Frank-Wolfe, en enklare algoritm som kräver bara en enda stokastisk gradient uppskattning i varje runda och uppnår en O(T 2/3 ) stokastisk ångra bundet för konvex och kontinuerlig submodulär optimering. Vi använder våra metoder för att utveckla en ny "lyftande" ram för online diskret submodulär maximering och ser också att de överträffar nuvarande toppmoderna tekniker på olika experiment.
I REF generaliserade de sitt resultat ytterligare och utvecklade en projektion-fri algoritm som endast kräver stokastiska gradient uppskattningar och uppnår en liknande ånger bundna.
Projection-Free Online Optimization with Stochastic Gradient: From Convexity to Submodularity
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}