Institut de Mathématiques de Toulouse

Les événements de la journée

1 événement

  • Mathématiques de l’apprentissage

    Jeudi 9 février 2017 12:30-13:00 - Guillaume Garrigos - Istituto Italiano di Tecnologia

    Convergence rates in convex optimization : Going beyond the worst-case analysis with geometry

    Résumé : We study the asymptotic behavior of the Forward-Backward algorithm, which is a cornerstone for the resolution of structured optimization problems. It is well-known that, for general convex functions, this algorithm converges in values with a convergence rate O(1/n) if there is minimizers, and can be arbitrarily slow if the problem has no solutions. We show how, by doing simple geometric assumptions, we can guarantee better rates for this algorithm. We will discuss how this geometry can be identified in practice, providing for instance a new sum rule. In particular, this analysis explains why most of the time the Forward-Backward converges linearly, even in the absence of strong convexity.

    Lieu : Salle MIP 1R3

    [En savoir plus]