Institut de Mathématiques de Toulouse

Accueil > Événements Scientifiques > Séminaires & Groupes de Travail > Groupes de Travail > GdT Mathématiques de l’apprentissage

Mathématiques de l’apprentissage

par Aurélien Garivier, Sébastien Gerchinovitz - publié le , mis à jour le

Ce groupe de travail hebdomadaire est dédié à l’étude mathématique des problèmes et des algorithmes de machine learning. Bien que rattaché à l’équipe-projet AOC qui réunit des membres de l’IMT et de l’IRIT, il est ouvert à toutes les personnes se sentant concernées par cette thématique sur le site toulousain, afin d’échanger des idées et de susciter des collaborations. Nous alternons entre exposés formels, séances de lecture, debriefings post-conférences, ou simples discussions.

* lieu : 1R3 - salle MIP si possible, sinon à voir selon disponibilités.
* fréquence : toutes les semaines le jeudi 12h30-13h30.




  • Mercredi 28 juin 17:00-18:00 - Michal Valko - INRIA Lille - Nord Europe (Sequel)

    Distributed sequential sampling for kernel matrix approximation

    Résumé : Most kernel-based methods, such as kernel regression, kernel PCA, ICA, or k-means clustering, do not scale to large datasets, because constructing and storing the kernel matrix Kn requires at least O(n^2) time and space for n samples. Recent works (Alaoui 2014, Musco 2016) show that sampling points with replacement according to their ridge leverage scores (RLS) generates small dictionaries of relevant points with strong spectral approximation guarantees for K_n. The drawback of RLS-based methods is that computing exact RLS requires constructing and storing the whole kernel matrix. In this paper, we introduce SQUEAK, a new algorithm for kernel approximation based on RLS sampling that sequentially processes the dataset, storing a dictionary which creates accurate kernel matrix approximations with a number of points that only depends on the effective dimension d_eff(gamma) of the dataset. Moreover, since all the RLS estimations are efficiently performed using only the small dictionary, SQUEAK never constructs the whole matrix K_n, runs in linear time O(n*d_eff(gamma)^3) w.r.t. n, and requires only a single pass over the dataset. We also propose a parallel and distributed version of SQUEAK achieving similar accuracy in as little as O(log(n)*d_eff(gamma)^3) time.
    Related paper (Aistats 2017) :
    http://researchers.lille.inria.fr/ valko/hp/serve.php?what=publications/calandriello2017distributed.pdf
    This is joint work with Daniele Calandriello and Alessandro Lazaric.

    Lieu : bâtiment 1R1, salle 106


iCal