Search

Nowadays, graph-based semi-supervised learning (GB-SSL) is a fast-growing area of classifying nodes in a graph with an extremely low number of labelled nodes. However, the GB-SSL algorithms have two general limitations: the first is the memory/time complexity that arises in all state-of-the-art GB-SSL algorithms on extremely large graphs. In particular, the high memory consumption occurs in graph convolution networks and leads to Out of Memory (OOM) issues on GPU or RAM; the second one appears in all GB-SSL algorithms based on Laplacian regularization loss. This thesis' major contribution is divided into two parts in order to suggest strategies that would guarantee to avoid the restrictions mentioned above. In the first part of this thesis, we propose a novel linear algorithm called Markov-Batch Stochastic Approximation (MBSA) for solving Personalized PageRank. MBSA updates node batches and proposes a significantly better tradeoff between memory consumption and convergence rate for an optimal classification result than other linear models. Then, we propose a novel scaling graph convolution network, denoted as MBSA-NN, which embeds our linear MBSA. MBSA-NN avoids OOM issues and significantly reduces time and memory consumption on GPU and RAM. We applied MBSA-NN on several very large datasets, and we showed that it can handle graphs with more than 10M nodes and 2M of features in under one minute on one standard machine, including preprocessing, training and inference time. Furthermore, we show that it has significantly improved memory/time consumption and competitive accuracy concerning the latest best GB-SSL scaling algorithms. The second part of this thesis focuses on solutions to Laplacian regularization loss issues. For that reason, we propose a novel framework called Graph Diffusion & PCA (GDPCA). This framework combines a modified Principal Component Analysis with the classical supervised loss and Laplacian regularization loss. GDPCA allows handling the case where the adjacency matrix presents through Binary edges and avoids the Curse of dimensionality. Also, GDPCA can be applied to non-graph datasets, such as images, by constructing a similarity graph. Furthermore, we propose a framework that embeds PageRank SSL in a generative model (GenPR). GenPR joint training of nodes latent space representation and label spreading through the reweighted adjacency matrix by node similarities in the latent space. We demonstrate that a generative model can improve accuracy and reduce the number of iteration steps for PageRank SSL. Moreover, we show how to embed MBSA into the GenPR framework for providing the batch training regime of GenPR. Finally, we propose a flexible SSL framework based on stacking GDPCA and Zoetrope Genetic Programming algorithms into a novel framework: PaZoe. This self-labelling framework shows that graph-based and non-graph based algorithms jointly improve the quality of predictions and outperform each component taken alone. We also show that PaZoe outperforms state-of-the-art SSL algorithms on real datasets. Note that one of the datasets was generated in house, taking data from industrial graded equipment to mimic DC motors during operation.; De nos jours, l'apprentissage semi-supervisé basé sur les graphes (GB-SSL) est un domaine en plein essor pour classer les nœuds d'un graphe avec un nombre extrêmement faible de nœuds labélisés. Cependant, les algorithmes GB-SSL ont deux limites générales: la première est la complexité mémoire/temps qui se présente dans tous les algorithmes GB-SSL de pointe sur de larges graphes. En particulier, la forte consommation de mémoire se produit dans les réseaux de convolution de graphes et conduit à des problèmes d'OOM (Out of Memory) sur GPU ou RAM; la seconde apparaît dans tous les algorithmes GB-SSL basés sur la perte de régularisation Laplacienne. La contribution majeure de cette thèse est divisée en deux parties afin de proposer des stratégies qui garantiraient d'éviter les restrictions mentionnées ci-dessus. Dans la première partie de cette thèse, nous proposons un nouvel algorithme linéaire appelé Markov-Batch Stochastic Approximation (MBSA) pour résoudre le PageRank Personnalisé. MBSA met à jour des lots de nœuds et propose un compromis significativement meilleur que les autres modèles linéaires entre la consommation de mémoire et le taux de convergence pour un résultat de classification optimal. Ensuite, nous proposons un nouveau réseau de convolution de graphes à échelle, appelé MBSA-NN, qui intègre notre MBSA linéaire. Le MBSA-NN évite les problèmes d'OOM et réduit considérablement la consommation de temps et de mémoire sur GPU et RAM. Nous avons appliqué le MBSA-NN à plusieurs grands ensembles de données, et nous avons montré qu'il peut traiter des graphes avec plus de 10M nœuds et 2M de caractéristiques en une minute sur une machine standard, y compris le temps de prétraitement, d'apprentissage et d'inférence. De plus, nous montrons qu'il a une consommation mémoire/temps significativement améliorée et une précision compétitive par rapport aux meilleurs algorithmes de mise à l'échelle GB-SSL les plus récents.La deuxième partie de cette thèse se concentre sur les solutions aux problèmes de perte de régularisation du Laplacien. Pour cette raison, nous proposons un nouveau cadre appelé Graph Diffusion & PCA (GDPCA). Ce cadre combine une analyse en composantes principales modifiée avec la perte supervisée classique et la perte de régularisation laplacienne. GDPCA permet de traiter le cas où la matrice d'adjacence présente des Arêtes binaires et évite la Malédiction de la dimensionnalité. De plus, GDPCA peut être appliqué à des ensembles de données non graphiques, tels que des images, en construisant un graphe de similarité. En outre, nous proposons un cadre qui intègre PageRank SSL dans un modèle génératif (GenPR). GenPR joint l'entraînement de la représentation de l'espace latent des nœuds et la propagation des labels à travers la matrice d'adjacence repondérée par les similarités des nœuds dans l'espace latent. Nous démontrons qu'un modèle génératif peut améliorer la précision et réduire le nombre d'étapes d'itération pour PageRank SSL. En outre, nous montrons comment intégrer MBSA dans le cadre de GenPR pour fournir le régime de formation par lots de GenPR. Enfin, nous proposons un cadre SSL flexible basé sur l'empilement des algorithmes GDPCA et de Zoetrope Genetic Programming dans un nouveau cadre : PaZoe. Ce cadre d'auto-labélisation montre que les algorithmes basés sur les graphes et les algorithmes non basés sur les graphes améliorent conjointement la qualité des prédictions et sont plus performants que chaque composant pris séparément. Nous montrons également que PaZoe surpasse les algorithmes SSL de pointe sur des jeux de données réels. Notez que l'un des ensembles de données a été généré par nos soins, en prenant les données d'un équipement industriel classé pour imiter les moteurs à courant continu pendant leur fonctionnement.

This thesis is focused on the convergence analysis of some popular stochastic approximation methods in use in the machine learning community with applications to optimization and reinforcement learning.The first part of the thesis is devoted to a popular algorithm in deep learning called ADAM used for training neural networks. This variant of stochastic gradient descent is more generally useful for finding a local minimizer of a function. Assuming that the objective function is differentiable and non-convex, we establish the convergence of the iterates in the long run to the set of critical points under a stability condition in the constant stepsize regime. Then, we introduce a novel decreasing stepsize version of ADAM. Under mild assumptions, it is shown that the iterates are almost surely bounded and converge almost surely to critical points of the objective function. Finally, we analyze the fluctuations of the algorithm by means of a conditional central limit theorem.In the second part of the thesis, in the vanishing stepsizes regime, we generalize our convergence and fluctuations results to a stochastic optimization procedure unifying several variants of the stochastic gradient descent such as, among others, the stochastic heavy ball method, the Stochastic Nesterov Accelerated Gradient algorithm, and the widely used ADAM algorithm. We conclude this second part by an avoidance of traps result establishing the non-convergence of the general algorithm to undesired critical points, such as local maxima or saddle points. Here, the main ingredient is a new avoidance of traps result for non-autonomous settings, which is of independent interest.Finally, the last part of this thesis which is independent from the two previous parts, is concerned with the analysis of a stochastic approximation algorithm for reinforcement learning. In this last part, we propose an analysis of an online target-based actor-critic algorithm with linear function approximation in the discounted reward setting. Our algorithm uses three different timescales: one for the actor and two for the critic. Instead of using the standard single timescale temporal difference (TD) learning algorithm as a critic, we use a two timescales target-based version of TD learning closely inspired from practical actor-critic algorithms implementing target networks. First, we establish asymptotic convergence results for both the critic and the actor under Markovian sampling. Then, we provide a finite-time analysis showing the impact of incorporating a target network into actor-critic methods.; Cette thèse est centrée autour de l'analyse de convergence de certains algorithmes d'approximation stochastiques utilisés en machine learning appliqués à l'optimisation et à l'apprentissage par renforcement. La première partie de la thèse est dédiée à un célèbre algorithme en apprentissage profond appelé ADAM, utilisé pour entraîner des réseaux de neurones. Cette célèbre variante de la descente de gradient stochastique est plus généralement utilisée pour la recherche d'un minimiseur local d'une fonction. En supposant que la fonction objective est différentiable et non convexe, nous établissons la convergence des itérées au temps long vers l'ensemble des points critiques sous une hypothèse de stabilité dans le régime des pas constants. Ensuite, nous introduisons une nouvelle variante de l'algorithme ADAM à pas décroissants. Nous montrons alors sous certaines hypothèses réalistes que les itérées sont presque sûrement bornées et convergent presque sûrement vers des points critiques de la fonction objective. Enfin, nous analysons les fluctuations de l'algorithme par le truchement d'un théorème central limite conditionnel. Dans la deuxième partie de cette thèse, dans le régime des pas décroissants, nous généralisons nos résultats de convergence et de fluctuations à une procédure d'optimisation stochastique unifiant plusieurs variantes de descente de gradient stochastique comme la méthode de la boule pesante, l'algorithme stochastique de Nesterov accéléré ou encore le célèbre algorithme ADAM, parmi d'autres. Nous concluons cette partie par un résultat d'évitement de pièges qui établit la non convergence de l'algorithme général vers des points critiques indésirables comme les maxima locaux ou les points-selles. Ici, le principal ingrédient est un nouveau résultat indépendant d'évitement de pièges pour un contexte non-autonome. Enfin, la dernière partie de cette thèse qui est indépendante des deux premières parties est dédiée à l'analyse d'un algorithme d'approximation stochastique pour l'apprentissage par renforcement. Dans cette dernière partie, dans le cadre des processus décisionnels de Markov avec critère de récompense gamma-pondéré, nous proposons une analyse d'un algorithme acteur-critique en ligne intégrant un réseau cible et avec approximation de fonction linéraire. Notre algorithme utilise trois échelles de temps distinctes: une échelle pour l'acteur et deux autres pour la critique. Au lieu d'utiliser l'algorithme de différence temporelle (TD) standard à une échelle de temps, nous utilisons une version de l'algorithme TD à deux échelles de temps intégrant un réseau cible inspiré des algorithmes acteur-critique utilisés en pratique. Tout d'abord, nous établissons des résultats de convergence pour la critique et l'acteur sous échantillonnage Markovien. Ensuite, nous menons une analyse à temps fini montrant l'impact de l'utilisation d'un réseau cible sur les méthodes acteur-critique.

L’algorithme EM (Dempster et al., 1977) permet de construire une séquence d’estimateurs qui converge vers l’estimateur de vraisemblance maximale pour des modèles à données manquantes pour lesquels l’estimateur du maximum de vraisemblance n’est pas calculable. Cet algorithme est remarquable compte tenu de ses nombreuses applications en apprentissage statistique. Toutefois, il peut avoir un lourd coût computationnel. Les auteurs Cappé et Moulines (2009) ont proposé une version en ligne de cet algorithme pour les modèles appartenant à la famille exponentielle qui permet de faire des gains d’efficacité computationnelle importants en présence de grands jeux de données. Cependant, le calcul de l’espérance a posteriori de la statistique exhaustive, qui est nécessaire dans la version de Cappé et Moulines (2009), est rarement possible pour des modèles complexes et/ou lorsque la dimension des données manquantes est grande. On doit alors la remplacer par un estimateur. Plusieurs questions se présentent naturellement : les résultats de convergence de l’algorithme initial restent-ils valides lorsqu’on remplace l’espérance par un estimateur ? En particulier, que dire de la normalité asymptotique de la séquence des estimateurs ainsi créés, de la variance asymptotique et de la vitesse de convergence ? Comment la variance de l’estimateur de l’espérance se reflète-t-elle sur la variance asymptotique de l’estimateur EM? Peut-on travailler avec des estimateurs de type Monte-Carlo ou MCMC? Peut-on emprunter des outils populaires de réduction de variance comme les variables de contrôle ? Ces questions seront étudiées à l’aide d’exemples de modèles à variables latentes. Les contributions principales de ce mémoire sont une présentation unifiée des algorithmes EM d’approximation stochastique, une illustration de l’impact au niveau de la variance lorsque l’espérance a posteriori est estimée dans les algorithmes EM en ligne et l’introduction d’algorithmes EM en ligne permettant de réduire la variance supplémentaire occasionnée par l’estimation de l’espérance a posteriori., The EM algorithm Dempster et al. (1977) yields a sequence of estimators that converges to the maximum likelihood estimator for missing data models whose maximum likelihood estimator is not directly tractable. The EM algorithm is remarkable given its numerous applications in statistical learning. However, it may suffer from its computational cost. Cappé and Moulines (2009) proposed an online version of the algorithm in models whose likelihood belongs to the exponential family that provides an upgrade in computational efficiency in large data sets. However, the conditional expected value of the sufficient statistic is often intractable for complex models and/or when the missing data is of a high dimension. In those cases, it is replaced by an estimator. Many questions then arise naturally: do the convergence results pertaining to the initial estimator hold when the expected value is substituted by an estimator? In particular, does the asymptotic normality property remain in this case? How does the variance of the estimator of the expected value affect the asymptotic variance of the EM estimator? Are Monte-Carlo and MCMC estimators suitable in this situation? Could variance reduction tools such as control variates provide variance relief? These questions will be tackled by the means of examples containing latent data models. This master’s thesis’ main contributions are the presentation of a unified framework for stochastic approximation EM algorithms, an illustration of the impact that the estimation of the conditional expected value has on the variance and the introduction of online EM algorithms which reduce the additional variance stemming from the estimation of the conditional expected value.

Machine Learning has received a lot of attention during the last two decades both from industry for data-driven decision problems and from the scientific community in general. This recent attention is certainly due to its ability to efficiently solve a wide class of high-dimensional problems with fast and easy- to-implement algorithms. What is the type of problems machine learning tackles ? Generally speaking, answering this question requires to divide it into two distinct topics: supervised and unsupervised learning. The first one aims to infer relationships between a phenomenon one seeks to predict and “explanatory” variables leveraging supervised information. On the contrary, the second one does not need any supervision and aims at extracting some structure, information or significant features of the variables.These two main directions find an echo in this thesis. On the one hand, the supervised learning part theoretically studies the cornerstone of all optimization techniques for these problems: stochastic gradient methods. For their versatility, they are the workhorses of the recent success of ML. However, despite their simplicity, their efficiency is not yet fully understood. Establishing some properties of this algorithm is one of the two important questions of this thesis. On the other hand, the part concerned with unsupervised learning is more problem-specific: we design an algorithm to find reduced order models in physically-based dynamics addressing an crucial question in computational statistical physics (also called molecular dynamics).; L’apprentissage automatique a reçu beaucoup d’attention au cours des deux dernières décennies, à la fois de la part de l’industrie pour des problèmes de décision basés sur des données et de la communauté scientifique en général. Cette attention récente est certainement due à sa capacité à résoudre efficacement une large classe de problèmes en grande dimension grâce à des algorithmes rapides et faciles à mettre en oeuvre. Plus spécifiquement, quel est le type de problèmes abordés par l’apprentissage automatique ? D’une manière générale, répondre à cette question nécessite de le diviser en deux thèmes distincts: l’apprentissage supervisé et l’apprentissage non supervisé. Le premier vise à déduire des relations entre un phénomène que l’on cherche à prédire et des variables “explicatives” exploitant des informations qui ont fait l’objet d’une supervision. Au contraire, la seconde ne nécessite aucune supervision et son but principal est de parvenir à extraire une structure, des informations ou des caractéristiques importantes relative aux données.Ces deux axes principaux trouvent un écho dans cette thèse. Dans un premier temps, la partie concernant l’apprentissage supervisé étudie théoriquement la pierre angulaire de toutes les techniques d’optimisation liées à ces problèmes: les méthodes de gradient stochastique. Grâce à leur polyvalence, elles participent largement au récent succès de l’apprentissage. Cependant, malgré leur simplicité, leur efficacité n’est pas encore pleinement comprise. L’étude de certaines propriétés de cet algorithme est l’une des deux questions importantes de cette thèse. Dand un second temps, la partie consacrée à l’apprentissage non supervisé est liée à un problème plus spécifique : nous concevons dans cette étude un algorithme pour trouver des modèles réduits pour des dynamiques empruntées à la physique. Cette partie aborde une question cruciale en physique statistique computationnelle (également appelée dynamique moléculaire).Même si les deux problèmes sont de nature différente, ces deux directions partagent une caractéristique commune : elles tirent parti de l’utilisation d’espaces à noyau reproduisant, qui possèdent deux propriétés essentielles : (i) ils s’adaptent naturellement au cadre stochastique tout en préservant une certaine efficacité numérique, (ii) ils montrent une grande expressivité en tant que classe de fonctions de test.

In an online setting, where data arrives continuously, we want to update the parameters of a "batch" score constructed with an ensemble method. To do so, we use stochastic approximation processes, the convergence of which has been theoretically established by the authors, so that parameter estimates can be updated when new observations are taken into account without the need to store all the data obtained previously. Here we study empirically the convergence of the online score to the "batch" score, using different datasets from which data streams are simulated and using different types of processes., Dans un contexte en ligne où des données arrivent de façon continue, on souhaite actualiser les paramètres d'un score "batch" construit à l'aide d'une méthode d'ensemble. On utilise pour cela des processus d'approximation stochastique, dont la convergence a été établie théoriquement par les auteurs, permettant d'actualiser les estimations des paramètres lors de la prise en compte de nouvelles observations sans avoir à conserver toutes les données obtenues précédemment. Nous étudions ici empiriquement la convergence du score en ligne vers le score "batch", en utilisant différents jeux de données a partir desquels on simule des flux de données et différents types de processus.

We widened the scope of the 0ja's eigenvector stochastic approximation process proving its almost sure convergence under more general assumptions. We study the application to generalized canonical correlation analysis (gCCA) of a random vector \imath{Z} in the case of big or streaming data. The general components of gCCA are principal components of PCA of Z with a particular metric \imath{M}. We define stochastic approximation processses using at each step all observations up to this step without storing them instead of the new observations at this step only, to estimate simultaneously the metric \imath{M}, the general components of gCCA and the corresponding eigenvalues., Nous avons étendu le domaine d'application du processus d'approximation stochastique de vecteurs propres de Oja en en démontrant la convergence presque sûre sous des hypothèses plus générales. Nous étudions l'application à l'analyse canonique généralisée (ACG) d'un vecteur aléatoire \imath{Z} dans le cas de données massives ou en flux. Les composantes générales de l'ACG sont les composantes principales de l'ACP de \imath{Z} avec une métrique particulière \imath{M}. Nous définissons des processus d'approximation stochastique où l'on peut utiliser à chaque étape toutes les observations de \imath{Z} effectuées jusqu'à cette étape sans avoir à les stocker au lieu uniquement des nouvelles observations à ce pas, pour estimer simultanément la métrique \imath{M}, les composantes générales de l'ACG et les valeurs propres associées.

Machine Learning has received a lot of attention during the last two decades, both from industry for data-driven decision problems and from the scientific community in general. This recent attention is certainly due to its ability to efficiently solve a wide class of high-dimensional problems with fast and easy- to-implement algorithms. What is the type of problems machine learning tackles ? Generally speaking, answering this question requires to divide it into two distinct topics: supervised and unsupervised learning. The first one aims to infer relationships between a phenomenon one seeks to predict and "explanatory" variables leveraging supervised information. On the contrary, the second one does not need any supervision and aims at extracting some structure, information or significant features of the variables. These two main directions find an echo in this thesis. On the one hand, the supervised learning part theoretically studies the cornerstone of all optimization techniques for these problems: stochastic gradient methods. For their versatility, they are the workhorses of the recent success of ML. However, despite their simplicity, their efficiency is not yet fully understood. Establishing some properties of this algorithm is one of the two important questions of this thesis. On the other hand, the part concerned with unsupervised learning is more problem-specific: we design an algorithm to find reduced order models in physically-based dynamics addressing a crucial question in computational statistical physics (also called molecular dynamics)., L'apprentissage automatique a reçu beaucoup d'attention au cours des deux dernières décennies, à la fois de la part de l'industrie pour des problèmes de décision basés sur des données et de la communauté scientifique en général. Cette attention récente est certainement due à sa capacité à résoudre efficacement une large classe de problèmes en grande dimension grâce à des algorithmes rapides et faciles à mettre en œuvre. Plus spécifiquement, quel est le type de problèmes abordés par l'apprentissage automatique ? D'une manière générale, répondre à cette question nécessite de le diviser en deux thèmes distincts : l'apprentissage supervisé et l'apprentissage non supervisé. Le premier vise à déduire des relations entre un phénomène que l'on cherche à prédire et des variables "explicatives" exploitant des informations qui ont fait l'objet d'une supervision. Au contraire, la seconde ne nécessite aucune supervision et son but principal est de parvenir à extraire une structure, des informations ou des caractéristiques importantes relative aux données. Ces deux axes principaux trouvent un écho dans cette thèse. Dans un premier temps, la partie concernant l'apprentissage supervisé étudie théoriquement la pierre angulaire de toutes les techniques d'optimisation liées à ces problèmes : les méthodes de gradient stochastique. Grâce à leur polyvalence, elles participent largement au récent succès de l'apprentissage. Cependant, malgré leur simplicité, leur efficacité n'est pas encore pleinement comprise. L'étude de certaines propriétés de cet algorithme est l'une des deux questions importantes de cette thèse. Dans un second temps, la partie consacrée à l'apprentissage non supervisé est liée à un problème plus spécifique : nous concevons dans cette étude un algorithme pour trouver des modèles réduits pour des dynamiques empruntées à la physique. Cette partie aborde une question cruciale en physique statistique computationnelle (également appelée dynamique moléculaire).

Many problems in machine learning pertain to tackling the minimization of a possibly non-convex and non-smooth function defined on a Many problems in machine learning pertain to tackling the minimization of a possibly non-convex and non-smooth function defined on a Euclidean space.Examples include topic models, neural networks or sparse logistic regression.Optimization methods, used to solve those problems, have been widely studied in the literature for convex objective functions and are extensively used in practice.However, recent breakthroughs in statistical modeling, such as deep learning, coupled with an explosion of data samples, require improvements of non-convex optimization procedure for large datasets.This thesis is an attempt to address those two challenges by developing algorithms with cheaper updates, ideally independent of the number of samples, and improving the theoretical understanding of non-convex optimization that remains rather limited.In this manuscript, we are interested in the minimization of such objective functions for latent data models, ie, when the data is partially observed which includes the conventional sense of missing data but is much broader than that.In the first part, we consider the minimization of a (possibly) non-convex and non-smooth objective function using incremental and online updates.To that end, we propose several algorithms exploiting the latent structure to efficiently optimize the objective and illustrate our findings with numerous applications.In the second part, we focus on the maximization of non-convex likelihood using the EM algorithm and its stochastic variants.We analyze several faster and cheaper algorithms and propose two new variants aiming at speeding the convergence of the estimated parameters., De nombreux problèmes en Apprentissage Statistique consistent à minimiser une fonction non convexe et non lisse définie sur un espace euclidien. Par exemple, les problèmes de maximisation de la vraisemblance et la minimisation du risque empirique en font partie.Les algorithmes d'optimisation utilisés pour résoudre ce genre de problèmes ont été largement étudié pour des fonctions convexes et grandement utilisés en pratique.Cependant, l'accrudescence du nombre d'observation dans l'évaluation de ce risque empirique ajoutée à l'utilisation de fonctions de perte de plus en plus sophistiquées représentent des obstacles.Ces obstacles requièrent d'améliorer les algorithmes existants avec des mis à jour moins coûteuses, idéalement indépendantes du nombre d'observations, et d'en garantir le comportement théorique sous des hypothèses moins restrictives, telles que la non convexité de la fonction à optimiser.Dans ce manuscrit de thèse, nous nous intéressons à la minimisation de fonctions objectives pour des modèles à données latentes, ie, lorsque les données sont partiellement observées ce qui inclut le sens conventionnel des données manquantes mais est un terme plus général que cela.Dans une première partie, nous considérons la minimisation d'une fonction (possiblement) non convexe et non lisse en utilisant des mises à jour incrémentales et en ligne. Nous proposons et analysons plusieurs algorithmes à travers quelques applications.Dans une seconde partie, nous nous concentrons sur le problème de maximisation de vraisemblance non convexe en ayant recourt à l'algorithme EM et ses variantes stochastiques. Nous en analysons plusieurs versions rapides et moins coûteuses et nous proposons deux nouveaux algorithmes du type EM dans le but d'accélérer la convergence des paramètres estimés.

This thesis mainly studies optimization algorithms. Programming problems arising in signal processing and machine learning are composite in many cases, i.e they exhibit constraints and non smooth regularization terms. Proximal methods are known to be efficient to solve such problems. However, in modern applications of data sciences, functions to be minimized are often represented as statistical expectations, whose evaluation is intractable. This cover the case of online learning, big data problems and distributed computation problems. To solve this problems, we study in this thesis proximal stochastic methods, that generalize proximal algorithms to the case of cost functions written as expectations. Stochastic proximal methods are first studied with a constant step size, using stochastic approximation techniques. More precisely, the Ordinary Differential Equation method is adapted to the case of differential inclusions. In order to study the asymptotic behavior of the algorithms, the stability of the sequences of iterates (seen as Markov chains) is studied. Then, generalizations of the stochastic proximal gradient algorithm with decreasing step sizes are designed to solve composite problems. Every quantities used to define the optimization problem are written as expectations. This include a primal dual algorithm to solve regularized and linearly constrained problems and an optimization over large graphs algorithm., Cette thèse porte essentiellement sur l'étude d'algorithmes d'optimisation. Les problèmes de programmation intervenant en apprentissage automatique ou en traitement du signal sont dans beaucoup de cas composites, c'est-à-dire qu'ils sont contraints ou régularisés par des termes non lisses. Les méthodes proximales sont une classe d'algorithmes très efficaces pour résoudre de tels problèmes. Cependant, dans les applications modernes de sciences des données, les fonctions à minimiser se représentent souvent comme une espérance mathématique, difficile ou impossible à évaluer. C'est le cas dans les problèmes d'apprentissage en ligne, dans les problèmes mettant en jeu un grand nombre de données ou dans les problèmes de calcul distribué. Pour résoudre ceux-ci, nous étudions dans cette thèse des méthodes proximales stochastiques, qui adaptent les algorithmes proximaux aux cas de fonctions écrites comme une espérance. Les méthodes proximales stochastiques sont d'abord étudiées à pas constant, en utilisant des techniques d'approximation stochastique. Plus précisément, la méthode de l'Equation Differentielle Ordinaire est adaptée au cas d'inclusions differentielles. Afin d'établir le comportement asymptotique des algorithmes, la stabilité des suites d'itérés (vues comme des chaines de Markov) est étudiée. Ensuite, des généralisations de l'algorithme du gradient proximal stochastique à pas décroissant sont mises au point pour resoudre des problèmes composites. Toutes les grandeurs qui permettent de décrire les problèmes à résoudre s'écrivent comme une espérance. Cela inclut un algorithme primal dual pour des problèmes régularisés et linéairement contraints ainsi qu'un algorithme d'optimisation sur les grands graphes.

In order to understand the global functioning principals of biological systems, system biology approach aims to integrate the methodologies used in the conception and the analysis of complex technological systems, within the biology. This PhD thesis fits into the system biology framework and in particular the extension of the already existing method Resource Balance Analysis (RBA). We aim in this PhD thesis to improve the predictive power of this method by introducing more complex model. However, this new model should respect a good trade-off between the representativity of the model and its efficient numerical computation. This PhD thesis is decomposed into two major parts. The first part aims the integration of the metabolic network inherent thermodynamical and kinetic aspects. The second part aims the comprehension of the impact of enzyme production stochastic aspect on the bacteria growth. Numerical methods are elaborated to solve the obtained models in both deterministic and stochastic cases .; L’approche de la biologie des systèmes vise à intégrer les méthodologies appliquées dans la conception et l’analyse des systèmes technologiques complexes, au sein de la biologie afin de comprendre les principes de fonctionnement globaux des systèmes biologiques. La thèse s’inscrit dans le cadre de la biologie des systèmes et en particulier dans la prolongation d’une méthode issue de ce cadre : la méthode Ressource Balance Analysis (RBA). Nous visons dans cette thèse à augmenter le pouvoir prédictif de la méthode via un travail de modélisation tout en gardant un bon compromis entre représentativité des modèles issus de ce cadre et leur résolution numérique efficace. La thèse se décompose en deux grandes parties : la première partie vise à intégrer les aspects thermodynamiques et cinétiques inhérents aux réseaux métaboliques. La deuxième partie vise à comprendre l’impact de l’aspect stochastique de la production des enzymes sur la croissance de la bactérie. Des méthodes numériques ont été élaborées pour la résolution des modèles ainsi établis dans les deux cas déterministe et stochastique

In order to understand the global functioning principals of biological systems, system biology approach aims to integrate the methodologies used in the conception and the analysis of complex technological systems, within the biology. This PhD thesis fits into the system biology framework and in particular the extension of the already existing method Resource Balance Analysis (RBA). We aim in this PhD thesis to improve the predictive power of this method by introducing more complex model. However, this new model should respect a good trade-off between the representativity of the model and its efficient numerical computation. This PhD thesis is decomposed into two major parts. The first part aims the integration of the metabolic network inherent thermodynamical and kinetic aspects. The second part aims the comprehension of the impact of enzyme production stochastic aspect on the bacteria growth. Numerical methods are elaborated to solve the obtained models in both deterministic and stochastic cases ., L’approche de la biologie des systèmes vise à intégrer les méthodologies appliquées dans la conception et l’analyse des systèmes technologiques complexes, au sein de la biologie afin de comprendre les principes de fonctionnement globaux des systèmes biologiques. La thèse s’inscrit dans le cadre de la biologie des systèmes et en particulier dans la prolongation d’une méthode issue de ce cadre : la méthode Ressource Balance Analysis (RBA). Nous visons dans cette thèse à augmenter le pouvoir prédictif de la méthode via un travail de modélisation tout en gardant un bon compromis entre représentativité des modèles issus de ce cadre et leur résolution numérique efficace. La thèse se décompose en deux grandes parties : la première partie vise à intégrer les aspects thermodynamiques et cinétiques inhérents aux réseaux métaboliques. La deuxième partie vise à comprendre l’impact de l’aspect stochastique de la production des enzymes sur la croissance de la bactérie. Des méthodes numériques ont été élaborées pour la résolution des modèles ainsi établis dans les deux cas déterministe et stochastique

This Ph.D. is dedicated to the application of the game theory for the understanding of users behaviour in Online Social Networks. The three main questions of this Ph.D. are: " How to maximize contents popularity ? "; " How to model the distribution of messages across sources and topics in OSNs ? "; " How to minimize gossip propagation and how to maximize contents diversity? ". After a survey concerning the research made about the previous problematics in chapter 1, we propose to study a competition over visibility in chapter 2. In chapter 3, we model and provide insight concerning the posting behaviour of publishers in OSNs by using the stochastic approximation framework. In chapter 4, it is a popularity competition which is described by using a differential game formulation. The chapter 5 is dedicated to the formulation of two convex optimization problems in the context of Online Social Networks. Finally conclusions and perspectives are given in chapter 6.; Cette thèse utilise la théorie des jeux pour comprendre le comportement des usagers dans les réseaux sociaux. Trois problématiques y sont abordées: "Comment maximiser la popularité des contenus postés dans les réseaux sociaux?";" Comment modéliser la répartition des messages par sujets?";"Comment minimiser la propagation d’une rumeur et maximiser la diversité des contenus postés?". Après un état de l’art concernant ces questions développé dans le chapitre 1, ce travail traite, dans le chapitre 2, de la manière d’aborder l’environnement compétitif pour accroître la visibilité. Dans le chapitre 3, c’est le comportement des usagers qui est modélisé, en terme de nombre de messages postés, en utilisant la théorie des approximations stochastiques. Dans le chapitre 4, c’est une compétition pour être populaire qui est étudiée. Le chapitre 5 propose de formuler deux problèmes d’optimisation convexes dans le contexte des réseaux sociaux en ligne. Finalement, le chapitre 6 conclue ce manuscrit.

Faults are discontinuities in rock volumes that affect mechanical properties and flow paths of hydrocarbon reservoirs. However, subsurface modeling remains limited by the incompleteness and resolution of available data, so that uncertainties remain on the geometry and the connectivity of fault networks. To assess fault network uncertainties, several stochastic approaches have been introduced in the literature. These methods generate a set of possible fault models conditioned by reservoir data. In this thesis, we investigate two main conditioning strategies of stochastic fault modeling methods. The first one takes into account the observations of the fault absence, for instance, as indicated by seismic reflector continuity. To do this, the reservoir volume is divided into two sub-volumes delimited by a 3D envelope surface: (1) a volume where no faults occur, and (2) a potentially-faulted volume. Then, faults are simulated and optimized in such a way as to be entirely confined to the potentially-faulted volume. The second presented strategy deals with the uncertainties related to the seismic interpretation of fault segmentation. It generates a set of fine-scale segmented faults from a larger-scale and continuous interpretation of the fault. The method uses the orientation variations of the continuous fault to subdivide it into several possible fault segments. The effects of the different segmentation configurations on flow simulations are studied; Les failles sont des zones de rupture de la roche qui affectent le comportement mécanique et fluide des réservoirs. De nombreuses incertitudes existent sur la géométrie et la topologie des réseaux de failles dues à la résolution et la qualité des données, mais aussi aux lacunes d'informations. Des approches stochastiques ont été utilisées dans la littérature pour gérer les incertitudes structurales. Ces méthodes génèrent un ensemble de modèles possibles de failles conditionné par les données disponibles. Dans cette thèse, nous explorons deux principales stratégies de conditionnement de la modélisation stochastique de réseaux de failles. La première stratégie élaborée permet de prendre en compte des observations d'absences de failles sur des données, par exemple, des zones où les réflecteurs sismiques sont continus. Dans ce but, le réservoir est divisé en deux sous-volumes délimités par une enveloppe surfacique 3D : un volume non-faillé et un volume potentiellement-faillé. Les surfaces de failles sont ensuite simulées et optimisées de manière à être entièrement positionnées dans la zone identifiée comme potentiellement faillée. La seconde stratégie de conditionnement présentée dans cette thèse gère les incertitudes relatives à l'interprétation de la segmentation des failles. La méthode génère un ensemble de modèles de segments de failles en-échelon à partir d'une interprétation continue à plus grande échelle d'une faille segmentée. La méthode utilise les variations d'orientations de la faille segmentée pour identifier la position des différents segments la composant. L'impact des différentes configurations de segmentation sur les simulations d'écoulements est étudié

Faults are discontinuities in rock volumes that affect mechanical properties and flow paths of hydrocarbon reservoirs. However, subsurface modeling remains limited by the incompleteness and resolution of available data, so that uncertainties remain on the geometry and the connectivity of fault networks. To assess fault network uncertainties, several stochastic approaches have been introduced in the literature. These methods generate a set of possible fault models conditioned by reservoir data. In this thesis, we investigate two main conditioning strategies of stochastic fault modeling methods. The first one takes into account the observations of the fault absence, for instance, as indicated by seismic reflector continuity. To do this, the reservoir volume is divided into two sub-volumes delimited by a 3D envelope surface: (1) a volume where no faults occur, and (2) a potentially-faulted volume. Then, faults are simulated and optimized in such a way as to be entirely confined to the potentially-faulted volume. The second presented strategy deals with the uncertainties related to the seismic interpretation of fault segmentation. It generates a set of fine-scale segmented faults from a larger-scale and continuous interpretation of the fault. The method uses the orientation variations of the continuous fault to subdivide it into several possible fault segments. The effects of the different segmentation configurations on flow simulations are studied, Les failles sont des zones de rupture de la roche qui affectent le comportement mécanique et fluide des réservoirs. De nombreuses incertitudes existent sur la géométrie et la topologie des réseaux de failles dues à la résolution et la qualité des données, mais aussi aux lacunes d'informations. Des approches stochastiques ont été utilisées dans la littérature pour gérer les incertitudes structurales. Ces méthodes génèrent un ensemble de modèles possibles de failles conditionné par les données disponibles. Dans cette thèse, nous explorons deux principales stratégies de conditionnement de la modélisation stochastique de réseaux de failles. La première stratégie élaborée permet de prendre en compte des observations d'absences de failles sur des données, par exemple, des zones où les réflecteurs sismiques sont continus. Dans ce but, le réservoir est divisé en deux sous-volumes délimités par une enveloppe surfacique 3D : un volume non-faillé et un volume potentiellement-faillé. Les surfaces de failles sont ensuite simulées et optimisées de manière à être entièrement positionnées dans la zone identifiée comme potentiellement faillée. La seconde stratégie de conditionnement présentée dans cette thèse gère les incertitudes relatives à l'interprétation de la segmentation des failles. La méthode génère un ensemble de modèles de segments de failles en-échelon à partir d'une interprétation continue à plus grande échelle d'une faille segmentée. La méthode utilise les variations d'orientations de la faille segmentée pour identifier la position des différents segments la composant. L'impact des différentes configurations de segmentation sur les simulations d'écoulements est étudié

The mobile network of Orange in France comprises more than 100 000 2G, 3G and 4G antennas with severalfrequency bands, not to mention many femto-cells for deep-indoor coverage. These numbers will continue toincrease in order to address the customers’ exponentially increasing need for mobile data. This is an illustrationof the challenge faced by the mobile operators for operating such a complex network with low OperationalExpenditures (OPEX) in order to stay competitive. This thesis is about leveraging the Self-Organizing Network(SON) concept to reduce this complexity by automating repetitive or complex tasks. We specifically proposeautomatic optimization algorithms for scenarios related to network densification using either small cells orActive Antenna Systems (AASs) used for Vertical Sectorization (VeSn), Virtual Sectorization (ViSn) and multilevelbeamforming. Problems such as load balancing with limited-capacity backhaul and interference coordination eitherin time-domain (eICIC) or in frequency-domain are tackled. We also propose optimal activation algorithms forVeSn and ViSn when their activation is not always beneficial. We make use of results from stochastic approximationand convex optimization for the mathematical formulation of the problems and their solutions. We also proposea generic methodology for the coordination of multiple SON algorithms running in parallel using results fromconcave game theory and Linear Matrix Inequality (LMI)-constrained optimization., Le réseau mobile d’Orange France comprend plus de 100 000 antennes 2G, 3G et 4G sur plusieurs bandes de fréquences sans compter les nombreuses femto-cells fournies aux clients pour résoudre les problèmes de couverture. Ces chiffres ne feront que s’accroître pour répondre à la demande sans cesse croissante des clients pour les données mobiles. Cela illustre le défi énorme que rencontrent les opérateurs de téléphonie mobile en général à savoir gérer un réseau aussi complexe tout en limitant les coûts d’opération pour rester compétitifs. Cette thèse s’attache à utiliser le concept SON (réseaux auto-organisants) pour réduire cette complexité en automatisant les tâches répétitives ou complexes. Plus spécifiquement, nous proposons des algorithmes d’optimisation automatique pour des scénarios liés à la densification par les small cells ou les antennes actives. Nous abordons les problèmes classiques d’équilibrage de charge mais avec un lien backhaul à capacité limitée et de coordination d’interférence que ce soit dans le domaine temporel (notamment avec le eICIC) ou le domaine fréquentiel. Nous proposons aussi des algorithmes d’activation optimale de certaines fonctionnalités lorsque cette activation n’est pas toujours bénéfique. Pour la formulation mathématique et la résolution de tous ces algorithmes, nous nous appuyons sur les résultats de l’approximation stochastique et de l’optimisation convexe. Nous proposons aussi une méthodologie systématique pour la coordination de multiples fonctionnalités SON qui seraient exécutées en parallèle. Cette méthodologie est basée sur les jeux concaves et l’optimisation convexe avec comme contraintes des inégalités matricielles linéaires.

Swiss National Foundation : FN 200020-149871/1. CIMI (Centre International de Mathematiques et d'Informatique) : ANR-11-LABX-0040-CIMI, ANR-11-IDEX-0002-02; International audience; This work is concerned with the analysis of a stochastic approximation algorithm for the simulation of quasi-stationary distributions on finite state spaces. This is a generalization of a method introduced by Aldous, Flannery and Palacios. It is shown that the asymptotic behavior of the empirical occupation measure of this process is precisely related to the asymptotic behavior of some deterministic dynamical system induced by a vector field on the unit simplex. This approach provides new proof of convergence as well as precise asymptotic rates for this type of algorithm. In the last part, our convergence results are compared with those of a particle system algorithm (a discrete-time version of the Fleming-Viot algorithm).

The mobile network of Orange in France comprises more than 100 000 2G, 3G and 4G antennas with severalfrequency bands, not to mention many femto-cells for deep-indoor coverage. These numbers will continue toincrease in order to address the customers’ exponentially increasing need for mobile data. This is an illustrationof the challenge faced by the mobile operators for operating such a complex network with low OperationalExpenditures (OPEX) in order to stay competitive. This thesis is about leveraging the Self-Organizing Network(SON) concept to reduce this complexity by automating repetitive or complex tasks. We specifically proposeautomatic optimization algorithms for scenarios related to network densification using either small cells orActive Antenna Systems (AASs) used for Vertical Sectorization (VeSn), Virtual Sectorization (ViSn) and multilevelbeamforming. Problems such as load balancing with limited-capacity backhaul and interference coordination eitherin time-domain (eICIC) or in frequency-domain are tackled. We also propose optimal activation algorithms forVeSn and ViSn when their activation is not always beneficial. We make use of results from stochastic approximationand convex optimization for the mathematical formulation of the problems and their solutions. We also proposea generic methodology for the coordination of multiple SON algorithms running in parallel using results fromconcave game theory and Linear Matrix Inequality (LMI)-constrained optimization., Le réseau mobile d’Orange France comprend plus de 100 000 antennes 2G, 3G et 4G sur plusieurs bandes de fréquences sans compter les nombreuses femto-cells fournies aux clients pour résoudre les problèmes de couverture. Ces chiffres ne feront que s’accroître pour répondre à la demande sans cesse croissante des clients pour les données mobiles. Cela illustre le défi énorme que rencontrent les opérateurs de téléphonie mobile en général à savoir gérer un réseau aussi complexe tout en limitant les coûts d’opération pour rester compétitifs. Cette thèse s’attache à utiliser le concept SON (réseaux auto-organisants) pour réduire cette complexité en automatisant les tâches répétitives ou complexes. Plus spécifiquement, nous proposons des algorithmes d’optimisation automatique pour des scénarios liés à la densification par les small cells ou les antennes actives. Nous abordons les problèmes classiques d’équilibrage de charge mais avec un lien backhaul à capacité limitée et de coordination d’interférence que ce soit dans le domaine temporel (notamment avec le eICIC) ou le domaine fréquentiel. Nous proposons aussi des algorithmes d’activation optimale de certaines fonctionnalités lorsque cette activation n’est pas toujours bénéfique. Pour la formulation mathématique et la résolution de tous ces algorithmes, nous nous appuyons sur les résultats de l’approximation stochastique et de l’optimisation convexe. Nous proposons aussi une méthodologie systématique pour la coordination de multiples fonctionnalités SON qui seraient exécutées en parallèle. Cette méthodologie est basée sur les jeux concaves et l’optimisation convexe avec comme contraintes des inégalités matricielles linéaires.

The thesis deals with the contribution of the Laplace method to the approximation of the Bayesian filter in hidden Markov models with continuous state--space, i.e. in a sequential framework, with target tracking as the main application domain. Originally, the Laplace method is an asymptotic method used to compute integrals, i.e. in a static framework, valid in theory as soon as the function to be integrated exhibits an increasingly dominating maximum point, which brings the essential contribution to the integral. The two main contributions of the thesis are the following. Firstly, we have combined the Laplace method and particle filters: indeed, it is well-known that sequential Monte Carlo methods based on importance sampling are inefficient when the weighting function (here, the likelihood function) is too much spatially localized, e.g. when the variance of the observation noise is too small, whereas this is precisely the situation where the Laplace method is efficient and theoretically justified, hence the natural idea of combining the two approaches. We thus propose an algorithm associating the Laplace method and particle filtering, called the Laplace particle filter. Secondly, we have analyzed the approximation of the Bayesian filter based on the Laplace method only (i.e. without any generation of random samples): the objective has been to control the propagation of the approximation error from one time step to the next time step, in an appropriate asymptotic framework, e.g. when the variance of the observation noise goes to zero, or when the variances of the model noise and of the observation noise jointly go (with the same rate) to zero, or more generally when the information contained in the system goes to infinity, with an interpretation in terms of identifiability., La thèse porte sur l'apport de la méthode de Laplace pour l'approximation du filtre bayésien dans des modèles de Markov cachés généraux, c'est-à-dire dans un cadre séquentiel, avec comme domaine d'application privilégié la poursuite de cibles mobiles. A la base, la méthode de Laplace est une méthode asymptotique pour le calcul d'intégrales, c'est-à-dire dans un cadre statique, valide en théorie dès que la fonction à intégrer présente un maximum de plus en plus significatif, lequel apporte la contribution essentielle au résultat. En pratique, cette méthode donne des résultats souvent très précis même en dehors de ce cadre de validité théorique. Les deux contributions principales de la thèse sont les suivantes. Premièrement, nous avons utilisé la méthode de Laplace en complément du filtrage particulaire : on sait en effet que les méthodes de Monte Carlo séquentielles basées sur l'échantillonnage pondéré sont mises en difficulté quand la fonction de pondération (ici la fonction de vraisemblance) est trop localisée, par exemple quand la variance du bruit d'observation est trop faible, or c'est précisément là le domaine où la méthode de Laplace est efficace et justifiée théoriquement, d'où l'idée naturelle de combiner les deux points de vue. Nous proposons ainsi un algorithme associant la méthode de Laplace et le filtrage particulaire, appelé le Laplace particle filter. Deuxièmement, nous avons analysé l'approximation du filtre bayésien grâce à la méthode de Laplace seulement (c'est-à-dire sans génération d'échantillons aléatoires) : il s'agit ici de contrôler la propagation de l'erreur d'approximation d'un pas de temps au pas de temps suivant, dans un cadre asymptotique approprié, par exemple quand le bruit d'observation tend vers zéro, ou quand le bruit d'état et le bruit d'observation tendent conjointement (et à la même vitesse) vers zéro, ou plus généralement quand l'information contenue dans le système tend vers l'infini, avec une interprétation en terme d'identifiabilité.

High dimensional data are supposed to be independent on-line observations of a random vector. In the second chapter, the latter is denoted by Z and sliced into two random vectors R et S and data are supposed to be identically distributed. A recursive method of sequential estimation of the factors of the projected PCA of R with respect to S is defined. Next, some particular cases are investigated : canonical correlation analysis, canonical discriminant analysis and canonical correspondence analysis ; in each case, several specific methods for the estimation of the factors are proposed. In the third chapter, data are observations of the random vector Zn whose expectation θn varies with time. Let Zn_tilde = Zn − θn and suppose that the vectors Zn_tilde form an independent and identically distributed sample of a random vector Z_tilde. Stochastic approximation processes are used to estimate on-line direction vectors of the principal axes of a partial principal components analysis (PCA) of Z_tilde. This is applied next to the particular case of a partial generalized canonical correlation analysis (gCCA) after defining a stochastic approximation process of the Robbins-Monro type to estimate recursively the inverse of a covariance matrix. In the fourth chapter, the case when both expectation and covariance matrix of Zn vary with time n is considered. Finally, simulation results are given in chapter 5., On suppose que des vecteurs de données de grande dimension arrivant en ligne sont des observations indépendantes d'un vecteur aléatoire. Dans le second chapitre, ce dernier, noté Z, est partitionné en deux vecteurs R et S et les observations sont supposées identiquement distribuées. On définit alors une méthode récursive d'estimation séquentielle des r premiers facteurs de l'ACP projetée de R par rapport à S. On étudie ensuite le cas particulier de l'analyse canonique, puis de l'analyse factorielle discriminante et enfin de l'analyse factorielle des correspondances. Dans chacun de ces cas, on définit plusieurs processus spécifiques à l'analyse envisagée. Dans le troisième chapitre, on suppose que l'espérance θn du vecteur aléatoire Zn dont sont issues les observations varie dans le temps. On note Zn_tilde = Zn − θn et on suppose que les vecteurs Zn_tilde forment un échantillon indépendant et identiquement distribué d'un vecteur aléatoire Z_tilde. On définit plusieurs processus d'approximation stochastique pour estimer des vecteurs directeurs des axes principaux d'une analyse en composantes principales (ACP) partielle de Z_tilde. On applique ensuite ce résultat au cas particulier de l'analyse canonique généralisée (ACG) partielle après avoir défini un processus d'approximation stochastique de type Robbins-Monro de l'inverse d'une matrice de covariance. Dans le quatrième chapitre, on considère le cas où à la fois l'espérance et la matrice de covariance de Zn varient dans le temps. On donne finalement des résultats de simulation dans le chapitre 5.

This thesis proposes a mathematical framework for the modeling the intraday dynamics of prices and order ow in limit order markets: electronic markets where participants buy and sell a nancial contract by submitting market orders and limit orders at high frequency to a centralized limit order book. We propose a stochastic model of a limit order book as a queueing system representing the dynamics of the queues of buy/sell limit orders at the best available (bid/ask) price levels and argue that the main features of price dynamics in limit order markets may be understood in this framework. We study in detail the relation between the statistical properties of the price and the dynamics of the point process describing the arrival and execution of orders, rst in a Markovian setting (Chapter 2) then, using asymptotic methods, in a more general setting of a stationary point process in the heavy tra c limit, where orders arrive very frequently, as in most liquid stock markets (Chapters 3 and 4). Chapter 2 studies a Markovian model for limit order book dynamics, in which arrivals of market order, limit orders and order cancelations are described in terms of a Poisson point process. The state of the order book is then described as a time-changed random walk in the positive quadrant regenerated at each hitting time of the boundary. This model allows to obtain analytical expressions for the distribution of the duration between price changes, the distribution and autocorrelation of price changes, and the probability of an upward move in the price, conditional on the state of the order book, by mapping them into quantities related to hitting times of a random walk in Z2 + killed at the boundary. We study the di usion limit of the price process and express the volatility of price changes in terms of parameters describing the arrival rates of buy and sell orders and cancelations. These analytical results provide some insight into the relation between order ow and price dynamics in order-driven markets. Chapter 3 studies a more general queueing model in which order arrivals and order sizes are described by a stationary point process, allowing for a wide range of distributional assumptions and temporal dependence structures in the order ow. We derive a functional central limit theorem for the joint dynamics of the bid and ask queues and show that, in a liquid market where buy and sell orders are submitted at high frequency, the intraday dynamics of the limit order book may be approximated by a Markovian jump-di usion process in the positive orthant, whose characteristics are explicitly described in terms of the statistical properties of the underlying order ow. This result allows to obtain tractable analytical approximations for various quantities of interest, such as the probability of a price increase or the distribution of the duration until the next price move, conditional on the state of the order book. Both quantities are expressed in terms of the solution of elliptic equation in the positive orthant, for which solutions are given in important special cases. These results apply to a wide class of stochastic models proposed for order book dynamics, including models based on Poisson point processes, self-exciting point processes and models of the ACD-GARCH family. Chapter 4 is a more detailed study of price dynamics in a limit order market where market orders, limit orders and order cancelations occur with high frequency according to a stationary marked point process. We rst study the discrete, high-frequency dynamics of the price and derive analytical relations between the statistical properties of intraday price changes -distribution of increments, mean reversion and autocorr elation- and properties of the process describing the order ow and depth of the order book. We then study the behavior of the price process at lower frequencies under various heavyviii tel-00738647, version 1 - 4 Oct 2012 CONTENTS ix tra c limits { uid limits and di usion limits{ and derive in each case the price trend and intraday volatility in terms of the arrival rates of buy and sell orders and cancelations and the variance of order sizes. These analytical formulae provide insights into the link between price volatility on one hand and high-frequency order ow and liquidity on the other hand and are shown to be in good agreement with high-frequency data for US stocks., Cette thèse propose un cadre mathématique pour la modélisation de la dynamique du prix et du flux d'ordres dans un marché électronique ou' les participants achètent et vendent un produit financier en soumettant des ordres limites et des ordres de marche à haute fréquence à un carnet d'ordres centralisé. Nous proposons un modèle stochastique de carnet d'ordres en tant que système de files d'attente représentant la totalité des ordres d'achat et de vente au meilleur niveau de prix (bid/ask) et nous montrons que les principales caractéristiques de la dynamique du prix dans un tel marche peuvent être comprises dans ce cadre. Nous étudions en détail la relation entre les principales propriétés du prix et la dynamique du processus ponctuel décrivant l'arrivée et l'exécution des ordres, d'abord dans un cadre Markovien (Chapitre 2) puis, en utilisant des méthodes asymptotiques, dans le cadre plus général d'un processus ponctuel stationnaire dans sa limite heavy traffic, pour lequel les ordres arrivent fréquemment, comme c'est le cas pour la plupart des marches liquides (Chapitres 3 et 4). Le Chapitre 2 étudie un modèle Markovien de dynamique de carnet d'ordres, dans lequel l'arrivée d'ordres de marche, d'ordres limites et d'annulations est d'écrite à l'aide d'un processus de Poisson ponctuel. L'état du carnet d'ordres est d'écrit par une marche aléatoire changée de temps dans le quadrant positif et régénérée à chaque fois qu'elle atteint le bord. Ce modèle permet d'obtenir des expressions analytiques pour la distribution des durées entre changements de prix, la distribution et les autocorrelations des changements de prix, ainsi que la probabilité que le prix augmente, conditionnellement à l'état du carnet d'ordres. Nous étudions la limite de diffusion du prix et exprimons la volatilité des changements de prix à l'aide de paramètres décrivant l'intensité des ordres d'achat, de vente et d'annulations. Ces résultats analytiques permettent de mieux comprendre le lien entre volatilité du prix et flux d'ordres. Le Chapitre 3 étudie un modèle plus général de carnet d'ordres pour lequel les arrivées d'ordres et les tailles d'ordres proviennent d'un processus ponctuel stationnaire très général. Nous obtenons un théorème central limite fonctionnel pour la dynamique jointe des files d'attente des ordres de vente et d'achat, et prouvons que, pour un marche liquide, dans lequel les ordres d'achat et de vente arrivent à haute fréquence, la dynamique du carnet d'ordres peut être approximée par un processus à sauts Markovien diffusant dans l'orthant et dont les caractéristiques peuvent être exprimées à l'aide de propriétés statistiques du flux d'ordres sous-jacent. Ce résultat permet d'obtenir des approximations analytiques pour plusieurs quantities d'intérêt telles que la probabilité que le prix augmente ou la distribution de la durée avant le prochain changement de prix, conditionnellement à l'état du carnet d'ordres. Ces quantités sont exprimées en tant que solutions d'équations elliptiques, pour lesquelles nous donnons des solutions explicites dans certains cas importants. Ces résultats s'appliquent à une classe importante de modèles stochastiques, incluant les mod'eles bas'es sur les processus de Poisson, les processus auto-excitants ou la famille de processus ACD-GARCH. Le Chapitre 4 est une étude plus détaillée de la dynamique du prix dans un marche où les ordres de marche, les ordres limites et les annulations arrivent à haute fréquence. Nous étudions d'abord la dynamique discrète du prix à l'échelle de la seconde et nous obtenons des relations analytiques entre les propriétés statistiques des changements de prix dans une journée -distribution des incréments du prix, retour à la moyenne et autocorrelations- et des propriétés du processus décrivant le flux d'ordres et la profondeur du carnet d'ordres. Ensuite nous étudions le comportement du prix à des fréquences vi CONTENTS vii plus faibles pour plusieurs régimes asymptotiques -limites fluides et diffusives- et nous obtenons pour chaque cas la tendance du prix et sa volatilité en fonction des intensités d'arrivées d'ordres d'achat, de vente et d'annulations ainsi que la variance des tailles d'ordres. Ces formules permettent de mieux comprendre le lien entre volatilité du prix d'un côté et le flux d'ordres, décrivant la liquidité, d'un autre cote. Nous montrons que ces résultats sont en accord avec la réalité des marches liquides.

This thesis is about stochastic approximation analysis and application in Finance. In the first part, a convergence result for stochastic approximation where the innovations satisfy averaging assumptions with some rate is established. It is applied to different types of innovations and illustrated on examples mainly motivated by Finance. A result on "universal" rate of convergence is then presented when the innovations are uniformly distributed and compared to those obtained in the i.i.d. framework. The second part is devoted to applications. First an optimal allocation problem applied to dark pools is studied. The execution of the maximum of the desired quantity leads to the design of a constrained stochastic algorithm studied in the i.i.d. and averaging frameworks. The next chapter presents a constrained optimization stochastic algorithm with projection to find the optimal posting distance in a limit order book by minimizing the execution cost of a given quantity. Parameter implicitation and calibration in financial models using stochastic approximation are then studied and illustrated by examples of applications on Black-Scholes, Merton and pseudo-CEV models. The last chapter is about stochastic approximation application to randomized urn models used in clinical trials. Thanks to ODE and SDE methods, the consistency and asymptotic normality results of Bai and Hu are retrieved under less stringent assumptions on the generating matrices., Cette thèse porte sur l'analyse d'algorithmes stochastiques et leur application en Finance notamment et est composée de deux parties. Dans la première partie, nous présentons un résultat de convergence pour des algorithmes stochastiques où les innovations vérifient une hypothèse de moyennisation avec une certaine vitesse. Nous l'appliquons ensuite à différents types d'innovations (suites i.i.d., suites à discrépance faible, chaînes de Markov homogènes, fonctionnelles de processus \alpha-mélangeant) et nous l'illustrons à l'aide d'exemples motivés principalement par la Finance. Nous établissons ensuite un résultat de vitesse ''universelle'' de convergence dans le cadre d'innovations équiréparties dans [0,1]^q et nous confrontons nos résultats à ceux obtenus dans le cadre i.i.d.. La seconde partie est consacrée aux applications. Nous présentons d'abord un problème d'allocation optimale appliqué au cas d'un nouveau type de place de trading: les {\em dark pools}. Ces places proposent un prix d'achat (ou de vente) certain, mais n'assurent pas le volume délivré. Le but est alors d'exécuter le maximum de la quantité souhaitée sur ces places. Ceci mène à la construction d'un algorithme stochastique sous contraintes à l'aide du Lagrangien que nous étudions dans les cadres d'innovations i.i.d. et moyennisantes. Le chapitre suivant présente un algorithme d'optimisation pour trouver la meilleure distance de placement d'ordres limites: il s'agit de minimiser le coût d'exécution d'une quantité donnée. Ceci mène à la construction d'un algorithme stochastique sous contraintes avec projection. Pour assurer l'existence et l'unicité de l'équilibre, des critères suffisants sur certains paramètres du modèle sont obtenus à l'aide d'un principe de monotonie opposée pour les diffusions unidimensionnelles. Le chapitre suivant porte sur l'implicitation et la calibration de paramètres dans des modèles financiers. La première technique mène à un algorithme de recherche de zéro et la seconde à une méthode de gradient stochastique. Nous illustrons ces deux techniques par des exemples d'applications sur 3 modèles: le modèle de Black-Scholes, le modèle de Merton et le modèle pseudo-CEV. Enfin le dernier chapitre porte sur l'application des algorithmes stochastiques dans le cadre de modèles d'urnes aléatoires utilisés en essais cliniques. A l'aide des méthodes de l'EDO et de l'EDS, nous retrouvons les résultats de consistance (convergence p.s.) et de normalité asymptotique (TCL) de Bai et Hu mais sous des hypothèses plus faibles sur les matrices génératrices. Nous étudions aussi un modèle ''multi-bras'' pour lequel nous retrouvons le résultat de convergence p.s. et nous montrons un nouveau résultat de normalité asymptotique par simple application du TCL pour les algorithmes stochastiques.

This thesis is concerned with probabilistic numerical problems about modeling, risk control and risk hedging motivated by applications to energy markets. The main tool is based on stochastic approximation and simulation methods. This thesis consists of three parts. The first one is devoted to the computation of two risk measures of the portfolio loss distribution L: the Value-at-Risk (VaR) and the Conditional Value-at-Risk (CVaR). This computation uses a stochastic algorithm combined with an adaptive variance reduction technique. The first part of this chapter deals with the finite dimensional case, the second part extends the results of the first part to the case of a path-dependency process and the last one deals low discrepancy sequences. The second chapter is devoted with risk minimizing hedging strategies in an incomplete market operating in discrete time using quantization based stochastic approximation. Theoretical results on CVaR hedging are presented then numerical aspects are adressed in a Markovian framework. The last part deals with joint modeling of Gas and Electricity spot prices. The multi-factor model presented is based on stationnary Ornstein process with parameterized diffusion coefficient., Cette thèse est consacrée à des problématiques numériques probabilistes liées à la modélisation, au contrôle et à la gestion du risque et motivées par des applications dans les marchés de l'énergie. Le principal outil utilisé est la théorie des algorithmes stochastiques et des méthodes de simulation. Cette thèse se compose de trois parties. La première est dévouée à l'estimation de deux mesures de risque de la distribution L des pertes d'un portefeuille: la Value-at-Risk (VaR) et la Conditional Value-at-Risk (CVaR). Cette estimation est effectuée à l'aide d'un algorithme stochastique combiné avec une méthode de réduction de variance adaptative. La première partie de ce chapitre traite du cas de la dimension finie, la deuxième étend la première au cas d'une fonction de la trajectoire d'un processus et la dernière traite du cas des suites à discrépance faible. Le deuxième chapitre est dédié à des méthodes de couverture du risque en CVaR dans un marché incomplet opérant à temps discret à l'aide d'algorithmes stochastiques et de quantification vectorielle optimale. Des résultats théoriques sur la couverture en CVaR sont présentés puis les aspects numériques sont abordés dans un cadre markovien. La dernière partie est consacrée à la modélisation conjointe des prix des contrats spot Gaz et l'Electricité. Le modèle multi-facteur présenté repose sur des processus d'Ornstein stationnaires à coefficient de diffusion paramétrique.

International audience; Des vecteurs de données arrivant en ligne sont considérés comme des réalisations indépendantes d'un vecteur aléatoire. On établit dans ce cadre un résultat de convergence presque sûre d'un processus d'approximation stochastique des facteurs de l'ACP de ce vecteur aléatoire. On peut l'appliquer par exemple à l'analyse factorielle multiple. On étudie ensuite le cas où l'espérance mathématique du vecteur aléatoire varie dans le temps selon un modèle linéaire.

Mémoire numérisé par la Division de la gestion de documents et des archives de l'Université de Montréal.

The first part of this thesis is devoted to the study randomly truncated stochastic algorithms as introduced by Chen and Zhu. The first study is concerned with the almost sure convergence. We continue the study with the convergence rate of the algorithm. We also consider a moving window version of the algorithm. Finally, we present a few applications to finance.The second part of the thesis is concerned with the pricing of Parisian options. The valuation technique is based on computing closed form formula for the Laplace transforms of the prices following the seminar work of Chesney, Jeanblanc and Yor on the topic. We determinethese formulae for the single and double barrier Parisian options. Then, prove the accuracy of the numerical inversion methods we use ton invert these Laplace transforms.; La première partie de cette thèse est consacrée à l'étude des algorithmes stochastiques aléatoirement tronqués de Chen et Zhu. La première étude de cet algorithme concerne sa convergence presque sûre. Dans le second chapitre, nous poursuivons l'étude de cet algorithme en nous intéressant à sa vitesse de convergence. Nous considérons également une version moyenne mobile de cet algorithme. Enfin nous terminons par quelques applications à la finance.La seconde partie de cette thèse s'intéresse à l'évaluation des options parisiennes en s'appuyant sur les travaux de Chesney, Jeanblanc et Yor. La méthode d'évaluation se base sur l'obtention de formules fermées pour les transformées de Laplace des prix par rapport à la maturité. Nous établissons ces formules pour les options parisiennes simple et double barrières. Nous étudions ensuite une méthode d'inversion numérique de ces transformées dont nous établissons la précision.

The first chapter is concerned with some self-interacting diffusions $(X_t,t\geq 0)$living on $\mathbb{R}^d$. These diffusions are solutions to stochastic differential equations:$$\mathrm{d}X_t = \mathrm{d}B_t - g(t)\nabla V(X_t -\overline{\mu}_t) \mathrm{d}t,$$ where $\overline{\mu}_t$ is the empirical mean of the process $X$, $V$ is an asymptotically strictly convex potential and $g$ is a given function. We study the ergodic behavior of $X$ and prove that it is strongly related to $g$. Actually, $X$ and $\overline{\mu}_t$ have the same asymptotic behavior and we will give necessary and sufficient conditions (on $g$ and $V$) for the almost sure convergence of $X$. In chapter 2, we finish the previous study. We have still studied the ergodic behavior of $X$ and proved that it is stronglyrelated to $g$. We go further and give necessary and sufficient conditions (for small $g$'s) in order that $X$ converges in law to $X_\infty$ (which is related to the global minima of $V$).In the second part, we begin to situate our study in Chapter 3. Self-interacting diffusions are solutions to SDEs with a drift term depending on the process and its normalized occupation measure $\mu_t$ (via an interaction potential $V$ and a confinement potential $W$):$$\mathrm{d}X_t = \mathrm{d}B_t -\left( \nabla V(X_t)+\frac{1}{t} \int_0^t \nabla_x W(X_t,X_s) \mathrm{d}s \right) \mathrm{d}t \\\mathrm{d}\mu_t = (\delta_{X_t} - \mu_t)\frac{\mathrm{d}t}{r+t}\\X_0 = x, \mu_0=\mu. $$ We establish a relation between the asymptotic behavior of $\mu_t$ and the asymptotic behavior of a deterministic dynamical flow (defined on the space of the Borel probability measures). We extend previous results on $\mathbb{R}^d$ or more generally a smooth complete connected Riemannian manifold without boundary. We will also give some sufficient conditions for the convergence of $\mu_t$. We then illustrate, in Chapter 5, the previous study of self-interacting diffusions living in $\mathbb{R}^d$ with some examples in the two-dimensional case. Thepreceding chapter contains abstract results, and therefore we describe here a simple example and illustrate some of our previous results. We will show in particular that, depending on $W$, either the empirical measure behaves like the ``Brownian motion" (constructed with respect to the measure $e^{V(x)} \mathrm{d}x$); or the empirical occupation measure converges almost surely to a probability measure, which is approximatively a Gaussian distribution ; or there is enough attraction, and then the term induced by $W$ forces $\mu_t$ to circle around and the limit set of $(\mu_t)$ is a circle of measures $\{\nu(\delta), 0\leq\delta, Le but de cette thèse est d'étudier le comportement asymptotique de diffusions auto-interactives sur $\mathbb{R}^d$. Nous étudions deux familles de processus renforcés. La première est régie par l'équation différentielle stochastique $$\mathrm{d}X_t = \mathrm{d}B_t - g(t)\nabla V(X_t -\overline{\mu}_t) \mathrm{d}t,$$ où $\overline{\mu}_t$ est la moyenne de la mesure empirique du processus $X$, $V$ est un potentiel strictement uniformément convexe en dehors d'un compact et $g$ est une fonction donnée. Nous étudions alors le comportement asymptotique de $X$, en fonction de $g$. Selon la forme de $g$, on peut montrer que $X$ converge presque-sûrement (chapitre 1) ou converge en loi (chapitre 2). Dans une seconde partie, nousnous intéressons à une famille plus complexe, correspondant aux diffusions renforcées par la mesure d'occupation. Il s'agit de processus satisfaisant l'équation $$\mathrm{d}X_t = \mathrm{d}B_t -\left( \nabla V(X_t)+\frac{1}{t} \int_0^t \nabla_x W(X_t,X_s) \mathrm{d}s \right) \mathrm{d}t \\\mathrm{d}\mu_t = (\delta_{X_t} - \mu_t)\frac{\mathrm{d}t}{r+t}\\X_0 = x, \mu_0=\mu. $$ Nous établissons une relationentre le comportement asymptotique de $\mu_t$ et le comportement asymptotique d'un système dynamique déterministe (défini sur l'espace des probabilités). Nous étendons alors de précédentsrésultats à $\mathbb{R}^d$. Nous donnons également des conditions suffisantes pour la convergence de $\mu_t$. Enfin, nous illustrons, au chaptre 5, l'étude précédente de diffusions auto-interactives par quelques exemples en dimension deux.

The first chapter is concerned with some self-interacting diffusions $(X_t,t\geq 0)$living on $\mathbb{R}^d$. These diffusions are solutions to stochastic differential equations:$$\mathrm{d}X_t = \mathrm{d}B_t - g(t)\nabla V(X_t -\overline{\mu}_t) \mathrm{d}t,$$ where $\overline{\mu}_t$ is the empirical mean of the process $X$, $V$ is an asymptotically strictly convex potential and $g$ is a given function. We study the ergodic behavior of $X$ and prove that it is strongly related to $g$. Actually, $X$ and $\overline{\mu}_t$ have the same asymptotic behavior and we will give necessary and sufficient conditions (on $g$ and $V$) for the almost sure convergence of $X$. In chapter 2, we finish the previous study. We have still studied the ergodic behavior of $X$ and proved that it is stronglyrelated to $g$. We go further and give necessary and sufficient conditions (for small $g$'s) in order that $X$ converges in law to $X_\infty$ (which is related to the global minima of $V$).In the second part, we begin to situate our study in Chapter 3. Self-interacting diffusions are solutions to SDEs with a drift term depending on the process and its normalized occupation measure $\mu_t$ (via an interaction potential $V$ and a confinement potential $W$):$$\mathrm{d}X_t = \mathrm{d}B_t -\left( \nabla V(X_t)+\frac{1}{t} \int_0^t \nabla_x W(X_t,X_s) \mathrm{d}s \right) \mathrm{d}t \\\mathrm{d}\mu_t = (\delta_{X_t} - \mu_t)\frac{\mathrm{d}t}{r+t}\\X_0 = x, \mu_0=\mu. $$ We establish a relation between the asymptotic behavior of $\mu_t$ and the asymptotic behavior of a deterministic dynamical flow (defined on the space of the Borel probability measures). We extend previous results on $\mathbb{R}^d$ or more generally a smooth complete connected Riemannian manifold without boundary. We will also give some sufficient conditions for the convergence of $\mu_t$. We then illustrate, in Chapter 5, the previous study of self-interacting diffusions living in $\mathbb{R}^d$ with some examples in the two-dimensional case. Thepreceding chapter contains abstract results, and therefore we describe here a simple example and illustrate some of our previous results. We will show in particular that, depending on $W$, either the empirical measure behaves like the ``Brownian motion" (constructed with respect to the measure $e^{V(x)} \mathrm{d}x$); or the empirical occupation measure converges almost surely to a probability measure, which is approximatively a Gaussian distribution ; or there is enough attraction, and then the term induced by $W$ forces $\mu_t$ to circle around and the limit set of $(\mu_t)$ is a circle of measures $\{\nu(\delta), 0\leq\delta, Le but de cette thèse est d'étudier le comportement asymptotique de diffusions auto-interactives sur $\mathbb{R}^d$. Nous étudions deux familles de processus renforcés. La première est régie par l'équation différentielle stochastique $$\mathrm{d}X_t = \mathrm{d}B_t - g(t)\nabla V(X_t -\overline{\mu}_t) \mathrm{d}t,$$ où $\overline{\mu}_t$ est la moyenne de la mesure empirique du processus $X$, $V$ est un potentiel strictement uniformément convexe en dehors d'un compact et $g$ est une fonction donnée. Nous étudions alors le comportement asymptotique de $X$, en fonction de $g$. Selon la forme de $g$, on peut montrer que $X$ converge presque-sûrement (chapitre 1) ou converge en loi (chapitre 2). Dans une seconde partie, nousnous intéressons à une famille plus complexe, correspondant aux diffusions renforcées par la mesure d'occupation. Il s'agit de processus satisfaisant l'équation $$\mathrm{d}X_t = \mathrm{d}B_t -\left( \nabla V(X_t)+\frac{1}{t} \int_0^t \nabla_x W(X_t,X_s) \mathrm{d}s \right) \mathrm{d}t \\\mathrm{d}\mu_t = (\delta_{X_t} - \mu_t)\frac{\mathrm{d}t}{r+t}\\X_0 = x, \mu_0=\mu. $$ Nous établissons une relationentre le comportement asymptotique de $\mu_t$ et le comportement asymptotique d'un système dynamique déterministe (défini sur l'espace des probabilités). Nous étendons alors de précédentsrésultats à $\mathbb{R}^d$. Nous donnons également des conditions suffisantes pour la convergence de $\mu_t$. Enfin, nous illustrons, au chaptre 5, l'étude précédente de diffusions auto-interactives par quelques exemples en dimension deux.

Statistical Learning Theory has been growing rapidly the last ten years. The introduction of efficient classification algorithms, such as boosting and Support Vector Machines, coping with high-dimensional data, generated new questions that Vapnik-Chervonenkis (VC) theory could not answer. The Empirical Risk Minimization principle does not account for practical learning algorithms and the VC dimension is not the appropriate concept to explain the generalization ability of suchmethods. In the first chapter, we recall the interpretations of boosting algorithms as implementations of convex risk minimizationprinciples and we study their properties under this viewpoint. In particular, we show the importance of regularization in order to obtain consistent strategies. We also develop a new class of algorithms called the Mirror Averaging Algorithm and we evaluatetheir performance through simulation experiments. After presenting the fundamental ideas underlying boosting, we study, in the second chapter, more advanced issues such as oracle inequalities. Thus, we propose some fine calibration of the penalty function according to the cost function being used and present non-asymptotic resultson the performance of penalized boosting estimators, with refinements such as fast rates of convergence under Mammen-Tsybakov margin conditions. We also describe the approximation properties of boosting using decision stumps. The third chapter explores the ranking problem. In applications such as information retrieval or credit scoring, ranking the instances can be much more significant than simply classifying them. We propose a simple formulation of this problem in which ranking isequivalent to classification with pairs of observations. The difference lies in the nature of the empirical risks which take the form of U-statistics and we develop classification theory in order to fit with this framework. We also investigate the possibilities of generalizing the ranking error in order to include priors on the ranking we are aiming at, for instance, when we want to focus only on the "best" instances., Depuis une dizaine d'années, la théorie statistique de l'apprentissage a connu une forte expansion. L'avènement d'algorithmes hautement performants pour la classification de données en grande dimension, tels que le boosting ou les machines à noyaux (SVM) a engendré de nombreuses questions statistiques que la théorie de Vapnik-Chervonenkis (VC) ne permettait pas de résoudre. En effet, le principe de Minimisation du Risque Empirique ne rend pas compte des méthodes d'apprentissage concrètes et le concept de complexité combinatoire de VC dimension ne permet pas d'expliquer les capacités de généralisation d'algorithmessélectionnant un estimateur au sein d'une classe massive telle que l'enveloppe convexe d'une classe de VC. Dans le premier volet du mémoire, on rappelle les interprétations des algorithmes de boosting comme des implémentations de principes de minimisationde risques convexes et on étudie leurs propriétés sous cet angle. En particulier, on montre l'importance de larégularisation pour obtenir des stratégies consistantes. On développe également une nouvelle classe d'algorithmes de type gradient stochastique appelés algorithmes de descente miroir avec moyennisation et on évalue leur comportement à travers des simulations informatiques. Après avoir présenté les principes fondamentaux du boosting, on s'attache dans ledeuxième volet à des questions plus avancées telles quel'élaboration d'inégalités d'oracle. Ainsi, on étudie lacalibration précise des pénalités en fonction des critèresde coût utilisés. On présente des résultatsnon-asymptotiques sur la performance des estimateurs du boosting pénalisés, notamment les vitesses rapides sous les conditions de marge de type Mammen-Tsybakov et on décrit les capacités d'approximation du boosting utilisant les "rampes" (stumps) de décision. Le troisième volet du mémoire explore le problème du ranking. Un enjeu important dans des applicationstelles que la fouille de documents ou le "credit scoring" est d'ordonner les instances plutôt que de les catégoriser. On propose une formulation simple de ce problème qui permet d'interpréter le ranking comme une classification sur des paires d'observations. La différence dans ce cas vient du fait que lescritères empiriques sont des U-statistiques et on développe donc la théorie de la classification adaptée à ce contexte. On explore également la question de la généralisation de l'erreur de ranking afin de pouvoir inclure des a priori sur l'ordre des instances, comme dans le cas où on ne s'intéresse qu'aux "meilleures" instances.

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

This thesis deals with maximum likelihood estimation in inverse problems. In the tree first chapters, we consider statistical models involving missing data in a parametric framework. Chapter 1 presents a version of the EM algorithm (Expectation Maximization), which combines a stochastic approximation with a Monte Carlo Markov Chain method: the missing data are drawn from a well-chosen transition probability. The almost sure convergence of the sequence generated by the algorithm to a local maximum of the likelihood of the observations is proved. Some applications to deconvolution and change-point detection are presented. Chapter 2 deals with the application of the algorithm to nonlinear mixed effects models. Besides the estimation of the parameters, we estimate the likelihood of the model and the Fisher information matrix. We assess the performance of the algorithm, comparing the results obtained with other methods, on examples coming from pharmacocinetics and pharmacodynamics. Chapter 3 presents an application to geophysics. We perform a joint inversion between teleseismic times and velocity and between gravimetric data and density. Our point of view is innovative because we estimate the parameters of the model which were generally fixed arbitrarily. Moreover we take into account a linear relation between slowness and density. Chapter 4 deals with non parametric density estimation in missing data problems. We propose a logspline estimator of the density of the non observed data, which maximizes the observed likelihood in a logspline model. We apply our algorithm in this parametric model. We study the convergence of this estimator to the density of the non observed data, when the size of the logpline model and the number of observations tend to infinity. Some applications illustrate this method., Cette thèse est consacrée à l'estimation par maximum de vraisemblance dans des problèmes inverses. Nous considérons des modèles statistiques à données manquantes, dans un cadre paramétrique au cours des trois premiers chapitres. Le Chapitre 1 présente une variante de l'algorithme EM (Expectation Maximization) qui combine une approximation stochastique à une méthode de Monte Carlo par chaînes de Markov : les données manquantes sont simulées selon une probabilité de transition bien choisie. Nous prouvons la convergence presque sûre de la suite générée par l'algorithme vers un maximum local de la vraisemblance des observations. Nous présentons des applications en déconvolution et en détection de ruptures. Dans le Chapitre 2, nous appliquons cet algorithme aux modèles non linéaires à effets mixtes et effectuons outre l'estimation des paramètres du modèle, des estimations de la vraisemblance du modèle et de l'information de Fisher. Les performances de l'algorithme sont illustrées via des comparaisons avec d'autres méthodes sur des exemples de pharmacocinétique et de pharmacodynamique. Le Chapitre 3 présente une application de l'algorithme en géophysique. Nous effectuons une inversion jointe, entre les temps de parcours des ondes sismiques et leurs vitesses et entre des mesures gravimétriques de surface et les densités du sous-sol, en estimant les paramètres du modèle, qui étaient en général fixés arbitrairement. De plus, nous prenons en compte une relation linéaire entre les densités et les vitesses des ondes. Le Chapitre 4 est consacré à l'estimation non paramétrique de la densité des données manquantes. Nous exhibons un estimateur logspline de cette densité qui maximise la vraisemblance des observations dans un modèle logspline et appliquons notre algorithme à ce modèle paramétrique. Nous étudions la convergence de cet estimateur vers la vraie densité lorsque la dimension du modèle logspline et le nombre d'observations tendent vers l'infini. Nous présentons quelques applications.

The dynamical systems approach to stochastic approximation is generalized to the case where the mean differential equation is replaced by a differential inclusion. The limit set theorem of Bena\"{\i}m and Hirsch is extended to this situation. Internally chain transitive sets and attractors are studied in detail for set-valued dynamical systems. Applications to game theory are given, in particular to Blackwell's approachability theorem and the convergence of fictitious play., L'approche en termes de systèmes dynamiques de l'approximation stochastique est étendue au cas ou l'équation différentielle moyenne est remplacée par une inclusion différentielle. Le théorème de Benaim et Hirsch sur l'ensemble limite est étendu a ce cas. On étudie en détail les ensembles ICT et les attracteurs. On donne des applications a des questions de théorie des jeux, en particulier concernant le théorème d'approchabilite de Blackwell et la convergence de "fictitious play".

There is studied the stochastic approximation of the eigenvectors of a M-symmetric matrix B, M and B being the expectations of observed random matrices. The convergence of the process defined is proved under general assumptions by means of a martingale technique used in the study of the processes of the Robbins-Monro type. The definition of the process has several classical particular cases., On étudie l'estimation récursive par approximation stochastique des vecteurs propres d'une matrice M-symétrique B, dont on fait des observations bruitées. On démontre, sous des hypothèses générales, par une méthode de martingales utilisée pour les processus du type Robbins-Monro, la convergence d'un processus dont la définition a pour cas particuliers celles de plusieurs processus classiques.

In the last decade nuclear physics research has found, with the observation of phenomena such as multifragmentation or vaporization, the possibility to get a deeper insight into the nuclear matter phase diagram. For example, a spinodal decomposition scenario has been proposed to explain the multifragmentation: because of the initial compression, the system may enter a region, the spinodal zone, in which the nuclear matter is no longer stable, and so any fluctuation leads to the formation of fragments. This thesis deals with spinodal decomposition within the theoretical framework of stochastic mean filed approaches, in which the one-body density function may experience a stochastic evolution. We have shown that these approaches are able to describe phenomena, such as first order phase transitions, in which fluctuations and many-body correlations plan an important role. In the framework of stochastic mean-filed approaches we have shown that the fragment production by spinodal decomposition is characterized by typical time scales of the order of 100 fm/c and by typical size scales around the Neon mass. We have also shown that these features are robust and that they are not affected significantly by a possible expansion of the system or by the finite size of nuclei. We have proposed as a signature of the spinodal decomposition some typical partition of the largest fragments. The study and the comparison with experimental data, performed for the reactions Xe + Cu at 45 MeV/A and Xe + Sn at 50 MeV/A, have shown a remarkable agreement. Moreover we would like to stress that the theory does not contain any adjustable parameter. These results seem to give a strong indication of the possibility to observe a spinodal decomposition of nuclei., Une perspective qui s'est ouverte pour la physique nucléaire dans les dernières années, avec la mise en évidence de phénomènes tels que la multifragmentation ou la vaporisation, est la possibilité d'observer une transition de phase dans la matière nucléaire. Une explication proposée de la multifragmentation est la décomposition spinodale: le passage du système à travers une zone du diagramme des phases, la région spinodale, dans laquelle la matière nucléaire n'est plus stable. Ce mémoire traite ce processus dans le cadre théorique d'une approche de champ moyen stochastique. Nous avons montré que ce type d'approche, dans laquelle la fonction de distribution à un corps peut avoir une évolution aléatoire, est capable de bien décrire des phénomènes dans lesquels corrélations et fluctuations jouent un rôle important, comme dans le cas d'une transition de phase du premier ordre. Dans le cadre d'une approche de champ moyen stochastique, nous avons montré que la production de fragments par décomposition spinodale est caractérisée par des temps typiques (de l'ordre d'une centaine de fm/c) et par des tailles typiques (autour de la masse du Néon). Nous avons montré que ces caractéristiques sont assez robustes et qu'elles ne sont pas affectées de façon importante par une éventuelle expansion du système ou par la taille finie des noyaux. Nous avons proposé de chercher de telles caractéristiques dans les partitions des fragments les plus gros. L'étude et la comparaison avec les données expérimentales ont montrés un très bon accord qui est d'autant plus remarquable que les théories que nous avons développées ne contiennent aucun paramètre ajustable. Ces résultats constituent une indication forte sur la possibilité d'observer une décomposition spinodale dans les noyaux

We give a simple proof of the convergence in direction of stochastic approximation processes to eigenvectors corresponding to the eigenvalues in decreasing order of an M-symmetric matrix. The proof makes use of a common martingale technique as in the study of processes of the Robbins-Monro type. We apply our results to the usual methods of factorial analysis, when the data are obtained sequentially., Nous donnons une démonstration simple, par une méthode classique de martingales utilisée dans l'étude des processus de Robbins-Monro, de la convergence en direction de processus d'approximation stochastique vers des vecteurs propres associés aux valeurs propres rangées par ordre décroissant d'une matrice M-symétrique, sous des hypothèses permettant l'application aux méthodes usuelles d'analyse factorielle placées dans un cadre séquentiel.