Semi-Proximal Mirror-Prox for nonsmooth composite minimization

Niao He, Zaid Harchaoui

Research output: Contribution to journalConference articlepeer-review


We propose a new first-order optimization algorithm to solve high-dimensional non-smooth composite minimization problems. Typical examples of such problems have an objective that decomposes into a non-smooth empirical risk part and a non-smooth regularization penalty. The proposed algorithm, called Semi-Proximal Mirror-Prox, leverages the saddle point representation of one part of the objective while handling the other part of the objective via linear minimization over the domain. The algorithm stands in contrast with more classical proximal gradient algorithms with smoothing, which require the computation of proximal operators at each iteration and can therefore be impractical for high-dimensional problems. We establish the theoretical convergence rate of Semi-Proximal Mirror-Prox, which exhibits the optimal complexity bounds, i.e. O(1/∈2), for the number of calls to linear minimization oracle. We present promising experimental results showing the interest of the approach in comparison to competing methods.

Original languageEnglish (US)
Pages (from-to)3411-3419
Number of pages9
JournalAdvances in Neural Information Processing Systems
StatePublished - Jan 1 2015
Externally publishedYes
Event29th Annual Conference on Neural Information Processing Systems, NIPS 2015 - Montreal, Canada
Duration: Dec 7 2015Dec 12 2015

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Information Systems
  • Signal Processing

Fingerprint Dive into the research topics of 'Semi-Proximal Mirror-Prox for nonsmooth composite minimization'. Together they form a unique fingerprint.

Cite this