Nous considérons le problème de débruitage d'un signal ou d'une image observés dans le bruit gaussien. Dans ce problème les estimateurs linéaires classiques sont quasi-optimaux quand l'ensemble des signaux, qui doit être convexe et compact, est connu a priori. Si cet ensemble n'est pas spécifié, la conception d'un estimateur adaptatif qui ``ne connait pas'' la structure cachée du signal reste un problème difficile. Dans cette thèse, nous étudions une nouvelle famille d'estimateurs des signaux satisfaisant certains propriétés d'invariance dans le temps. De tels signaux sont caractérisés par leur structure harmonique, qui est généralement inconnu dans la pratique.Nous proposons des nouveaux estimateurs capables d'exploiter la structure harmonique inconnue du signal è reconstruire. Nous démontrons que ces estimateurs obéissent aux divers "inégalités d'oracle," et nous proposons une implémentation algorithmique numériquement efficace de ces estimateurs basée sur des algorithmes d'optimisation de "premier ordre." Nous évaluons ces estimateurs sur des données synthétiques et sur des signaux et images réelles. / We consider the problem of denoising a signal observed in Gaussian noise.In this problem, classical linear estimators are quasi-optimal provided that the set of possible signals is convex, compact, and known a priori. However, when the set is unspecified, designing an estimator which does not ``know'' the underlying structure of a signal yet has favorable theoretical guarantees of statistical performance remains a challenging problem. In this thesis, we study a new family of estimators for statistical recovery of signals satisfying certain time-invariance properties. Such signals are characterized by their harmonic structure, which is usually unknown in practice. We propose new estimators which are capable to exploit the unknown harmonic structure of a signal to reconstruct. We demonstrate that these estimators admit theoretical performance guarantees, in the form of oracle inequalities, in a variety of settings.We provide efficient algorithmic implementations of these estimators via first-order optimization algorithm with non-Euclidean geometry, and evaluate them on synthetic data, as well as some real-world signals and images.

Cette thèse consiste à étudier l'organisation du système de contrôle des voies métaboliques des bactéries afin de dégager des propriétés systémiques révélant son fonctionnement. Dans un premier temps, nous montrons que le contrôle des voies métaboliques est hautement structuré et peut se décomposer en modules fortement découplés en régime stationnaire. Ces modules possèdent des propriétés mathématiques remarquables ayant des conséquences importantes en biologie. Cette décomposition, basée intrinsèquement sur la vision système de l'Automatique, offre un cadre théorique formel général d'analyse du contrôle des voies métaboliques qui s'est révélé effectif pour analyser des données expérimentales. dans un deuxième temps, nous nous intéressons aux raisons possibles de l'émergence de cette structure de contrôle similaire. Nous identifions un ensemble de contraintes structurelles agissant au niveau de la répartition d'une ressource commune, les protéines, entre les processus cellulaires. Respecter ces contraintes pour un taux de croissance donné conduit à formaliser et résoudre un problème d'optimisation convexe non différentiable, que nous appelons Resource balance Analysis. Ce problème d'optimisation se résout numériquement à l'échelle de la bactérie grâce à un problème de Programmation Linéaire équivalent. plusieurs propriétés sont déduites de l'analyse théorique du critère obtenu. Tout d'abord, le taux de croissance est structurellement limité par la répartition d'une quantité finie de protéines entre les voies métaboliques et les ribosomes. Ensuite, l'émergence des modules dans les voies métaboliques provient d'une politique générale d'économie en protéines chez la bactérie pour gagner du taux de croissance. Certaines stratégies de transport bien connues comme la répression catabolique ou la substitution de transporteurs haute/basse affinités sont prédites par notre méthode et peuvent alors être interprétées comme le moyen de maximiser la croissance tout en minimisant l'investissement en protéines. / This thesis consist in studying the organization of the control system of metabolic pathways of bacteria to identify systemic properties revealing its operation. At first, we show that control of metabolic pathways is highly structured and can be decomposed into modules strongly decoupled in steady-state. These modules are defined by their singular mathematical properties having important implications in biology. This decomposition, based inherently on the system outlook of automatic control, offers a formal theoretical analysis of general control of metabolic pathways, which has been effective in analysing experimental data. In a second step, we consider the possible reasons for the emergence of this modular control structure. We identify a set of structural constraints acting at the distribution of a common resourc, the proteins between cellular processes. Satisfying these constraints for a given growth rate leads to formalize and to solve a non-differentiable convex optimization problem, that we call Resource Balance Analysis. This optimization problem is solved numerically at the scale of the bacteria through an equivalent linear programming problem. Several properties are derived from theoretical analysis of the obtained criterion. Firts, the growth rate is structurally limited by the distribution of a finite amount of proteines between the metabolic pathways and the ribosomes. Second, the emergence of modules in metabolic pathways arises from a policy of economy in proteins in the bacterium to increase the growth rate. Some well known transport strategies such as catabolite repression of the substitution between low/highaffinity transporters are predicted by our methods and could consequently be interpretd as ways to maximize growth while minimizing investment in proteins.

L’entropie d’une distribution sur un ensemble de variables aléatoires discrètes est toujours bornée par l’entropie de la distribution factorisée correspondante. Cette propriété est due à la sous-modularité de l’entropie. Par ailleurs, les fonctions sous-modulaires sont une généralisation des fonctions de rang des matroïdes ; ainsi, les fonctions linéaires sur les polytopes associés peuvent être minimisées exactement par un algorithme glouton. Dans ce manuscrit, nous exploitons ces liens entre les structures des modèles graphiques et les fonctions sous-modulaires. Nous utilisons des algorithmes gloutons pour optimiser des fonctions linéaires sur des polytopes liés aux matroïdes graphiques et hypergraphiques pour apprendre la structure de modèles graphiques, tandis que nous utilisons des algorithmes d’inférence sur les graphes pour optimiser des fonctions sous-modulaires. La première contribution de cette thèse consiste à approcher par maximum de vraisemblance une distribution de probabilité par une distribution factorisable et de complexité algorithmique contrôlée. Comme cette complexité est exponentielle dans la largeur arborescente du graphe, notre but est d’apprendre un graphe décomposable avec une largeur arborescente bornée, ce qui est connu pour être NP-difficile. Nous posons ce problème comme un problème d’optimisation combinatoire et nous proposons une relaxation convexe basée sur les matroïdes graphiques et hypergraphiques. Ceci donne lieu à une solution approchée avec une bonne performance pratique. Pour la seconde contribution principale, nous utilisons le fait que l’entropie d’une distribution est toujours bornée par l’entropie de sa distribution factorisée associée, comme conséquence principale de la sous-modularité, permettant une généralisation à toutes les fonctions sous-modulaires de bornes basées sur les concepts de modèles graphiques. Un algorithme est développé pour maximiser les fonctions sous-modulaires, un autre problème NP-difficile, en maximisant ces bornes en utilisant des algorithmes d’inférence vibrationnels sur les graphes. En troisième contribution, nous proposons et analysons des algorithmes visant à minimiser des fonctions sous-modulaires pouvant s’écrire comme somme de fonctions plus simples. Nos algorithmes n’utilisent que des oracles de ces fonctions simple basés sur minimisation sous-modulaires et de variation totale de telle fonctions. / The entropy of a probability distribution on a set of discrete random variables is always bounded by the entropy of its factorisable counterpart. This is due to the submodularity of entropy on the set of discrete random variables. Submodular functions are also generalisation of matroid rank function; therefore, linear functions may be optimised on the associated polytopes exactly using a greedy algorithm. In this manuscript, we exploit these links between the structures of graphical models and submodular functions: we use greedy algorithms to optimise linear functions on the polytopes related to graphic and hypergraphic matroids for learning the structures of graphical models, while we use inference algorithms on graphs to optimise submodular functions.The first main contribution of the thesis aims at approximating a probabilistic distribution with a factorisable tractable distribution under the maximum likelihood framework. Since the tractability of exact inference is exponential in the treewidth of the decomposable graph, our goal is to learn bounded treewidth decomposable graphs, which is known to be NP-hard. We pose this as a combinatorial optimisation problem and provide convex relaxations based on graphic and hypergraphic matroids. This leads to an approximate solution with good empirical performance. In the second main contribution, we use the fact that the entropy of a probability distribution is always bounded by the entropy of its factorisable counterpart mainly as a consequence of submodularity. This property of entropy is generalised to all submodular functions and bounds based on graphical models are proposed. We refer to them as graph-based bounds. An algorithm is developped to maximise submodular functions, which is NPhard, by maximising the graph-based bound using variational inference algorithms on graphs. As third contribution, we propose and analyse algorithms aiming at minimizing submodular functions that can be written as sum of simple functions. Our algorithms only make use of submodular function minimisation and total variation oracles of simple functions.

Cette thèse est particulièrement destinée à traiter deux types de problèmes : clustering et l'alignement multiple de séquence. Notre objectif est de résoudre de manière satisfaisante ces problèmes globaux et de tester l'approche de la Programmation DC et DCA sur des jeux de données réelles. La thèse comporte trois parties : la première partie est consacrée aux nouvelles approches de l'optimisation non convexe. Nous y présentons une étude en profondeur de l'algorithme qui est utilisé dans cette thèse, à savoir la programmation DC et l'algorithme DC (DCA). Dans la deuxième partie, nous allons modéliser le problème clustering en trois sous-problèmes non convexes. Les deux premiers sous-problèmes se distinguent par rapport au choix de la norme utilisée, (clustering via les normes 1 et 2). Le troisième sous-problème utilise la méthode du noyau, (clustering via la méthode du noyau). La troisième partie sera consacrée à la bio-informatique. On va se focaliser sur la modélisation et la résolution de deux sous-problèmes : l'alignement multiple de séquence et l'alignement de séquence d'ARN par structure. Tous les chapitres excepté le premier se terminent par des tests numériques. / This Ph.D. thesis is particularly intended to treat two types of problems : clustering and the multiple alignment of sequence. Our objective is to solve efficiently these global problems and to test DC Programming approach and DCA on real datasets. The thesis is divided into three parts : the first part is devoted to the new approaches of nonconvex optimization-global optimization. We present it a study in depth of the algorithm which is used in this thesis, namely the programming DC and the algorithm DC ( DCA). In the second part, we will model the problem clustering in three nonconvex subproblems. The first two subproblems are distinguished compared to the choice from the norm used, (clustering via norm 1 and 2). The third subproblem uses the method of the kernel, (clustering via the method of the kernel). The third part will be devoted to bioinformatics, one goes this focused on the modeling and the resolution of two subproblems : the multiple alignment of sequence and the alignment of sequence of RNA. All the chapters except the first end in numerical tests.

Le problème de l'adaptation d'impédance en ingénierie des hyper fréquences et en électronique en général consiste à minimiser la réflexion de la puissance qui doit être transmise, par un générateur, à une charge donnée dans une bande de fréquence. Les exigences d'adaptation et de filtrage dans les systèmes de communication classiques sont généralement satisfaites en utilisant un circuit d'adaptation suivi d'un filtre. Nous proposons ici de concevoir des filtres d'adaptation qui intègrent à la fois les exigences d'adaptation et de filtrage dans un seul appareil et augmentent ainsi l'efficacité globale et la compacité du système. Dans ce travail, le problème d'adaptation est formulé en introduisant un problème d'optimisation convexe dans le cadre établi par la théorie de d'adaptation de Fano et Youla. De ce contexte, au moyen de techniques modernes de programmation semi-définies non linéaires, un problème convexe, et donc avec une optimalité garantie, est obtenu. Enfin, pour démontrer les avantages fournis par la théorie développée au-delà de la synthèse de filtres avec des charges complexes variables en fréquence, nous examinons deux applications pratiques récurrentes dans la conception de ce type de dispositifs. Ces applications correspondent, d'une part, à l'adaptation d'un réseau d'antennes dans le but de maximiser l'efficacité du rayonnement, et, d'autre part, à la synthèse de multiplexeurs où chacun des filtres de canal est adapté au reste du dispositif, notamment les filtres correspondant aux autres canaux. / The problem of impedance matching in electronics and particularly in RF engineering consists on minimising the reflection of the power that is to be transmitted, by a generator, to a given load within a frequency band. The matching and filtering requirements in classical communication systems are usually satisfied by using a matching circuit followed by a filter. We propose here to design matching filters that integrate both, matching and filtering requirements, in a single device and thereby increase the overall efficiency and compactness of the system. In this work, the matching problem is formulated by introducing convex optimisation on the framework established by the matching theory of Fano and Youla. As a result, by means of modern non-linear semi-definite programming techniques, a convex problem, and therefore with guaranteed optimality, is achieved. Finally, to demonstrate the advantages provided by the developed theory beyond the synthesis of filters with frequency varying loads, we consider two practical applications which are recurrent in the design of communication devices. These applications are, on the one hand, the matching of an array of antennas with the objective of maximizing the radiation efficiency, and on the other hand the synthesis of multiplexers where each of the channel filters is matched to the rest of the device, including the filters corresponding to the other channels.

L’estimation des matrices origine-destination (OD) est un sujet de recherche important depuis les années 1950. En effet, ces tableaux à deux entrées recensent la demande de transport d'une zone géographique donnée et sont de ce fait un élément clé de l'ingénierie du trafic. Historiquement, les seules données disponibles pour leur estimation par les statistiques étaient les comptages de véhicules par les boucles magnétiques. Ce travail s'inscrit alors dans le contexte de l'installation à Brisbane de plus de 600 détecteurs Bluetooth qui ont la capacité de détecter et d'identifier les appareils électroniques équipés de cette technologie.Dans un premier temps, il explore la possibilité offerte par ces détecteurs pour les applications en ingénierie du transport en caractérisant ces données et leurs bruits. Ce projet aboutit, à l'issue de cette étude, à une méthode de reconstruction des trajectoires des véhicules équipés du Bluetooth à partir de ces seules données. Dans un second temps, en partant de l'hypothèse que l'accès à des échantillons importants de trajectoires va se démocratiser, cette thèse propose d'étendre la notion de matrice OD à celle de matrice OD par lien afin de combiner la description de la demande avec celle de l'utilisation du réseau. Reposant sur les derniers outils méthodologies développés en optimisation convexe, nous proposons une méthode d'estimation de ces matrices à partir des trajectoires inférées par Bluetooth et des comptages routiers.A partir de peu d'hypothèses, il est possible d'inférer ces nouvelles matrices pour l'ensemble des utilisateurs d'un réseau routier (indépendamment de leur équipement en nouvelles technologies). Ce travail se distingue ainsi des méthodes traditionnelles d'estimation qui reposaient sur des étapes successives et indépendantes d'inférence et de modélisation. / Origin Destination matrix estimation is a critical problem of the Transportation field since the fifties. OD matrix is a two-entry table taking census of the zone-to-zone traffic of a geographic area. This traffic description tools is therefore paramount for traffic engineering applications. Traditionally, the OD matrix estimation has solely been based on traffic counts collected by networks of magnetic loops. This thesis takes place in a context with over 600 Bluetooth detectors installed in the City of Brisbane. These detectors permit in-car Bluetooth device detection and thus vehicle identification.This manuscript explores first, the potentialities of Bluetooth detectors for Transport Engineering applications by characterising the data, their noises and biases. This leads to propose a new methodology for Bluetooth equipped vehicle trajectory reconstruction. In a second step, based on the idea that probe trajectories will become more and more available by means of new technologies, this thesis proposes to extend the concept of OD matrix to the one of link dependent origin destination matrix that describes simultaneously both the traffic demand and the usage of the network. The problem of LOD matrix estimation is formulated as a minimisation problem based on probe trajectories and traffic counts and is then solved thanks to the latest advances in nonsmooth convex optimisation.This thesis demonstrates that, with few hypothesis, it is possible to retrieve the LOD matrix for the whole set of users in a road network. It is thus different from traditional OD matrix estimation approaches that relied on successive steps of modelling and of statistical inferences.

L'objectif général est de développer un nouvel outil numérique dédié à la focalisation en 3D de l'énergie en zone de champ très proche par un système antennaire. Cet outil permettra de définir la distribution spatiale complexe des champs dans l'ouverture rayonnante afin de focaliser l'énergie sur un volume quelconque en zone de champ réactif. L'hybridation de cet outil avec un code de calcul dédié à l'analyse rapide d‘antennes SIW par la méthode des moments permettra de synthétiser une antenne SIW ad-hoc. Les structures antennaires sélectionnées seront planaires comme par exemple les antennes RLSA (Radial Line Slot Array). Les dimensions de l'antenne (positions, dimensions et nombre de fentes) seront définies à l'aide des outils décrits ci-dessus. Les résultats numériques ainsi obtenus seront validés d'abord numériquement par analyse électromagnétique globale à l'aide de simulateurs commerciaux, puis expérimentalement en ondes millimétriques (mesure en zone de champ très proche). Pour atteindre ces objectifs, nous avons défini quatre tâches principales : Développement d'un outil de synthèse de champ dans l'ouverture rayonnante (formulation théorique couplée à une méthode dite des projections alternées) ; développement d'un outil de calcul rapide (sur la base de traitements par FFT) du champ électromagnétique rayonné en zone de champ proche par une ouverture rayonnante, et retro-propagation ; hybridation de ces algorithmes avec un code de calcul (méthode des moments) en cours de développement à l'IETR et dédié à l'analyse très rapide d'antennes en technologie SIW ; conception d'une preuve ou plusieurs preuves de concept, et validations numérique et expérimentale des concepts proposés. / With the demand for near-field antennas continuously growing, the antenna engineer is charged with the development of new concepts and design procedures for this regime. From the microwave and up to terahertz frequencies, a vast number of applications, especially in the biomedical domain, are in need for focused or shaped fields in the antenna proximity. This work proposes new theoretical methods for near-field shaping based on different optimization schemes. Continuous radiating planar apertures are optimized to radiate a near field with required characteristics. In particular, a versatile optimization technique based on the alternating projection scheme is proposed. It is demonstrated that, based on this scheme, it is feasible to achieve 3-D control of focal spots generated by planar apertures. Additionally, with the same setup, also the vectorial problem (shaping the norm of the field) is addressed. Convex optimization is additionally introduced for near-field shaping of continuous aperture sources. The capabilities of this scheme are demonstrated in the context of different shaping scenarios. Additionally, the discussion is extended to shaping the field in lossy stratified media, based on a spectral Green's functions approach. Besides, the biomedical applications of wireless power transfer to implants and breast cancer imaging are addressed. For the latter, an extensive study is included here, which delivers an outstanding improvement on the penetration depth at higher frequencies. The thesis is completed by several prototypes used for validation. Four different antennas have been designed, based either on the radial line slot array topology or on metasurfaces. The prototypes have been manufactured and measured, validating the overall approach of the thesis.

L'imagerie par résonance magnétique fonctionnelle (IRMf) permet de mesurer l'activité cérébrale à travers le flux sanguin apporté aux neurones. Dans cette thèse nous évaluons la capacité de modèles biologiquement plausibles et issus de la vision par ordinateur à représenter le contenu d'une image de façon similaire au cerveau. Les principaux modèles de vision évalués sont les réseaux convolutionnels.Les réseaux de neurones profonds ont connu un progrès bouleversant pendant les dernières années dans divers domaines. Des travaux antérieurs ont identifié des similarités entre le traitement de l'information visuelle à la première et dernière couche entre un réseau de neurones et le cerveau. Nous avons généralisé ces similarités en identifiant des régions cérébrales correspondante à chaque étape du réseau de neurones. Le résultat consiste en une progression des niveaux de complexité représentés dans le cerveau qui correspondent à l'architecture connue des aires visuelles: Plus la couche convolutionnelle est profonde, plus abstraits sont ses calculs et plus haut niveau sera la fonction cérébrale qu'elle sait modéliser au mieux. Entre la détection de contours en V1 et la spécificité à l'objet en cortex inférotemporal, fonctions assez bien comprises, nous montrons pour la première fois que les réseaux de neurones convolutionnels de détection d'objet fournissent un outil pour l'étude de toutes les étapes intermédiaires du traitement visuel effectué par le cerveau.Un résultat préliminaire à celui-ci est aussi inclus dans le manuscrit: L'étude de la réponse cérébrale aux textures visuelles et sa modélisation avec les réseaux convolutionnels de scattering.L'autre aspect global de cette thèse sont modèles de “décodage”: Dans la partie précédente, nous prédisions l'activité cérébrale à partir d'un stimulus (modèles dits d’”encodage”). La prédiction du stimulus à partir de l'activité cérébrale est le méchanisme d'inférence inverse et peut servir comme preuve que cette information est présente dans le signal. Le plus souvent, des modèles linéaires généralisés tels que la régression linéaire ou logistique ou les SVM sont utilisés, donnant ainsi accès à une interprétation des coefficients du modèle en tant que carte cérébrale. Leur interprétation visuelle est cependant difficile car le problème linéaire sous-jacent est soit mal posé et mal conditionné ou bien non adéquatement régularisé, résultant en des cartes non-informatives. En supposant une organisation contigüe en espace et parcimonieuse, nous nous appuyons sur la pénalité convexe d'une somme de variation totale et la norme L1 (TV+L1) pour développer une pénalité regroupant un terme d'activation et un terme de dérivée spatiale. Cette pénalité a la propriété de mettre à zéro la plupart des coefficients tout en permettant une variation libre des coefficients dans une zone d'activation, contrairement à TV+L1 qui impose des zones d’activation plates. Cette méthode améliore l'interprétabilité des cartes obtenues dans un schéma de validation croisée basé sur la précision du modèle prédictif.Dans le contexte des modèles d’encodage et décodage nous tâchons à améliorer les prétraitements des données. Nous étudions le comportement du signal IRMf par rapport à la stimulation ponctuelle : la réponse impulsionnelle hémodynamique. Pour générer des cartes d'activation, au lieu d’un modèle linéaire classique qui impose une réponse impulsionnelle canonique fixe, nous utilisons un modèle bilinéaire à réponse hémodynamique variable spatialement mais fixe à travers les événements de stimulation. Nous proposons un algorithme efficace pour l'estimation et montrons un gain en capacité prédictive sur les analyses menées, en encodage et décodage. / Blood-oxygen-level dependent (BOLD) functional magnetic resonance imaging (fMRI) makes it possible to measure brain activity through blood flow to areas with metabolically active neurons. In this thesis we use these measurements to evaluate the capacity of biologically inspired models of vision coming from computer vision to represent image content in a similar way as the human brain. The main vision models used are convolutional networks.Deep neural networks have made unprecedented progress in many fields in recent years. Even strongholds of biological systems such as scene analysis and object detection have been addressed with enormous success. A body of prior work has been able to establish firm links between the first and last layers of deep convolutional nets and brain regions: The first layer and V1 essentially perform edge detection and the last layer as well as inferotemporal cortex permit a linear read-out of object category. In this work we have generalized this correspondence to all intermediate layers of a convolutional net. We found that each layer of a convnet maps to a stage of processing along the ventral stream, following the hierarchy of biological processing: Along the ventral stream we observe a stage-by-stage increase in complexity. Between edge detection and object detection, for the first time we are given a toolbox to study the intermediate processing steps.A preliminary result to this was obtained by studying the response of the visual areas to presentation of visual textures and analysing it using convolutional scattering networks.The other global aspect of this thesis is “decoding” models: In the preceding part, we predicted brain activity from the stimulus presented (this is called “encoding”). Predicting a stimulus from brain activity is the inverse inference mechanism and can be used as an omnibus test for presence of this information in brain signal. Most often generalized linear models such as linear or logistic regression or SVMs are used for this task, giving access to a coefficient vector the same size as a brain sample, which can thus be visualized as a brain map. However, interpretation of these maps is difficult, because the underlying linear system is either ill-defined and ill-conditioned or non-adequately regularized, resulting in non-informative maps. Supposing a sparse and spatially contiguous organization of coefficient maps, we build on the convex penalty consisting of the sum of total variation (TV) seminorm and L1 norm (“TV+L1”) to develop a penalty grouping an activation term with a spatial derivative. This penalty sets most coefficients to zero but permits free smooth variations in active zones, as opposed to TV+L1 which creates flat active zones. This method improves interpretability of brain maps obtained through cross-validation to determine the best hyperparameter.In the context of encoding and decoding models, we also work on improving data preprocessing in order to obtain the best performance. We study the impulse response of the BOLD signal: the hemodynamic response function. To generate activation maps, instead of using a classical linear model with fixed canonical response function, we use a bilinear model with spatially variable hemodynamic response (but fixed across events). We propose an efficient optimization algorithm and show a gain in predictive capacity for encoding and decoding models on different datasets.

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.

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.