L'objet de cette thèse est l'analyse fine de méthodes de Monte Carlopar chaînes de Markov (MCMC) et la proposition de méthodologies nouvelles pour échantillonner une mesure de probabilité en grande dimension. Nos travaux s'articulent autour de trois grands sujets.Le premier thème que nous abordons est la convergence de chaînes de Markov en distance de Wasserstein. Nous établissons des bornes explicites de convergence géométrique et sous-géométrique. Nous appliquons ensuite ces résultats à l'étude d'algorithmes MCMC. Nous nous intéressons à une variante de l'algorithme de Metropolis-Langevin ajusté (MALA) pour lequel nous donnons des bornes explicites de convergence. Le deuxième algorithme MCMC que nous analysons est l'algorithme de Crank-Nicolson pré-conditionné, pour lequel nous montrerons une convergence sous-géométrique.Le second objet de cette thèse est l'étude de l'algorithme de Langevin unajusté (ULA). Nous nous intéressons tout d'abord à des bornes explicites en variation totale suivant différentes hypothèses sur le potentiel associé à la distribution cible. Notre étude traite le cas où le pas de discrétisation est maintenu constant mais aussi du cas d'une suite de pas tendant vers 0. Nous prêtons dans cette étude une attention toute particulière à la dépendance de l'algorithme en la dimension de l'espace d'état. Dans le cas où la densité est fortement convexe, nous établissons des bornes de convergence en distance de Wasserstein. Ces bornes nous permettent ensuite de déduire des bornes de convergence en variation totale qui sont plus précises que celles reportées précédemment sous des conditions plus faibles sur le potentiel. Le dernier sujet de cette thèse est l'étude des algorithmes de type Metropolis-Hastings par échelonnage optimal. Tout d'abord, nous étendons le résultat pionnier sur l'échelonnage optimal de l'algorithme de Metropolis à marche aléatoire aux densités cibles dérivables en moyenne Lp pour p ≥ 2. Ensuite, nous proposons de nouveaux algorithmes de type Metropolis-Hastings qui présentent un échelonnage optimal plus avantageux que celui de l'algorithme MALA. Enfin, nous analysons la stabilité et la convergence en variation totale de ces nouveaux algorithmes. / The subject of this thesis is the analysis of Markov Chain Monte Carlo (MCMC) methods and the development of new methodologies to sample from a high dimensional distribution. Our work is divided into three main topics. The first problem addressed in this manuscript is the convergence of Markov chains in Wasserstein distance. Geometric and sub-geometric convergence with explicit constants, are derived under appropriate conditions. These results are then applied to thestudy of MCMC algorithms. The first analyzed algorithm is an alternative scheme to the Metropolis Adjusted Langevin algorithm for which explicit geometric convergence bounds are established. The second method is the pre-Conditioned Crank-Nicolson algorithm. It is shown that under mild assumption, the Markov chain associated with thisalgorithm is sub-geometrically ergodic in an appropriated Wasserstein distance. The second topic of this thesis is the study of the Unadjusted Langevin algorithm (ULA). We are first interested in explicit convergence bounds in total variation under different kinds of assumption on the potential associated with the target distribution. In particular, we pay attention to the dependence of the algorithm on the dimension of the state space. The case of fixed step sizes as well as the case of nonincreasing sequences of step sizes are dealt with. When the target density is strongly log-concave, explicit bounds in Wasserstein distance are established. These results are then used to derived new bounds in the total variation distance which improve the one previously derived under weaker conditions on the target density.The last part tackles new optimal scaling results for Metropolis-Hastings type algorithms. First, we extend the pioneer result on the optimal scaling of the random walk Metropolis algorithm to target densities which are differentiable in Lp mean for p ≥ 2. Then, we derive new Metropolis-Hastings type algorithms which have a better optimal scaling compared the MALA algorithm. Finally, the stability and the convergence in total variation of these new algorithms are studied.

Nous nous intéressons à des résultats d'approximation et de régularité pour des solutions de viscosité d'équations elliptiques et paraboliques non-linéaires. Dans le chapitre 1, nous proposons, pour une classe générale d'équations elliptiques et paraboliques non-linéaires munies de conditions de Neumann inhomogènes, une interprétation de contrôle déterministe par des jeux répétés à deux personnes qui consiste à représenter la solution comme la limite de la suite des scores associés aux jeux. La condition de Neumann intervient par une pénalisation adaptée près de la frontière. En s'inspirant d'une approche abstraite proposée par Barles et Souganidis, nous prouvons la convergence en établissant des propriétés de monotonie, stabilité et consistance. Le chapitre 2 est consacré à des résultats de régularité sur les solutions d'équations paraboliques non-linéaires associés à un opérateur uniformément elliptique. Nous donnons une estimation de la mesure de Lebesgue de l'ensemble des points possédant un développement de Taylor quadratique global avec un contrôle sur la taille du terme cubique. Sous une hypothèse supplémentaire sur la régularité de la non-linéarité, nous en déduisons un résultat de régularité partielle höldérienne des solutions. Dans les chapitres 3 et 4, nous proposons une méthode générale pour obtenir des taux algébriques de convergence de solutions de schémas d'approximation vers la solution de viscosité sous l'hypothèse d'uniforme ellipticité de l'opérateur. Nous donnons un taux de convergence pour des schémas elliptiques obtenus par principe de programmation dynamique et nous prouvons un taux pour des schémas paraboliques par différences finies et implicites en temps. / In this thesis we study some approximation and regularity results for viscosity solutions of fully nonlinear elliptic and parabolic equations. In the first chapter, we consider a broad class of fully nonlinear elliptic and parabolic equations with inhomogeneous Neumann boundary conditions. We provide a deterministic control interpretation through two-person repeated games which represents the solution as the limit of the sequence of the scores associated to the games. The Neumann condition is modeled by a suitable penalization near the boundary. Inspiring by an abstract method of Barles and Souganidis, we prove the convergence of the score to the solution of the equation by establishing monotonicity, stability and consistency. The second chapter presents some regularity results about viscosity solutions of parabolic equations associated to a uniformly elliptic operator. First we obtain a Lebesgue measure estimate on the points having a quadratic Taylor expansion with a controlled cubic term. Under an additional assumption on the regularity of the nonlinearity, we deduce a partial regularity result about the Hölder regularity of these solutions. In the third and fourth chapters, we propose a general approach to determine algebraic rates of convergence of solutions of approximation schemes to the viscosity solution of fully nonlinear elliptic or parabolic equations under the assumption of uniform ellipticity of the operator. We first give the rate associated to the elliptic schemes derived by dynamic programming principles and proposed by Kohn and Serfaty. We then prove a rate of convergence for finite-difference schemes implicit in time associated to fully nonlinear parabolic equations.

Cette thèse est consacrée au développement de méthodes numériques pour la simulation de plaques et coques fissurées. Pour ce problème, les méthodes classiques sont basées sur la Méthode des Elements Finis (MEF). En raison de la présence d'une singularité en fond de fissure, la MEF souffre de plusieurs défauts. Son taux de convergence n'est pas optimal. De plus, en cas de propagation de la fissure, le domaine doit être remaillé. Une nouvelle méthode d'éléments finis, introduite en 1999 et baptisée XFEM, permet de s'affranchir de ces inconvénients. Dans cette méthode, la base éléments finis est enrichie par des fonctions de forme spécifiques qui représentent la séparation du matériau et la singularité de fond de fissure. Ainsi, domaine et fissure sont indépendants et le taux de convergence est optimal. Dans cette thèse, on développe deux formulations XFEM adaptées à un modèle de plaques minces. Ces méthodes ont pu être implémentées dans la bibliothèque d'éléments finis Getfem++, et testées sur des exemples où la solution exacte est connue. L'étude d'erreur montre que la méthode XFEM possède un taux de convergence optimal, alors que la MEF montre une convergence plus lente. L'autre contribution de cette thèse concerne le calcul de Facteurs d'Intensité de Contraintes (FIC) : ces grandeurs indiquent le risque de propagation de la fissure. Nous proposons deux méthodes de calcul originales, basées sur nos formulations XFEM. La première méthode utilise l'intégrale-J, et la deuxième fournit une estimation directe, sans post-traitement.

Les méthodes de Monte Carlo par chaîne de Markov (MCMC) sont des outils très populaires pour l’échantillonnage de lois de probabilité complexes et/ou en grandes dimensions. Étant donné leur facilité d’application, ces méthodes sont largement répandues dans plusieurs communautés scientifiques et bien certainement en statistique, particulièrement en analyse bayésienne. Depuis l’apparition de la première méthode MCMC en 1953, le nombre de ces algorithmes a considérablement augmenté et ce sujet continue d’être une aire de recherche active. Un nouvel algorithme MCMC avec ajustement directionnel a été récemment développé par Bédard et al. (IJSS, 9 :2008) et certaines de ses propriétés restent partiellement méconnues. L’objectif de ce mémoire est de tenter d’établir l’impact d’un paramètre clé de cette méthode sur la performance globale de l’approche. Un second objectif est de comparer cet algorithme à d’autres méthodes MCMC plus versatiles afin de juger de sa performance de façon relative. / Markov Chain Monte Carlo algorithms (MCMC) have become popular tools for sampling from complex and/or high dimensional probability distributions. Given their relative ease of implementation, these methods are frequently used in various scientific areas, particularly in Statistics and Bayesian analysis. The volume of such methods has risen considerably since the first MCMC algorithm described in 1953 and this area of research remains extremely active. A new MCMC algorithm using a directional adjustment has recently been described by Bédard et al. (IJSS, 9:2008) and some of its properties remain unknown. The objective of this thesis is to attempt determining the impact of a key parameter on the global performance of the algorithm. Moreover, another aim is to compare this new method to existing MCMC algorithms in order to evaluate its performance in a relative fashion.

Les méthodes de Monte Carlo par chaîne de Markov (MCMC) sont des outils très populaires pour l’échantillonnage de lois de probabilité complexes et/ou en grandes dimensions. Étant donné leur facilité d’application, ces méthodes sont largement répandues dans plusieurs communautés scientifiques et bien certainement en statistique, particulièrement en analyse bayésienne. Depuis l’apparition de la première méthode MCMC en 1953, le nombre de ces algorithmes a considérablement augmenté et ce sujet continue d’être une aire de recherche active. Un nouvel algorithme MCMC avec ajustement directionnel a été récemment développé par Bédard et al. (IJSS, 9 :2008) et certaines de ses propriétés restent partiellement méconnues. L’objectif de ce mémoire est de tenter d’établir l’impact d’un paramètre clé de cette méthode sur la performance globale de l’approche. Un second objectif est de comparer cet algorithme à d’autres méthodes MCMC plus versatiles afin de juger de sa performance de façon relative. / Markov Chain Monte Carlo algorithms (MCMC) have become popular tools for sampling from complex and/or high dimensional probability distributions. Given their relative ease of implementation, these methods are frequently used in various scientific areas, particularly in Statistics and Bayesian analysis. The volume of such methods has risen considerably since the first MCMC algorithm described in 1953 and this area of research remains extremely active. A new MCMC algorithm using a directional adjustment has recently been described by Bédard et al. (IJSS, 9:2008) and some of its properties remain unknown. The objective of this thesis is to attempt determining the impact of a key parameter on the global performance of the algorithm. Moreover, another aim is to compare this new method to existing MCMC algorithms in order to evaluate its performance in a relative fashion.

Ce mémoire de thèse est consacré à l’équation de Fokker-Planckpartial_ f=∆f+div(Ef).Il est subdivisé en deux parties :une partie linéaire et une partie non linéaire. Dans la partie linéaire on considère un champ de vecteur E(x) dépendant seulement de x. Cette partie est constituée des chapitres 3, 4 et 5. Dans le chapitre 3 on montre que l’opérateur linéaire Lf :=∆ f + div(E f ) est le générateur d’un semi-groupe fortement continu (SL(t))_{t≥0} dans tous les espaces L^p. On y établit également que le semi-groupe (SL(t))_{t≥0} est positif et ultracontractif. Dans le chapitre 4 nous montrons comment est qu’une décomposition adéquate de l’opérateur L permet d’établir certaines propriétés du semi-groupe (SL(t))_{t≥0} notamment sa bornitude. Le chapitre 5 est consacré à l’existence d’un état d’équilibre. De plus on y montre que cet état d’équi- libre est asymptotiquement stable. Dans la partie non linéaire on considère un champ de vecteur de la forme E(x,f) := x+nabla (a*f) ou a et f sont des fonctions assez régulières et * est l’opérateur de convolution. Cette parties est contituée des chapitre 6 et 7. Dans le chapitre 6 nous établissons que poura appartenant à W^{2,infini}_locl’équation de Fokker-Planck non linéaire admet une unique solution locale dans l’espace L^2_{K_alpha} (R^d). Dans le dernier chapitre nous montrons que le problème non linéaire admet une solution globale. De plus cette solution dépend continument des données. / This thesis is devoted to the Fokker-Planck équation partial_t f =∆f + div(E f).It is divided into two parts. The rst part deals with the linear problem. In this part we consider a vector E(x) depending only on x. It is composed of chapters 3, 4 and 5. In chapter 3 we prove that the linear operator Lf :=∆f + div(Ef ) is an in nitesimal generator of a strong continuous semigroup (SL(t))_{t≥0}. We establish also that (SL(t))_{t≥0} is positive and ultracontractive. In chapter 4 we show how an adequate decomposition of the linear operator L allows us to deduce interesting properties for the semigroup (SL(t))_{t≥0}. Indeed using this decomposition we prove that (SL(t))_{t≥0} is a bounded semigroup. In the last chapter of this part we establish that the linear Fokker-Planck admits a unique steady state. Moreover this stationary solution is asymptotically stable.In the nonlinear part we consider a vector eld of the form E(x, f ) := x +nabla (a *f ), where a and f are regular functions. It is composed of two chapters. In chapter 6 we establish that fora in W^{2,infini}_locthe nonlinear problem has a unique local solution in L^2_{K_alpha}(R^d); . To end this part we prove in chapter 7 that the nonlinear problem has a unique global solution in L^2_k(R^d). This solution depends continuously on the data.

L'idée centrale de cette thèse est de comprendre la notion d'accélération dans les algorithmes d'approximation stochastique. Plus précisément, nous tentons de répondre à la question suivante : Comment l'accélération apparaît-elle naturellement dans les algorithmes d'approximation stochastique ? Nous adoptons une approche de systèmes dynamiques et proposons de nouvelles méthodes accélérées pour l'apprentissage par différence temporelle (TD) avec approximation de fonction linéaire : Polyak TD(0) et Nesterov TD(0). Contrairement aux travaux antérieurs, nos méthodes ne reposent pas sur une conception des méthodes de TD comme des méthodes de descente de gradient. Nous étudions l'interaction entre l'accélération, la stabilité et la convergence des méthodes accélérées proposées en temps continu. Pour établir la convergence du système dynamique sous-jacent, nous analysons les modèles en temps continu des méthodes d'approximation stochastique accélérées proposées en dérivant la loi de conservation dans un système de coordonnées dilaté. Nous montrons que le système dynamique sous-jacent des algorithmes proposés converge à un rythme accéléré. Ce cadre nous fournit également des recommandations pour le choix des paramètres d'amortissement afin d'obtenir ce comportement convergent. Enfin, nous discrétisons ces ODE convergentes en utilisant deux schémas de discrétisation différents, Euler explicite et Euler symplectique, et nous analysons leurs performances sur de petites tâches de prédiction linéaire. / The central idea of this thesis is to understand the notion of acceleration in stochastic approximation algorithms. Specifically, we attempt to answer the question: How does acceleration naturally show up in SA algorithms? We adopt a dynamical systems approach and propose new accelerated methods for temporal difference (TD) learning with linear function approximation: Polyak TD(0) and Nesterov TD(0). In contrast to earlier works, our methods do not rely on viewing TD methods as gradient descent methods. We study the interplay between acceleration, stability, and convergence of the proposed accelerated methods in continuous time. To establish the convergence of the underlying dynamical system, we analyze continuous-time models of the proposed accelerated stochastic approximation methods by deriving the conservation law in a dilated coordinate system. We show that the underlying dynamical system of our proposed algorithms converges at an accelerated rate. This framework also provides us recommendations for the choice of the damping parameters to obtain this convergent behavior. Finally, we discretize these convergent ODEs using two different discretization schemes, explicit Euler, and symplectic Euler, and analyze their performance on small, linear prediction tasks.

Les familles exponentielles sont une classe de modèles omniprésente en statistique. D'une part, elle peut modéliser n'importe quel type de données. En fait la plupart des distributions communes en font partie : Gaussiennes, variables catégoriques, Poisson, Gamma, Wishart, Dirichlet. D'autre part elle est à la base des modèles linéaires généralisés (GLM), une classe de modèles fondamentale en apprentissage automatique. Enfin les mathématiques qui les sous-tendent sont souvent magnifiques, grâce à leur lien avec la dualité convexe et la transformée de Laplace. L'auteur de cette thèse a fréquemment été motivé par cette beauté. Dans cette thèse, nous faisons trois contributions à l'intersection de l'optimisation et des statistiques, qui tournent toutes autour de la famille exponentielle. La première contribution adapte et améliore un algorithme d'optimisation à variance réduite appelé ascension des coordonnées duales stochastique (SDCA), pour entraîner une classe particulière de GLM appelée champ aléatoire conditionnel (CRF). Les CRF sont un des piliers de la prédiction structurée. Les CRF étaient connus pour être difficiles à entraîner jusqu'à la découverte des technique d'optimisation à variance réduite. Notre version améliorée de SDCA obtient des performances favorables comparées à l'état de l'art antérieur et actuel. La deuxième contribution s'intéresse à la découverte causale. Les familles exponentielles sont fréquemment utilisées dans les modèles graphiques, et en particulier dans les modèles graphique causaux. Cette contribution mène l'enquête sur une conjecture spécifique qui a attiré l'attention dans de précédents travaux : les modèles causaux s'adaptent plus rapidement aux perturbations de l'environnement. Nos résultats, obtenus à partir de théorèmes d'optimisation, soutiennent cette hypothèse sous certaines conditions. Mais sous d'autre conditions, nos résultats contredisent cette hypothèse. Cela appelle à une précision de cette hypothèse, ou à une sophistication de notre notion de modèle causal. La troisième contribution s'intéresse à une propriété fondamentale des familles exponentielles. L'une des propriétés les plus séduisantes des familles exponentielles est la forme close de l'estimateur du maximum de vraisemblance (MLE), ou maximum a posteriori (MAP) pour un choix naturel de prior conjugué. Ces deux estimateurs sont utilisés presque partout, souvent sans même y penser. (Combien de fois calcule-t-on une moyenne et une variance pour des données en cloche sans penser au modèle Gaussien sous-jacent ?) Pourtant la littérature actuelle manque de résultats sur la convergence de ces modèles pour des tailles d'échantillons finis, lorsque l'on mesure la qualité de ces modèles avec la divergence de Kullback-Leibler (KL). Pourtant cette divergence est la mesure de différence standard en théorie de l'information. En établissant un parallèle avec l'optimisation, nous faisons quelques pas vers un tel résultat, et nous relevons quelques directions pouvant mener à des progrès, tant en statistiques qu'en optimisation. Ces trois contributions mettent des outil d'optimisation au service des statistiques dans les familles exponentielles : améliorer la vitesse d'apprentissage de GLM de prédiction structurée, caractériser la vitesse d'adaptation de modèles causaux, estimer la vitesse d'apprentissage de modèles omniprésents. En traçant des ponts entre statistiques et optimisation, cette thèse fait progresser notre maîtrise de méthodes fondamentales d'apprentissage automatique. / Exponential families are a ubiquitous class of models in statistics. On the one hand, they can model any data type. Actually, the most common distributions are exponential families: Gaussians, categorical, Poisson, Gamma, Wishart, or Dirichlet. On the other hand, they sit at the core of generalized linear models (GLM), a foundational class of models in machine learning. They are also supported by beautiful mathematics thanks to their connection with convex duality and the Laplace transform. This beauty is definitely responsible for the existence of this thesis. In this manuscript, we make three contributions at the intersection of optimization and statistics, all revolving around exponential families. The first contribution adapts and improves a variance reduction optimization algorithm called stochastic dual coordinate ascent (SDCA) to train a particular class of GLM called conditional random fields (CRF). CRF are one of the cornerstones of structured prediction. CRF were notoriously hard to train until the advent of variance reduction techniques, and our improved version of SDCA performs favorably compared to the previous state-of-the-art. The second contribution focuses on causal discovery. Exponential families are widely used in graphical models, and in particular in causal graphical models. This contribution investigates a specific conjecture that gained some traction in previous work: causal models adapt faster to perturbations of the environment. Using results from optimization, we find strong support for this assumption when the perturbation is coming from an intervention on a cause, and support against this assumption when perturbation is coming from an intervention on an effect. These pieces of evidence are calling for a refinement of the conjecture. The third contribution addresses a fundamental property of exponential families. One of the most appealing properties of exponential families is its closed-form maximum likelihood estimate (MLE) and maximum a posteriori (MAP) for a natural choice of conjugate prior. These two estimators are used almost everywhere, often unknowingly -- how often are mean and variance computed for bell-shaped data without thinking about the Gaussian model they underly? Nevertheless, literature to date lacks results on the finite sample convergence property of the information (Kulback-Leibler) divergence between these estimators and the true distribution. Drawing on a parallel with optimization, we take some steps towards such a result, and we highlight directions for progress both in statistics and optimization. These three contributions are all using tools from optimization at the service of statistics in exponential families: improving upon an algorithm to learn GLM, characterizing the adaptation speed of causal models, and estimating the learning speed of ubiquitous models. By tying together optimization and statistics, this thesis is taking a step towards a better understanding of the fundamentals of machine learning.