A Unified Analysis of Stochastic Optimization Methods Using Jump System Theory and Quadratic Constraints
Hu, Bin ; Seiler, Peter and Rantzer, Anders LU
(2017)
Conference on Learning Theory
65.
p.1157-1189
- Abstract
- We develop a simple routine unifying the analysis of several important recently-developed stochastic optimization methods including SAGA, Finito, and stochastic dual coordinate ascent (SDCA). First, we show an intrinsic connection between stochastic optimization methods and dynamic jump systems, and propose a general jump system model for stochastic optimization methods. Our proposed model recovers SAGA, SDCA, Finito, and SAG as special cases. Then we combine jump system theory with several simple quadratic inequalities to derive sufficient conditions for convergence rate certifications of the proposed jump system model under various assumptions (with or without individual convexity, etc). The derived conditions are linear matrix... (More)
- We develop a simple routine unifying the analysis of several important recently-developed stochastic optimization methods including SAGA, Finito, and stochastic dual coordinate ascent (SDCA). First, we show an intrinsic connection between stochastic optimization methods and dynamic jump systems, and propose a general jump system model for stochastic optimization methods. Our proposed model recovers SAGA, SDCA, Finito, and SAG as special cases. Then we combine jump system theory with several simple quadratic inequalities to derive sufficient conditions for convergence rate certifications of the proposed jump system model under various assumptions (with or without individual convexity, etc). The derived conditions are linear matrix inequalities (LMIs) whose size roughly scale with the size of the training set. We make use of the symmetry in the stochastic optimization methods and reduce these LMIs to some equivalent small LMIs whose sizes are at most 3 by 3. We solve these small LMIs to provide analytical proofs of new convergence rates for SAGA, Finito and SDCA (with or without individual convexity). We also explain why our proposed LMI fails in analyzing SAG. We reveal a key difference between SAG and other methods, and briefly discuss how to extend our LMI analysis for SAG. An advantage of our approach is that the proposed analysis can be automated for a large class of stochastic methods under various assumptions (with or without individual convexity, etc). (Less)
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/6976dd16-cb43-4b48-9a56-b0c85ec1b112
- author
- Hu, Bin
; Seiler, Peter
and Rantzer, Anders
LU
- organization
- publishing date
- 2017-07-07
- type
- Chapter in Book/Report/Conference proceeding
- publication status
- published
- subject
- host publication
- Proceedings of Machine Learning Research
- volume
- 65
- pages
- 33 pages
- conference name
- Conference on Learning Theory
- conference location
- Amsterdam, Netherlands
- conference dates
- 2017-07-07 - 2017-07-10
- language
- English
- LU publication?
- yes
- id
- 6976dd16-cb43-4b48-9a56-b0c85ec1b112
- date added to LUP
- 2017-08-11 09:50:19
- date last changed
- 2018-11-21 21:33:49
@inproceedings{6976dd16-cb43-4b48-9a56-b0c85ec1b112,
abstract = {{We develop a simple routine unifying the analysis of several important recently-developed stochastic optimization methods including SAGA, Finito, and stochastic dual coordinate ascent (SDCA). First, we show an intrinsic connection between stochastic optimization methods and dynamic jump systems, and propose a general jump system model for stochastic optimization methods. Our proposed model recovers SAGA, SDCA, Finito, and SAG as special cases. Then we combine jump system theory with several simple quadratic inequalities to derive sufficient conditions for convergence rate certifications of the proposed jump system model under various assumptions (with or without individual convexity, etc). The derived conditions are linear matrix inequalities (LMIs) whose size roughly scale with the size of the training set. We make use of the symmetry in the stochastic optimization methods and reduce these LMIs to some equivalent small LMIs whose sizes are at most 3 by 3. We solve these small LMIs to provide analytical proofs of new convergence rates for SAGA, Finito and SDCA (with or without individual convexity). We also explain why our proposed LMI fails in analyzing SAG. We reveal a key difference between SAG and other methods, and briefly discuss how to extend our LMI analysis for SAG. An advantage of our approach is that the proposed analysis can be automated for a large class of stochastic methods under various assumptions (with or without individual convexity, etc).}},
author = {{Hu, Bin and Seiler, Peter and Rantzer, Anders}},
booktitle = {{Proceedings of Machine Learning Research}},
language = {{eng}},
month = {{07}},
pages = {{1157--1189}},
title = {{A Unified Analysis of Stochastic Optimization Methods Using Jump System Theory and Quadratic Constraints}},
url = {{https://lup.lub.lu.se/search/files/29452823/2017Hu_COLT.pdf}},
volume = {{65}},
year = {{2017}},
}