Enhetlig provtagning av träningsdata har ofta använts i traditionella stokastiska optimeringsalgoritmer som Proximal Stochastic Gradient Descent (prox-SGD) och Proximal Stochastic Dual Coordinate Ascent (prox-SDCA). Även om en enhetlig provtagning kan garantera att den provtagna stokastiska kvantiteten är en objektiv uppskattning av motsvarande verkliga kvantitet, kan den resulterande estimatorn ha en ganska hög varians, vilket negativt påverkar konvergensen av det underliggande optimeringsförfarandet. I detta papper studerar vi stokastisk optimering med viktig provtagning, vilket förbättrar konvergenshastigheten genom att minska den stokastiska variansen. Vi studerar specifikt prox-SGD med viktiga provtagningar och prox-SDCA med viktiga provtagningar. För prox-SGD, i stället för att anta enhetlig provtagning under hela utbildningsprocessen, använder den föreslagna algoritmen viktig provtagning för att minimera variansen av den stokastiska lutningen. För prox-SDCA syftar det föreslagna systemet för provtagning av betydelse till att uppnå ett högre förväntat dubbelt värde vid varje koordinatsteg. Vi tillhandahåller omfattande teoretisk analys för att visa att konvergensgraden med den föreslagna betydelsen provtagningsmetoder kan förbättras avsevärt under lämpliga förhållanden både för prox-SGD och för prox-SDCA. Experiment tillhandahålls för att verifiera den teoretiska analysen.
Även om den provtagna stokastiska kvantiteten är en opartisk uppskattning av motsvarande verkliga kvantitet, kan variansen av den resulterande stokastiska kvantiteten vara mycket hög eftersom enskilda uppskattningar kan variera betydligt över olika exempel REF.
Stochastic Optimization with Importance Sampling
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}