Adaptation des m?thodes d?apprentissage aux U-statistiques.

Résumé 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.