Projet ANR-12-BS02-0004 – GRETA : GREediness: Theory and Algorithms
Programme : Blanc - SIMI 2 - Science informatique et applications (Blanc SIMI 2)
Année de financement : 2012
Coordinateur du projet : Monsieur Liva RALAIVOLA (Laboratoire d'Informatique Fondamentale de Marseille)
Partenaires : Laboratoire d'Analyse, Topologie, Probabilités; Laboratoire public; Laboratoire d'Informatique Fondamentale de Marseille; Laboratoire d'Informatique, de Traitement de l'Information et des Systèmes
Montant : 372330.0 euros
Date de début : 2012
Durée : 36 mois
Résumé : GRETA -- GREdiness: Theory and AlgorithmsOver the past few years, many problems of automatically computing sparse representations of data have been addressed through convex optimization formulations. However, aiming for sparsity actually involves an l0 “norm” regularization/constraint, and the convex optimization way is essentially a proxy to achieve this sparsity. Here, we want to set the focus on another way of dealing with the sparsity objective, which, to our opinion, has been overlooked: greedy methods.
Connexions entre apprentissage et traitement du signal, le point de vue gloutonL'objectif principal de GRETA est d'établir et d'identifier des liens méthodologiques entre l'apprentissage automatique et traitement du signal du point de vue des méthodes gloutonnes. Plus précisément , nous allons aborder et apporter des solutions originales aux problèmes partiellement résolus suivantes :• le développement de nouvelles procédures MP / OMP pour le cas de dictionnaires qui ne sont pas associés à des transformées rapides : i ) des propositions algorithmiques sont visées, qui s'appuieront sur la création de structures de données appropriées , ii ) des questions relatives à la parcimonie structurée seront d'un intérêt primordial , et iii ) le problème de l'apprentissage de dictionnaires appropriés sera abordé.• le développement de nouvelles procédures MP / OMP pour le cas de fonctions de perte arbitraires, autres que la perte des moindres carrés : i ) la vitesse de convergence des algorithmes proposés sera au centre de ce problème et ii ) la pertinence des algorithmes pour diverses tâches d'apprentissage (par exemple, l'apprentissage semi-supervisé, la transduction et sa connexion à inpainting ) sera étudiée ;• la bénédiction de la gloutonnerie : au-delà de la simple efficacité de calcul  apportée par les méthodes gloutonnes, nous pensons qu'il y a un certain nombre de situations où elles ont des conséquences positives du point de vue de la généralisation ; en conséquence, nous allons travailler sur la proposition de nouveaux outils pour l'apprentissage statistique qui permettraient de lier formellement les propriétés des algorithmes gloutons et la généralisation : ces outils peuvent largement s'appuyer sur les quantités comme telles que le «spark« ou l'incohérence .
Vertus des méthodes gloutonnes et au-delàLes membres de l'ANR Greta s'appuient principalement sur les outils et théories suivantes pour effectuer leurs travaux : optimisation convexe, optimisation combinatoriale, théorie de l'apprentissage computationel et informatique fondamentale.Le stratégie implémentée par le groupe est de revisiter des résultats connus sous un nouvel angle porté par les perspectives ouvertes par les domaines précédemment cités. Nous essayons de comprendre de cette manière quelles méthodes existantes peuvent être étendues et le cas échéant, de préciser leurs limites.
Résumé de la soumission : Over the past few years, many problems of automatically computing sparse representations of data have been addressed through convex optimization formulations. This holds both for contributions in machine learning and signal processing. However, aiming at sparsity actually involves an l0 “norm” regularization/constraint, and the convex optimization way is essentially a proxy to achieve this sparsity – through the recourse to an l1 norm, which itself is a proxy to the l0. In this project, we want to set the focus on another way of dealing with the sparsity objective, which, to our opinion, has been neglected recently: greedy methods. From a broad perspective, greedy algorithms constitute another way of approximating the solution of an l0 based problems and we think there is a lot of interesting questions that accompany the use of greedy methods. In particular, we will carry out our research along three different axis. First, we will devote time to develop new projection/matching pursuit-based algorithms, focusing on two specific points: on the one hand, we will be interested in making use of elaborate data structures and algorithms (e.g. kd-tree, hash tables, graph algorithms) to speed up matching pursuit learning, and, on the other hand, we will devise new pursuit algorithms capable of handling structured sparsity. Second, we aim at analyzing the properties of greedy methods in terms of generalization ability: results exist that establish conditions for (perfect) recoverability of the ’hidden’ or unobserved signal, but few exist that draw the connection with the generalization ability of the learned function – the question of using a loss function different from the squared error is one issue directly connected to this line of research. Finally, on a broader scope, we would like to elucidate some connections between pivotal quantities such as (mutual) incoherence, Babel function and spark that appear in the signal processing literature and VC-dimension, Rademacher complexities and algorithmic stability, which are notions widely used in machine learning. The former quantities are essential to prove results on recoverability while the latter play a central role to demonstrate the consistency of learning procedures: we anticipate that these notions are closely related and this is our purpose to precisely establish their connections.
Résultats : Voici les principaux résultats obtenus jusqu'à présent dans le projet Greta:
- Un nouveau principe d'accélération des méthodes d'optimisation visant à trouver des solutions parcimonieuses à des problèmes convexes, le «Dynamic Screening«, a été développé. Antoine Bonnefoy, doctorant financé par le projet a reçu pour ce travail le prix du meilleur papier étudiant dans la conférence internationale «Eusipco 2014«.
- Une méthode gloutonne d'optimisation basée sur une stratégie d'«Active Sets« a été développée. Elle permet d'identifier par un ensemble infini de caractéristiques, celles qui rendent essentiellement compte du signal.
- Une famille de méthodes gloutonnes pour traiter le coût quadratique a été généralisée pour la recherche de zéros d'un opérateur dans le cadre Hilbertien. Cette méthode a été appliquée au débruitage d'images corrompues par un bruit de Poisson via la régularisation de Moreau-Yosida. 
Par ailleurs, une journée thématique permettant la rencontre des chercheurs dans les domaines du traitement de signal, de l'apprentissage statistique et de l'optimisation combinatoriale a eu lieu avec succès en septembre 2014. Un workshop d'audience plus large est prévu pour 2015.
Un certain nombre de chercheurs ont fait (ou ont planifié) un séjour scientifique sur les sites du projet Greta.
Perspectives : Les principales perspectives sont les suivantes :
- revisiter la question de l'«inpainting« du point de vue de la «transduction« et de l'optimisation gloutonne;
- explorer dans quelle mesure les résultats théoriques de l'estimation exacte du support d'un signal («recovery«) peuvent être adaptés au cas de la procédure d'optimisation de Franck-Wolfe, qui est par ailleurs très efficace.
- établir les liens entre méthodes gloutonnes et techniques d'apprentissage développée pour les problèmes de bandits, sachant qu'elles ont en commun de s'appuyer principalement sur des stratégies locales;
- comprendre comment utiliser les méthodes gloutonnes pour dériver de nouveaux algorithmes d'apprentissage actif.
Publications et brevets : Jusqu'à présent :
- 2 articles de journaux, 1 en révision mineure
- 9 articles de conférences internationales.