The Frank-Wolfe (FW) optimization algorithm, due to its projection free property, has gained popularity in recent years with typical application within the field of machine learning. In the stochastic setting, it is still relatively understudied in comparison to the more expensive projected method of Stochastic Gradient Descent (SGD). We propose a novel Stochastic Frank-Wolfe (SFW) algorithm, inspired by SGDo where random sampling is considered without replacement. In analogy to this abbreviation, we call the proposed algorithm SFWo. We consider a convex setting of gradient Lipschitz (smooth) functions over compact domains. Depending on experiment design (LASSO, Matrix Sensing, Matrix Completion), the SFWo algorithm, exhibits a faster or matching empirical convergence, and a tendency of bounded suboptimality by the precursor SFW. Benchmarks on both synthetic and real world data display that SFWo improves on the number of stochastic gradient evaluations needed to achieve the same guarantee as SFW. / Intresset för Frank-Wolfes (FW) optimeringsalgoritm har tack vare dess projektionsfria egenskap ökat de senaste åren med typisk tillämpning inom området maskininlärning. I sitt stokastiska uförande är den fortfarande relativt understuderad i jämförelse med den dyrare projicerande metoden Stochastic Gradient Descent (SGD). Vi föreslår en ny Stochastic Frank-Wolfe(SFW) algoritm, inspirerad av SGDo där slumpmässigt urval görs utan återläggning. I analogi med denna förkortning så kallar vi den föreslagna algoritmen SFWo. Vi betraktar en konvex miljö och gradient Lipschitz kontinuerliga (släta) funktioner över kompakta definitionsmängder. Beroende på experimentdesign (LASSO, Matrix Sensing, Matrix Completion) så visar den föreslagna algoritmen SFWo på en snabbare eller matchande empirisk konvergens och tenderar vara begränsad i suboptimalitet av föregångaren SFW. Prestandajämförelser på både syntetisk och verklig data visar att SFWo förbättrarantalet stokastiska gradientevalueringar som behövs för att uppnå samma garanti som för SFW.

Disertacijoje tiriamos negrąžintinių imčių pozicinių statistikų tiesinių kombinacijų (L-statistikų) savybės. Pagrindinis disertacijos uždavinys yra L-statistikų skirstinių normaliosios aproksimacijos patikslinimas trumpaisiais Edgeworth'o skleidiniais. Šių aproksimacijų tikslumui įvertinti disertacijoje naudojamas baigtinių populiacijų simetrinių statistikų Hoeffding'o skleidinys. Pirmame disertacijos skyriuje gautos išreikštinės pirmųjų L-statistikos Hoeffding'o skleidinio narių ir skleidinio liekamųjų narių formulės. Jomis naudojantis, antrame disertacijos skyriuje išspręsti tokie uždaviniai: gautas optimalus imties ekstremaliųjų reikšmių dispersijų viršutinysis įvertis; nustatytos pakankamosios L-statistikų asimptotinio normalumo sąlygos; sukonstruotas trumpasis L-statistikos Edgeworth'o skleidinys ir nustatytos pakankamosios šios aproksimacijos sąlygos. Trečiame disertacijos skyriuje sukonstruoti L-statistikos dispersijos ir Edgeworth'o skleidinio parametrų įvertiniai. Ketvirtame disertacijos skyriuje sukonstruoti ir ištirti Stjudentizuotų ir kartotinių imčių L-statistikų trumpieji Edgeworth'o skleidiniai. / Properties of linear combinations of order statistics (L-statistics), where samples are drawn without replacement, are considered in the thesis. The main object of the thesis is an improvement of the normal approximation to distributions of L-statistics by one-term Edgeworth expansions. An accuracy of these approximations is estimated using the Hoeffding decomposition of finite population symmetric statistics. In the first chapter of the thesis, explicit expressions of the first terms and remainder terms of the Hoeffding decomposition of L-statistics are obtained. The main applications of the decomposition are given in the second chapter: the optimal upper bound for variances of the sample minimum and maximum is obtained; sufficient conditions for the asymptotic normality of L-statistics are established; the one-term Edgeworth expansion for L-statistics is constructed and sufficient conditions for the validity of this approximation are obtained. In the third chapter, estimators of the variance and parameters that define the Edgeworth expansion of an L-statistic are constructed. In the fourth chapter, a one-term Edgeworth expansion for a Studentized L-statistic and empirical Edgeworth expansions are constructed and analyzed.

Ce document rassemble les travaux effectués durant mes années de thèse. Je commence par une présentation concise des résultats principaux, puis viennent trois parties relativement indépendantes.Dans la première partie, je considère des problèmes d'inférence statistique sur un échantillon i.i.d. issu d'une loi inconnue à support dénombrable. Le premier chapitre est consacré aux propriétés de concentration du profil de l'échantillon et de la masse manquante. Il s'agit d'un travail commun avec Stéphane Boucheron et Mesrob Ohannessian. Après avoir obtenu des bornes sur les variances, nous établissons des inégalités de concentration de type Bernstein, et exhibons un vaste domaine de lois pour lesquelles le facteur de variance dans ces inégalités est tendu. Le deuxième chapitre présente un travail en cours avec Stéphane Boucheron et Elisabeth Gassiat, concernant le problème de la compression universelle adaptative d'un tel échantillon. Nous établissons des bornes sur la redondance minimax des classes enveloppes, et construisons un code quasi-adaptatif sur la collection des classes définies par une enveloppe à variation régulière. Dans la deuxième partie, je m'intéresse à des marches aléatoires sur des graphes aléatoires à degrés precrits. Je présente d'abord un résultat obtenu avec Justin Salez, établissant le phénomène de cutoff pour la marche sans rebroussement. Sous certaines hypothèses sur les degrés, nous déterminons précisément le temps de mélange, la fenêtre du cutoff, et montrons que le profil de la distance à l'équilibre converge vers la fonction de queue gaussienne. Puis je m'intéresse à la comparaison des temps de mélange de la marche simple et de la marche sans rebroussement. Enfin, la troisième partie est consacrée aux propriétés de concentration de tirages pondérés sans remise et correspond à un travail commun avec Yuval Peres et Justin Salez. / This document presents the problems I have been interested in during my PhD thesis. I begin with a concise presentation of the main results, followed by three relatively independent parts. In the first part, I consider statistical inference problems on an i.i.d. sample from an unknown distribution over a countable alphabet. The first chapter is devoted to the concentration properties of the sample's profile and of the missing mass. This is a joint work with Stéphane Boucheron and Mesrob Ohannessian. After obtaining bounds on variances, we establish Bernstein-type concentration inequalities and exhibit a vast domain of sampling distributions for which the variance factor in these inequalities is tight. The second chapter presents a work in progress with Stéphane Boucheron and Elisabeth Gassiat, on the problem of universal adaptive compression over countable alphabets. We give bounds on the minimax redundancy of envelope classes, and construct a quasi-adaptive code on the collection of classes defined by a regularly varying envelope. In the second part, I consider random walks on random graphs with prescribed degrees. I first present a result obtained with Justin Salez, establishing the cutoff phenomenon for non-backtracking random walks. Under certain degree assumptions, we precisely determine the mixing time, the cutoff window, and show that the profile of the distance to equilibrium converges to the Gaussian tail function. Then I consider the problem of comparing the mixing times of the simple and non-backtracking random walks. The third part is devoted to the concentration properties of weighted sampling without replacement and corresponds to a joint work with Yuval Peres and Justin Salez.

No description available.

Dans cette thèse, nous nous intéressons à l'estimation de la synchrone de consommation électrique (courbe moyenne). Etant donné que les variables étudiées sont fonctionnelles et que les capacités de stockage sont limitées et les coûts de transmission élevés, nous nous sommes intéressés à des méthodes d'estimation par sondage, alternatives intéressantes aux techniques de compression du signal. Nous étendons au cadre fonctionnel des méthodes d'estimation qui prennent en compte l'information auxiliaire disponible afin d'améliorer la précision de l'estimateur de Horvitz-Thompson de la courbe moyenne de consommation électrique. La première méthode fait intervenir l'information auxiliaire au niveau de l'estimation, la courbe moyenne est estimée à l'aide d'un estimateur basé sur un modèle de régression fonctionnelle. La deuxième l'utilise au niveau du plan de sondage, nous utilisons un plan à probabilités inégales à forte entropie puis l'estimateur de Horvitz-Thompson fonctionnel. Une estimation de la fonction de covariance est donnée par l'extension au cadre fonctionnel de l'approximation de la covariance donnée par Hájek. Nous justifions de manière rigoureuse leur utilisation par une étude asymptotique. Pour chacune de ces méthodes, nous donnons, sous de faibles hypothèses sur les probabilités d'inclusion et sur la régularité des trajectoires, les propriétés de convergence de l'estimateur de la courbe moyenne ainsi que de sa fonction de covariance. Nous établissons également un théorème central limite fonctionnel. Afin de contrôler la qualité de nos estimateurs, nous comparons deux méthodes de construction de bande de confiance sur un jeu de données de courbes de charge réelles. La première repose sur la simulation de processus gaussiens. Une justification asymptotique de cette méthode sera donnée pour chacun des estimateurs proposés. La deuxième utilise des techniques de bootstrap qui ont été adaptées afin de tenir compte du caractère fonctionnel des données / In this thesis, we are interested in estimating the mean electricity consumption curve. Since the study variable is functional and storage capacities are limited or transmission cost are high survey sampling techniques are interesting alternatives to signal compression techniques. We extend, in this functional framework, estimation methods that take into account available auxiliary information and that can improve the accuracy of the Horvitz-Thompson estimator of the mean trajectory. The first approach uses the auxiliary information at the estimation stage, the mean curve is estimated using model-assisted estimators with functional linear regression models. The second method involves the auxiliary information at the sampling stage, considering πps (unequal probability) sampling designs and the functional Horvitz-Thompson estimator. Under conditions on the entropy of the sampling design the covariance function of the Horvitz-Thompson estimator can be estimated with the Hájek approximation extended to the functional framework. For each method, we show, under weak hypotheses on the sampling design and the regularity of the trajectories, some asymptotic properties of the estimator of the mean curve and of its covariance function. We also establish a functional central limit theorem.Next, we compare two methods that can be used to build confidence bands. The first one is based on simulations of Gaussian processes and is assessed rigorously. The second one uses bootstrap techniques in a finite population framework which have been adapted to take into account the functional nature of the data