Cette année, la conférence internationale sur l'apprentissage automatique (ICML) sera virtuelle et se déroulera du dimanche 13 au samedi 18 juillet. 

L'ICML est l'une des principales conférences mondiales sur l'apprentissage automatique, comme en témoigne le volume massif d'articles sur l'apprentissage automatique soumis. Cette année, la conférence a accepté 1 088 articles sur 4 990 soumissions, soit un taux d'acceptation de 21,8 % (en baisse par rapport à 22,6 % en 2019). Les membres du corps professoral de Vector ont eu 19 articles acceptés, avec cinq autres provenant des affiliés du corps professoral de Vector. Dans l'ensemble, les articles liés à Vector représentent 2,21 % du nombre total d'articles acceptés à l'ICML 2020.

Vous trouverez ci-dessous des résumés en langage clair de certains des travaux que les chercheurs de Vector présenteront lors de la conférence de cette année. Les résumés marqués d'un astérisque (*) renvoient au résumé original de l'article.

Vecteur Faculté

Dureté visuelle angulaire
Beidi Chen (Rice University) - Weiyang Liu (Georgia Tech) - Zhiding Yu (NVIDIA) - Jan Kautz (NVIDIA) - Anshumali Shrivastava (Rice University) - Animesh Garg (University of Toronto, Vector Institute, Nvidia) - Anima Anandkumar (Caltech)
Les modèles d'apprentissage profond pour le raisonnement sur les images ont des performances impressionnantes mais souffrent souvent d'un mauvais calibrage. Ils ont tendance à être trop confiants, la confiance du modèle ne reflétant pas toujours la véritable ambiguïté sous-jacente et la dureté des points de données. Nous proposons une nouvelle méthode de mesure de la dureté des points de données, que nous appelons dureté visuelle angulaire (Angular Visual Hardness) : étant donné une image particulière, quelle est la difficulté pour un modèle d'apprentissage automatique de dire s'il s'agit d'une brioche à la cannelle ou d'un chiot recroquevillé ? Nous avons également constaté que l'AVH présente une corrélation statistiquement significative avec la dureté visuelle humaine, ce qui signifie que les gens trouvent ces problèmes tout aussi difficiles. La mesure de cette confusion est importante pour former de meilleurs modèles avec moins de données, ainsi que des modèles qui peuvent être plus justes dans la prise de décision avec des ensembles de données déséquilibrés. L'alignement de la formation sur cette mesure de la dureté permet également une meilleure généralisation en cas de modification de la distribution des données de test. 

Modélisation causale pour l'équité dans les systèmes dynamiques
Elliot Creager (Université de Toronto) - David Madras (Université de Toronto) - Toniann Pitassi (Université de Toronto) - Richard Zemel (Vector Institute)
Dans les applications d'apprentissage machine (ML) qui posent des problèmes d'équité, les données disponibles sont souvent "manquantes de manière non aléatoire" en raison de biais dans la politique historique utilisée pour la prise de décision. Dans le domaine du crédit, par exemple, la véritable solvabilité d'un demandeur est inconnue tant qu'un prêt ne lui a pas été proposé. Si une population de demandeurs s'est vu proposer moins de prêts dans le cadre de la politique historique, cette population sera "pauvre en données" dans l'ensemble de données résultant de cette politique. Nous étudions l'équité à long terme de la prise de décision par ML et montrons que les articles récents de cette littérature peuvent être refondus en modèles causaux. Ce paradigme de modélisation est mieux adapté aux problèmes de données manquantes non aléatoires et permet d'utiliser des outils issus de la littérature sur l'inférence causale afin d'améliorer l'estimation de la manière dont les politiques futures se comporteront dans les populations à données limitées, ce qui améliore en fin de compte la recherche de politiques plus équitables dans ces contextes.

Apprentissage par représentation convexe pour l'invariance généralisée dans l'espace semi-produit intérieur
Yingyi Ma (UIC) - Vignesh Ganapathiraman (Université de l'Illinois à Chicago) - Yaoliang Yu (Université de Waterloo) - Xinhua Zhang (Université de l'Illinois à Chicago (UIC))
La découverte automatique de représentations invariantes par rapport à certaines transformations (telles que les changements de pose et d'expressions faciales, la translation ou la rotation d'objets rigides, les relations sémantiques ou logiques entre les classes et les relations structurées entre les entités) a été la clé de l'apprentissage des algorithmes pour faire face à l'énorme quantité de variations d'objets réels. Nous développons un cadre de régularisation basé sur des produits semi-intérieurs pour induire un large ensemble d'invariances généralisées qui s'étendent au-delà des espaces de Hilbert classiques à noyau reproducteur. Nous fournissons des implémentations efficaces basées sur les encastrements euclidiens et démontrons l'efficacité de notre algorithme sur l'augmentation des données et la prédiction structurée multi-labels.

Supprimer l'intermédiaire : formation et évaluation de modèles basés sur l'énergie sans échantillonnage
Will Grathwohl (Université de Toronto) - Kuan-Chieh Wang (Université de Toronto) - Joern-Henrik Jacobsen (Institut Vecteur et Université de Toronto) - David Duvenaud (Université de Toronto) - Richard Zemel (Institut Vecteur)
Si nous voulons faire des prédictions à partir d'un ensemble de données, nous devons ajuster un modèle qui indique la probabilité de différentes prédictions. L'ajustement de ce modèle implique de comparer les prédictions aux données d'origine. Comme il existe une infinité de prédictions possibles, il peut être difficile de quantifier la différence entre toutes les prédictions possibles que le modèle pourrait faire et les données. Notre article propose d'utiliser un réseau neuronal pour apprendre la différence entre les prédictions du modèle et les données. Une fois que nous avons ajusté ce réseau, nous pouvons ajuster les prédictions du modèle pour réduire cette différence.

Détection d'exemples hors distribution avec les matrices de Gram
Chandramouli Shama Sastry (Dalhousie University/Vector Institute) - Sageev Oore (Dalhousie University and Vector Institute)
Souvent, les réseaux neuronaux "ne savent pas ce qu'ils ne savent pas" : un classificateur de lésions cutanées précis pourrait non seulement classer une image de chien comme un type particulier de lésion, mais il pourrait le faire avec beaucoup de confiance. Cela s'explique par le fait que les chiens constituent un type (c'est-à-dire une distribution) d'image différent de tout ce que le réseau a vu au cours de la formation. L'une des difficultés rencontrées dans la pratique est que le réseau ne peut pas s'y préparer à l'avance (c'est-à-dire qu'il ne peut pas examiner tous les types d'images qu'il pourrait voir lorsqu'il est déployé). Cette recherche permet d'obtenir des résultats de pointe en matière de détection de la présentation d'un type d'image inconnu. Notre algorithme y parvient en remarquant des schémas inhabituels dans les activations internes du réseau.

Évaluation des taux de compression avec perte des modèles génératifs profonds
Sicong Huang (Université de Toronto) - Alireza Makhzani (Université de Toronto) - Yanshuai Cao (Borealis AI) - Roger Grosse (Université de Toronto et Vector Institute)
Les réseaux adversoriels génératifs (GAN) ont démontré une capacité impressionnante à générer des images convaincantes, mais nous ne savons toujours pas dans quelle mesure ils correspondent à la distribution globale des images. Nous avons introduit une méthode pour évaluer leur capacité à modéliser la distribution en termes de compression avec perte : la capacité d'encoder une image en utilisant un nombre de bits beaucoup plus petit que ce qu'il faudrait pour l'encoder exactement. En mesurant la courbe de compromis entre le nombre de bits et l'erreur de reconstruction, nous obtenons une image beaucoup plus complète de la performance de la modélisation de la distribution, par rapport aux mesures traditionnelles à valeur scalaire.

Compromis fondamentaux entre invariance et sensibilité aux perturbations adverses
Florian Tramer (Université de Stanford) - Jens Behrmann (Université de Brême) - Nicholas Carlini (Google) - Nicolas Papernot (Université de Toronto et Institut Vector) - Joern-Henrik Jacobsen (Institut Vector et Université de Toronto)
Notre travail portait sur les exemples adverses : dans les tâches de perception, les exemples adverses sont des images perturbées pour induire un modèle ML en erreur et l'amener à faire des prédictions incorrectes. La principale question que nous avons posée dans notre article de l'ICML était la suivante : les progrès que nous réalisons dans la défense contre la recherche d'exemples adverses conduisent-ils à des progrès significatifs pour la robustesse du ML dans la pratique ? Nous avons montré que ce n'était pas tout à fait le cas en raison de la manière dont nous définissons les exemples adverses, qui font des hypothèses trop simples, exposant ainsi les modèles à de nouvelles formes d'attaques.

Généralisation par dérandomisation
Jeffrey Negrea (étudiant de l'Université de Toronto, chez Vector), Gintare Karolina Dziugaite (Element AI), Daniel M. Roy
Il existe un large fossé entre les performances de l'apprentissage profond que nous observons dans la pratique et celles prédites par nos meilleures théories. Ce travail démontre comment contourner un obstacle théorique qui a apparemment rendu inefficaces de nombreux outils standard.

Hierarchical Verification for Adversarial Robustness*
Cong Han Lim (Uber ATG) - Raquel Urtasun (Uber ATG) - Ersin Yumer (Uber ATG)
Nous présentons un nouveau cadre pour le problème de vérification de la robustesse `p ponctuelle exacte qui exploite la structure géométrique en couches des réseaux feed-forward profonds avec des activations linéaires rectifiées (réseaux ReLU). Les régions d'activation du réseau partitionnent l'espace d'entrée et il est possible de vérifier la robustesse `p autour d'un point en vérifiant toutes les régions d'activation dans le rayon souhaité. L'algorithme GeoCert (Jordan et al., 2019) traite cette partition comme un complexe polyédrique générique afin de détecter la région à vérifier ensuite. En revanche, notre cadre LayerCert considère la structure d'arrangement d'hyperplans imbriqués induite par les couches du réseau ReLU et explore les régions de manière hiérarchique. Nous montrons que, sous certaines conditions relatives aux paramètres de l'algorithme, LayerCert réduit de manière prouvée le nombre et la taille des programmes convexes à résoudre par rapport à GeoCert. En outre, notre cadre LayerCert permet d'incorporer des routines de limites inférieures basées sur des relaxations convexes afin d'améliorer encore les performances. Les résultats expérimentaux démontrent que LayerCert peut réduire de manière significative le nombre de programmes convexes résolus et le temps d'exécution par rapport à l'état de l'art.

Limites améliorées du Regret Minimax en cas de perte logarithmique via l'autoconcordance
Blair Bilodeau (Université de Toronto), Dylan Foster (MIT), Daniel Roy (Université de Toronto)
Nous sommes souvent intéressés par la prévision d'événements futurs dans le temps, tels que la météo du lendemain ou la performance du marché boursier. Dans ce travail, nous faisons des progrès significatifs dans notre compréhension des limites mathématiques de la performance des prévisions.

Améliorer l'optimisation des transformateurs grâce à une meilleure initialisation*
XiaoShi Huang (Layer6 AI) - Felipe Perez (Layer6 AI) - Jimmy Ba (University of Toronto) - Maksims Volkovs (Layer6 AI)
L'architecture Transformer a connu récemment un succès considérable ; le composant clé du Transformer est la couche d'attention qui permet au modèle de se concentrer sur les régions importantes d'une séquence d'entrée. L'optimisation du gradient avec des couches d'attention peut être notoirement difficile, nécessitant des astuces telles que l'échauffement du taux d'apprentissage pour éviter la divergence. Les modèles Transformer devenant plus volumineux et plus coûteux à entraîner, la recherche récente s'est concentrée sur la compréhension et l'amélioration de l'optimisation dans ces architectures. Dans ce travail, nos contributions sont doubles : nous étudions et validons empiriquement la source des problèmes d'optimisation dans l'architecture du codeur-décodeur Transformer ; nous proposons ensuite un nouveau schéma d'initialisation des poids avec une justification théorique, qui permet l'apprentissage sans échauffement ni normalisation des couches. Les résultats empiriques sur des benchmarks publics de traduction automatique montrent que notre approche atteint une précision de premier plan, permettant d'entraîner sans difficulté des modèles Transformer profonds avec 200 couches dans l'encodeur et le décodeur (plus de 1000 blocs d'attention/MLP).

Connectivité des modes linéaires et hypothèse du billet de loterie
Jonathan Frankle (MIT), Gintare Karolina Dziugaite (Element AI), Daniel M. Roy (Vector Institute), Michael Carbin (MIT)
Dans ce travail, nous relions deux phénomènes apparemment distincts dans l'apprentissage des réseaux neuronaux : la connectivité en mode linéaire et l'hypothèse du billet de loterie. Sur des réseaux de vision standard et des points de référence, nous montrons que des sous-réseaux d'entraînement clairsemés apparaissent lorsque l'effet du bruit de minibatch tombe en dessous d'un niveau bien défini.

Exploration du gain d'entropie maximale pour l'apprentissage par renforcement multi-buts à horizon long
Silviu Pitis (Université de Toronto) - Harris Chan (Université de Toronto, Institut Vecteur) - Stephen Zhao (Université de Toronto) - Bradly Stadie (Institut Vecteur) - Jimmy Ba (Université de Toronto)
Nous concevons des robots à la recherche d'objectifs qui se fixent et poursuivent des objectifs en fonction de leur expérience et de leurs capacités passées. En fixant des objectifs qui les conduisent à des situations nouvelles et peu explorées, nos robots simulés apprennent à naviguer dans des labyrinthes et à manipuler des blocs en un temps record, avec seulement une fraction des interactions avec l'environnement utilisées par les approches antérieures de pointe.

Multi-Agent Routing Value Iteration Network*
Quinlan Sykora (Uber ATG) - Mengye Ren (Uber ATG / University of Toronto) - Raquel Urtasun (Uber ATG)
Dans cet article, nous abordons le problème de l'acheminement coordonné de plusieurs agents. Il s'agit d'un problème complexe qui a un large éventail d'applications dans la gestion de flotte pour atteindre un objectif commun, comme la cartographie à partir d'un essaim de robots et le covoiturage. Les méthodes traditionnelles ne sont généralement pas conçues pour des environnements réalistes qui contiennent des graphes peu connectés et un trafic inconnu, et sont souvent trop lentes pour être pratiques. En revanche, nous proposons un modèle basé sur un réseau neuronal graphique capable d'effectuer un routage multi-agents basé sur l'itération de valeurs apprises dans un graphe peu connecté avec des conditions de trafic changeant dynamiquement. En outre, notre module de communication apprise permet aux agents de se coordonner en ligne et de s'adapter aux changements de manière plus efficace. Nous avons créé un environnement simulé pour imiter la cartographie réaliste réalisée par des véhicules autonomes avec une couverture minimale des bords et des conditions de trafic inconnues ; notre approche surpasse de manière significative les solveurs traditionnels à la fois en termes de coût total et de temps d'exécution. Nous montrons également que notre modèle formé avec seulement deux agents sur des graphes avec un maximum de 25 nœuds peut facilement se généraliser à des situations avec plus d'agents et/ou de nœuds.

Heuristique de résolution SAT basée sur l'appariement bayésien des moments en ligne
Haonan Duan (Université de Waterloo) - Saeed Nejati (Université de Waterloo) - George Trimponias (Noah's Ark Lab) - Pascal Poupart (Université de Waterloo et Borealis AI) - Vijay Ganesh (Université de Waterloo, génie électrique et informatique)
Ce travail décrit une technique d'apprentissage bayésien pour initialiser la recherche d'une solution aux problèmes de satisfaction de contraintes formulés en tant que satisfiabilité booléenne. L'approche apprend à satisfaire la plupart des contraintes en une fraction de seconde, ce qui accélère la recherche d'une solution dans les problèmes cryptographiques difficiles et d'autres problèmes combinatoires industriels.

Optimiser le bien-être social à long terme dans les systèmes de recommandation : A Constrained Matching Approach*
Martin Mladenov (Google) - Elliot Creager (University of Toronto) - Omer Ben-Porat (Technion-Israel Institute of Technology) - Kevin Swersky (Google Brain) - Richard Zemel (Vector Institute) - Craig Boutilier (Google)
La plupart des recherches sur les systèmes de recommandation (SR) partent du principe que l'utilité d'un utilisateur peut être maximisée indépendamment de l'utilité des autres agents (par exemple, d'autres utilisateurs, des fournisseurs de contenu). Dans la réalité, ce n'est souvent pas le cas : la dynamique d'un écosystème de SR couple l'utilité à long terme de tous les agents. Dans ce travail, nous explorons des contextes dans lesquels les fournisseurs de contenu ne peuvent rester viables que s'ils bénéficient d'un certain niveau d'engagement de la part des utilisateurs. Nous formulons le problème de la recommandation dans ce contexte comme un problème de sélection d'équilibre dans le système dynamique induit, et nous montrons qu'il peut être résolu comme un problème d'appariement optimal sous contrainte. Notre modèle garantit que le système atteint un équilibre avec un bien-être social maximal soutenu par un ensemble suffisamment diversifié de fournisseurs viables. Nous démontrons que même dans un modèle dynamique simple et stylisé de RS, l'approche myope standard de la recommandation - qui consiste à toujours faire correspondre un utilisateur au meilleur fournisseur - donne de piètres résultats. Nous développons plusieurs techniques évolutives pour résoudre le problème de l'appariement et nous établissons également des liens avec diverses notions de regret de l'utilisateur et d'équité, en soutenant que ces résultats sont plus équitables dans un sens utilitaire.

StyleGAN semi-supervisé pour l'apprentissage du démêlage
Weili Nie (Rice University) - Tero Karras (NVIDIA) - Animesh Garg (University of Toronto, Vector Institute, Nvidia) - Shoubhik Debnath (Nvidia) - Anjul Patney (Nvidia) - Ankit Patel (Rice University, Baylor College of Medicine) - Anima Anandkumar (Amazon AI & Caltech)
Les récents progrès réalisés dans le domaine des modèles génératifs pour les images ont donné des résultats impressionnants. Cependant, la génération n'est pas contrôlable. La génération contrefactuelle - où nous voulons changer une seule caractéristique de l'image d'entrée - nécessite de grandes étiquettes au niveau des caractéristiques. Ce problème est appelé "démêlage" dans les modèles génératifs. Cela signifie que nous avons besoin d'ensembles de données avec des étiquettes détaillées telles que lunettes, barbe, couleur des yeux, sourire - et ce uniquement pour les visages. Dans d'autres domaines d'images naturelles, cet espace d'étiquettes peut être encore plus grand. Ce travail vise à améliorer le démêlage sans utiliser d'ensembles de données entièrement étiquetés. Nous parvenons à générer un contrefactuel contrôlable avec seulement 1 % de données étiquetées, contrairement à d'autres approches contemporaines qui nécessitent une supervision complète. Les résultats nous permettent donc de séparer les facteurs de variation dans les ensembles de données d'entrée tels que la couleur, la forme, les caractéristiques faciales, etc. Et en utilisant cette séparabilité, nous pouvons maintenant modifier l'entrée pour changer n'importe laquelle de ces caractéristiques de manière sélective afin d'imaginer à quoi ressemblerait cette personne avec des lunettes, ou à quoi ressemblerait cette pièce avec un éclairage différent. 

Attaques adverses de Wasserstein plus fortes et plus rapides
Kaiwen Wu (Université de Waterloo) - Allen Wang (Université de Waterloo) - Yaoliang Yu (Université de Waterloo)
Les modèles profonds sont étonnamment vulnérables aux attaques adverses, c'est-à-dire à des perturbations imperceptibles qui modifient complètement la sortie du réseau, ce qui soulève de graves problèmes de sécurité pour les systèmes d'intelligence artificielle. Nous développons deux nouveaux algorithmes pour effectuer des attaques adverses plus rapides et plus fortes dans le cadre du récent modèle de menace de Wasserstein. En outre, nous démontrons que nos algorithmes d'attaque, lorsqu'ils sont combinés à un entraînement contradictoire, améliorent largement la robustesse des modèles profonds contre les attaques contradictoires. Nous pensons que nos outils aideront les praticiens à mieux évaluer la robustesse de leurs modèles et, à terme, à construire des systèmes d'IA plus robustes.

Queues des flux triangulaires Lipschitz
Priyank Jaini (Université de Waterloo, Institut Vecteur) - Ivan Kobyzev (Borealis AI) - Yaoliang Yu (Université de Waterloo) - Marcus Brubaker (Borealis AI)
La distribution d'objets réels (tels que des visages humains ou des documents écrits en anglais) peut être apprise en "déformant" une distribution préalable fixe par le biais de transformations triangulaires multicouches, après quoi de nouveaux objets peuvent être facilement synthétisés et incorporés dans divers algorithmes et applications d'apprentissage. Nous étudions comment la queue (c'est-à-dire les objets extrêmes) d'une distribution peut ou ne peut pas changer de manière adéquate à travers les architectures existantes dans les flux triangulaires. En conséquence, nous proposons un modèle de flux adaptatif à la queue qui peut mieux adapter les modèles de flux existants aux distributions cibles à queue lourde, telles que celles couramment utilisées dans la modélisation des risques financiers et des valeurs extrêmes.

Vecteurs affiliés à la faculté

Certification et apprentissage sous perturbations adverses*
Hassan Ashtiani (McMaster University) - Vinayak Pathak (Scotiabank) - Ruth Urner (York University)
Nous étudions formellement le problème de la classification sous perturbations adverses, à la fois du point de vue de l'apprenant et du point de vue d'un tiers qui vise à certifier la robustesse d'un classificateur boîte noire donné. Nous analysons un cadre d'apprentissage semi-supervisé de type PAC et identifions des résultats de possibilité et d'impossibilité pour un apprentissage correct des classes VC dans ce cadre. Nous introduisons et étudions également un nouveau cadre de certification de boîte noire avec un budget d'interrogation limité. Nous l'analysons pour différentes classes de prédicteurs et différents types de perturbations. Nous considérons également le point de vue d'un adversaire de boîte noire qui vise à trouver des exemples adverses, en montrant que l'existence d'un adversaire avec une complexité de requête polynomiale implique l'existence d'un apprenant robuste avec une petite complexité d'échantillon.

Faster Graph Embeddings via Coarsening*
Matthew Fahrbach (Georgia Institute of Technology) - Gramoz Goranci (University of Toronto) - Sushant Sachdeva (University of Toronto) - Richard Peng (Georgia Tech / MSR Redmond) - Chi Wang (Microsoft Research)
Les graph embeddings sont un outil omniprésent pour les tâches d'apprentissage automatique, telles que la classification des nœuds et la prédiction des liens, sur des données structurées sous forme de graphes. Cependant, le calcul des encastrements pour les graphes à grande échelle est prohibitivement inefficace, même si nous ne nous intéressons qu'à un petit sous-ensemble de sommets pertinents. Pour remédier à ce problème, nous présentons une approche efficace de coarsening des graphes, basée sur les compléments de Schur, pour calculer l'encastrement des sommets pertinents. Nous prouvons que ces encastrements sont préservés exactement par le graphe des compléments de Schur obtenu par élimination gaussienne des sommets non pertinents. Le calcul des compléments de Schur étant coûteux, nous proposons un algorithme en temps quasi-linéaire qui génère un graphe plus grossier sur les sommets pertinents qui correspond de manière prouvée au complément de Schur dans l'attente à chaque itération. Nos expériences impliquant des tâches de prédiction sur des graphes démontrent que le calcul des encastrements sur le graphe grossier, plutôt que sur le graphe entier, conduit à des gains de temps significatifs sans sacrifier la précision.

Generalized and Scalable Optimal Sparse Decision Trees*
Jimmy Lin (University of British Columbia) - Chudi Zhong (Duke University) - Diane Hu (Duke University) - Cynthia Rudin (Duke) - Margo Seltzer (University of British Columbia)
L'optimisation des arbres de décision est notoirement difficile d'un point de vue informatique, mais essentielle pour le domaine de l'apprentissage automatique interprétable. Malgré les efforts déployés au cours des 40 dernières années, ce n'est que récemment que des percées en matière d'optimisation ont été réalisées, permettant à des algorithmes pratiques de trouver des arbres de décision optimaux. Ces nouvelles techniques ont le potentiel de déclencher un changement de paradigme où il est possible de construire des arbres de décision clairsemés pour optimiser efficacement une variété de fonctions objectives sans dépendre des heuristiques de division et d'élagage gourmandes qui conduisent souvent à des solutions sous-optimales. La contribution de ce travail est de fournir un cadre général pour l'optimisation des arbres de décision qui aborde les deux problèmes ouverts importants dans le domaine : le traitement des données déséquilibrées et l'optimisation complète sur des variables continues. Nous présentons des techniques qui produisent des arbres de décision optimaux pour une variété d'objectifs, y compris le F-score, l'AUC et l'aire partielle sous la coque convexe ROC. Nous introduisons également un algorithme évolutif qui produit des résultats optimaux prouvés en présence de variables continues et qui accélère la construction d'arbres de décision de plusieurs ordres de grandeur par rapport à l'état de l'art.

Private Query Release Assisted by Public Data*
Raef Bassily (The Ohio State University) - Albert Cheu (Northeastern University) - Shay Moran (IAS, Princeton) - Aleksandar Nikolov (University of Toronto) - Jonathan Ullman (Northeastern University) - Steven Wu (University of Minnesota)
Nous étudions le problème de la diffusion de requêtes différentiellement privées assistée par l'accès à des données publiques. Dans ce problème, l'objectif est de répondre à une grande classe  de requêtes statistiques avec une erreur inférieure à α en utilisant une combinaison d'échantillons publics et privés. L'algorithme doit satisfaire à la confidentialité différentielle uniquement en ce qui concerne les échantillons privés. Nous étudions les limites de cette tâche en termes de complexité des échantillons publics et privés.
Tout d'abord, nous montrons que nous pouvons résoudre le problème pour toute classe de requête  de dimension VC finie en utilisant seulement d/α échantillons publics et p‾√d3/2/α2 échantillons privés, où d et p sont la dimension VC et la dimension VC duale de , respectivement. En comparaison, avec seulement des échantillons privés, ce problème ne peut pas être résolu même pour des classes de requêtes simples avec une dimension VC de un, et sans aucun échantillon privé, un échantillon public plus grand de taille d/α2 est nécessaire. Nous donnons ensuite des limites inférieures de la complexité de l'échantillon qui dépendent étroitement de p et de α. Pour la classe des souches de décision, nous donnons une limite inférieure de p‾√/α sur la complexité de l'échantillon privé chaque fois que la taille de l'échantillon public est inférieure à 1/α2. Compte tenu de nos limites supérieures, cela montre que la dépendance à l'égard de p‾√ est nécessaire dans la complexité de l'échantillon privé. Nous donnons également une borne inférieure de 1/α sur la complexité de l'échantillon public pour une large famille de classes de requêtes, qui, d'après notre borne supérieure, est étroite en α.

Convolutions à grand noyau tenant compte du temps*
Vasileios Lioutas (Carleton University) - Yuhong Guo (Carleton University)
Jusqu'à présent, la plupart des architectures de modélisation de séquences de pointe utilisent l'attention pour construire des modèles génératifs pour les tâches basées sur le langage. Certains de ces modèles utilisent tous les jetons de séquence disponibles pour générer une distribution de l'attention, ce qui se traduit par une complexité temporelle de O(n2). Ils utilisent également des convolutions en profondeur avec des noyaux normalisés softmax de taille k agissant comme une auto-attention à fenêtre limitée, ce qui entraîne une complexité temporelle de O(k⋅n). Dans cet article, nous présentons les convolutions à grand noyau temporel (TaLK), une nouvelle opération de convolution adaptative qui apprend à prédire la taille d'un noyau de sommation au lieu d'utiliser une matrice de noyau de taille fixe. Cette méthode permet d'obtenir une complexité temporelle de O(n), ce qui rend le processus d'encodage des séquences linéaire par rapport au nombre de jetons. Nous évaluons la méthode proposée sur des ensembles de données standard à grande échelle de traduction automatique, de résumé abstractif et de modélisation linguistique et nous montrons que les convolutions TaLK constituent une amélioration efficace par rapport à d'autres approches basées sur l'attention/convolution.