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 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 sizes 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).

To Appear in Proceedings of the Annual Conference on Learning Theory (COLT) 2017

References in corpus (9)

• HOGWILD!: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent
• Stochastic Variance Reduction for Nonconvex Optimization
• On the Linear Convergence of the Alternating Direction Method of Multipliers
• A General Analysis of the Convergence of ADMM
• Variance Reduction for Faster Non-Convex Optimization
• SDCA without Duality
• Fast Incremental Method for Nonconvex Optimization
• Dissipativity Theory for Nesterov's Accelerated Method
• On the Efficiency of Random Permutation for ADMM and Coordinate Descent

Cited by in corpus (7)

• The Analysis of Optimization Algorithms, A Dissipativity Approach
• Finite-Sample Analysis of Nonlinear Stochastic Approximation with Applications in Reinforcement Learning
• A Unified Analysis of First-Order Methods for Smooth Games via Integral Quadratic Constraints
• Analysis of Biased Stochastic Gradient Descent Using Sequential Semidefinite Programs
• A Unifying Framework for Variance Reduction Algorithms for Finding Zeroes of Monotone Operators
• Global Convergence Using Policy Gradient Methods for Model-free Markovian Jump Linear Quadratic Control
• Analytical Convergence Regions of Accelerated Gradient Descent in Nonconvex Optimization under Regularity Condition