A Unified Analysis of Stochastic Optimization Methods Using Jump System Theory and Quadratic Constraints
Abstract:
We develop a simple routine unifying the analysis of several important recently-developed stochastic optimization methods, including stochastic average gradient (SAG), SAGA, Finito, and stochastic dual coordinate ascent (SDCA). The basis is an intrinsic connection between stochastic optimization methods and dynamic jump systems. Our proposed model recovers SAG, SAGA, Finito and SDCA as special cases. Moreover, we combine jump system theory with quadratic constraints to derive sufficient conditions for convergence rate certifications of the jump system model under various assumptions. The derived conditions are linear matrix inequalities (LMIs). We make use of symmetry in the stochastic optimization methods and reduce the LMIs to sizes at most 4 by 4. The LMIs are then solved to provide analytical proofs of new convergence rates for SAGA, Finito and SDCA (with or without individual convexity). For SAG, we solve the LMIs numerically and obtain new numerical linear rate bounds. An advantage of our approach is that the proposed analysis can be automated for a large class of stochastic methods. Joint work with Bin Hu and Peter Seiler.
Biography:
Anders Rantzer received a PhD in 1991 from KTH, Stockholm, Sweden. After postdoctoral positions at KTH and at IMA, University of Minnesota, he joined Lund University in 1993 and was appointed professor of Automatic Control in 1999. The academic year of 2004/05 he was visiting associate faculty member at Caltech and 2015/16 he was Taylor Family Distinguished Visiting Professor at University of Minnesota. Since 2008 he coordinates the Linnaeus center LCCC at Lund University. Rantzer is an editorial board member fo Proceedings of the IEEE and several other publications. He is a winner of the SIAM Student Paper Competition, the IFAC Congress Young Author Price and the IET Premium Award for the best article in IEE Proceedings - Control Theory & Applications. He is a Fellow of IEEE and a member of the Royal Swedish Academy of Engineering Sciences. For the period 2013-15 he was also chairman of the Swedish Scientific Council for Natural and Engineering Sciences. His research interests are in modeling, analysis and synthesis of control systems, with particular attention to uncertainty, optimization and distributed control.