Dual Optimization for convex constrained objectives without the gradient-Lipschitz assumptions
Bompaire, Martin; Gaïffas, Stéphane; Bacry, Emmanuel (2018), Dual Optimization for convex constrained objectives without the gradient-Lipschitz assumptions. https://basepub.dauphine.fr/handle/123456789/20687
TypeDocument de travail / Working paper
External document linkhttps://arxiv.org/abs/1807.03545
Series titleCahier de recherche CEREMADE, Université Paris Dauphine-PSL
MetadataShow full item record
Centre de Mathématiques Appliquées - Ecole Polytechnique [CMAP]
Laboratoire de Probabilités, Statistiques et Modélisations [LPSM (UMR_8001)]
CEntre de REcherches en MAthématiques de la DEcision [CEREMADE]
Abstract (EN)The minimization of convex objectives coming from linear supervised learning problems, such as penalized generalized linear models, can be formulated as finite sums of convex functions. For such problems, a large set of stochastic first-order solvers based on the idea of variance reduction are available and combine both computational efficiency and sound theoretical guarantees (linear convergence rates). Such rates are obtained under both gradient-Lipschitz and strong convexity assumptions. Motivated by learning problems that do not meet the gradient-Lipschitz assumption, such as linear Poisson regression, we work under another smoothness assumption, and obtain a linear convergence rate for a shifted version of Stochastic Dual Coordinate Ascent (SDCA) that improves the current state-of-the-art. Our motivation for considering a solver working on the Fenchel-dual problem comes from the fact that such objectives include many linear constraints, that are easier to deal with in the dual. Our approach and theoretical findings are validated on several datasets, for Poisson regression and another objective coming from the negative log-likelihood of the Hawkes process, which is a family of models which proves extremely useful for the modeling of information propagation in social networks and causality inference.
Subjects / Keywordsconvex objectives
Showing items related by title and author.
Morel, Maryan; Bacry, Emmanuel; Gaïffas, Stéphane; Guilloux, Agathe; Leroy, Fanny (2019) Article accepté pour publication ou publié
Bacry, Emmanuel; Gaiffas, Stéphane; Leroy, Fanny; Morel, Maryan; Nguyen, Dinh Phong; Sebiat, Youcef; Sun, Dian (2019) Document de travail / Working paper
Kabeshova, Anastasiia; Yu, Yiyang; Lukacs, B.; Bacry, Emmanuel; Gaïffas, Stéphane (2019) Document de travail / Working paper