caa a22 4500 605478023 CHVBK 20210128100403.0 cr unu---uuuuu 210128e20150301xx s 000 0 eng 10.1007/s10994-014-5436-1 doi (NATIONALLICENCE)springer-10.1007/s10994-014-5436-1 An efficient primal dual prox method for non-smooth optimization [Elektronische Daten] [Tianbao Yang, Mehrdad Mahdavi, Rong Jin, Shenghuo Zhu] We study the non-smooth optimization problems in machine learning, where both the loss function and the regularizer are non-smooth functions. Previous studies on efficient empirical loss minimization assume either a smooth loss function or a strongly convex regularizer, making them unsuitable for non-smooth optimization. We develop a simple yet efficient method for a family of non-smooth optimization problems where the dual form of the loss function is bilinear in primal and dual variables. We cast a non-smooth optimization problem into a minimax optimization problem, and develop a primal dual prox method that solves the minimax optimization problem at a rate of $$O(1/T)$$ O ( 1 / T ) assuming that the proximal step can be efficiently solved, significantly faster than a standard subgradient descent method that has an $$O(1/\sqrt{T})$$ O ( 1 / T ) convergence rate. Our empirical studies verify the efficiency of the proposed method for various non-smooth optimization problems that arise ubiquitously in machine learning by comparing it to the state-of-the-art first order methods. The Author(s), 2014 Non-smooth optimization nationallicence Primal dual method nationallicence Convergence rate nationallicence Sparsity nationallicence Efficiency nationallicence Yang Tianbao NEC Laboratories America, Inc., Cupertino, CA, USA aut Mahdavi Mehrdad Department of Computer Science and Engineering, Michigan State University, East Lansing, MI, USA aut Jin Rong Department of Computer Science and Engineering, Michigan State University, East Lansing, MI, USA aut Zhu Shenghuo NEC Laboratories America, Inc., Cupertino, CA, USA aut Machine Learning Springer US; http://www.springer-ny.com 98/3(2015-03-01), 369-406 0885-6125 98:3<369 2015 98 10994 https://doi.org/10.1007/s10994-014-5436-1 text/html Onlinezugriff via DOI BK010053 XK010053 XK010000 Metadata rights reserved Springer special CC-BY-NC licence nationallicence 1 research-article jats NATIONALLICENCE NATIONALLICENCE NL-springer NATIONALLICENCE 856 40 https://doi.org/10.1007/s10994-014-5436-1 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Yang Tianbao NEC Laboratories America, Inc., Cupertino, CA, USA aut NATIONALLICENCE 700 1- Mahdavi Mehrdad Department of Computer Science and Engineering, Michigan State University, East Lansing, MI, USA aut NATIONALLICENCE 700 1- Jin Rong Department of Computer Science and Engineering, Michigan State University, East Lansing, MI, USA aut NATIONALLICENCE 700 1- Zhu Shenghuo NEC Laboratories America, Inc., Cupertino, CA, USA aut NATIONALLICENCE 773 0- Machine Learning Springer US; http://www.springer-ny.com 98/3(2015-03-01), 369-406 0885-6125 98:3<369 2015 98 10994