COLIN Igor

Le théorème de Shapley-Folkman montre que les moyennes de Minkowski d'ensembles uniformément bornés ont tendance à être convexes lorsque le nombre de termes dans la somme devient beaucoup plus grand que la dimension ambiante. En optimisation, Aubin et Ekeland [1976] montrent que cela produit une limite a priori sur l'écart de dualité des problèmes d'optimisation non convexes séparables impliquant des sommes finies. Cette limite est très conservatrice et dépend de quantités instables, et nous la relaxons dans plusieurs directions pour montrer que la non-convexité peut avoir un impact beaucoup plus faible sur les problèmes de minimisation de sommes finies tels que la minimisation du risque empirique et la classification multi-tâches. Comme sous-produit, nous montrons une nouvelle version du lemme classique approximatif de Carath'eodory de Maurey où nous échantillonnons une fraction significative des coefficients, sans remplacement, ainsi qu'un résultat sur les contraintes d'échantillonnage utilisant un théorème de Helly approximatif, tous deux d'intérêt indépendant.

Dans les réseaux décentralisés (de capteurs, d'objets connectés, etc.), il existe un besoin important d'algorithmes efficaces pour optimiser une fonction de coût globale, par exemple pour apprendre un modèle global à partir des données locales collectées par chaque unité de calcul. Dans cet article, nous abordons le problème de la minimisation décentralisée de fonctions par paires de points de données, où ces points sont distribués sur les nœuds d'un graphe définissant la topologie de communication du réseau. Ce problème général trouve des applications dans le classement, l'apprentissage métrique de la distance et l'inférence de graphes, entre autres. Nous proposons de nouveaux algorithmes de commérage basés sur la moyenne double qui visent à résoudre de tels problèmes à la fois dans des contextes synchrones et asynchrones. Le cadre proposé est suffisamment flexible pour traiter les variantes contraintes et régularisées du problème d'optimisation. Notre analyse théorique révèle que les algorithmes proposés préservent le taux de convergence de la double moyenne centralisée jusqu'à un terme de biais additif. Nous présentons des simulations numériques sur des problèmes de maximisation de l'aire sous la courbe ROC (AUC) et d'apprentissage métrique qui illustrent l'intérêt pratique de notre approche.

Avec la disponibilité croissante de grandes quantités de données, la complexité du calcul est devenue la clé de voûte de nombreux algorithmes d'apprentissage automatique. Les algorithmes d'optimisation stochastique et les méthodes distribuées/décentralisées ont été largement étudiés au cours de la dernière décennie et offrent une évolutivité accrue pour optimiser un risque empirique qui est séparable dans l'échantillon de données. Pourtant, dans un large éventail de problèmes d'apprentissage statistique, le risque est estimé avec précision par des statistiques U, c'est-à-dire des fonctionnelles des données d'apprentissage à faible variance qui prennent la forme de moyennes sur d-tuples. Nous abordons d'abord le problème de l'échantillonnage pour le problème de minimisation du risque empirique. Nous montrons que les risques empiriques peuvent être remplacés par des estimations de Monte-Carlo drastiquement plus simples en termes de calcul et basées sur O(n) termes seulement, généralement appelées statistiques U incomplètes, sans nuire au taux d'apprentissage. Nous établissons des résultats de déviation uniforme et des exemples numériques montrent que cette approche surpasse les techniques de sous-échantillonnage plus naïves. Nous nous concentrons ensuite sur le sujet de l'estimation décentralisée, où l'échantillon de données est distribué sur un réseau connecté. Nous introduisons de nouveaux algorithmes de commérage aléatoire synchrone et asynchrone qui propagent simultanément les données à travers le réseau et maintiennent des estimations locales de la statistique U d'intérêt. Nous établissons des limites de taux de convergence avec des termes explicites dépendant des données et du réseau. Enfin, nous traitons de l'optimisation décentralisée de fonctions qui dépendent de paires d'observations. Comme dans le cas de l'estimation, nous introduisons une méthode basée sur des mises à jour locales concurrentes et la propagation des données. Notre analyse théorique révèle que les algorithmes proposés préservent le taux de convergence de la double moyenne centralisée jusqu'à un terme de biais additif. Nos simulations illustrent l'intérêt pratique de notre approche.

Dans les réseaux décentralisés (de capteurs, d'objets connectés, etc.), il existe un besoin important d'algorithmes efficaces pour optimiser une fonction de coût globale, par exemple pour apprendre un modèle global à partir des données locales collectées par chaque unité de calcul. Dans cet article, nous abordons le problème de la minimisation décentralisée de fonctions par paires de points de données, où ces points sont distribués sur les nœuds d'un graphe définissant la topologie de communication du réseau. Ce problème général trouve des applications dans le classement, l'apprentissage métrique de la distance et l'inférence de graphes, entre autres. Nous proposons de nouveaux algorithmes de commérage basés sur la moyenne double qui visent à résoudre de tels problèmes à la fois dans des contextes synchrones et asynchrones. Le cadre proposé est suffisamment flexible pour traiter les variantes contraintes et régularisées du problème d'optimisation. Notre analyse théorique révèle que les algorithmes proposés préservent le taux de convergence de la double moyenne centralisée jusqu'à un terme de biais additif. Nous présentons des simulations numériques sur des problèmes de maximisation de l'aire sous la courbe ROC (AUC) et d'apprentissage métrique qui illustrent l'intérêt pratique de notre approche.

L?explosion re?cente des volumes de donne?es disponibles a fait de la complexite? algorithmique un e?le?ment central des me?thodes d?apprentissage automatique. Les algorithmes d?optimisation stochastique ainsi que les me?thodes distribue?es et de?centralise?es ont e?te? largement de?veloppe?s durant les dix dernie?res anne?es. Ces me?thodes ont permis de faciliter le passage a? l?e?chelle pour optimiser des risques empiriques dont la formulation est se?parable en les observations associe?es. Pourtant, dans de nombreux proble?mes d?apprentissage statistique, l?estimation pre?cise du risque s?effectue a? l?aide de U-statistiques, des fonctions des donne?es prenant la forme de moyennes sur des d-uplets. Nous nous inte?ressons tout d?abord au proble?me de l?e?chantillonnage pour la minimisation du risque empirique. Nous montrons que le risque peut e?tre remplace? par un estimateur de Monte-Carlo, intitule? U-statistique incomple?te, base? sur seulement O(n) termes et permettant de conserver un taux d?apprentissage du me?me ordre. Nous e?tablissons des bornes sur l?erreur d?approximation du U-processus et les simulations nume?riques mettent en e?vidence l?avantage d?une telle technique d?e?chantillonnage. Nous portons par la suite notre attention sur l?estimation de?centralise?e, ou? les observations sont de?sormais distribue?es sur un re?seau connexe. Nous e?laborons des algorithmes dits gossip, dans des cadres synchrones et asynchrones, qui diffusent les observations tout en maintenant des estimateurs locaux de la U-statistique a? estimer. Nous de?montrons la convergence de ces algorithmes avec des de?pendances explicites en les donne?es et la topologie du re?seau. Enfin, nous traitons de l?optimisation de?centralise?e de fonctions de?pendant de paires d?observations. De me?me que pour l?estimation, nos me?thodes sont base?es sur la concomitance de la propagation des observations et l?optimisation local du risque. Notre analyse the?orique souligne que ces me?thodes conservent une vitesse de convergence du me?me ordre que dans le cas centralise?. Les expe?riences nume?riques confirment l?inte?re?t pratique de notre approche.

Pas de résumé disponible.

Les réseaux préservant la confidentialité peuvent être modélisés comme des réseaux décentralisés (par exemple, capteurs, objets connectés, smartphones), où la communication entre les nœuds du réseau n'est pas contrôlée par un nœud maître ou central. Pour ce type de réseaux, le problème principal est de rassembler/apprendre des informations globales sur le réseau (par exemple, en optimisant une fonction de coût global) tout en conservant les informations (sensibles) à chaque nœud. Dans ce travail, nous nous concentrons sur les informations textuelles que les agents ne veulent pas partager (par exemple, les messages texte, les courriels, les rapports confidentiels). Nous utilisons les avancées récentes sur l'optimisation décentralisée et les modèles de thèmes pour inférer des thèmes à partir d'un graphe avec une communication limitée. Nous proposons une méthode pour adapter le modèle d'allocation latente de Dirichlet (LDA) à l'optimisation décentralisée et montrons sur des données synthétiques que nous récupérons toujours des paramètres similaires et des performances similaires à chaque nœud qu'avec des méthodes stochastiques accédant à toute l'information du graphe.

Dans un large éventail de problèmes d'apprentissage statistique tels que le classement, le clustering ou l'apprentissage métrique entre autres, le risque est estimé avec précision par des U-statistiques de degré d ≥ 1, c'est-à-dire des fonctionnelles des données d'apprentissage à faible variance qui prennent la forme de moyennes sur k-tuples. D'un point de vue informatique, le calcul de ces statistiques est très coûteux, même pour un échantillon de taille modérée n, car il nécessite de calculer la moyenne de O(n^d) termes. Cela rend les procédures d'apprentissage reposant sur l'optimisation de telles fonctions de données difficilement réalisables en pratique. L'objectif principal de cet article est de montrer que, de manière frappante, de tels risques empiriques peuvent être remplacés par des estimations de Monte-Carlo radicalement plus simples en termes de calcul et basées sur O(n) termes seulement, généralement appelées statistiques U incomplètes, sans nuire au taux d'apprentissage O(1/√n) des procédures de minimisation des risques empiriques (ERM). À cette fin, nous établissons des résultats de déviation uniforme décrivant l'erreur commise lors de l'approximation d'un processus U par sa version incomplète sous des hypothèses de complexité appropriées. Des extensions à la sélection de modèles, aux situations de taux rapides et à diverses techniques d'échantillonnage sont également considérées, ainsi qu'une application à la descente de gradient stochastique pour la MRE. Enfin, des exemples numériques sont présentés afin de fournir des preuves empiriques solides que l'approche que nous promouvons surpasse largement les techniques de sous-échantillonnage plus naïves.

Des algorithmes efficaces et robustes pour l'estimation décentralisée dans les réseaux sont essentiels pour de nombreux systèmes distribués. Alors que l'estimation distribuée des statistiques de la moyenne de l'échantillon a fait l'objet d'une grande attention, le calcul des statistiques U, qui repose sur le calcul plus coûteux de la moyenne sur des paires d'observations, est un domaine moins étudié. Pourtant, de telles fonctions de données sont essentielles pour décrire les propriétés globales d'une population statistique, avec des exemples importants comme l'aire sous la courbe, la variance empirique, la différence de moyenne de Gini et la dispersion ponctuelle au sein d'un cluster. Cet article propose de nouveaux algorithmes de commérage aléatoires synchrones et asynchrones qui propagent simultanément les données à travers le réseau et maintiennent les estimations locales de la statistique U d'intérêt. Nous établissons des limites de taux de convergence de O(1 / t) et O(log t / t) pour les cas synchrones et asynchrones respectivement, où t est le nombre d'itérations, avec des termes explicites dépendant des données et du réseau. Au-delà des comparaisons favorables en termes d'analyse de taux, les expériences numériques fournissent des preuves empiriques que les algorithmes proposés surpassent l'approche introduite précédemment.

Des algorithmes efficaces et robustes pour l'estimation décentralisée dans les réseaux sont essentiels pour de nombreux systèmes distribués. Alors que l'estimation distribuée des statistiques de la moyenne de l'échantillon a fait l'objet d'une grande attention, le calcul des statistiques U, qui repose sur le calcul plus coûteux de la moyenne sur des paires d'observations, est un domaine moins étudié. Pourtant, de telles fonctions de données sont essentielles pour décrire les propriétés globales d'une population statistique, avec des exemples importants comme l'aire sous la courbe, la variance empirique, la différence de moyenne de Gini et la dispersion ponctuelle au sein d'un cluster. Cet article propose de nouveaux algorithmes de commérage aléatoires synchrones et asynchrones qui propagent simultanément les données à travers le réseau et maintiennent les estimations locales de la statistique U d'intérêt. Nous établissons des limites de taux de convergence de O(1/t) et O(log t/t) pour les cas synchrones et asynchrones respectivement, où t est le nombre d'itérations, avec des termes explicites dépendant des données et du réseau. Au-delà des comparaisons favorables en termes d'analyse de taux, les expériences numériques fournissent des preuves empiriques que les algorithmes proposés surpassent l'approche introduite précédemment.