• français
    • English
  • English 
    • français
    • English
  • Login
JavaScript is disabled for your browser. Some features of this site may not work without it.
BIRD Home

Browse

This CollectionBy Issue DateAuthorsTitlesSubjectsJournals BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesSubjectsJournals

My Account

Login

Statistics

View Usage Statistics

Dual Optimization for convex constrained objectives without the gradient-Lipschitz assumptions

Thumbnail
View/Open
1807.03545.pdf (900.4Kb)
Date
2018
Publisher city
Paris
Collection title
Cahier de recherche CEREMADE, Université Paris Dauphine-PSL
Link to item file
https://arxiv.org/abs/1807.03545
Dewey
Probabilités et mathématiques appliquées
Sujet
convex objectives
URI
https://basepub.dauphine.fr/handle/123456789/20687
Collections
  • CEREMADE : Publications
Metadata
Show full item record
Author
Bompaire, Martin
89626 Centre de Mathématiques Appliquées - Ecole Polytechnique [CMAP]
Gaïffas, Stéphane
542130 Laboratoire de Probabilités, Statistiques et Modélisations [LPSM (UMR_8001)]
Bacry, Emmanuel
60 CEntre de REcherches en MAthématiques de la DEcision [CEREMADE]
Type
Document de travail / Working paper
Item number of pages
36
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.

  • Accueil Bibliothèque
  • Site de l'Université Paris-Dauphine
  • Contact
SCD Paris Dauphine - Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16

 Content on this site is licensed under a Creative Commons 2.0 France (CC BY-NC-ND 2.0) license.