Les recherches d'Amii à la conférence internationale sur l'apprentissage automatique (International Conference on Machine Learning 2023)

Cette année marque la 40e édition de la conférence internationale sur l'apprentissage automatique (ICML), et les chercheurs et étudiants d'Amii y présentent leurs travaux.

L'ICML, qui se déroulera cette année du 23 au 29 juillet à Hawaï, est le premier rassemblement de professionnels qui se consacrent à l'avancement de la branche de l'IA connue sous le nom d'apprentissage automatique (AAM). Mondialement reconnue pour la présentation et la publication de recherches de pointe sur tous les aspects de l'apprentissage automatique et des domaines d'application, la conférence figure parmi les dix conférences sur l'apprentissage automatique et l'IA les mieux classées au monde sur la base des valeurs de l'indice h et de l'indice d'impact (Impact Score).

Découvrez quelques-unes des recherches de pointe présentées par les scientifiques d'Amii.

Les noms en gras désignent les étudiants, les boursiers et le personnel d'Amii.

Vers une estimation efficace de la valeur basée sur le gradient

Arsalan Sharifnassab, Richard Sutton

Résumé : Les méthodes basées sur le gradient pour l'estimation des valeurs dans l'apprentissage par renforcement ont des propriétés de stabilité favorables, mais elles sont généralement beaucoup plus lentes que les méthodes d'apprentissage par différence temporelle (TD). Nous étudions les causes profondes de cette lenteur et montrons que l'erreur quadratique moyenne de Bellman (MSBE) est une fonction de perte mal conditionnée dans le sens où son hessien a un grand nombre de conditions. Pour résoudre l'effet négatif du mauvais conditionnement de la MSBE sur les méthodes basées sur le gradient, nous proposons une méthode proximale sans lot de faible complexité qui suit approximativement la direction de Gauss-Newton et qui est asymptotiquement robuste à la paramétrisation. Notre algorithme principal, appelé RANS, est efficace dans le sens où il est significativement plus rapide que les méthodes de gradient résiduel tout en ayant presque la même complexité de calcul, et il est compétitif avec TD sur les problèmes classiques que nous avons testés.

La résolution de l'hypothèse de la récompense

Michael BowlingJohn D. Martin, David Abel, Will Dabney

Résumé : L'hypothèse de la récompense postule que "tout ce que nous entendons par objectifs et buts peut être considéré comme la maximisation de la valeur attendue de la somme cumulée d'un signal scalaire reçu (récompense)". Notre objectif est de vérifier pleinement cette hypothèse. Il ne s'agira pas de conclure par une simple affirmation ou réfutation, mais plutôt de spécifier complètement les exigences implicites sur les buts et finalités en vertu desquelles l'hypothèse se vérifie.

Un moyen efficace et significatif d'évaluer les modèles de survie

Shi-ang Qi, Neeraj KumarMahtab Farrokh, Weijie Sun, Li-Hao Kuan, Rajesh Ranganath, Ricardo Henao, Russell Greiner

Résumé : Une mesure simple pour évaluer un modèle de prédiction de survie est basée sur l'erreur absolue moyenne (MAE) - la moyenne de la différence absolue entre le temps prédit par le modèle et le temps réel de l'événement, sur tous les sujets. Malheureusement, il s'agit d'un défi car, dans la pratique, l'ensemble de test comprend des individus censurés (à droite), ce qui signifie que nous ne savons pas quand un individu censuré a réellement vécu l'événement. Dans cet article, nous explorons différentes mesures pour estimer la MAE pour les ensembles de données de survie qui comprennent (beaucoup) d'individus censurés. En outre, nous présentons une approche nouvelle et efficace pour générer des ensembles de données de survie semi-synthétiques réalistes afin de faciliter l'évaluation des mesures. Nos résultats, basés sur l'analyse des ensembles de données semi-synthétiques, révèlent que notre métrique proposée (MAE utilisant des pseudo-observations) est capable de classer les modèles avec précision sur la base de leur performance, et correspond souvent de près à la véritable MAE - en particulier, elle est meilleure que plusieurs méthodes alternatives.

Formalisation des préférences sur les distributions de temps d'exécution

Devon R. Graham, Kevin Leyton-BrownTim Roughgarden

Résumé : Lorsque nous essayons de résoudre un problème informatique, nous sommes souvent confrontés à un choix entre des algorithmes qui sont garantis de renvoyer la bonne réponse mais qui diffèrent dans leurs distributions de temps d'exécution (par exemple, les solveurs SAT, les algorithmes de tri). Cet article vise à jeter les bases théoriques de ces choix en formalisant les préférences sur les distributions de temps d'exécution. Il pourrait sembler que nous devrions simplement préférer l'algorithme qui minimise la durée d'exécution attendue. Cependant, ces préférences seraient déterminées par la lenteur exacte de notre algorithme sur de mauvaises entrées, alors qu'en pratique, nous sommes généralement prêts à interrompre des exécutions occasionnelles, suffisamment longues, avant qu'elles ne se terminent. Nous proposons une alternative fondée sur des principes, en adoptant une approche théorique de l'utilité pour caractériser les fonctions de notation qui décrivent les préférences sur les algorithmes. Ces fonctions dépendent de la façon dont notre valeur pour la résolution de notre problème diminue avec le temps et de la distribution à partir de laquelle les captimes sont tirés. Nous décrivons des exemples de fonctions d'utilité réalistes et montrons comment tirer parti d'une approche d'entropie maximale pour modéliser des distributions de captimes non spécifiées. Enfin, nous montrons comment estimer efficacement l'utilité attendue d'un algorithme à partir d'échantillons de temps d'exécution.

Options basées sur le Laplacien profond pour l'exploration étendue dans le temps

Martin Klissarov, Marlos C. Machado

Résumé : La sélection d'actions exploratoires générant un riche flux d'expériences pour un meilleur apprentissage est un défi fondamental dans l'apprentissage par renforcement (RL). Une approche pour aborder ce problème consiste à sélectionner des actions selon des politiques spécifiques pour une période de temps prolongée, également connues sous le nom d'options. Une ligne de travail récente pour dériver de telles options exploratoires s'appuie sur les fonctions propres du laplacien du graphe. Il est important de noter que, jusqu'à présent, ces méthodes ont été principalement limitées à des domaines tabulaires dans lesquels (1) la matrice du laplacien du graphe était donnée ou pouvait être entièrement estimée, (2) l'exécution d'une décomposition propre sur cette matrice était calculable et (3) les fonctions de valeur pouvaient être apprises avec exactitude. En outre, ces méthodes nécessitaient une phase distincte de découverte des options. Ces hypothèses ne sont fondamentalement pas extensibles. Dans cet article, nous nous attaquons à ces limites et montrons comment les résultats récents de l'approximation directe des fonctions propres du laplacien peuvent être exploités pour améliorer réellement l'exploration basée sur les options. Pour ce faire, nous introduisons un algorithme RL profond entièrement en ligne pour découvrir des options basées sur le Laplacien et nous évaluons notre approche sur une variété de tâches basées sur les pixels. Nous comparons notre approche à plusieurs méthodes d'exploration de pointe et montrons qu'elle est efficace, générale et particulièrement prometteuse dans des contextes non stationnaires.

Correction de l'inadéquation du facteur d'actualisation dans les méthodes de gradient de politique en cours d'exécution

Fengdi Che, Gautham Vasan, A. Rupam Mahmood

Résumé : Le théorème du gradient de politique donne une forme pratique du gradient de politique en termes de trois facteurs : une valeur d'action, un gradient de la vraisemblance d'action et une distribution d'état impliquant une actualisation appelée distribution stationnaire actualisée. Cependant, les méthodes sur politique couramment utilisées et basées sur le théorème du gradient de politique ignorent le facteur d'actualisation dans la distribution d'état, ce qui est techniquement incorrect et peut même entraîner un comportement d'apprentissage dégénéré dans certains environnements. Une solution existante corrige cette divergence en utilisant γ comme facteur dans l'estimation du gradient. Cependant, cette solution n'est pas largement adoptée et ne fonctionne pas bien dans les tâches où les états ultérieurs sont similaires aux états antérieurs. Nous introduisons une nouvelle correction de distribution pour tenir compte de la distribution stationnaire actualisée qui peut être intégrée dans de nombreux estimateurs de gradient existants. Notre correction contourne la dégradation des performances associée à la correction γ avec une variance plus faible. Il est important de noter que, par rapport aux estimateurs non corrigés, notre algorithme fournit une meilleure mise en évidence de l'état pour éviter les politiques sous-optimales dans certains environnements et qu'il atteint ou dépasse systématiquement les performances originales sur plusieurs benchmarks de la gym OpenAI et de la suite DeepMind.

Substituts basés sur des cibles pour l'optimisation stochastique

Jonathan Wilder Lavington, Sharan Vaswani, Reza Babanezhad, Mark SchmidtNicolas Le Roux

Abstract: We consider minimizing functions for which it is expensive to compute the (possibly stochastic) gradient. Such functions are prevalent in reinforcement learning, imitation learning and adversarial training. Our target optimization framework uses the (expensive) gradient computation to construct surrogate functions in a \emph{target space} (e.g. the logits output by a linear model for classification) that can be minimized efficiently. This allows for multiple parameter updates to the model, amortizing the cost of gradient computation. In the full-batch setting, we prove that our surrogate is a global upper-bound on the loss, and can be (locally) minimized using a black-box optimization algorithm. We prove that the resulting majorization-minimization algorithm ensures convergence to a stationary point of the loss. Next, we instantiate our framework in the stochastic setting and propose the SSO algorithm, which can be viewed as projected stochastic gradient descent in the target space. This connection enables us to prove theoretical guarantees for SSO when minimizing convex functions. Our framework allows the use of standard stochastic optimization algorithms to construct surrogates which can be minimized by any deterministic optimization method. To evaluate our framework, we consider a suite of supervised learning and imitation learning problems. Our experiments indicate the benefits of target optimization and the effectiveness of SSO.

Faisons converger plus rapidement la descente des blocs de coordonnées : Règles gourmandes plus rapides, passage de messages, complexité des ensembles actifs et convergence superlinéaire

Julie Nutini, Issam Laradji, Mark Schmidt

Résumé : Les méthodes de descente par blocs de coordonnées (BCD) sont largement utilisées pour l'optimisation numérique à grande échelle en raison de leurs coûts d'itération peu élevés, de leurs faibles besoins en mémoire, de leur aptitude à la parallélisation et de leur capacité à exploiter la structure du problème. Trois choix algorithmiques principaux influencent les performances des méthodes BCD : la stratégie de partitionnement des blocs, la règle de sélection des blocs et la règle de mise à jour des blocs. Dans cet article, nous explorons ces trois éléments constitutifs et proposons des variations pour chacun d'entre eux qui peuvent améliorer de manière significative les progrès réalisés par chaque itération BCD. Nous (i) proposons de nouvelles stratégies gourmandes de sélection de blocs qui garantissent plus de progrès par itération que la règle de Gauss-Southwell ; (ii) examinons des questions pratiques telles que la mise en œuvre des nouvelles règles lors de l'utilisation de blocs "variables" ; (iii) explorons l'utilisation du passage de messages pour calculer efficacement les mises à jour de la matrice ou de Newton sur d'énormes blocs pour les problèmes présentant des dépendances peu nombreuses entre les variables ; et (iv) examiner l'identification optimale du collecteur actif, qui conduit à des limites sur la "complexité de l'ensemble actif" des méthodes BCD et conduit à une convergence superlinéaire pour certains problèmes avec des solutions éparses (et dans certains cas à une terminaison finie à une solution optimale). Nous étayons toutes nos conclusions par des résultats numériques pour les problèmes classiques d'apprentissage automatique des moindres carrés, de la régression logistique, de la régression logistique multi-classes, de la propagation d'étiquettes et de la régularisation L1.

Simplification de l'optimisation de sous-manifold positif-défini basée sur le momentum et applications à l'apprentissage profond

Wu Lin, Valentin Duruisseaux, Melvin Leok, Frank Nielsen, Mohammad Emtiyaz Khan, Mark Schmidt

Résumé : L'optimisation d'un sous-milieu riemannien avec momentum est un défi informatique car, pour s'assurer que les itérés restent sur le sous-milieu, nous devons souvent résoudre des équations différentielles difficiles. Nous simplifions ici ces difficultés pour une classe de matrices symétriques positives-définies structurées avec la métrique affine-invariante. Pour ce faire, nous proposons une version généralisée des coordonnées normales riemanniennes qui orthonormalise dynamiquement la métrique et convertit localement le problème en un problème sans contrainte dans l'espace euclidien. Nous utilisons notre approche pour simplifier les approches existantes pour les covariances structurées et développer des optimiseurs du 2e ordre sans inversion de matrice pour l'apprentissage profond avec une faible précision en utilisant uniquement des multiplications de matrice.

Élagage structuré sans gradient avec des données non étiquetées

Azade Nova, Hanjun Dai, Dale Schuurmans

Résumé : Les grands modèles de langage (LLM) ont remporté un grand succès dans la résolution de tâches difficiles dans de nombreux domaines, mais ce succès s'accompagne d'un coût de calcul élevé et d'un temps de latence pour l'inférence. Comme les développeurs et les tiers personnalisent ces modèles, la nécessité de fournir une inférence efficace s'est accrue. De nombreux efforts ont tenté de réduire le coût de l'inférence grâce à des techniques de compression de modèles telles que l'élagage et la distillation. Cependant, ces techniques nécessitent des données étiquetées ou prennent beaucoup de temps car elles exigent que le modèle compressé soit réentraîné pour retrouver sa précision. Dans cet article, nous proposons un cadre d'élagage structuré sans gradient qui n'utilise que des données non étiquetées. Une évaluation sur les benchmarks GLUE et SQuAD utilisant BERTBASE et DistilBERT illustre l'efficacité de l'approche proposée. En utilisant uniquement les poids du modèle pré-entraîné et les données non étiquetées, en quelques minutes sur un seul GPU, jusqu'à 40% du nombre de FLOP d'origine peut être réduit avec moins de 4% de perte de précision pour toutes les tâches considérées.

Réexamen de l'échantillonnage pour l'optimisation combinatoire

Haoran Sun, Katayoon Goshvadi, Azade Nova, Dale SchuurmansHanjun Dai

Résumé : Les approches d'échantillonnage telles que la chaîne de Markov Monte Carlo étaient autrefois populaires pour l'optimisation combinatoire, mais l'inefficacité des méthodes classiques et la nécessité d'une conception spécifique au problème ont freiné leur développement. Des travaux récents ont favorisé les approches basées sur les données qui atténuent la nécessité de créer des heuristiques à la main, mais ces approches ne sont souvent pas utilisables comme solveurs prêts à l'emploi en raison de leur dépendance à l'entraînement dans la distribution et de leur évolutivité limitée à de grandes instances. Dans cet article, nous revisitons l'idée d'utiliser l'échantillonnage pour l'optimisation combinatoire, motivés par les progrès récents et significatifs du MCMC discret basé sur le gradient et les nouvelles techniques d'exploration parallèle du voisinage sur les accélérateurs. Il est remarquable de constater que les stratégies d'échantillonnage modernes peuvent exploiter les informations sur le paysage pour fournir des solveurs polyvalents qui ne nécessitent pas d'entraînement et qui sont pourtant compétitifs par rapport aux solveurs combinatoires de pointe. En particulier, les expériences sur la sélection des sommets de couverture, la partition des graphes et le routage démontrent de meilleurs compromis vitesse-qualité que les approches actuelles basées sur l'apprentissage, et parfois même des performances supérieures à celles des solveurs commerciaux et des algorithmes spécialisés.

Le gradient stochastique réussit pour les bandits

Jincheng Mei, Zixin Zhong, Bo Dai, Alekh Agarwal, Csaba Szepesvari, Dale Schuurmans

Résumé : Nous montrons que l'algorithme de bandit à gradient stochastique converge vers une politique globalement optimale à un taux O(1/t), même avec une taille de pas constante. Fait remarquable, la convergence globale de l'algorithme de bandit à gradient stochastique n'a jamais été établie auparavant, même s'il s'agit d'un ancien algorithme connu pour être applicable aux bandits. Ce nouveau résultat est obtenu grâce à deux nouvelles découvertes techniques : premièrement, le bruit des mises à jour stochastiques dans l'algorithme de bandit à gradient satisfait à une forte "condition de croissance", où la variance diminue chaque fois que le progrès devient faible, ce qui implique qu'un contrôle supplémentaire du bruit via des tailles de pas décroissantes n'est pas nécessaire ; deuxièmement, une forme d'"exploration faible" est automatiquement obtenue grâce aux mises à jour stochastiques du gradient, puisqu'elles empêchent les probabilités d'action de décroître plus rapidement que O(1/t), garantissant ainsi que chaque action est échantillonnée infiniment souvent avec une probabilité de 1. Ces deux résultats peuvent être utilisés pour montrer que la mise à jour stochastique du gradient est déjà "suffisante" pour les bandits dans le sens où l'exploration par rapport à l'exploitation est automatiquement équilibrée d'une manière qui garantit une convergence presque sûre vers un optimum global. Ces nouvelles conclusions théoriques sont vérifiées par des résultats expérimentaux.

Une approximation rapide et bien fondée du noyau de tangente neuronale empirique

Mohamad Amin Mohamadi, Wonho Bae, Danica J. Sutherland

Résumé : Les noyaux tangents neuronaux empiriques (eNTK) peuvent fournir une bonne compréhension de la représentation d'un réseau donné : ils sont souvent beaucoup moins coûteux à calculer et applicables plus largement que les NTK à largeur infinie. Toutefois, pour les réseaux comportant O unités de sortie (par exemple, un classificateur de classe O), l'eNTK sur N entrées est de taille NO×NO, ce qui nécessite O((NO)2) de mémoire et jusqu'à O((NO)3) de calcul. La plupart des applications existantes ont donc utilisé l'une des quelques approximations permettant d'obtenir des matrices à noyau N×N, ce qui permet d'économiser des ordres de grandeur en termes de calcul, mais avec une justification limitée, voire inexistante. Nous prouvons que l'une de ces approximations, que nous appelons "somme des logits", converge vers le vrai eNTK à l'initialisation pour tout réseau avec une large couche finale de "lecture". Nos expériences démontrent la qualité de cette approximation pour diverses utilisations dans un large éventail de contextes.

Traces d'éligibilité tenant compte de la trajectoire pour l'apprentissage par renforcement hors politique

Brett Daley, Martha WhiteChristopher Amato, Marlos C. Machado

Résumé : L'apprentissage hors politique à partir de retours multi-étapes est crucial pour l'apprentissage par renforcement efficace par échantillonnage, mais il est difficile de contrecarrer le biais hors politique sans exacerber la variance. Classiquement, le biais hors politique est corrigé par décision : les erreurs de différence temporelle passées sont repondérées par le ratio d'échantillonnage d'importance instantané après chaque action via les traces d'éligibilité. De nombreux algorithmes hors politique s'appuient sur ce mécanisme, ainsi que sur différents protocoles de découpage des ratios IS pour lutter contre la variance de l'estimateur IS. Malheureusement, une fois qu'une trace a été entièrement coupée, l'effet ne peut être inversé. Cela a conduit au développement de stratégies d'attribution de crédits qui tiennent compte de plusieurs expériences passées à la fois. Ces méthodes tenant compte de la trajectoire n'ont pas fait l'objet d'une analyse approfondie et leur justification théorique reste incertaine. Dans cet article, nous proposons un opérateur à plusieurs étapes qui peut exprimer à la fois les méthodes par décision et les méthodes tenant compte de la trajectoire. Nous prouvons les conditions de convergence de notre opérateur dans le cadre tabulaire, en établissant les premières garanties pour plusieurs méthodes existantes ainsi que pour de nombreuses nouvelles méthodes. Enfin, nous introduisons l'échantillonnage d'importance limité à la récence (RBIS), qui tire parti de la connaissance de la trajectoire pour obtenir des résultats robustes à travers les valeurs λ dans une tâche de contrôle hors politique.

Exphormer : Transformateurs épars pour les graphes

Hamed Shirzad, Ameya Velingker, Balaji Venkatachalam, Danica J. SutherlandAli Kemal Sinop

Résumé : Les transformateurs de graphes sont apparus comme une architecture prometteuse pour diverses tâches d'apprentissage et de représentation des graphes. Malgré leur succès, il reste difficile de faire évoluer les transformateurs de graphes vers de grands graphes tout en maintenant une précision compétitive par rapport aux réseaux à passage de messages. Dans cet article, nous présentons Exphormer, un cadre permettant de construire des transformateurs de graphes puissants et évolutifs. Exphormer consiste en un mécanisme d'attention clairsemé basé sur deux mécanismes : les nœuds globaux virtuels et les graphes d'expansion, dont les caractéristiques mathématiques, telles que l'expansion spectrale, le caractère aléatoire et clairsemé, produisent des transformateurs de graphes dont la complexité n'est que linéaire par rapport à la taille du graphe, tout en nous permettant de prouver les propriétés théoriques souhaitables des modèles de transformateurs qui en résultent. Nous montrons que l'intégration d'Exphormer dans le cadre récemment proposé par GraphGPS produit des modèles avec des résultats empiriques compétitifs sur une grande variété d'ensembles de données graphiques, y compris des résultats de pointe sur trois ensembles de données. Nous montrons également qu'Exphormer peut s'adapter à des ensembles de données sur des graphes plus grands que les architectures de transformateurs de graphes précédentes.

Facteurs d'approximation optimaux dans l'estimation de la fonction de valeur hors politique mal spécifiée

Philip Amortila, Nan Jiang, Csaba Szepesvari

Résumé : Les garanties théoriques dans l'apprentissage par renforcement (RL) sont connues pour souffrir de facteurs d'expansion multiplicatifs en ce qui concerne l'erreur de mauvaise spécification de l'approximation de la fonction. Cependant, la nature de ces facteurs d'approximation - en particulier leur forme optimale dans un problème d'apprentissage donné - est mal comprise. Dans cet article, nous étudions cette question dans le cadre de l'estimation linéaire de la fonction de valeur hors politique, où de nombreuses questions restent ouvertes. Nous étudions le facteur d'approximation dans un large éventail de contextes, tels que la présence ou l'absence de changement d'état et la couverture complète ou partielle de l'espace d'état. Nos principaux résultats comprennent des bornes supérieures dépendantes de l'instance sur les facteurs d'approximation par rapport à la norme L(2) pondérée (où la pondération est la distribution de l'état hors ligne) et à la norme L(∞). Nous montrons que ces facteurs d'approximation sont optimaux (dans un sens dépendant de l'instance) pour un certain nombre de ces paramètres. Dans d'autres cas, nous montrons que les paramètres dépendant de l'instance qui apparaissent dans les limites supérieures sont nécessaires et que la finitude de l'un ou l'autre ne peut à elle seule garantir un facteur d'approximation fini, même dans la limite de données infinies.

Revoir le simple regret : Tarifs rapides pour le retour d'un bon bras

Yao Zhao, Connor James Stephens, Csaba SzepesváriKwang-Sung Jun

Abstract: Simple regret is a natural and parameter-free performance criterion for pure exploration in multi-armed bandits yet is less popular than the probability of missing the best arm or an ϵ-good arm, perhaps due to lack of easy ways to characterize it. In this paper, we make significant progress on minimizing simple regret in both data-rich (T≥n) and data-poor regime (T≤n) where n is the number of arms, and T is the number of samples. At its heart is our improved instance-dependent analysis of the well-known Sequential Halving (SH) algorithm, where we bound the probability of returning an arm whose mean reward is not within ϵ from the best (i.e., not ϵ-good) for \textit{any} choice of ϵ>0, although ϵ is not an input to SH. Our bound not only leads to an optimal worst-case simple regret bound of n/T‾‾‾‾√ up to logarithmic factors but also essentially matches the instance-dependent lower bound for returning an ϵ-good arm reported by Katz-Samuels and Jamieson (2020). For the more challenging data-poor regime, we propose Bracketing SH (BSH) that enjoys the same improvement even without sampling each arm at least once. Our empirical study shows that BSH outperforms existing methods on real-world tasks.