Vi utvecklar en enkel rutin som förenar analysen av flera viktiga nyutvecklade stokastiska optimeringsmetoder, inklusive SAGA, Finito och stokastisk dual coordinate ascent (SDCA). Först visar vi en inneboende koppling mellan stokastiska optimeringsmetoder och dynamiska hoppsystem, och föreslår en allmän hoppsystemmodell för stokastiska optimeringsmetoder. Vår föreslagna modell återvinner SAGA, SDCA, Finito och SAG som specialfall. Då kombinerar vi hopp systemteori med flera enkla kvadratiska ojämlikheter för att härleda tillräckliga villkor för konvergens hastighet certifieringar av den föreslagna hoppa systemmodellen under olika antaganden (med eller utan individuell konvexitet, etc). De härledda villkoren är linjär matris ojämlikhet (LMI) vars storlekar ungefär skala med storleken på träningssetet. Vi använder symmetrin i de stokastiska optimeringsmetoderna och reducerar dessa LMI till några likvärdiga små LMI vars storlekar är högst 3 × 3. Vi löser dessa små LMI för att ge analytiska bevis på nya konvergensnivåer för SAGA, Finito och SDCA (med eller utan individuell konvexitet). Vi förklarar också varför vårt föreslagna LMI misslyckas med att analysera SAG. Vi avslöjar en viktig skillnad mellan SAG och andra metoder, och diskuterar kortfattat hur vi kan utöka vår LMI-analys för SAG. En fördel med vår strategi är att den föreslagna analysen kan automatiseras för en stor klass av stokastiska metoder enligt olika antaganden (med eller utan individuell konvexitet, etc).
Dessutom användes IQC också för att analysera de stokastiska optimeringsmetoderna REF.
A Unified Analysis of Stochastic Optimization Methods Using Jump System Theory and Quadratic Constraints
{'venue': 'COLT', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}