Contributions to Frugal Learning - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Thèse Année : 2022

Contributions to Frugal Learning

Quelques contributions à l'apprentissage frugal

Résumé

The increasing size of available data has led machine learning specialists to consider more complex models in order to achieve better performance. From a theoretical point of view, statistical learning under resource constraints has known a growing interest in the machine learning community. Many settings were developed to formalize budgeted limitations. In this thesis, we are motivated by these challenges, where we consider classical learning problems under the ``frugal lens". First, we tackle support recovery in a sparse linear regression problem, with one pass over data. We develop an online greedy algorithm named "online orthogonal matching pursuit" that actively selects covariates in a sequential way, with guarantees on its computational complexity that is adaptive to the unknown magnitude of the regression coefficients. Second, we consider the problem of model selection aggregation of experts. We present procedures that achieve fast rates under various budgeted settings and discuss the attainability of fast rates in different settings. Third, we tackle the problem of online prediction of individual sequences, where no distributional assumption is made in the process of generating data. We consider some natural budgeted constraints on the number of experts used for prediction and the number of observed feedbacks. We develop new strategies for each setting and discuss the attainability of constant regrets. Finally, we consider the problem of fixed confidence best arm identification. Given a confidence level, the learner wants to identify the arm with the largest mean using the least number of queries possible. We suppose that simultaneous queries are possible and prove that significant improvement can be made with respect to the BAI standard algorithms by taking the unknown covariance of the arms into consideration.
Depuis le début du développement de la théorie de l'apprentissage statistique, un intérêt particulier a été porté aux méthodes efficaces en temps de calcul ainsi qu'en espace de stockage nécessaire, afin qu'elles soient utilisables en pratique. Ceci a motivé plusieurs théoriciens à formaliser différents problèmes d'apprentissage statistique sous contrainte d'accès aux données et aux ressources computationnelles. Dans cette thèse, nous avons considéré plusieurs problèmes d'apprentissage statistiques et d'apprentissage séquentiel, sous différents types de contraintes. Le premier problème traité concerne la régression parcimonieuse sous une contrainte de nature computationnelle. Nous développons un algorithme effectuant un seul passage sur les données (celles-ci sont supposées arriver en temps réel) avec une limitation sur l'espace mémoire disponible. Le deuxième problème traité concerne l'agrégation d'experts. Nous revisitons ce problème dans le cas où l'accès aux données est limité et développons des méthodes permettant d'atteindre des taux rapides pour l'excès de risques. Le problème suivant concerne l'agrégation d'experts pour la prédiction des suites individuelles fixes. Nous introduisant un formalisme similaire à celui utilisé dans le problème précédent: nous supposons que pour chaque tour, le joueur a une contrainte sur le nombre d'experts à utiliser pour la prédiction et une contrainte sur le nombre de pertes d'experts individuels observées après avoir fait une prédiction. Nous présentant des procédures pour chaque cas et développons des garanties théoriques sur le regret cumulé des stratégies présentées. Le dernier problème considéré est une instance du problème de l'identification du meilleur bras dans le cadre de la théorie des bandits stochastiques. Nous présentons une extension du formalisme standard en permettant le tirage de plusieurs bras simultanément. Dans ce cadre nous montrons que de nouvelles bornes, potentiellement meilleurs que les bornes classiques, sont possibles, et nous présentons des procédures permettant de les atteindre.
Fichier principal
Vignette du fichier
110937_SAAD_2022_archivage.pdf (1.92 Mo) Télécharger le fichier
Origine : Version validée par le jury (STAR)

Dates et versions

tel-03940730 , version 1 (16-01-2023)

Identifiants

  • HAL Id : tel-03940730 , version 1

Citer

El Mehdi Saad. Contributions to Frugal Learning. Machine Learning [stat.ML]. Université Paris-Saclay, 2022. English. ⟨NNT : 2022UPASM041⟩. ⟨tel-03940730⟩
111 Consultations
58 Téléchargements

Partager

Gmail Facebook X LinkedIn More