Accelerated proximal stochastic dual coordinate ascent for regularized loss minimization

• 成果类型: Article
• 署名作者: Shalev-Shwartz, Shai; Zhang, Tong
• 署名单位: Hebrew University of Jerusalem; Rutgers University System; Rutgers University New Brunswick; Baidu
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-014-0839-0
• 发表日期: 2016
• 页码: 105-145
• 关键词: Optimization; algorithms; online

摘要

We introduce a proximal version of the stochastic dual coordinate ascent method and show how to accelerate the method using an inner-outer iteration procedure. We analyze the runtime of the framework and obtain rates that improve state-of-the-art results for various key machine learning optimization problems including SVM, logistic regression, ridge regression, Lasso, and multiclass SVM. Experiments validate our theoretical findings.