An efficient primal dual prox method for non-smooth optimization

Tianbao Yang, Mehrdad Mahdavi, Rong Jin, Shenghuo Zhu

Research output: Contribution to journalArticlepeer-review

16 Scopus citations


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) assuming that the proximal step can be efficiently solved, significantly faster than a standard subgradient descent method that has an (Formula Presented) 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.

Original languageEnglish (US)
Pages (from-to)369-406
Number of pages38
JournalMachine Learning
Issue number3
StatePublished - Mar 2014

All Science Journal Classification (ASJC) codes

  • Software
  • Artificial Intelligence


Dive into the research topics of 'An efficient primal dual prox method for non-smooth optimization'. Together they form a unique fingerprint.

Cite this