Abstrakt. I detta papper introducerar vi en ny stokastisk approximation (SA) typ algoritm, nämligen den randomiserade stokastisk gradient (RSG) metod, för att lösa en viktig klass av ickelinjära (eventuellt icke konvexa) stokastisk programmering (SP) problem. Vi fastställer komplexiteten i denna metod för att beräkna en ungefärlig stationär punkt i ett icke-linjär programmeringsproblem. Vi visar också att denna metod har en nästan optimal konvergensgrad om problemet är konvext. Vi diskuterar en variant av algoritmen som består av att tillämpa en postoptimeringsfas för att utvärdera en kort lista över lösningar som genereras av flera oberoende körningar av RSG-metoden, och visar att en sådan modifiering gör det möjligt att avsevärt förbättra algoritmens storundvikande egenskaper. Dessa metoder är sedan specialiserade för att lösa en klass av simuleringsbaserade optimeringsproblem där endast stokastisk noll-order information finns tillgänglig.
I REF föreslogs en randomiserad stokastisk gradient (RSG) metod, och bevisade sin O(1/ ε T ) konvergenshastighet till en stationär punkt.
Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming
{'venue': 'SIAM Journal on Optimization', 'journal': 'SIAM Journal on Optimization', 'mag_field_of_study': ['Computer Science', 'Mathematics']}