L’explosion récente des volumes de données disponibles a fait de la complexité algorithmique un élément central des méthodes d’apprentissage automatique. Les algorithmes d’optimisation stochastique ainsi que les méthodes distribuées et décentralisées ont été largement développés durant les dix dernières années. Ces méthodes ont permis de faciliter le passage à l’échelle pour optimiser des risques empiriques dont la formulation est séparable en les observations associées. Pourtant, dans de nombreux problèmes d’apprentissage statistique, l’estimation précise du risque s’effectue à l’aide de U-statistiques, des fonctions des données prenant la forme de moyennes sur des d-uplets. Nous nous intéressons tout d’abord au problème de l’échantillonnage pour la minimisation du risque empirique. Nous montrons que le risque peut être remplacé par un estimateur de Monte-Carlo, intitulé U-statistique incomplète, basé sur seulement O(n) termes et permettant de conserver un taux d’apprentissage du même ordre. Nous établissons des bornes sur l’erreur d’approximation du U-processus et les simulations numériques mettent en évidence l’avantage d’une telle technique d’échantillonnage. Nous portons par la suite notre attention sur l’estimation décentralisée, où les observations sont désormais distribuées sur un réseau connexe. Nous é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 à estimer. Nous démontrons la convergence de ces algorithmes avec des dépendances explicites en les données et la topologie du réseau. Enfin, nous traitons de l’optimisation décentralisée de fonctions dépendant de paires d’observations. De même que pour l’estimation, nos méthodes sont basées sur la concomitance de la propagation des observations et l’optimisation local du risque. Notre analyse théorique souligne que ces méthodes conservent une vitesse de convergence du même ordre que dans le cas centralisé. Les expériences numériques confirment l’intérêt pratique de notre approche. / With the increasing availability of large amounts of data, computational complexity has become a keystone of many machine learning algorithms. Stochastic optimization algorithms and distributed/decentralized methods have been widely studied over the last decade and provide increased scalability for optimizing an empirical risk that is separable in the data sample. Yet, in a wide range of statistical learning problems, the risk is accurately estimated by U-statistics, i.e., functionals of the training data with low variance that take the form of averages over d-tuples. We first tackle the problem of sampling for the empirical risk minimization problem. We show that empirical risks can be replaced by drastically computationally simpler Monte-Carlo estimates based on O(n) terms only, usually referred to as incomplete U-statistics, without damaging the learning rate. We establish uniform deviation results and numerical examples show that such approach surpasses more naive subsampling techniques. We then focus on the decentralized estimation topic, where the data sample is distributed over a connected network. We introduce new synchronous and asynchronous randomized gossip algorithms which simultaneously propagate data across the network and maintain local estimates of the U-statistic of interest. We establish convergence rate bounds with explicit data and network dependent terms. Finally, we deal with the decentralized optimization of functions that depend on pairs of observations. Similarly to the estimation case, we introduce a method based on concurrent local updates and data propagation. Our theoretical analysis reveals that the proposed algorithms preserve the convergence rate of centralized dual averaging up to an additive bias term. Our simulations illustrate the practical interest of our approach.

L'analyse en composantes indépendantes (ACI) est une forme d'analyse multivariée qui a émergée en tant que concept dans les années 1980-90. C'est un type de problème inverse où on observe une variable X dont les composantes sont les mélanges linéaires d'une variable S inobservable. Les composantes de S sont mutuellement indépendantes. La relation entre les deux variables s'exprime par X=AS, où A est une matrice de mixage inconnue .<br /><br />Le problème principal de l'ACI est d'estimer la matrice A, à partir de l'observation d'un échantillon i.i.d. de X, pour atteindre S qui constitue un système explicatif meilleur que X dans l'étude d'un phénomène particulier. Le problème se résout généralement par la minimisation d'un certain critère, issu d'une mesure de dépendance.<br /><br />L'ACI ressemble à l'analyse en composantes principales (ACP) dans la formulation du problème. Dans le cas de l'ACP on cherche des composantes non corrélées, c'est-à-dire indépendantes par paire à l'ordre 2 ; dans le cas de l'ACI on cherche des composantes mutuellement indépendantes, ce qui est beaucoup plus contraignant; dans le cas général, il n'existe plus de solution algébrique simple. Les principaux problèmes d'identification de A sont évités par un certain nombre de conventions adoptées dans le modèle ACI classique.<br /><br />L'approche qui est proposée dans cette thèse est du type non paramétrique. Sous des hypothèses de type Besov, on étudie plusieurs estimateurs d'un critère de dépendance exact donné par la norme L2 de la différence entre une densité et le produit de ses marges. Ce critère constitue une alternative à l'information mutuelle qui représentait jusqu'ici le critère exact de référence de la plupart des méthodes ACI.<br /><br />On donne une majoration de l'erreur en moyenne quadratique de différents estimateurs du contraste L2. Cette majoration prend en compte le biais d'approximation entre le Besov et l'espace de projection qui, ici, est issu d'une analyse multirésolution (AMR) générée par le produit tensoriel d'ondelettes de Daubechies. Ce type de majoration avec prise en compte du biais d'approximation est en général absent des méthodes non paramétriques récentes en ACI (méthodes kernel, information mutuelle).<br /><br />Le critère en norme L2 permet de se rapprocher de problèmes déjà connus dans la littérature statistique, estimation de l'intégrale de f au carré, tests d'homogénéité en norme L2, résultats de convergence d'estimateurs adoptant un seuillage par bloc. <br /><br />On propose des estimateurs du contraste L2 qui atteignent la vitesse minimax optimale du problème de intégrale de f au carré. Ces estimateurs de type U-statistique ont des complexités numériques quadratique en n, ce qui peut poser un problème pour la minimisation du contraste à suivre, en vue d'obtenir l'estimation concrète de la matrice A. En revanche, ces estimateurs admettent une forme de seuillage par bloc où la connaissance de la régularité s de la densité multivariée sous-jacente est inutile pour obtenir une vitesse optimale.<br /><br />On propose un estimateur de type plug-in dont la vitesse de convergence est sous-optimale mais qui est de complexité numérique linéaire en n. L'estimateur plug-in admet aussi une forme seuillée terme à terme, qui dégrade la vitesse de convergence mais permet d'obtenir un critère auto-adaptatif. Dans sa version linéaire, l'estimateur plug-in semble déjà quasiment auto-adaptatif dans les faits, c'est-à-dire que sous la contrainte 2^{jd} < n, où d est la dimension du problème et n le nombre d'observations, la majorité des résolutions j permettent d'estimer A après minimisation.<br /><br />Pour obtenir ces résultats on a été amené à développer une technique combinatoire spécifique permettant de majorer le moment d'ordre r d'une U-statistique ou d'une V-statistique. Les résultats classiques sur les U-statistiques ne sont en effet pas directement utilisables et pas facilement adaptables dans le contexte d'étude de la thèse. La méthode développée est utilisable dans d'autres contextes.<br /><br />La méthode par ondelettes s'appuie sur le paradigme usuel estimation d'un critère de dépendance, puis minimisation. On étudie donc dans la thèse les éléments permettant de faciliter la minimisation. On donne notamment des formulations du gradient et du hessien de l'estimateur du contraste qui se prêtent à un changement de résolution par simple filtrage et qui se calculent selon une complexité équivalente à celle de l'évaluation de l'estimateur lui même. <br /><br />Des simulations proposées dans la thèse confirment l'applicabilité de la méthode et donnent des résultats excellents. Tous les éléments nécessaires à l'implémentation de la méthode, et le code commenté des parties clefs de la programmation (notamment des algorithmes d-dimensionnels) figurent également dans le document.

Soient X et Y , deux variables aléatoires. De nombreuses procédures statistiques permettent d'ajuster un modèle à ces données dans le but d'expliquer Y à partir de X. La mise en place d'un tel modèle fait généralement appel à diverses hypothèses que <br />l'on doit valider pour justifier son utilisation. Dans ce travail, on propose une approche globale où toutes les hypothèses faites pour asseoir ce modèle sont testées simultanément. <br />Plus précisément, on construit un test basé sur une quantité qui permet de canaliser toute l'information liant X à Y : la fonction de répartition conditionnelle de Y sachant (X = x) définie par F(y|x)=P(Y<=y|X=x). Notre test compare la valeur prise par l'estimateur polynômial local de F(y|x) à une estimation paramétrique du modèle supposé et rejette sa <br />validité si la distance entre ces deux quantités est trop grande. Dans un premier temps, on considère le cas où la fonction de répartition supposée est entièrement spécifiée et, dans <br />ce contexte, on établit le comportement asymptotique du test. Dans la deuxième partie du travail, on généralise ce résultat au cas plus courant en pratique où le modèle supposé contient un certain nombre de paramètres inconnus. On étudie ensuite la puissance locale du test en déterminant son comportement asymptotique local sous des suites d'hypothèses contigües. Enfin, on propose un critère de choix de la fenêtre d'ajustement qui intervient lors de l'étape d'estimation polynômiale locale de la fonction de répartition conditionnelle.