Semi-proximal Mirror-Prox for Nonsmooth Composite Minimization

Niao He 1 Zaid Harchaoui 2, 3
3 LEAR - Learning and recognition in vision
Inria Grenoble - Rhône-Alpes, LJK - Laboratoire Jean Kuntzmann, INPG - Institut National Polytechnique de Grenoble
Abstract : We propose a new first-order optimisation algorithm to solve high-dimensional non-smooth composite minimisation problems. Typical examples of such problems have an objective that decomposes into a non-smooth empirical risk part and a non-smooth regularisation penalty. The proposed algorithm, called Semi-Proximal Mirror-Prox, leverages the Fenchel-type 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.
Type de document :
Communication dans un congrès
Advances in Neural Information Processing Systems (NIPS), Dec 2015, Montreal, Canada. MIT Press, pp.3411-3419
Liste complète des métadonnées
Contributeur : Thoth Team <>
Soumis le : dimanche 5 juillet 2015 - 16:28:02
Dernière modification le : vendredi 10 février 2017 - 01:02:48
Document(s) archivé(s) le : mardi 25 avril 2017 - 23:34:52


Fichiers produits par l'(les) auteur(s)


  • HAL Id : hal-01171567, version 1


Niao He, Zaid Harchaoui. Semi-proximal Mirror-Prox for Nonsmooth Composite Minimization. Advances in Neural Information Processing Systems (NIPS), Dec 2015, Montreal, Canada. MIT Press, pp.3411-3419. <hal-01171567>



Consultations de
la notice


Téléchargements du document