Search

Stochastic gradient descent (SGD) optimization algorithms are key ingredients in a series of machine learning applications. In this article we perform a rigorous strong error analysis for SGD optimization algorithms. In particular, we prove for every arbitrarily small $\varepsilon \in (0,\infty)$ and every arbitrarily large $p\in (0,\infty)$ that the considered SGD optimization algorithm converges in the strong $L^p$-sense with order $\frac{1}{2}-\varepsilon$ to the global minimum of the objective function of the considered stochastic approximation problem under standard convexity-type assumptions on the objective function and relaxed assumptions on the moments of the stochastic errors appearing in the employed SGD optimization algorithm. The key ideas in our convergence proof are, first, to employ techniques from the theory of Lyapunov-type functions for dynamical systems to develop a general convergence machinery for SGD optimization algorithms based on such functions, then, to apply this general machinery to concrete Lyapunov-type functions with polynomial structures, and, thereafter, to perform an induction argument along the powers appearing in the Lyapunov-type functions in order to achieve for every arbitrarily large $ p \in (0,\infty) $ strong $ L^p $-convergence rates. This article also contains an extensive review of results on SGD optimization algorithms in the scientific literature.

This thesis deals with estimation in frailty models in survival analysis. Our first contribution concerns a new estimation method based on integrated partial likelihood in the frailty model. No approximation of the integrated partial likelihood is made as compared to other methods proposed in the literature. We implement a stochastic approximation of the Expectation Maximization (EM) algorithm to calculate the maximum of partial likelihood estimators of the model parameters. We also establish the theoretical convergence properties of the algorithm. Our method allows for different correlation structures and for a wide range of frailty distributions. Our second contribution concerns the study of the convergence rates of maximum likelihood estimators in parametric shared frailty models. The convergence rates of are notably different following the factorization of the conditional likelihood. We study this phenomenon via a simulation study. We also highlight the influence of the level of covariates on convergence rates analytically in a linear mixed effects model. We illustrate these differences via an intensive simulation study on a parametric frailty model. Our third contribution presents a new frailty model which takes into account spatial correlations which may be present in data. This new spatial modeling is motivated by malaria infection data collected in Ethiopia. Since the distances between individuals play an important role in the transmission of the disease, it may be relevant to take them into account in the model. A stochastic version of the EM algorithm adapted to this context is implemented and studied. The estimation method is validated on simulated data and then implemented to analyze the malaria data.; Cette thèse porte sur l’estimation dans les modèles de fragilité en analyse de survie. Notre première contribution concerne une nouvelle méthode d’estimation basée sur la vraisemblance partielle intégrée dans le modèle de fragilité. Cette méthode ne réalise aucune approximation de la vraisemblance partielle intégrée contrairement aux autres méthodes proposées dans la littérature. Nous mettons en œuvre une approximation stochastique de l’algorithme Expectation Maximization (EM) pour calculer les estimateurs du maximum de vraisemblance partielle des paramètres du modèle. De plus, nous établissons les propriétés théoriques de convergence de l’algorithme. Notre méthode permet de considérer des modèles de fragilité avec différentes structures de corrélations et une large gamme de lois de fragilité. Notre deuxième contribution porte sur l'étude des vitesses de convergence des estimateurs du maximum de vraisemblance dans les modèles à fragilités partagées paramétriques. En particulier, les vitesses diffèrent selon la factorisation de la vraisemblance conditionnelle. Nous étudions ce phénomène au travers d’une étude de simulation. Nous mettons aussi en évidence l’influence du niveau des covariables sur les vitesses de convergence à travers une étude de simulation intensive dans les modèles de fragilité et de façon analytique dans un modèle linéaire à effets mixtes. Notre troisième contribution présente un nouveau modèle de fragilité qui permet de prendre en compte les corrélations spatiales présentes dans les données. Cette nouvelle modélisation spatiale a été motivée par des données d’infection de malaria en Éthiopie. Les distances entre les individus jouant un rôle important dans la transmission de la maladie, il s’avère judicieux de les prendre en compte dans le modèle. Une version stochastique de l’algorithme EM adaptée à ce contexte est mise en œuvre et étudiée. La méthode d’estimation est validée sur des données simulées puis mise en œuvre pour analyser les données de malaria.

This thesis deals with estimation in frailty models in survival analysis. Our first contribution concerns a new estimation method based on integrated partial likelihood in the frailty model. No approximation of the integrated partial likelihood is made as compared to other methods proposed in the literature. We implement a stochastic approximation of the Expectation Maximization (EM) algorithm to calculate the maximum of partial likelihood estimators of the model parameters. We also establish the theoretical convergence properties of the algorithm. Our method allows for different correlation structures and for a wide range of frailty distributions. Our second contribution concerns the study of the convergence rates of maximum likelihood estimators in parametric shared frailty models. The convergence rates of are notably different following the factorization of the conditional likelihood. We study this phenomenon via a simulation study. We also highlight the influence of the level of covariates on convergence rates analytically in a linear mixed effects model. We illustrate these differences via an intensive simulation study on a parametric frailty model. Our third contribution presents a new frailty model which takes into account spatial correlations which may be present in data. This new spatial modeling is motivated by malaria infection data collected in Ethiopia. Since the distances between individuals play an important role in the transmission of the disease, it may be relevant to take them into account in the model. A stochastic version of the EM algorithm adapted to this context is implemented and studied. The estimation method is validated on simulated data and then implemented to analyze the malaria data., Cette thèse porte sur l’estimation dans les modèles de fragilité en analyse de survie. Notre première contribution concerne une nouvelle méthode d’estimation basée sur la vraisemblance partielle intégrée dans le modèle de fragilité. Cette méthode ne réalise aucune approximation de la vraisemblance partielle intégrée contrairement aux autres méthodes proposées dans la littérature. Nous mettons en œuvre une approximation stochastique de l’algorithme Expectation Maximization (EM) pour calculer les estimateurs du maximum de vraisemblance partielle des paramètres du modèle. De plus, nous établissons les propriétés théoriques de convergence de l’algorithme. Notre méthode permet de considérer des modèles de fragilité avec différentes structures de corrélations et une large gamme de lois de fragilité. Notre deuxième contribution porte sur l'étude des vitesses de convergence des estimateurs du maximum de vraisemblance dans les modèles à fragilités partagées paramétriques. En particulier, les vitesses diffèrent selon la factorisation de la vraisemblance conditionnelle. Nous étudions ce phénomène au travers d’une étude de simulation. Nous mettons aussi en évidence l’influence du niveau des covariables sur les vitesses de convergence à travers une étude de simulation intensive dans les modèles de fragilité et de façon analytique dans un modèle linéaire à effets mixtes. Notre troisième contribution présente un nouveau modèle de fragilité qui permet de prendre en compte les corrélations spatiales présentes dans les données. Cette nouvelle modélisation spatiale a été motivée par des données d’infection de malaria en Éthiopie. Les distances entre les individus jouant un rôle important dans la transmission de la maladie, il s’avère judicieux de les prendre en compte dans le modèle. Une version stochastique de l’algorithme EM adaptée à ce contexte est mise en œuvre et étudiée. La méthode d’estimation est validée sur des données simulées puis mise en œuvre pour analyser les données de malaria.

Many articles were devoted to the problem of estimating recursively the eigenvectors and eigenvalues in decreasing order of the expectation of a random matrix using an i.i.d. sample of it. The present study makes the following contributions. The convergence of a normed process is proved under more general assumptions: the random matrices are not supposed i.i.d. and a new data mini-batch or all data until the current step are taken into account at each step without storing them; three types of processes are studied; this is applied to online principal component analysis of a data stream, assuming that data are realizations of a random vector Z whose expectation is unknown and must be estimated online, as well as possibly the metrics used when it depends on unknown characteristics of Z.

2000 Mathematics Subject Classification: 62G07, 62L20., Tsybakov [31] introduced the method of stochastic approximation to construct a recursive estimator of the location q of the mode of a probability density. The aim of this paper is to provide a companion algorithm to Tsybakov's algorithm, which allows to simultaneously recursively approximate the size m of the mode. We provide a precise study of the joint weak convergence rate of both estimators. Moreover, we introduce the averaging principle of stochastic approximation algorithms to construct asymptotically efficient algorithms approximating the couple (q,m).

Pricing is an effective tool to control congestion and achieve quality of service (QoS) provisioning for multiple differentiated levels of service. In this paper, we consider the problem of pricing for congestion control in the case of a network of nodes with multiple queues and multiple grades of service. We present a closed-loop multi-layered pricing scheme and propose an algorithm for finding the optimal state dependent price levels for individual queues, at each node. This is different from most adaptive pricing schemes in the literature that do not obtain a closed-loop state dependent pricing policy. The method that we propose finds optimal price levels that are functions of the queue lengths at individual queues. Further, we also propose a variant of the above scheme that assigns prices to incoming packets at each node according to a weighted average queue length at that node. This is done to reduce frequent price variations and is in the spirit of the random early detection (RED) mechanism used in TCP/IP networks. We observe in our numerical results a considerable improvement in performance using both of our schemes over that of a recently proposed related scheme in terms of both throughput and delay performance. In particular, our first scheme exhibits a throughput improvement in the range of 67-82% among all routes over the above scheme. (C) 2011 Elsevier B.V. All rights reserved.

Stochastic approximation algorithms have been the subject of an enormous body of literature, both theoretical and applied. Recently, Laruelle and Pages [Ann. Appl. Probab. 23 (2013) 1409–1436] presented a link between the stochastic approximation and response-adaptive designs in clinical trials based on randomized urn models investigated in Bai and Hu [Stochastic Process. Appl. 80 (1999) 87–101; Ann. Appl. Probab. 15 (2005) 914–940], and derived the asymptotic normality or central limit theorem for the normalized procedure using a central limit theorem for the stochastic approximation algorithm. However, the classical central limit theorem for the stochastic approximation algorithm does not include all cases of its regression function, creating a gap between the results of Laruelle and Pages [Ann. Appl. Probab. 23 (2013) 1409–1436] and those of Bai and Hu [Ann. Appl. Probab. 15 (2005) 914–940] for randomized urn models. In this paper, we establish new central limit theorems of the stochastic approximation algorithm under the popular Lindeberg condition to fill this gap. Moreover, we prove that the process of the algorithms can be approximated by a Gaussian process that is a solution of a stochastic differential equation. In our application, we investigate a more involved family of urn models and related adaptive designs in which it is possible to remove the balls from the urn, and the expectation of the total number of balls updated at each stage is not necessary a constant. The asymptotic properties are derived under much less stringent assumptions than those in Bai and Hu [Stochastic Process. Appl. 80 (1999) 87–101; Ann. Appl. Probab. 15 (2005) 914–940] and Laruelle and Pages [Ann. Appl. Probab. 23 (2013) 1409–1436].

Our aim in this Ph. D. thesis is to study the diffusion of information as well as the opinion dynamics of users in social networks. Information diffusion models explore the paths taken by information being transmitted through a social network in order to understand and analyze the relationships between users in such network, leading to a better comprehension of human relations and dynamics. This thesis is based on both sides of information diffusion: first by developing mathematical theories and models to study the relationships between people and information, and in a second time by creating tools to better exploit the hidden patterns in these relationships. The theoretical tools developed in this thesis are opinion dynamics models and information diffusion models, where we study the information flow from users in social networks, and the practical tools developed in this thesis are a novel community detection algorithm and a novel trend detection algorithm. We start by introducing an opinion dynamics model in which agents interact with each other about several distinct opinions/contents. In our framework, agents do not exchange all their opinions with each other, they communicate about randomly chosen opinions at each time. We show, using stochastic approximation algorithms, that under mild assumptions this opinion dynamics algorithm converges as time increases, whose behavior is ruled by how users choose the opinions to broadcast at each time. We develop next a community detection algorithm which is a direct application of this opinion dynamics model: when agents broadcast the content they appreciate the most. Communities are thus formed, where they are defined as groups of users that appreciate mostly the same content. This algorithm, which is distributed by nature, has the remarkable property that the discovered communities can be studied from a solid mathematical standpoint. In addition to the theoretical advantage over heuristic community detection methods, the presented algorithm is able to accommodate weighted networks, parametric and nonparametric versions, with the discovery of overlapping communities a byproduct with no mathematical overhead. In a second part, we define a general framework to model information diffusion in social networks. The proposed framework takes into consideration not only the hidden interactions between users, but as well the interactions between contents and multiple social networks. It also accommodates dynamic networks and various temporal effects of the diffusion. This framework can be combined with topic modeling, for which several estimation techniques are derived, which are based on nonnegative tensor factorization techniques. Together with a dimensionality reduction argument, this techniques discover, in addition, the latent community structure of the users in the social networks. At last, we use one instance of the previous framework to develop a trend detection algorithm designed to find trendy topics in a social network. We take into consideration the interaction between users and topics, we formally define trendiness and derive trend indices for each topic being disseminated in the social network. These indices take into consideration the distance between the real broadcast intensity and the maximum expected broadcast intensity and the social network topology. The proposed trend detection algorithm uses stochastic control techniques in order calculate the trend indices, is fast and aggregates all the information of the broadcasts into a simple one-dimensional process, thus reducing its complexity and the quantity of necessary data to the detection. To the best of our knowledge, this is the first trend detection algorithm that is based solely on the individual performances of topics, La dissémination d'information explore les chemins pris par l'information qui est transmise dans un réseau social, afin de comprendre et modéliser les relations entre les utilisateurs de ce réseau, ce qui permet une meilleur compréhension des relations humaines et leurs dynamique. Même si la priorité de ce travail soit théorique, en envisageant des aspects psychologiques et sociologiques des réseaux sociaux, les modèles de dissémination d'information sont aussi à la base de plusieurs applications concrètes, comme la maximisation d'influence, la prédication de liens, la découverte des noeuds influents, la détection des communautés, la détection des tendances, etc. Cette thèse est donc basée sur ces deux facettes de la dissémination d'information: nous développons d'abord des cadres théoriques mathématiquement solides pour étudier les relations entre les personnes et l'information, et dans un deuxième moment nous créons des outils responsables pour une exploration plus cohérente des liens cachés dans ces relations. Les outils théoriques développés ici sont les modèles de dynamique d'opinions et de dissémination d'information, où nous étudions le flot d'informations des utilisateurs dans les réseaux sociaux, et les outils pratiques développés ici sont un nouveau algorithme de détection de communautés et un nouveau algorithme de détection de tendances dans les réseaux sociaux

Consumer reviews and ratings of products and services have become ubiquitous on the Internet. This paper analyzes, given the sequential nature of reviews and the limited feedback of such past reviews, the information content they communicate to future customers. We consider a model with heterogeneous customers who buy a product of unknown quality and we focus on two different informational settings. In the first setting, customers observe the whole history of past reviews. In the second one they only observe the sample mean of past reviews. We examine under which conditions, in each setting, customers can recover the true quality of the product based on the feedback they observe. In the case of total monitoring, if consumers adopt a fully rational Bayesian updating paradigm, then they asymptotically learn the unknown quality. With access to only the sample mean of past reviews, inference becomes intricate for customers and it is not clear if, when, and how social learning can take place. We first analyze the setting when customers interpret the mean as the proxy of quality. We show that in the long run, the sample mean of reviews stabilizes and, in general, customers overestimate the underlying quality of the product. We establish properties of the bias, stemming from the selection associated with observing only reviews of customers who purchase. Then, we show the existence of a simple non-Bayesian quality inference rule that leads to social learning when all customers use such a rule. The results point to the strong information content of even limited statistics of past reviews as long as customers have minimal sophistication.

We obtain new transport-entropy inequalities and, as a by-product, new deviation estimates for the laws of two kinds of discrete stochastic approximation schemes. The first one refers to the law of an Euler like discretization scheme of a diffusion process at a fixed deterministic date and the second one concerns the law of a stochastic approximation algorithm at a given time-step. Our results notably improve and complete those obtained in [Frikha, Menozzi,2012]. The key point is to properly quantify the contribution of the diffusion term to the concentration regime. We also derive a general non-asymptotic deviation bound for the difference between a function of the trajectory of a continuous Euler scheme associated to a diffusion process and its mean. Finally, we obtain non-asymptotic bound for stochastic approximation with averaging of trajectories, in particular we prove that averaging a stochastic approximation algorithm with a slow decreasing step sequence gives rise to optimal concentration rate., Comment: 35 pages

This is an erratum for paper " Concentration bounds for stochastic approximation " appeared in ECP volume 17 paper number 47 .

We obtain non asymptotic concentration bounds for two kinds of stochastic approximations. We first consider the deviations between the expectation of a given function of the Euler scheme of some diffusion process at a fixed deterministic time and its empirical mean obtained by the Monte-Carlo procedure. We then give some estimates concerning the deviation between the value at a given time-step of a stochastic approximation algorithm and its target. Under suitable assumptions both concentration bounds turn out to be Gaussian. The key tool consists in exploiting accurately the concentration properties of the increments of the schemes. For the first case, as opposed to the previous work of Lemaire and Menozzi (EJP, 2010), we do not have any systematic bias in our estimates. Also, no specific non-degeneracy conditions are assumed., 14 pages

The problem of the definition and the estimation of generative models based on deformable templates from raw data is of particular importance for modelling non aligned data affected by various types of geometrical variability. This is especially true in shape modelling in the computer vision community or in probabilistic atlas building for Computational Anatomy (CA). A first coherent statistical framework modelling the geometrical variability as hidden variables has been given by Allassonniere, Amit and Trouve (JRSS 2006). Setting the problem in a Bayesian context they proved the consistency of the MAP estimator and provided a simple iterative deterministic algorithm with an EM flavour leading to some reasonable approximations of the MAP estimator under low noise conditions. In this paper we present a stochastic algorithm for approximating the MAP estimator in the spirit of the SAEM algorithm. We prove its convergence to a critical point of the observed likelihood with an illustration on images of handwritten digits.

The problem of the definition and the estimation of generative models based on deformable templates from raw data is of particular importance for modelling non aligned data affected by various types of geometrical variability. This is especially true in shape modelling in the computer vision community or in probabilistic atlas building for Computational Anatomy (CA). A first coherent statistical framework modelling the geometrical variability as hidden variables has been given by Allassonni\`ere, Amit and Trouv\'e (JRSS 2006). Setting the problem in a Bayesian context they proved the consistency of the MAP estimator and provided a simple iterative deterministic algorithm with an EM flavour leading to some reasonable approximations of the MAP estimator under low noise conditions. In this paper we present a stochastic algorithm for approximating the MAP estimator in the spirit of the SAEM algorithm. We prove its convergence to a critical point of the observed likelihood with an illustration on images of handwritten digits.