Cette thèse s'attache à l'étude des problèmes d'optimisation stochastique, en les abordant sous divers angles. Le premier chapitre donne un panorama des problèmes d'optimisation stochastique. Le deuxième chapitre montre qu'en dimension un, seuls les systèmes à espace d'état à dynamique et observation linéaire sont sans effet dual en boucle ouverte. Le troisième chapitre s'attache à montrer la nécessité de tenir compte de la structure d'information dans la discrétisation et les résultats de stabilité pour les problèmes à plusieurs pas de temps. Le quatrième chapitre propose une nouvelle famille d'algorithmes stochastiques permettant de rechercher les commandes optimales fonctionnellement sans aucune discrétisation préalable de l'aléa, et avec une garantie asymptotique d'optimalité. Le cinquième chapitre étudie les possibilités de décomposition et d'agrégation pour les problèmes stochastiques de grande taille.

Actuellement, le principal obstacle à la mise en œuvre de la FWI élastique en trois dimensions sur des cas d'étude réalistes réside dans le coût de calcul associé aux taches de modélisation sismique. Pour surmonter cette difficulté, je propose deux contributions. Tout d'abord, je propose de calculer le gradient de la fonctionnelle avec la méthode de l'état adjoint à partir d'une forme symétrisée des équations de l'élastodynamique formulées sous forme d'un système du premier ordre en vitesse-contrainte. Cette formulation auto-adjointe des équations de l'élastodynamique permet de calculer les champs incidents et adjoints intervenant dans l'expression du gradient avec un seul opérateur de modélisation numérique. Le gradient ainsi calculé facilite également l'interfaçage de plusieurs outils de modélisation avec l'algorithme d'inversion. Deuxièmement, j'explore dans cette thèse dans quelle mesure les encodages des sources avec des algorithmes d'optimisation du second-ordre de quasi-Newton et de Newton tronqué permettait de réduire encore le coût de la FWI. Finalement, le problème d'optimisation associé à la FWI est mal posé, nécessitant ainsi d'ajouter des contraintes de régularisation à la fonctionnelle à minimiser. Je montre ici comment une régularisation fondée sur la variation totale du modèle fournissait une représentation adéquate des modèles du sous-sol en préservant le caractère discontinu des interfaces lithologiques. Pour améliorer les images du sous-sol, je propose un algorithme de débruitage fondé sur une variation totale locale au sein duquel j'incorpore l'information structurale fournie par une image migrée pour préserver les structures de faible dimension.

Le travail général de cette thèse consiste à étendre les outils analytiques et algébriques usuellement employés dans la résolution de problèmes combinatoires déterministes à un cadre combinatoire stochastique. Deux cadres distincts sont étudiés : les problèmes combinatoires stochastiques discrets et les problèmes stochastiques continus. Le cadre discret est abordé à travers le problème de la forêt couvrante de poids maximal dans une formulation Two-Stage à multi-scénarios. La version déterministe très connue de ce problème établit des liens entre la fonction de rang dans un matroïde et la formulation duale, via l'algorithme glouton. La formulation stochastique discrète du problème de la forêt maximale couvrante est transformée en un problème déterministe équivalent, mais du fait de la multiplicité des scénarios, le dual associé est en quelque sorte incomplet. Le travail réalisé ici consiste à comprendre en quelles circonstances la formulation duale atteint néanmoins un minimum égal au problème primal intégral. D'ordinaire, une approche combinatoire classique des problèmes de graphes pondérés consiste à rechercher des configurations particulières au sein des graphes, comme les circuits, et à explorer d'éventuelles recombinaisons. Pour donner une illustration simple, si on change d'une manière infinitésimale les valeurs de poids des arêtes d'un graphe, il est possible que la forêt couvrante de poids maximal se réorganise complètement. Ceci est vu comme un obstacle dans une approche purement combinatoire. Pourtant, certaines grandeurs analytiques vont varier de manière continue en fonction de ces variations infinitésimales, comme la somme des poids des arêtes choisies. Nous introduisons des fonctions qui rendent compte de ces variations continues, et nous examinons dans quels cas les formulations duales atteignent la même valeur que les formulations primales intégrales. Nous proposons une méthode d'approximation dans le cas contraire et nous statuons sur la NP complétude de ce type de problème.Les problèmes stochastiques continus sont abordés via le problème de sac à dos avec contrainte stochastique. La formulation est de type ''chance constraint'', et la dualisation par variable lagrangienne est adaptée à une situation où la probabilité de respecter la contrainte doit rester proche de $1$. Le modèle étudié est celui d'un sac à dos où les objets ont une valeur et un poids déterminés par des distributions normales. Dans notre approche, nous nous attachons à appliquer des méthodes de gradient directement sur la formulation en espérance de la fonction objectif et de la contrainte. Nous délaissons donc une possible reformulation classique du problème sous forme géométrique pour détailler les conditions de convergence de la méthode du gradient stochastique. Cette partie est illustrée par des tests numériques de comparaison avec la méthode SOCP sur des instances combinatoires avec méthode de Branch and Bound, et sur des instances relaxées.

La construction d'algorithmes classifiant des images à grande échelle est devenue une tache essentielle du fait de la difficulté d'effectuer des recherches dans les immenses collections de données visuelles inetiquetées présentes sur Internet. Nous visons à classifier des images en fonction de leur contenu pour simplifier la gestion de telles bases de données. La classification d'images à grande échelle est un problème complèxe, de par l'importance de la taille des ensembles de données, tant en nombre d'images qu'en nombre de classes. Certaines de ces classes sont dites "fine-grained" (sémantiquement proches les unes des autres) et peuvent même ne contenir aucun représentant étiqueté. Dans cette thèse, nous utilisons des représentations état de l'art d'images et nous concentrons sur des méthodes d'apprentissage efficaces. Nos contributions sont (1) un banc d'essai d'algorithmes d'apprentissage pour la classification à grande échelle et (2) un nouvel algorithme basé sur l'incorporation d'étiquettes pour apprendre sur des données peu abondantes. En premier lieu, nous introduisons un banc d'essai d'algorithmes d'apprentissage pour la classification à grande échelle, dans le cadre entièrement supervisé. Il compare plusieurs fonctions objectifs pour apprendre des classifieurs linéaires, tels que "un contre tous", "multiclasse", "ranking", "ranking pondéré moyen" par descente de gradient stochastique. Ce banc d'essai se conclut en un ensemble de recommandations pour la classification à grande échelle. Avec une simple repondération des données, la stratégie "un contre tous" donne des performances meilleures que toutes les autres. Par ailleurs, en apprentissage en ligne, un pas d'apprentissage assez petit s'avère suffisant pour obtenir des résultats au niveau de l'état de l'art. Enfin, l'arrêt anticipé de la descente de gradient stochastique introduit une régularisation qui améliore la vitesse d'entraînement ainsi que la capacité de régularisation. Deuxièmement, face à des milliers de classes, il est parfois difficile de rassembler suffisamment de données d'entraînement pour chacune des classes. En particulier, certaines classes peuvent être entièrement dénuées d'exemples. En conséquence, nous proposons un nouvel algorithme adapté à ce scénario d'apprentissage dit "zero-shot". notre algorithme utilise des données parallèles, comme les attributs, pour incorporer les classes dans un espace euclidien. Nous introduisons par ailleurs une fonction pour mesurer la compatibilité entre image et étiquette. Les paramètres de cette fonction sont appris en utilisant un objectif de type "ranking". Notre algorithme dépasse l'état de l'art pour l'apprentissage "zero-shot", et fait preuve d'une grande flexibilité en permettant d'incorporer d'autres sources d'information parallèle, comme des hiérarchies. Il permet en outre une transition sans heurt du cas "zero-shot" au cas où peu d'exemples sont disponibles.

Actuellement, le principal obstacle à la mise en œuvre de la FWI élastique en trois dimensions sur des cas d'étude réalistes réside dans le coût de calcul associé aux taches de modélisation sismique. Pour surmonter cette difficulté, je propose deux contributions. Tout d'abord, je propose de calculer le gradient de la fonctionnelle avec la méthode de l'état adjoint à partir d'une forme symétrisée des équations de l'élastodynamique formulées sous forme d'un système du premier ordre en vitesse-contrainte. Cette formulation auto-adjointe des équations de l'élastodynamique permet de calculer les champs incidents et adjoints intervenant dans l'expression du gradient avec un seul opérateur de modélisation numérique. Le gradient ainsi calculé facilite également l'interfaçage de plusieurs outils de modélisation avec l'algorithme d'inversion. Deuxièmement, j'explore dans cette thèse dans quelle mesure les encodages des sources avec des algorithmes d'optimisation du second-ordre de quasi-Newton et de Newton tronqué permettait de réduire encore le coût de la FWI. Finalement, le problème d'optimisation associé à la FWI est mal posé, nécessitant ainsi d'ajouter des contraintes de régularisation à la fonctionnelle à minimiser. Je montre ici comment une régularisation fondée sur la variation totale du modèle fournissait une représentation adéquate des modèles du sous-sol en préservant le caractère discontinu des interfaces lithologiques. Pour améliorer les images du sous-sol, je propose un algorithme de débruitage fondé sur une variation totale locale au sein duquel j'incorpore l'information structurale fournie par une image migrée pour préserver les structures de faible dimension. / Currently, the main limitation to perform 3D elastic full waveform inversion on a production level is the computational cost it represents. With this in mind, we provide two contributions. First, we develop a self adjoint formulation of the isotropic first order velocity-stress elastic equations that allow to implement only one forward modeling operator in the gradient computation. Second, we combine Newton and quasi-Newton optimization methods with source encoding techniques to see to what extent the computational cost could be further reduced. Finally, the optimization process associated to FWI is ill posed and requires regularization constraints. I show that the total variation of the model as a regularization term provides and adequate description of earth models, preserving the discontinuous character of the lithological layers. To improve the quality of the images, we propose a local total variation denoising algorithm based on the incorporation of the information provided by a migrated image.

Nous présentons deux contributions majeures : 1) une combinaison de plusieurs descripteurs d’images pour la classification à grande échelle, 2) des algorithmes parallèles de SVM pour la classification d’images à grande échelle. Nous proposons aussi un algorithme incrémental et parallèle de classification lorsque les données ne peuvent plus tenir en mémoire vive. / We have proposed a novel method of combination multiple of different features for image classification. For large scale learning classifiers, we have developed the parallel versions of both state-of-the-art linear and nonlinear SVMs. We have also proposed a novel algorithm to extend stochastic gradient descent SVM for large scale learning. A class of large scale incremental SVM classifiers has been developed in order to perform classification tasks on large datasets with very large number of classes and training data can not fit into memory.

La construction d'algorithmes classifiant des images à grande échelle est devenue une t^ache essentielle du fait de la difficulté d'effectuer des recherches dans les immenses collections de données visuelles non-etiquetées présentes sur Internet. L'objetif est de classifier des images en fonction de leur contenu pour simplifier la gestion de telles bases de données. La classification d'images à grande échelle est un problème complexe, de par l'importance de la taille des ensembles de données, tant en nombre d'images qu'en nombre de classes. Certaines de ces classes sont dites "fine-grained" (sémantiquement proches les unes des autres) et peuvent même ne contenir aucun représentant étiqueté. Dans cette thèse, nous utilisons des représentations à l'état de l'art d'images et nous concentrons sur des méthodes d'apprentissage efficaces. Nos contributions sont (1) un banc d'essai d'algorithmes d'apprentissage pour la classification à grande échelle et (2) un nouvel algorithme basé sur l'incorporation d'étiquettes pour apprendre sur des données peu abondantes. En premier lieu, nous introduisons un banc d'essai d'algorithmes d'apprentissage pour la classification à grande échelle, dans un cadre entièrement supervisé. Il compare plusieurs fonctions objectifs pour apprendre des classifieurs linéaires, tels que "un contre tous", "multiclasse", "classement", "classement avec pondération" par descente de gradient stochastique. Ce banc d'essai se conclut en un ensemble de recommandations pour la classification à grande échelle. Avec une simple repondération des données, la stratégie "un contre tous" donne des performances meilleures que toutes les autres. Par ailleurs, en apprentissage en ligne, un pas d'apprentissage assez petit s'avère suffisant pour obtenir des résultats au niveau de l'état de l'art. Enfin, l'arrêt prématuré de la descente de gradient stochastique introduit une régularisation qui améliore la vitesse d'entraînement ainsi que la capacité de régularisation. Deuxièmement, face à des milliers de classes, il est parfois difficile de rassembler suffisamment de données d'entraînement pour chacune des classes. En particulier, certaines classes peuvent être entièrement dénuées d'exemples. En conséquence, nous proposons un nouvel algorithme adapté à ce scénario d'apprentissage dit "zero-shot". Notre algorithme utilise des données parallèles, comme les attributs, pour incorporer les classes dans un espace euclidien. Nous introduisons par ailleurs une fonction pour mesurer la compatibilité entre image et étiquette. Les paramètres de cette fonction sont appris en utilisant un objectif de type "ranking". Notre algorithme dépasse l'état de l'art pour l'apprentissage "zero-shot", et fait preuve d'une grande flexibilité en permettant d'incorporer d'autres sources d'information parallèle, comme des hiérarchies. Il permet en outre une transition sans heurt du cas "zero-shot" au cas où peu d'exemples sont disponibles. / Building algorithms that classify images on a large scale is an essential task due to the difficulty in searching massive amount of unlabeled visual data available on the Internet. We aim at classifying images based on their content to simplify the manageability of such large-scale collections. Large-scale image classification is a difficult problem as datasets are large with respect to both the number of images and the number of classes. Some of these classes are fine grained and they may not contain any labeled representatives. In this thesis, we use state-of-the-art image representations and focus on efficient learning methods. Our contributions are (1) a benchmark of learning algorithms for large scale image classification, and (2) a novel learning algorithm based on label embedding for learning with scarce training data. Firstly, we propose a benchmark of learning algorithms for large scale image classification in the fully supervised setting. It compares several objective functions for learning linear classifiers such as one-vs-rest, multiclass, ranking and weighted average ranking using the stochastic gradient descent optimization. The output of this benchmark is a set of recommendations for large-scale learning. We experimentally show that, online learning is well suited for large-scale image classification. With simple data rebalancing, One-vs-Rest performs better than all other methods. Moreover, in online learning, using a small enough step size with respect to the learning rate is sufficient for state-of-the-art performance. Finally, regularization through early stopping results in fast training and a good generalization performance. Secondly, when dealing with thousands of classes, it is difficult to collect sufficient labeled training data for each class. For some classes we might not even have a single training example. We propose a novel algorithm for this zero-shot learning scenario. Our algorithm uses side information, such as attributes to embed classes in a Euclidean space. We also introduce a function to measure the compatibility between an image and a label. The parameters of this function are learned using a ranking objective. Our algorithm outperforms the state-of-the-art for zero-shot learning. It is flexible and can accommodate other sources of side information such as hierarchies. It also allows for a smooth transition from zero-shot to few-shots learning.

Le travail général de cette thèse consiste à étendre les outils analytiques et algébriques usuellement employés dans la résolution de problèmes combinatoires déterministes à un cadre combinatoire stochastique. Deux cadres distincts sont étudiés : les problèmes combinatoires stochastiques discrets et les problèmes stochastiques continus. Le cadre discret est abordé à travers le problème de la forêt couvrante de poids maximal dans une formulation Two-Stage à multi-scénarios. La version déterministe très connue de ce problème établit des liens entre la fonction de rang dans un matroïde et la formulation duale, via l'algorithme glouton. La formulation stochastique discrète du problème de la forêt maximale couvrante est transformée en un problème déterministe équivalent, mais du fait de la multiplicité des scénarios, le dual associé est en quelque sorte incomplet. Le travail réalisé ici consiste à comprendre en quelles circonstances la formulation duale atteint néanmoins un minimum égal au problème primal intégral. D'ordinaire, une approche combinatoire classique des problèmes de graphes pondérés consiste à rechercher des configurations particulières au sein des graphes, comme les circuits, et à explorer d'éventuelles recombinaisons. Pour donner une illustration simple, si on change d'une manière infinitésimale les valeurs de poids des arêtes d'un graphe, il est possible que la forêt couvrante de poids maximal se réorganise complètement. Ceci est vu comme un obstacle dans une approche purement combinatoire. Pourtant, certaines grandeurs analytiques vont varier de manière continue en fonction de ces variations infinitésimales, comme la somme des poids des arêtes choisies. Nous introduisons des fonctions qui rendent compte de ces variations continues, et nous examinons dans quels cas les formulations duales atteignent la même valeur que les formulations primales intégrales. Nous proposons une méthode d'approximation dans le cas contraire et nous statuons sur la NP complétude de ce type de problème.Les problèmes stochastiques continus sont abordés via le problème de sac à dos avec contrainte stochastique. La formulation est de type ``chance constraint'', et la dualisation par variable lagrangienne est adaptée à une situation où la probabilité de respecter la contrainte doit rester proche de $1$. Le modèle étudié est celui d'un sac à dos où les objets ont une valeur et un poids déterminés par des distributions normales. Dans notre approche, nous nous attachons à appliquer des méthodes de gradient directement sur la formulation en espérance de la fonction objectif et de la contrainte. Nous délaissons donc une possible reformulation classique du problème sous forme géométrique pour détailler les conditions de convergence de la méthode du gradient stochastique. Cette partie est illustrée par des tests numériques de comparaison avec la méthode SOCP sur des instances combinatoires avec méthode de Branch and Bound, et sur des instances relaxées. / The global purpose of this thesis is to study the conditions to extend analytical and algebraical properties commonly observed in the resolution of deterministic combinatorial problems to the corresponding stochastic formulations of these problems. Two distinct situations are treated : discrete combinatorial stochastic problems and continuous stochastic problems. Discrete situation is examined with the Two Stage formulation of the Maximum Weight Covering Forest. The well known corresponding deterministic formulation shows the connexions between the rank function of a matroid, the greedy algorithm , and the dual formulation. The discrete stochastic formulation of the Maximal Covering Forest is turned into a deterministic equivalent formulation, but, due to the number of scenarios, the associated dual is not complete. The work of this thesis leads to understand in which cases the dual formulation still has the same value as the primal integer formulation. Usually, classical combinatorial approaches aim to find particular configurations in the graph, as circuits, in order to handle possible reconfigurations. For example, slight modifications of the weights of the edges might change considerably the configuration of the Maximum Weight Covering Forest. This can be seen as an obstacle to handle pure combinatorial proofs. However, some global relevant quantities, like the global weight of the selected edges during the greedy algorithm, have a continuous variation in function of slight modifications. We introduce some functions in order to outline these continuous variations. And we state in which cases Primal integral problems have the same objective values as dual formulations. When it is not the case, we propose an approximation method and we examine the NP completeness of this problem.Continuous stochastic problems are presented with the stochastic Knapsack with chance constraint. Chance constraint and dual Lagrangian formulation are adapted in the case where the expected probability of not exceeding the knapsack capacity is close to $1$. The introduced model consists in items whose costs and rewards follow normal distributions. In our case, we try to apply direct gradient methods without reformulating the problem into geometrical terms. We detail convergence conditions of gradient based methods directly on the initial formulation. This part is illustrated with numerical tests on combinatorial instances and Branch and Bound evaluations on relaxed formulations.

Les émetteurs-récepteurs actuels tendent à devenir multi-standards c’est-àdireque plusieurs standards de communication peuvent cohabiter sur la même puce. Lespuces sont donc amenées à traiter des signaux de formes très différentes, et les composantsanalogiques subissent des contraintes de conception de plus en plus fortes associées au supportdes différentes normes. Les auto-interférences, c’est à dire les interférences généréespar le système lui-même, sont donc de plus en plus présentes, et de plus en plus problématiquesdans les architectures actuelles. Ces travaux s’inscrivent dans le paradigmede la « radio sale » qui consiste à accepter une pollution partielle du signal d’intérêtet à réaliser, par l’intermédiaire d’algorithmes, une atténuation de l’impact de ces pollutionsauto-générées. Dans ce manuscrit, on s’intéresse à différentes auto-interférences(phénomène de "spurs", de "Tx leakage", ...) dont on étudie les modèles numériques etpour lesquelles nous proposons des stratégies de compensation. Les algorithmes proposéssont des algorithmes de traitement du signal adaptatif qui peuvent être vus comme des« algorithmes de soustraction de bruit » basés sur des références plus ou moins précises.Nous dérivons analytiquement les performances transitionnelles et asymptotiques théoriquesdes algorithmes proposés. On se propose également d’ajouter à nos systèmes unesur-couche originale qui permet d’accélérer la convergence, tout en maintenant des performancesasymptotiques prédictibles et paramétrables. Nous validons enfin notre approchesur une puce dédiée aux communications cellulaires ainsi que sur une plateforme de radiologicielle. / Radio frequency transceivers are now massively multi-standards, which meansthat several communication standards can cohabit in the same environment. As a consequence,analog components have to face critical design constraints to match the differentstandards requirements and self-interferences that are directly introduced by the architectureitself are more and more present and detrimental. This work exploits the dirty RFparadigm : we accept the signal to be polluted by self-interferences and we develop digitalsignal processing algorithms to mitigate those aforementioned pollutions and improve signalquality. We study here different self-interferences and propose baseband models anddigital adaptive algorithms for which we derive closed form formulae of both transientand asymptotic performance. We also propose an original adaptive step-size overlay toimprove transient performance of our method. We finally validate our approach on a systemon chip dedicated to cellular communications and on a software defined radio.

Les émetteurs-récepteurs actuels tendent à devenir multi-standards c’est-àdireque plusieurs standards de communication peuvent cohabiter sur la même puce. Lespuces sont donc amenées à traiter des signaux de formes très différentes, et les composantsanalogiques subissent des contraintes de conception de plus en plus fortes associées au supportdes différentes normes. Les auto-interférences, c’est à dire les interférences généréespar le système lui-même, sont donc de plus en plus présentes, et de plus en plus problématiquesdans les architectures actuelles. Ces travaux s’inscrivent dans le paradigmede la « radio sale » qui consiste à accepter une pollution partielle du signal d’intérêtet à réaliser, par l’intermédiaire d’algorithmes, une atténuation de l’impact de ces pollutionsauto-générées. Dans ce manuscrit, on s’intéresse à différentes auto-interférences(phénomène de "spurs", de "Tx leakage", ...) dont on étudie les modèles numériques etpour lesquelles nous proposons des stratégies de compensation. Les algorithmes proposéssont des algorithmes de traitement du signal adaptatif qui peuvent être vus comme des« algorithmes de soustraction de bruit » basés sur des références plus ou moins précises.Nous dérivons analytiquement les performances transitionnelles et asymptotiques théoriquesdes algorithmes proposés. On se propose également d’ajouter à nos systèmes unesur-couche originale qui permet d’accélérer la convergence, tout en maintenant des performancesasymptotiques prédictibles et paramétrables. Nous validons enfin notre approchesur une puce dédiée aux communications cellulaires ainsi que sur une plateforme de radiologicielle. / Radio frequency transceivers are now massively multi-standards, which meansthat several communication standards can cohabit in the same environment. As a consequence,analog components have to face critical design constraints to match the differentstandards requirements and self-interferences that are directly introduced by the architectureitself are more and more present and detrimental. This work exploits the dirty RFparadigm : we accept the signal to be polluted by self-interferences and we develop digitalsignal processing algorithms to mitigate those aforementioned pollutions and improve signalquality. We study here different self-interferences and propose baseband models anddigital adaptive algorithms for which we derive closed form formulae of both transientand asymptotic performance. We also propose an original adaptive step-size overlay toimprove transient performance of our method. We finally validate our approach on a systemon chip dedicated to cellular communications and on a software defined radio.