Multi angle

H 1 Large-scale machine learning and convex optimization 1/2

Auteurs : Bach, Francis (Auteur de la Conférence)
CIRM (Editeur )

    Loading the player...

    Résumé : Many machine learning and signal processing problems are traditionally cast as convex optimization problems. A common difficulty in solving these problems is the size of the data, where there are many observations ("large n") and each of these is large ("large p"). In this setting, online algorithms such as stochastic gradient descent which pass over the data only once, are usually preferred over batch algorithms, which require multiple passes over the data. Given n observations/iterations, the optimal convergence rates of these algorithms are $O(1/\sqrt{n})$ for general convex functions and reaches $O(1/n)$ for strongly-convex functions. In this tutorial, I will first present the classical results in stochastic approximation and relate them to classical optimization and statistics results. I will then show how the smoothness of loss functions may be used to design novel algorithms with improved behavior, both in theory and practice: in the ideal infinite-data setting, an efficient novel Newton-based stochastic approximation algorithm leads to a convergence rate of $O(1/n)$ without strong convexity assumptions, while in the practical finite-data setting, an appropriate combination of batch and online algorithms leads to unexpected behaviors, such as a linear convergence rate for strongly convex problems, with an iteration cost similar to stochastic gradient descent.

    Codes MSC :
    62L20 - Stochastic approximation
    68T05 - Learning and adaptive systems
    90C06 - Large-scale problems
    90C25 - Convex programming

      Informations sur la Vidéo

      Langue : Anglais
      Date de publication : 18/02/16
      Date de captation : 02/02/16
      Collection : Research talks ; Computer Science ; Control Theory and Optimization ; Probability and Statistics
      Format : MP4
      Durée : 01:22:16
      Domaine : Probability & Statistics ; Computer Science ; Control Theory & Optimization
      Audience : Chercheurs ; Doctorants , Post - Doctorants
      Download : https://videos.cirm-math.fr/2016-02-02_Bach_part1.mp4

    Informations sur la rencontre

    Nom de la rencontre : Thematic month on statistics - Week 1: Statistical learning / Mois thématique sur les statistiques - Semaine 1 : apprentissage
    Organisateurs de la rencontre : Ghattas, Badih ; Ralaivola, Liva
    Dates : 01/02/16 - 05/02/16
    Année de la rencontre : 2016
    URL Congrès : http://conferences.cirm-math.fr/1615.html

    Citation Data

    DOI : 10.24350/CIRM.V.18919903
    Cite this video as: Bach, Francis (2016). Large-scale machine learning and convex optimization 1/2. CIRM. Audiovisual resource. doi:10.24350/CIRM.V.18919903
    URI : http://dx.doi.org/10.24350/CIRM.V.18919903


Titres de périodiques et e-books électroniques (Depuis le CIRM)

Ressources Electroniques

Books & Print journals

Recherche avancée