• Refine Query
  • Source
  • Publication year
  • to
  • Language
  • 2
  • 1
  • Tagged with
  • 2
  • 2
  • 2
  • 2
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • About
  • The Global ETD Search service is a free service for researchers to find electronic theses and dissertations. This service is provided by the Networked Digital Library of Theses and Dissertations.
    Our metadata is collected from universities around the world. If you manage a university/consortium/country archive and want to be added, details can be found on the NDLTD website.
1

Adaptation des méthodes d’apprentissage aux U-statistiques / Adapting machine learning methods to U-statistics

Colin, Igor 24 November 2016 (has links)
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.
2

Game theory and Optimization Methods for Decentralized Electric Systems / Méthodes d'Optimisation et de Théorie des Jeux Appliquées aux Systèmes Électriques Décentralisés

Jacquot, Paulin 05 December 2019 (has links)
Dans le contexte de transition vers un système électrique décentralisé et intelligent, nous abordons le problème de la gestion des flexibilités de consommation électriques. Nous développons différentes méthodes basées sur l'optimisation distribuée et la théorie des jeux.Nous commençons par adopter le point de vue d'un opérateur central en charge de la gestion des flexibilités de plusieurs agents. Nous présentons un algorithme distribué permettant le calcul des profils de consommations des agents optimaux pour l'opérateur.Cet algorithme garantit la confidentialité des agents~: les contraintes individuelles, ainsi que le profil individuel de consommation de chaque agent, ne sont jamais révélés à l'opérateur ni aux autres agents.Ensuite, nous adoptons dans un second modèle une vision plus décentralisée et considérons un cadre de théorie des jeux pour la gestion des flexibilités de consommation.Cette approche nous permet en particulier de modéliser les comportements stratégiques des consommateurs.Dans ce cadre, une classe de jeux adéquate est donnée par les jeux de congestion atomiques fractionnables.Nous obtenons plusieurs résultats théoriques concernant les équilibres de Nash dans cette classe de jeux, et nous quantifions l'efficacité de ces équilibres en établissant des bornes supérieures sur le prix de l'anarchie.Nous traitons la question du calcul décentralisé des équilibres de Nash dans ce contexte en étudiant les conditions et les vitesses de convergence des algorithmes de meilleure réponse et de gradient projeté.En pratique un opérateur peut faire face à un très grand nombre de joueurs, et calculer les équilibres d'un jeu de congestion dans ce cas est difficile.Afin de traiter ce problème, nous établissons des résultats sur l'approximation d'un équilibre dans les jeux de congestion et jeux agrégatifs avec un très grand nombre de joueurs et en présence de contraintes couplantes.Ces résultats, obtenus dans le cadre des inégalités variationnelles et sous certaines hypothèses de monotonie, peuvent être utilisés pour calculer un équilibre approché comme solution d'un problème de petite dimension.Toujours dans la perspective de modéliser un très grand nombre d'agents, nous considérons des jeux de congestion nonatomiques avec contraintes couplantes et avec une infinité de joueurs hétérogènes~: ce type de jeux apparaît lorsque les caractéristiques d'une population sont décrites par une fonction de distribution paramétrique.Sous certaines hypothèses de monotonie, nous prouvons que les équilibres de Wardrop de ces jeux, définis comme solutions d'une inégalité variationnelle de dimension infinie, peuvent être approchés par des équilibres de Wardrop symétriques de jeux annexes, solutions d'inégalités variationnelles de petite dimension.Enfin, nous considérons un modèle de jeu pour l'étude d'échanges d'électricité pair-à-pair au sein d'une communauté de consommateurs possédant des actifs de production électrique renouvelable.Nous étudions les équilibres généralisés du jeu obtenu, qui caractérisent les échanges possibles d'énergie et les consommations individuelles.Nous comparons ces équilibres avec la solution centralisée minimisant le coût social, et nous évaluons l'efficacité des équilibres via la notion de prix de l'anarchie. / In the context of smart grid and in the transition to decentralized electric systems, we address the problem of the management of distributed electric consumption flexibilities. We develop different methods based on distributed optimization and game theory approaches.We start by adopting the point of view of a centralized operator in charge of the management of flexibilities for several agents. We provide a distributed and privacy-preserving algorithm to compute consumption profiles for agents that are optimal for the operator.In the proposed method, the individual constraints as well as the individual consumption profile of each agent are never revealed to the operator or the other agents.Then, in a second model, we adopt a more decentralized vision and consider a game theoretic framework for the management of consumption flexibilities.This approach enables, in particular, to take into account the strategic behavior of consumers.Individual objectives are determined by dynamic billing mechanisms, which is motivated by the modeling of congestion effects occurring on time periods receiving a high electricity load from consumers.A relevant class of games in this framework is given by atomic splittable congestion games.We obtain several theoretical results on Nash equilibria for this class of games, and we quantify the efficiency of those equilibria by providing bounds on the price of anarchy.We address the question of the decentralized computation of equilibria in this context by studying the conditions and rates of convergence of the best response and projected gradients algorithms.In practice an operator may deal with a very large number of players, and evaluating the equilibria in a congestion game in this case will be difficult.To address this issue, we give approximation results on the equilibria in congestion and aggregative games with a very large number of players, in the presence of coupling constraints.These results, obtained in the framework of variational inequalities and under some monotonicity conditions, can be used to compute an approximate equilibrium, solution of a small dimension problem.In line with the idea of modeling large populations, we consider nonatomic congestion games with coupling constraints, with an infinity of heterogeneous players: these games arise when the characteristics of a population are described by a parametric density function.Under monotonicity hypotheses, we prove that Wardrop equilibria of such games, given as solutions of an infinite dimensional variational inequality, can be approximated by symmetric Wardrop equilibria of auxiliary games, solutions of low dimension variational inequalities.Again, those results can be the basis of tractable methods to compute an approximate Wardrop equilibrium in a nonatomic infinite-type congestion game.Last, we consider a game model for the study of decentralized peer-to-peer energy exchanges between a community of consumers with renewable production sources.We study the generalized equilibria in this game, which characterize the possible energy trades and associated individual consumptions.We compare the equilibria with the centralized solution minimizing the social cost, and evaluate the efficiency of equilibria through the price of anarchy.

Page generated in 0.1512 seconds