We propose an algorithm-independent framework to equip existing optimization methods with primal-dual certificates. Such certificates and corresponding rate of convergence guarantees are important for practitioners to diagnose progress, in particular in machine learning applications. We obtain new primal-dual convergence rates, e.g., for the Lasso as well as many L1, Elastic Net, group Lasso and TV-regularized problems. The theory applies to any norm-regularized generalized linear model. Our approach provides efficiently computable duality gaps which are globally defined, without modifying the original problems in the region of interest.
@cite_13: 
@cite_7: We consider a generic convex optimization problem associated with regularized empirical risk minimization of linear predictors. The problem structure allows us to reformulate it as a convex-concave saddle point problem. We propose a stochastic primal-dual coordinate (SPDC) method, which alternates between maximizing over a randomly chosen dual variable and minimizing over the primal variable. An extrapolation step on the primal variable is performed to obtain accelerated convergence rate. We also develop a mini-batch version of the SPDC method which facilitates parallel computing, and an extension with weighted sampling probabilities on the dual variables, which has a better complexity than uniform sampling on unnormalized data. Both theoretically and empirically, we show that the SPDC method has comparable or better performance than several state-of-the-art optimization methods.
@cite_8: Nous etudions dans cette these une representation particuliere de signaux fondee sur une methode d’apprentissage statistique, qui consiste a modeliser des donnees comme combinaisons lineaires de quelques elements d’un dictionnaire appris. Ceci peut etre vu comme une extension du cadre classique des ondelettes, dont le but est de construire de tels dictionnaires (souvent des bases orthonormales) qui sont adaptes aux signaux naturels. Un succes important de cette approche a ete sa capacite a modeliser des imagettes, et la performance des methodes de debruitage d’images fondees sur elle. Nous traitons plusieurs questions ouvertes, qui sont reliees a ce cadre : Comment apprendre efficacement un dictionnaire ? Comment enrichir ce modele en ajoutant une structure sous-jacente au dictionnaire ? Est-il possible d’ameliorer les methodes actuelles de traitement d’image fondees sur cette approche ? Comment doit-on apprendre le dictionnaire lorsque celui-ci est utilise pour une tâche autre que la reconstruction de signaux ? Y a-t-il des applications interessantes de cette methode en vision par ordinateur ? Nous repondons a ces questions, avec un point de vue multidisciplinaire, en empruntant des outils d’apprentissage statistique, d’optimisation convexe et stochastique, de traitement des signaux et des images, de vison par ordinateur, mais aussi d'optimisation sur des graphes.
Linearized ADMM solvers. For the problem structure of our interest here, one of the most natural algorithms is the splitting method known as the Chambolle-Pock algorithm (also known as Primal-Dual Hybrid Gradient, Arrow-Hurwicz method, or linearized ADMM) @cite_13 . While this algorithm can give rise to a duality gap, it is significantly less general compared to our framework. In each iteration, it requires a complete solution of the proximal operators of both @math and @math , which can be computationally expensive. Its convergence rate is sensitive to the used step-size @cite_8 . Our framework is not algorithm-specific, and holds for arbitrary iterate sequences. More recently, the SPDC method @cite_7 was proposed as a coordinate-wise variant of @cite_13 , but only for strongly convex @math .