L’étude de la pollution troposphérique inclut l’étude des gaz traces provenant de sources anthropiquesdiverses, dont l’impact varie de l’échelle locale à globale. Pour caractériser cette pollution, il est nécessairede mesurer avec précision les concentrations en polluants. Dans le cadre de projets européens, troiscampagnes aéroportées ont été conduites, dans le bassin méditerranéen, en Afrique de l’ouest et enMalaisie, pour mesurer différents types de polluants grâce, entre autres, à un spectromètre à lasersinfrarouges, SPIRIT, capable de mesurer rapidement en ligne de faibles variations de NO2 et CO. Les jeuxde données de ces gaz traces (et d’autres) ont été combinés avec un modèle lagrangien de dispersion departicules, FLEXPART, pour identifier différentes sources de pollution locales et régionales de l’air. Cettethèse présente ainsi les mesures et le travail de modélisation entrepris afin de définir les sources depollution de chaque région. Il a été montré que le bassin méditerranéen a été impacté, de la moyenne à lahaute troposphère pendant l’été, par des émissions de feux de biomasse venant de Sibérie et du continentnord-américain. Les régions ouest-africaine et malaisienne sont aussi impactées par des émissions de feuxde biomasse transportées depuis l’Afrique centrale dans le premier cas, et de feux locaux dans le second.En outre, ces régions sont influencées par des émissions provenant de l’exploitation du pétrole et du traficmaritime. FLEXPART a été utilisé afin d’identifier l’origine des pics de pollution mesurés au cours descampagnes. Nous avons ainsi montré que les conditions atmosphériques, qui définissent la hauteurd’injection du panache de la plateforme pétrolière, ainsi que le flux d’émission sont des paramètres clésdans la caractérisation des mesures par le modèle. / The study of tropospheric pollution includes the study of trace gases coming from various anthropogenicsources that can impact scales ranging from local to global. To characterise this pollution, it is necessary tobe able to measure with precision pollutant concentrations. Within the frame of European projects, threeairborne campaigns in the Mediterranean Basin, in West Africa and in Malaysia were conducted to measuredifferent types of pollutants thanks to, among others, an infrared laser spectrometer, SPIRIT, able to rapidlymeasure on-line small variations in NO2 and CO. The data sets of these trace gases (and others) have beencombined with a Lagrangian model of particle dispersion, FLEXPART, to fingerprint different sources of localand regional air pollution. Thus, this thesis presents the measurements and the modelling work undertakenin order to define the sources of pollution of each region. It has been shown that the Mediterranean Basinwas impacted, in the mid to upper troposphere during summer, by biomass burning emissions coming fromSiberia and the Northern American continent. West African and Malaysian regions are also impacted bybiomass burning emissions transported from central Africa in the first case, and from local fires in thesecond. In addition, those regions are influenced by emissions coming from oil exploitation and maritimetraffic. FLEXPART was used in order to identify the origin of the pollution peaks measured during thecampaigns. It has been shown that atmospheric conditions, which define the injection height of the oilplatform plume, and also the emission flux are key parameters in the characterisation of the measurementsby the model.

La conception de réseaux est un riche sous-domaine de l'optimisation combinatoire ayant de nombreuses applications pratiques. Du point de vue méthodologique, la plupart des problèmes de cette classe sont notoirement difficiles en raison de leur nature combinatoire et de l'interdépendance des décisions qu'ils impliquent. Ce mémoire aborde deux problèmes de conception de réseaux dont les structures respectives posent des défis bien distincts. Tout d'abord, nous examinons un problème déterministe dans lequel un client doit acquérir au prix minimum un certain nombre d'unités d'un produit auprès d'un ensemble de fournisseurs proposant différents coûts fixes et unitaires, et dont les stocks sont limités. Ensuite, nous étudions un problème probabiliste dans lequel une entreprise entrant sur un marché existant cherche, en ouvrant un certain nombre d'installations parmi un ensemble de sites disponibles, à maximiser sa part espérée d'un marché composé de clients maximisant une fonction d'utilité aléatoire. Ces deux problèmes, soit le problème de transport à coût fixe à un puits et le problème d'emplacement d'installations compétitif basé sur les choix, sont étroitement liés au problème du sac à dos et au problème de couverture maximale, respectivement. Nous introduisons de nouvelles reformulations prenant avantage de ces connexions avec des problèmes classiques d'optimisation combinatoire. Dans les deux cas, nous exploitons ces reformulations pour démontrer de nouvelles propriétés théoriques et développer des méthodes de résolution efficaces. Notre nouvel algorithme pour le problème de transport à coûts fixes à un puits domine les meilleurs algorithmes de la littérature, réduisant le temps de résolution des instances de grande taille jusqu'à quatre ordres de grandeur. Une autre contribution notable de ce mémoire est la démonstration que la fonction objectif du problème d'emplacement d'installations compétitif basé sur les choix est sous-modulaire sous n'importe quel modèle de maximisation d’utilité aléatoire. Notre méthode de résolution basée sur la simulation exploite cette propriété et améliore l'état de l'art pour plusieurs groupes d'instances. / Network design is a rich subfield of combinatorial optimization with wide-ranging real-life applications. From a methodological standpoint, most problems in this class are notoriously difficult due to their combinatorial nature and the interdependence of the decisions they involve. This thesis addresses two network design problems whose respective structures pose very distinct challenges. First, we consider a deterministic problem in which a customer must acquire at the minimum price a number of units of a product from a set of vendors offering different fixed and unit costs and whose supply is limited. Second, we study a probabilistic problem in which a firm entering an existing market seeks, by opening a number of facilities from a set of available locations, to maximize its expected share in a market composed of random utility-maximizing customers. These two problems, namely the single-sink fixed-charge-transportation problem and the choice-based competitive facility location problem, are closely related to the knapsack problem and the maximum covering problem, respectively. We introduce novel model reformulations that leverage these connections to classical combinatorial optimization problems. In both cases, we exploit these reformulations to prove new theoretical properties and to develop efficient solution methods. Our novel algorithm for the single-sink fixed-charge-transportation problem dominates the state-of-the-art methods from the literature, reducing the solving time of large instances by up to four orders of magnitude. Another notable contribution of this thesis is the demonstration that the objective function of the choice-based competitive facility location problem is submodular under any random utility maximization model. Our simulation-based method exploits this property and achieves state-of-the-art results for several groups of instances.

Le déploiement généralisé de modèles d’apprentissage automatique de plus en plus performants a entraîné des pressions croissantes pour améliorer la robustesse, la sécurité et l’équité de ces modèles—-souvent en raison de considérations réglementaires et éthiques. En outre, la mise en œuvre de solutions d’intelligence artificielle dans des applications réelles est limitée par leur incapacité actuelle à garantir la conformité aux normes industrielles et aux réglementations gouvernementales. Les pipelines standards pour le développement de modèles d’apprentissage automatique adoptent une mentalité de “construire maintenant, réparer plus tard”, intégrant des mesures de sécurité a posteriori. Cette accumulation continue de dette technique entrave le progrès du domaine à long terme. L’optimisation sous contraintes offre un cadre conceptuel accompagné d’outils algorithmiques permettant d’imposer de manière fiable des propriétés complexes sur des modèles d’apprentissage automatique. Cette thèse appelle à un changement de paradigme dans lequel les contraintes constituent une partie intégrante du processus de développement des modèles, visant à produire des modèles d’apprentissage automatique qui sont intrinsèquement sécurisés par conception. Cette thèse offre une perspective holistique sur l’usage de l’optimisation sous contraintes dans les tâches d’apprentissage profond. Nous examinerons i) la nécessité de formulations contraintes, ii) les avantages offerts par le point de vue de l’optimisation sous contraintes, et iii) les défis algorithmiques qui surgissent dans la résolution de ces problèmes. Nous présentons plusieurs études de cas illustrant l’application des techniques d’optimisation sous contraintes à des problèmes courants d’apprentissage automatique. Dans la Contribution I, nous plaidons en faveur de l’utilisation des formulations sous contraintes en apprentissage automatique. Nous soutenons qu’il est préférable de gérer des régularisateurs interprétables via des contraintes explicites plutôt que par des pénalités additives, particulièrement lorsqu’il s’agit de modèles non convexes. Nous considérons l’entraînement de modèles creux avec une régularisation L0 et démontrons que i) il est possible de trouver des solutions réalisables et performantes à des problèmes de grande envergure avec des contraintes non convexes ; et que ii) l’approche contrainte peut éviter les coûteux ajustements par essais et erreurs inhérents aux techniques basées sur les pénalités. La Contribution II approfondit la contribution précédente en imposant des contraintes explicites sur le taux de compression atteint par les Représentations Neuronales Implicites—-une classe de modèles visant à entreposer efficacement des données (telles qu’une image) dans les paramètres d’un réseau neuronal. Dans ce travail, nous nous concentrons sur l’interaction entre la taille du modèle, sa capacité représentationnelle, et le temps d’entraînement requis. Plutôt que de restreindre la taille du modèle à un budget fixe (qui se conforme au taux de compression requis), nous entraînons un modèle surparamétré et creux avec des contraintes de taux de compression. Cela nous permet d’exploiter la puissance de modèles plus grands pour obtenir de meilleures reconstructions, plus rapidement, sans avoir à nous engager à leur taux de compression indésirable. La Contribution III présente les avantages des formulations sous contraintes dans une application réaliste de la parcimonie des modèles avec des contraintes liées à l’équité non différentiables. Les performances des réseaux neuronaux élagués se dégradent de manière inégale entre les sous-groupes de données, nécessitant ainsi l’utilisation de techniques d’atténuation. Nous proposons une formulation qui impose des contraintes sur les changements de précision du modèle dans chaque sous-groupe, contrairement aux travaux antérieurs qui considèrent des contraintes basées sur des métriques de substitution (telles que la perte du sous-groupe). Nous abordons les défis de la non-différentiabilité et de la stochasticité posés par nos contraintes proposées, et démontrons que notre méthode s’adapte de manière fiable aux problèmes d’optimisation impliquant de grands modèles et des centaines de sous-groupes. Dans la Contribution IV, nous nous concentrons sur la dynamique de l’optimisation lagrangienne basée sur le gradient, une technique populaire pour résoudre les problèmes sous contraintes non convexes en apprentissage profond. La nature adversariale du jeu min-max lagrangien le rend sujet à des comportements oscillatoires ou instables. En nous basant sur des idées tirées de la littérature sur les régulateurs PID, nous proposons un algorithme pour modifier les multiplicateurs de Lagrange qui offre une dynamique d’entraînement robuste et stable. Cette contribution met en place les bases pour que les praticiens adoptent et mettent en œuvre des approches sous contraintes avec confiance dans diverses applications réelles. Dans la Contribution V, nous fournissons un aperçu de Cooper : une bibliothèque pour l’optimisation sous contraintes basée sur le lagrangien dans PyTorch. Cette bibliothèque open-source implémente toutes les contributions principales présentées dans les chapitres précédents et s’intègre harmonieusement dans le cadre PyTorch. Nous avons développé Cooper dans le but de rendre les techniques d’optimisation sous contraintes facilement accessibles aux chercheurs et praticiens de l’apprentissage automatique. / The widespread deployment of increasingly capable machine learning models has resulted in mounting pressures to enhance the robustness, safety and fairness of such models--often arising from regulatory and ethical considerations. Further, the implementation of artificial intelligence solutions in real-world applications is limited by their current inability to guarantee compliance with industry standards and governmental regulations. Current standard pipelines for developing machine learning models embrace a “build now, fix later” mentality, retrofitting safety measures as afterthoughts. This continuous incurrence of technical debt hinders the progress of the field in the long-term. Constrained optimization offers a conceptual framework accompanied by algorithmic tools for reliably enforcing complex properties on machine learning models. This thesis calls for a paradigm shift in which constraints constitute an integral part of the model development process, aiming to produce machine learning models that are inherently secure by design. This thesis provides a holistic perspective on the use of constrained optimization in deep learning tasks. We shall explore i) the need for constrained formulations, ii) the advantages afforded by the constrained optimization standpoint and iii) the algorithmic challenges arising in the solution of such problems. We present several case-studies illustrating the application of constrained optimization techniques to popular machine learning problems. In Contribution I, we advocate for the use of constrained formulations in machine learning. We argue that it is preferable to handle interpretable regularizers via explicit constraints, rather than using additive penalties, specially when dealing with non-convex models. We consider the training of sparse models with L0-regularization and demonstrate that i) it is possible to find feasible, well-performing solutions to large-scale problems with non-convex constraints; and that ii) the constrained approach can avoid the costly trial-and-error tuning inherent to penalty-based techniques. Contribution II expands on the previous contribution by imposing explicit constraints on the compression-rate achieved by Implicit Neural Representations—-a class of models that aim to efficiently store data (such as an image) within a neural network’s parameters. In this work we concentrate on the interplay between the model size, its representational capacity and the required training time. Rather than restricting the model size to a fixed budget (that complies with the required compression rate), we train an overparametrized, sparse model with compression-rate constraints. This allows us to exploit the power of larger models to achieve better reconstructions, faster; without having to commit to their undesirable compression rate. Contribution III showcases the advantages of constrained formulations in a realistic model sparsity application with non-differentiable fairness-related constraints. The performance of pruned neural networks degrades unevenly across data sub-groups, thus requiring the use of mitigation techniques. We propose a formulation that imposes constraints on changes in the model accuracy in each sub-group, in contrast to prior work which considers constraints based on surrogate metrics (such as the sub-group loss). We address the non-differentiability and stochasticity challenges posed by our proposed constraints, and demonstrate that our method scales reliably to optimization problems involving large models and hundreds of sub-groups. In Contribution IV, we focus on the dynamics of gradient-based Lagrangian optimization, a popular technique for solving the non-convex constrained problems arising in deep learning. The adversarial nature of the min-max Lagrangian game makes it prone to oscillatory or unstable behaviors. Based on ideas from the PID control literature, we propose an algorithm for updating the Lagrange multipliers which yields robust, stable training dynamics. This contribution lays the groundwork for practitioners to adopt and implement constrained approaches confidently in diverse real-world applications. In Contribution V, we provide an overview of Cooper: a library for Lagrangian-based constrained optimization in PyTorch. This open-source library implements all the core contributions presented in the preceding chapters and integrates seamlessly with the PyTorch framework. We developed Cooper with the goal of making constrained optimization techniques readily available to machine learning researchers and practitioners.