Den Frank-Wolfe optimeringsalgoritm har nyligen återfått popularitet för maskininlärning program på grund av dess projektion-fri egendom och dess förmåga att hantera strukturerade begränsningar. Men i den stokastiska inlärningsmiljön, är den fortfarande relativt understuderad jämfört med gradienten nedstigning motsvarighet. I detta arbete, utnyttja en ny variansreduktion teknik, föreslår vi två stokastiska Frank-Wolfe varianter som avsevärt förbättrar tidigare resultat i fråga om antalet stokastiska gradient utvärderingar som krävs för att uppnå 1 − noggrannhet. Till exempel förbättrar vi från O( 1 ) till O( ln 1 ) om den objektiva funktionen är smidig och starkt konvex, och från O( ) om den objektiva funktionen är slät och Lipschitz. Den teoretiska förbättringen observeras också i experiment på verkliga datauppsättningar för en flerklassig klassificeringsapplikation.
REF introducerar en stokastisk-CGM-metod med variansreduktion som uppnår komplexitet av O(1/ε 3 ) när det förväntade målet är smidigt och Lipschitz kontinuerlig.
Variance-Reduced and Projection-Free Stochastic Optimization
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}