Traditionella algoritmer för stokastisk optimering kräver projicering av lösningen vid varje iteration till en given domän för att säkerställa dess genomförbarhet. När man står inför komplexa domäner, såsom positiva halvdefinita kottar, kan projektionen bli dyr, vilket leder till en hög beräkningskostnad per iteration. I den här artikeln presenterar vi en ny algoritm som syftar till att minska antalet projektioner för stokastisk optimering. Den föreslagna algoritmen kombinerar styrkan i flera senaste utvecklingen inom stokastisk optimering, inklusive mini-batch, extra-gradient, och epokgradient nedstigning, för att effektivt utforska jämnhet och stark konvexitet. Vi visar, både i förväntan och med stor sannolikhet, att när den objektiva funktionen är både smidig och starkt konvex, den föreslagna algoritmen uppnår den optimala O(1/T ) graden av konvergens med endast O(log T ) prognoser. Vår empiriska studie verifierar det teoretiska resultatet.
Nyligen, REF föreslå en algoritm för stokastisk starkt konvex och smidig optimering med O(σ log 2 T ) projektioner.
O(logT) Projections for Stochastic Optimization of Smooth and Strongly Convex Functions
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}