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. / 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.

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 En du vecteur aléatoire Zn dont sont issues les observations varie dans le temps. On note Rn = Zn - En et on suppose que les vecteurs Rn forment un échantillon indépendant et identiquement distribué d'un vecteur aléatoire R. 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 R. 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 / 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 En varies with time. Let Rn = Zn - En be and suppose that the vectors Rn form an independent and identically distributed sample of a random vector R. Stochastic approximation processes are used to estimate on-line direction vectors of the principal axes of a partial principal components analysis (PCA) of ~Z. 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

L'entrée en application depuis le 1er Janvier 2016 de la réforme réglementaire européenne du secteur des assurances Solvabilité 2 est un événement historique qui va changer radicalement les pratiques en matière de gestion des risques. Elle repose sur une prise en compte importante du profil et de la vision du risque, via la possibilité d'utiliser des modèles internes pour calculer les capitaux de solvabilité et l'approche ORSA (Own Risk and Solvency Assessment) pour la gestion interne du risque. La modélisation mathématique est ainsi un outil indispensable pour réussir un exercice réglementaire. La théorie du risque doit être en mesure d'accompagner ce développement en proposant des réponses à des problématiques pratiques, liées notamment à la modélisation des dépendances et aux choix des mesures de risques. Dans ce contexte, cette thèse présente une contribution à l'amélioration de la gestion des risques actuariels. En quatre chapitres nous présentons des mesures multivariées de risque et leurs applications à l'allocation du capital de solvabilité. La première partie de cette thèse est consacrée à l'introduction et l'étude d'une nouvelle famille de mesures multivariées élicitables de risque qu'on appellera des expectiles multivariés. Son premier chapitre présente ces mesures et explique les différentes approches utilisées pour les construire. Les expectiles multivariés vérifient un ensemble de propriétés de cohérence que nous abordons aussi dans ce chapitre avant de proposer un outil d'approximation stochastique de ces mesures de risque. Les performances de cette méthode étant insuffisantes au voisinage des niveaux asymptotiques des seuils des expectiles, l'analyse théorique du comportement asymptotique est nécessaire, et fera le sujet du deuxième chapitre de cette partie. L'analyse asymptotique est effectuée dans un environnement à variations régulières multivariées, elle permet d'obtenir des résultats dans le cas des queues marginales équivalentes. Nous présentons aussi dans le deuxième chapitre le comportement asymptotique des expectiles multivariés sous les hypothèses précédentes en présence d'une dépendance parfaite, ou d'une indépendance asymptotique, et nous proposons à l'aide des statistiques des valeurs extrêmes des estimateurs de l'expectile asymptotique dans ces cas. La deuxième partie de la thèse est focalisée sur la problématique de l'allocation du capital de solvabilité en assurance. Elle est composée de deux chapitres sous forme d'articles publiés. Le premier présente une axiomatisation de la cohérence d'une méthode d'allocation du capital dans le cadre le plus général possible, puis étudie les propriétés de cohérence d'une approche d'allocation basée sur la minimisation d'indicateurs multivariés de risque. Le deuxième article est une analyse probabiliste du comportement de cette dernière approche d'allocation en fonction de la nature des distributions marginales des risques et de la structure de la dépendance. Le comportement asymptotique de l'allocation est aussi étudié et l'impact de la dépendance est illustré par différents modèles marginaux et différentes copules. La présence de la dépendance entre les différents risques supportés par les compagnies d'assurance fait de l'approche multivariée une réponse plus appropriée aux différentes problématiques de la gestion des risques. Cette thèse est fondée sur une vision multidimensionnelle du risque et propose des mesures de nature multivariée qui peuvent être appliquées pour différentes problématiques actuarielles de cette nature / The entry into force since January 1st, 2016 of Solvency 2, the European regulatory reform of insurance industry, is a historic event that will radically change the practices in risk management. It is based on taking into account the own risk profile and the internal view of risk through the ability to use internal models for calculating solvency capital requirement and ORSA (Own Risk and Solvency Assessment) approach for internal risk management. It makes the mathematical modeling an essential tool for a successful regulatory exercise. The risk theory must allow to support this development by providing answers to practical problems, especially those related to the dependence modeling and the choice of risk measures. In the same context, this thesis presents a contribution to improving the management of insurance risks. In four chapters we present multivariate risk measures and their application to the allocation of solvency capital. The first part of this thesis is devoted to the introduction and study of a new family of multivariate elicitable risk measures that we will call multivariate expectiles. The first chapter presents these measures and explains the different construction approaches. The multivariate expectiles verify a set of coherence properties that we also discuss in this chapter before proposing a stochastic approximation tool of these risk measures. The performance of this method is insufficient in the asymptotic levels of the expectiles thresholds. That makes the theoretical analysis of the asymptotic behavior necessary. The asymptotic behavior of multivariate expectiles is then the subject of the second chapter of this part. It is studied in a multivariate regular variations framework, and some results are given in the case of equivalent marginal tails. We also study in the second chapter of the first part the asymptotic behavior of multivariate expectiles under previous assumptions in the presence of a perfect dependence, or in the case of asymptotic independence. Finally, we propose using extreme values statistics some estimators of the asymptotic expectile in these cases. The second part of the thesis is focused on the issue of solvency capital allocation in insurance. It is divided into two chapters; each chapter consists of a published paper. The first one presents an axiomatic characterization of the coherence of a capital allocation method in a general framework. Then it studies the coherence properties of an allocation approach based on the minimization of some multivariate risk indicators. The second paper is a probabilistic analysis of the behavior of this capital allocation method based on the nature of the marginal distributions of risks and the dependence structure. The asymptotic behavior of the optimal allocation is also studied and the impact of dependence is illustrated using some selected models and copulas. Faced to the significant presence of dependence between the various risks taken by insurance companies, a multivariate approach seems more appropriate to build responses to the various issues of risk management. This thesis is based on a multidimensional vision of risk and proposes some multivariate risk measures that can be applied to several actuarial issues of a multivariate nature

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.

De multiples problèmes en apprentissage automatique consistent à minimiser une fonction lisse sur un espace euclidien. Pour l’apprentissage supervisé, cela inclut les régressions par moindres carrés et logistique. Si les problèmes de petite taille sont résolus efficacement avec de nombreux algorithmes d’optimisation, les problèmes de grande échelle nécessitent en revanche des méthodes du premier ordre issues de la descente de gradient. Dans ce manuscrit, nous considérons le cas particulier de la perte quadratique. Dans une première partie, nous nous proposons de la minimiser grâce à un oracle stochastique. Dans une seconde partie, nous considérons deux de ses applications à l’apprentissage automatique : au partitionnement de données et à l’estimation sous contrainte de forme. La première contribution est un cadre unifié pour l’optimisation de fonctions quadratiques non-fortement convexes. Celui-ci comprend la descente de gradient accélérée et la descente de gradient moyennée. Ce nouveau cadre suggère un algorithme alternatif qui combine les aspects positifs du moyennage et de l’accélération. La deuxième contribution est d’obtenir le taux optimal d’erreur de prédiction pour la régression par moindres carrés en fonction de la dépendance au bruit du problème et à l’oubli des conditions initiales. Notre nouvel algorithme est issu de la descente de gradient accélérée et moyennée. La troisième contribution traite de la minimisation de fonctions composites, somme de l’espérance de fonctions quadratiques et d’une régularisation convexe. Nous étendons les résultats existants pour les moindres carrés à toute régularisation et aux différentes géométries induites par une divergence de Bregman. Dans une quatrième contribution, nous considérons le problème du partitionnement discriminatif. Nous proposons sa première analyse théorique, une extension parcimonieuse, son extension au cas multi-labels et un nouvel algorithme ayant une meilleure complexité que les méthodes existantes. La dernière contribution de cette thèse considère le problème de la sériation. Nous adoptons une approche statistique où la matrice est observée avec du bruit et nous étudions les taux d’estimation minimax. Nous proposons aussi un estimateur computationellement efficace. / Many problems in machine learning are naturally cast as the minimization of a smooth function defined on a Euclidean space. For supervised learning, this includes least-squares regression and logistic regression. While small problems are efficiently solved by classical optimization algorithms, large-scale problems are typically solved with first-order techniques based on gradient descent. In this manuscript, we consider the particular case of the quadratic loss. In the first part, we are interestedin its minimization when its gradients are only accessible through a stochastic oracle. In the second part, we consider two applications of the quadratic loss in machine learning: clustering and estimation with shape constraints. In the first main contribution, we provided a unified framework for optimizing non-strongly convex quadratic functions, which encompasses accelerated gradient descent and averaged gradient descent. This new framework suggests an alternative algorithm that exhibits the positive behavior of both averaging and acceleration. The second main contribution aims at obtaining the optimal prediction error rates for least-squares regression, both in terms of dependence on the noise of the problem and of forgetting the initial conditions. Our new algorithm rests upon averaged accelerated gradient descent. The third main contribution deals with minimization of composite objective functions composed of the expectation of quadratic functions and a convex function. Weextend earlier results on least-squares regression to any regularizer and any geometry represented by a Bregman divergence. As a fourth contribution, we consider the the discriminative clustering framework. We propose its first theoretical analysis, a novel sparse extension, a natural extension for the multi-label scenario and an efficient iterative algorithm with better running-time complexity than existing methods. The fifth main contribution deals with the seriation problem. We propose a statistical approach to this problem where the matrix is observed with noise and study the corresponding minimax rate of estimation. We also suggest a computationally efficient estimator whose performance is studied both theoretically and experimentally.

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

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 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.