Academy of Mathematics and Systems Science, CAS Colloquia & Seminars
Speaker:
Senior Researcher Lin XIAO, Microsoft Research
Inviter:
Yuhong Dai
Title:
Stochastic Primal-Dual Coordinate Method for Regularized Empirical Risk Minimization
Time & Venue:
2015.6.23 16:30-17:30 Z311
Abstract:
We consider a generic convex optimization problem associated with regularized empirical risk minimization of linear predictors in machine learning. The problem structure allows us to reformulate it as a convex-concave saddle point problem. We propose a stochastic primal-dual coordinate (SPDC) method, which alternates between maximizing over a randomly chosen dual variable and minimizing over the primal variable. An extrapolation step on the primal variable is performed to obtain accelerated convergence rate (in the sense of Nesterov). We also develop a mini-batch version of the SPDC method which facilitates parallel computing, and an extension with weighted sampling probabilities on the dual variables, which has a better complexity than uniform sampling on unnormalized data. Both theoretically and empirically, we show that the SPDC method has comparable or better performance than several state-of-the-art optimization methods. This is joint work with Yuchen Zhang.
Appendix：
Copyright@2008, All Rights Reserved, Academy of Mathematics and Systems Science, CAS
Tel: 86-10-82541777 Fax: 86-10-82541972 E-mail: contact@amss.ac.cn
