SMILE in Paris

Travail joint avec Damien Lamberton.  Nous avons revisité de très anciennes familles d'algorithmes d'apprentissage, issues de la psychologie mathématique et des automates d'apprentissage et connues en approximation stochatique récursive pour leur comportement atypique et longtemps mal élucidé. Dans leur forme historique, la problématique est plutôt ici de détecter on line le meilleur des bras d'un bandit, plutôt que de maximiser le gain que l'on retire à les actionner. Nous analyserons le comportement de ces procédures en termes de convergence et de vitesse. Diverses extensions (en cours) seront aussi évoquées si […]

Computational learning theory is concerned with the complexityof machine learning problems, for instance with the question ofhow many training examples are needed for a machine toidentify a concept in a given class of possible target concepts.   This presentation focuses on the combinatorial structureof concept classes that can be learned from a small number ofexamples. When learning from randomly chosen examples, theVC-dimension is known to provide bounds on the numberof examples needed for learning. However, for previously studiedmodels of algorithmic teaching (i.e., learning from helpfulexamples), no such combinatorial parameters are […]

In this talk, I will revisit information complexity of black-box convex optimization, first studied in the seminal work of Nemirovski and Yudin, from the perspective of feedback information theory. These days, large-scale convex programming arises in a variety of applications, and it is important to refine our understanding of its fundamental limitations. The goal of black-box convex optimization is to minimize an unknown convex objective function from a given class over a compact, convex domain using an iterative scheme that generates approximate solutions by querying an oracle for local information […]

Le compressed sensing est une nouvelle façon d'envisager l'échantillonnage de données complexes telles que les signaux sonores ou les images. Plutôt que d'évaluer localement les signaux à l'aide de capteurs très précis, les signaux sont projetés sur un petit nombre de vecteurs aléatoires délocalisés. La théorie initiale a été développée conjointement par Donoho et Candès, Romberg et Tao . Elle exploite la parcimonie de certains signaux afin de minimiser le nombre de mesures aléaroires nécessaires. Les images naturelles sont par exemple bien approchées par un petit nombre d'ondelettes, et cette […]

We consider multiarmed bandit problems where the expected reward isunimodal over a partially ordered set of arms. In particular, thearms may belong to a continuous interval or correspond to verticesin a graph. We present efficient algorithms to minimize the regretin these bandit problems and also to detect abrupt changes in thereward distributions. The unimodality assumption has an importantadvantage: we can determine if a given arm is optimal by samplingthe possible directions around it. This property allows us toquickly find the optimal arm in a graph and detect changes. Notably,our method […]

Exposé en français mais transparents en anglais   I will present recent works on least-squares regression using randomly generated subspaces.In this approach, the regression function is the empirical risk minimizer in a low dimensional randomly generated subspace of a high (possibly infinite) dimensional function space. This approach can be seen as an alternative to usual penalization techniques. Approximation error and excess risk bounds are derived and the issue of numerical complexity will be discussed.This is joint work with Odalric Maillard and is described in the following papers: - Compressed Least-Squares […]

La parallélisation des algorithmes apparait comme la manière la plus prometteuse d'accroître les ressources de calcul disponibles. Le calcul distribué est par conséquent fortement sollicité en data mining où les données sont de plus en plus importantes et complexes. Parmi les algorithmes populaires de la fouille de données, les algorithmes dits de clustering tiennent une place de choix. Il s'agit de partitionner les données, souvent de grande dimension, en groupes d'objets similaires. Ces algorithmes se doivent d'être performants suivant les critères de groupement mais également en termes de temps de […]

Many problems in machine learning have to deal with wide data - manymore features than observations. Most of the features are of no use,and even the useful ones are often too sparse. For these problems L1regularization and its variants have proven to be useful for both featureselection and complexity control. This talk is a review of a number oftopics in this area, with a focus on computational aspects. This is joint work with Jerome Friedman, Rob Tibshirani, and our pastand present students.

Cet exposé est destiné à expliquer comment la régularisation L1 peut être vue comme procédure de sélection de modèles parmi des boules L1. Dans un premier temps, j'analyserai la performance du Lasso en tant qu'algorithme de régularisation L1 en proposant une inégalité oracle L1 satisfaite par cet estimateur dans le cadre de la régression linéaire pour un dictionnaire fini. Dans un second temps, je présenterai un estimateur particulièrement adapté à l'utilisation de dictionnaires infinis, construit par pénalisation L0 d'une suite d'estimateurs Lasso associés à une suite dyadique croissante de dictionnaires […]

On s'intéresse au problème de la régression linéaire séquentielle en grande dimension pour des suites déterministes arbitraires. Dans ce cadre, on prouve des bornes de regret qui sont un équivalent déterministe des bornes oracle de sparsité introduites au cours de la dernière décennie dans un cadre stochastique. Notre algorithme séquentiel SeqSEW procède par mélange exponentiel et troncature dépendante des données. Dans un second temps, on applique une version totalement automatique de cet algorithme aux modèles de régression avec design aléatoire et design fixe. Dans ces deux modèles, les bornes obtenues […]

Liens vers les articles : - l'un publié à Journal of Machine Learning Research, - l'autre, soumis.

Présentation de quatre articles acceptés à COLT'11:- Laëtitia Comminges (ENPC) --- Tight conditions for consistent variable selection in high dimensional nonparametric regression- Odalric-Ambrym Maillard (INRIA Lille) --- A Finite-Time Analysis of Multi-armed Bandits Problems with Kullback-Leibler Divergences- Vianney Perchet (ENS Cachan) --- Robust approachability and regret minimization in games with partial monitoring- Clément Levrard (Université Paris-Sud and Université Paris Pierre-et-Marie-Curie) --- Oracle inequalities for computationally budgeted model selectionNotez que quatre (cinq ?) autres articles écrits par des Français ont été acceptés cette année à COLT !