abstract: In this dissertation, we present a H-infinity based multivariable control design methodology that can be used to systematically address design specifications at distinct feedback loop-breaking points. It is well understood that for multivariable systems, obtaining good/acceptable closed loop properties at one loop-breaking point does not mean the same at another. This is especially true for multivariable systems that are ill-conditioned (having high condition number and/or relative gain array and/or scaled condition number). We analyze the tradeoffs involved in shaping closed loop properties at these distinct loop-breaking points and illustrate through examples the existence of pareto optimal points associated with them. Further, we study the limitations and tradeoffs associated with shaping the properties in the presence of right half plane poles/zeros, limited available bandwidth and peak time-domain constraints. To address the above tradeoffs, we present a methodology for designing multiobjective constrained H-infinity based controllers, called Generalized Mixed Sensitivity (GMS), to effectively and efficiently shape properties at distinct loop-breaking points. The methodology accommodates a broad class of convex frequency- and time-domain design specifications. This is accomplished by exploiting the Youla-Jabr-Bongiorno-Kucera parameterization that transforms the nonlinear problem in the controller to an affine one in the Youla et al. parameter. Basis parameters that result in efficient approximation (using lesser number of basis terms) of the infinite-dimensional parameter are studied. Three state-of-the-art subgradient-based non-differentiable constrained convex optimization solvers, namely Analytic Center Cutting Plane Method (ACCPM), Kelley's CPM and SolvOpt are implemented and compared. The above approach is used to design controllers for and tradeoff between several control properties of longitudinal dynamics of 3-DOF Hypersonic vehicle model -– one that is unstable, non-minimum phase and possesses significant coupling between channels. A hierarchical inner-outer loop control architecture is used to exploit additional feedback information in order to significantly help in making reasonable tradeoffs between properties at distinct loop-breaking points. The methodology is shown to generate very good designs –- designs that would be difficult to obtain without our presented methodology. Critical control tradeoffs associated are studied and compared with other design methods (e.g., classically motivated, standard mixed sensitivity) to further illustrate its power and transparency. / Dissertation/Thesis / Doctoral Dissertation Electrical Engineering 2018

In this doctoral thesis, we propose new iterative methods for solving a class of convex optimization problems. In general, we consider problems in which the objective function is composed of a finite sum of convex functions and the set of constraints is, at least, convex and closed. The iterative methods we propose are basically designed through the combination of incremental subgradient methods and string-averaging algorithms. Furthermore, in order to obtain methods able to solve optimization problems with many constraints (and possibly in high dimensions), generally given by convex functions, our analysis includes an operator that calculates approximate projections onto the feasible set, instead of the Euclidean projection. This feature is employed in the two methods we propose; one deterministic and the other stochastic. A convergence analysis is proposed for both methods and numerical experiments are performed in order to verify their applicability, especially in large scale problems. / Nesta tese de doutorado, propomos novos métodos iterativos para a solução de uma classe de problemas de otimização convexa. Em geral, consideramos problemas nos quais a função objetivo é composta por uma soma finita de funções convexas e o conjunto de restrições é, pelo menos, convexo e fechado. Os métodos iterativos que propomos são criados, basicamente, através da junção de métodos de subgradientes incrementais e do algoritmo de média das sequências. Além disso, visando obter métodos flexíveis para soluções de problemas de otimização com muitas restrições (e possivelmente em altas dimensões), dadas em geral por funções convexas, a nossa análise inclui um operador que calcula projeções aproximadas sobre o conjunto viável, no lugar da projeção Euclideana. Essa característica é empregada nos dois métodos que propomos; um determinístico e o outro estocástico. Uma análise de convergência é proposta para ambos os métodos e experimentos numéricos são realizados a fim de verificar a sua aplicabilidade, principalmente em problemas de grande escala.

Made available in DSpace on 2014-07-29T16:02:20Z (GMT). No. of bitstreams: 1 Dissertacao-Jose Henrique Salazar do Amaral.pdf: 346281 bytes, checksum: ed448001994e6dc5edb294a83390961a (MD5) Previous issue date: 2012-06-27 / This paper presents an analysis of convergence of the proximal point method for functions that satisfy the inequality of Lojasiewicz. / Neste trabalho é feita uma análise de convergência do Método do Ponto Proximal para funções não necessariamente convexas que satisfazem a desigualdade de Łojasiewicz.

Cette thèse traite de problèmes liés à la couleur. En particulier, on s’intéresse à des problématiques communes à la colorisation d’images, de vidéos et au rehaussement de contraste. Si on considère qu’une image est composée de deux informations complémentaires, une achromatique (sans couleur) et l’autre chromatique (en couleur), les applications étudiées consistent à traiter une de ces deux informations en préservant sa complémentaire. En colorisation, la difficulté est de calculer une image couleur en imposant son niveau de gris. Le rehaussement de contraste vise à modifier l’intensité d’une image en préservant sa teinte. Ces problématiques communes nous ont conduits à étudier formellement la géométrie de l’espace RGB. On a démontré que les espaces couleur classiques de la littérature pour résoudre ces types de problème conduisent à des erreurs. Un algorithme, appelé spécification luminance-teinte, qui calcule une couleur ayant une teinte et une luminance données est décrit dans cette thèse. L’extension de cette méthode à un cadre variationnel a été proposée. Ce modèle a été utilisé avec succès pour rehausser les images couleur, en utilisant des hypothèses connues sur le système visuel humain. Les méthodes de l’état-de-l’art pour la colorisation d’images se divisent en deux catégories. La première catégorie regroupe celles qui diffusent des points de couleurs posés par l’utilisateur pour obtenir une image colorisée (colorisation manuelle). La seconde est constituée de celles qui utilisent une image couleur de référence ou une base d’images couleur et transfèrent les couleurs de la référence sur l’image en niveaux de gris (colorisation basée exemple). Les deux types de méthodes ont leurs avantages et inconvénients. Dans cette thèse, on propose un modèle variationnel pour la colorisation basée exemple. Celui-ci est étendu en une méthode unifiant la colorisation manuelle et basée exemple. Enfin, nous décrivons des modèles variationnels qui colorisent des vidéos tout en permettent une interaction avec l’utilisateur. / This thesis deals with problems related to color. In particular, we are interested inproblems which arise in image and video colorization and contrast enhancement. When considering color images composed of two complementary information, oneachromatic (without color) and the other chromatic (in color), the applications studied in this thesis are based on the processing one of these information while preserving its complement. In colorization, the challenge is to compute a color image while constraining its gray-scale channel. Contrast enhancement aims to modify the intensity channel of an image while preserving its hue.These joined problems require to formally study the RGB space geometry. In this work, it has been shown that the classical color spaces of the literature designed to solve these classes of problems lead to errors. An novel algorithm, called luminance-hue specification, which computes a color with a given hue and luminance is described in this thesis. The extension of this method to a variational framework has been proposed. This model has been used successfully to enhance color images, using well-known assumptions about the human visual system. The state-of-the-art methods for image colorization fall into two categories. The first category includes those that diffuse color scribbles drawn by the user (manual colorization). The second consists of those that benefits from a reference color image or a base of reference images to transfer the colors from the reference to the grayscale image (exemplar-based colorization). Both approach have their advantages and drawbacks. In this thesis, we design a variational model for exemplar-based colorization which is extended to a method unifying the manual colorization and the exemplar-based one. Finally, we describe two variational models to colorize videos in interaction with the user.

Efficient design of high-voltage power cables is important to achieve an economical delivery of electric power from wind farms and power plants over the very long distances as well as the overseas electric power. The main focus of this thesis is the investigation of electromagnetic losses in components of high-voltage power cables. The objective of the ongoing research is to develop the theory and optimization techniques as tools to make material choices and geometry designs to minimize the high-frequency attenuation and dispersion for HVDC power cables and the power losses associated with HVAC cables. Physical limitations, dispersion relationships and the application of sum rules as well as convex optimization will be investigated to obtain adequate physical insight and a priori modeling information for these problems. For HVAC power cables, the objectives are addressed by performing measurements and estimation of complex valued permeability of cable armour steel in Papers I and II. Efficient analytical solutions for the electromagnetic field generated by helical structures with applications for HVAC power cables have been obtained in Paper III. For HVDC power cables, estimation of insulation characteristics from dielectric spectroscopy data using Herglotz functions, convex optimization and B-splines, has been investigated in Papers V and VI. The unique solution requirements in waveguide problems have been reviewed in Paper IV.

Dans cette thèse, on présente de nouvelles approches à base de parcimonie et d'invariance d' échelle pour le développement de techniques rapides et efficaces en traitement d'images. Au lieu d'utiliser la norme l1 pour imposer la parcimonie, on exploite plutôt des pénalités non-convexes qui encouragent plus la parcimonie. On propose une approche de premier ordre pour estimer une solution d'un opérateur proximal non-convexe, ce qui permet d'exploiter facilement la non-convexité. On étudie aussi le problème de pluri-parcimonie quand le problème d'optimisation est composé de plusieurs termes parcimonieux. Ce cas survient généralement dans les problèmes qui nécessitent à la fois une estimation robuste pour rejeter les valeurs aberrantes et exploiter une information de parcimonie connue a priori. Ces techniques sont appliquées à plusieurs problèmes importants en vision par ordinateur bas niveau telles que le lissage sélectif, la séparation d'images, l'intégration robuste et la déconvolution. On propose aussi d'aller au-delà de la parcimonie et apprendre un modèle de mapping spectral non-local pour le débruitage d'images. La notion d'invariance d' échelle joue aussi un rôle important dans nos travaux. En exploitant ce principe, une définition précise des contours est définie, ce qui peut être complémentaire à la notion de parcimonie. Plus précisément, on peut construire des représentations invariantes pour la classification en se basant sur une architecture de réseaux convolutionnels profonds. L'invariance d' échelle permet aussi d'extraire les pixels qui portent les informations nécessaires pour la reconstruction ou aussi améliorer l'estimation du flot optique sur les images turbulentes en imposant la parcimonie comme régularisation sur les exposants de singularité locaux. / In this thesis, we present new techniques based on the notions of sparsity and scale invariance to design fast and efficient image processing applications. Instead of using the popular l1-norm to model sparsity, we focus on the use of non-convex penalties that promote more sparsity. We propose to use a first-order approximation to estimate a solution of non-convex proximal operators, which permits to easily use a wide rangeof penalties. We address also the problem of multi-sparsity, when the minimization problem is composed of various sparse terms, which typically arises in problems that require both a robust estimation to reject outliers and a sparse prior. These techniques are applied to various important problems in low-level computer vision such as edgeaware smoothing, image separation, robust integration and image deconvolution. We propose also to go beyond sparsity models and learn non-local spectral mapping with application to image denoising. Scale-invariance is another notion that plays an important role in our work. Using this principle, a precise definition of edges can be derived which can be complementary to sparsity. More precisely, we can extractinvariant features for classification from sparse representations in a deep convolutional framework. Scale-invariance permits also to extract relevant pixels for sparsifying images. We use this principle as well to improve optical ow estimation on turbulent images by imposing a sparse regularization on the local singular exponents instead of regular gradients.

Une approche efficace pour la résolution de problèmes inverses consiste à définir le signal (ou l'image) recherché(e) par minimisation d'un critère pénalisé. Ce dernier s'écrit souvent sous la forme d'une somme de fonctions composées avec des opérateurs linéaires. En pratique, ces fonctions peuvent n'être ni convexes ni différentiables. De plus, les problèmes auxquels on doit faire face sont souvent de grande dimension. L'objectif de cette thèse est de concevoir de nouvelles méthodes pour résoudre de tels problèmes de minimisation, tout en accordant une attention particulière aux coûts de calculs ainsi qu'aux résultats théoriques de convergence. Une première idée pour construire des algorithmes rapides d'optimisation est d'employer une stratégie de préconditionnement, la métrique sous-jacente étant adaptée à chaque itération. Nous appliquons cette technique à l'algorithme explicite-implicite et proposons une méthode, fondée sur le principe de majoration-minimisation, afin de choisir automatiquement les matrices de préconditionnement. L'analyse de la convergence de cet algorithme repose sur l'inégalité de Kurdyka-L ojasiewicz. Une seconde stratégie consiste à découper les données traitées en différents blocs de dimension réduite. Cette approche nous permet de contrôler à la fois le nombre d'opérations s'effectuant à chaque itération de l'algorithme, ainsi que les besoins en mémoire, lors de son implémentation. Nous proposons ainsi des méthodes alternées par bloc dans les contextes de l'optimisation non convexe et convexe. Dans le cadre non convexe, une version alternée par bloc de l'algorithme explicite-implicite préconditionné est proposée. Les blocs sont alors mis à jour suivant une règle déterministe acyclique. Lorsque des hypothèses supplémentaires de convexité peuvent être faites, nous obtenons divers algorithmes proximaux primaux-duaux alternés, permettant l'usage d'une règle aléatoire arbitraire de balayage des blocs. L'analyse théorique de ces algorithmes stochastiques d'optimisation convexe se base sur la théorie des opérateurs monotones. Un élément clé permettant de résoudre des problèmes d'optimisation de grande dimension réside dans la possibilité de mettre en oeuvre en parallèle certaines étapes de calculs. Cette parallélisation est possible pour les algorithmes proximaux primaux-duaux alternés par bloc que nous proposons: les variables primales, ainsi que celles duales, peuvent être mises à jour en parallèle, de manière tout à fait flexible. A partir de ces résultats, nous déduisons de nouvelles méthodes distribuées, où les calculs sont répartis sur différents agents communiquant entre eux suivant une topologie d'hypergraphe. Finalement, nos contributions méthodologiques sont validées sur différentes applications en traitement du signal et des images. Nous nous intéressons dans un premier temps à divers problèmes d'optimisation faisant intervenir des critères non convexes, en particulier en restauration d'images lorsque l'image originale est dégradée par un bruit gaussien dépendant du signal, en démélange spectral, en reconstruction de phase en tomographie, et en déconvolution aveugle pour la reconstruction de signaux sismiques parcimonieux. Puis, dans un second temps, nous abordons des problèmes convexes intervenant dans la reconstruction de maillages 3D et dans l'optimisation de requêtes pour la gestion de bases de données / An efficient approach for solving an inverse problem is to define the recovered signal/image as a minimizer of a penalized criterion which is often split in a sum of simpler functions composed with linear operators. In the situations of practical interest, these functions may be neither convex nor smooth. In addition, large scale optimization problems often have to be faced. This thesis is devoted to the design of new methods to solve such difficult minimization problems, while paying attention to computational issues and theoretical convergence properties. A first idea to build fast minimization algorithms is to make use of a preconditioning strategy by adapting, at each iteration, the underlying metric. We incorporate this technique in the forward-backward algorithm and provide an automatic method for choosing the preconditioning matrices, based on a majorization-minimization principle. The convergence proofs rely on the Kurdyka-L ojasiewicz inequality. A second strategy consists of splitting the involved data in different blocks of reduced dimension. This approach allows us to control the number of operations performed at each iteration of the algorithms, as well as the required memory. For this purpose, block alternating methods are developed in the context of both non-convex and convex optimization problems. In the non-convex case, a block alternating version of the preconditioned forward-backward algorithm is proposed, where the blocks are updated according to an acyclic deterministic rule. When additional convexity assumptions can be made, various alternating proximal primal-dual algorithms are obtained by using an arbitrary random sweeping rule. The theoretical analysis of these stochastic convex optimization algorithms is grounded on the theory of monotone operators. A key ingredient in the solution of high dimensional optimization problems lies in the possibility of performing some of the computation steps in a parallel manner. This parallelization is made possible in the proposed block alternating primal-dual methods where the primal variables, as well as the dual ones, can be updated in a quite flexible way. As an offspring of these results, new distributed algorithms are derived, where the computations are spread over a set of agents connected through a general hyper graph topology. Finally, our methodological contributions are validated on a number of applications in signal and image processing. First, we focus on optimization problems involving non-convex criteria, in particular image restoration when the original image is corrupted with a signal dependent Gaussian noise, spectral unmixing, phase reconstruction in tomography, and blind deconvolution in seismic sparse signal reconstruction. Then, we address convex minimization problems arising in the context of 3D mesh denoising and in query optimization for database management

Problemas reais em áreas como aprendizado de máquina têm chamado atenção pela enorme quantidade de variáveis (> 10^6) e volume de dados. Em problemas dessa escala o custo para se obter e trabalhar com informações de segunda ordem são proibitivos. Tais problemas apresentam características que podem ser aproveitadas por métodos de busca em coordenada. Essa classe de métodos é caracterizada pela alteração de apenas uma ou poucas variáveis a cada iteração. A variante do método comumente descrita na literatura é a minimização cíclica de variáveis. Porém, resultados recentes sugerem que variantes aleatórias do método possuem melhores garantias de convergência. Nessa variante, a cada iteração, a variável a ser alterada é sorteada com uma probabilidade preestabelecida não necessariamente uniforme. Neste trabalho estudamos algumas variações do método de busca em coordenada. São apresentados aspectos teóricos desses métodos, porém focamos nos aspectos práticos de implementação e na comparação experimental entre variações do método de busca em coordenada aplicados a diferentes problemas com aplicações reais. / Real world problemas in areas such as machine learning are known for the huge number of decision variables (> 10^6) and data volume. For such problems working with second order derivatives is prohibitive. These problems have properties that benefits the application of coordinate descent/minimization methods. These kind of methods are defined by the change of a single, or small number of, decision variable at each iteration. In the literature, the commonly found description of this type of method is based on the cyclic change of variables. Recent papers have shown that randomized versions of this method have better convergence properties. This version is based on the change of a single variable chosen randomly at each iteration, based on a fixed, but not necessarily uniform, distribution. In this work we present some theoretical aspects of such methods, but we focus on practical aspects.

Dans de nombreux domaines tels que l’apprentissage statistique, la recherche opérationnelle ou encore la conception de circuits, une tâche est modélisée par un jeu de paramètres que l’on cherche à optimiser pour prendre la meilleure décision possible. Mathématiquement, le problème revient à minimiser une fonction de l’objectif recherché par des algorithmes itératifs. Le développement de ces derniers dépend alors de la géométrie de la fonction ou de la structure du problème. Dans une première partie, cette thèse étudie comment l’acuité d’une fonction autour de ses minima peut être exploitée par le redémarrage d’algorithmes classiques. Les schémas optimaux sont présentés pour des problèmes convexes généraux. Ils nécessitent cependant une description complète de la fonction, ce qui est rarement disponible. Des stratégies adaptatives sont donc développées et prouvées être quasi-optimales. Une analyse spécifique est ensuite conduite pour les problèmes parcimonieux qui cherchent des représentations compressées des variables du problème. Leur géométrie conique sous-jacente, qui décrit l’acuité de la fonction de l’objectif, se révèle contrôler à la fois la performance statistique du problème et l’efficacité des procédures d’optimisation par une seule quantité. Une seconde partie est dédiée aux problèmes d’apprentissage statistique. Ceux-ci effectuent une analyse prédictive de données à l’aide d’un large nombre d’exemples. Une approche générique est présentée pour à la fois résoudre le problème de prédiction et le simplifier en groupant soit les variables, les exemples ou les tâches. Des méthodes algorithmiques systématiques sont développées en analysant la géométrie induite par une partition des données. Une analyse théorique est finalement conduite lorsque les variables sont groupées par analogie avec les méthodes parcimonieuses. / In numerous fields such as machine learning, operational research or circuit design, a task is modeled by a set of parameters to be optimized in order to take the best possible decision. Formally, the problem amounts to minimize a function describing the desired objective with iterative algorithms. The development of these latter depends then on the characterization of the geometry of the function or the structure of the problem. In a first part, this thesis studies how sharpness of a function around its minimizers can be exploited by restarting classical algorithms. Optimal schemes are presented for general convex problems. They require however a complete description of the function that is rarely available. Adaptive strategies are therefore developed and shown to achieve nearly optimal rates. A specific analysis is then carried out for sparse problems that seek for compressed representation of the variables of the problem. Their underlying conic geometry, that describes sharpness of the objective, is shown to control both the statistical performance of the problem and the efficiency of dedicated optimization methods by a single quantity. A second part is dedicated to machine learning problems. These perform predictive analysis of data from large set of examples. A generic framework is presented to both solve the prediction problem and simplify it by grouping either features, samples or tasks. Systematic algorithmic approaches are developed by analyzing the geometry induced by partitions of the data. A theoretical analysis is then carried out for grouping features by analogy to sparse methods.

Le but de l’apprentissage supervisé est d’inférer des relations entre un phénomène que l’on souhaite prédire et des variables « explicatives ». À cette fin, on dispose d’observations de multiples réalisations du phénomène, à partir desquelles on propose une règle de prédiction. L’émergence récente de sources de données à très grande échelle, tant par le nombre d’observations effectuées (en analyse d’image, par exemple) que par le grand nombre de variables explicatives (en génétique), a fait émerger deux difficultés : d’une part, il devient difficile d’éviter l’écueil du sur-apprentissage lorsque le nombre de variables explicatives est très supérieur au nombre d’observations; d’autre part, l’aspect algorithmique devient déterminant, car la seule résolution d’un système linéaire dans les espaces en jeupeut devenir une difficulté majeure. Des algorithmes issus des méthodes d’approximation stochastique proposent uneréponse simultanée à ces deux difficultés : l’utilisation d’une méthode stochastique réduit drastiquement le coût algorithmique, sans dégrader la qualité de la règle de prédiction proposée, en évitant naturellement le sur-apprentissage. En particulier, le cœur de cette thèse portera sur les méthodes de gradient stochastique. Les très populaires méthodes paramétriques proposent comme prédictions des fonctions linéaires d’un ensemble choisi de variables explicatives. Cependant, ces méthodes aboutissent souvent à une approximation imprécise de la structure statistique sous-jacente. Dans le cadre non-paramétrique, qui est un des thèmes centraux de cette thèse, la restriction aux prédicteurs linéaires est levée. La classe de fonctions dans laquelle le prédicteur est construit dépend elle-même des observations. En pratique, les méthodes non-paramétriques sont cruciales pour diverses applications, en particulier pour l’analyse de données non vectorielles, qui peuvent être associées à un vecteur dans un espace fonctionnel via l’utilisation d’un noyau défini positif. Cela autorise l’utilisation d’algorithmes associés à des données vectorielles, mais exige une compréhension de ces algorithmes dans l’espace non-paramétrique associé : l’espace à noyau reproduisant. Par ailleurs, l’analyse de l’estimation non-paramétrique fournit également un éclairage révélateur sur le cadre paramétrique, lorsque le nombre de prédicteurs surpasse largement le nombre d’observations. La première contribution de cette thèse consiste en une analyse détaillée de l’approximation stochastique dans le cadre non-paramétrique, en particulier dans le cadre des espaces à noyaux reproduisants. Cette analyse permet d’obtenir des taux de convergence optimaux pour l’algorithme de descente de gradient stochastique moyennée. L’analyse proposée s’applique à de nombreux cadres, et une attention particulière est portée à l’utilisation d’hypothèses minimales, ainsi qu’à l’étude des cadres où le nombre d’observations est connu à l’avance, ou peut évoluer. La seconde contribution est de proposer un algorithme, basé sur un principe d’accélération, qui converge à une vitesse optimale, tant du point de vue de l’optimisation que du point de vue statistique. Cela permet, dans le cadre non-paramétrique, d’améliorer la convergence jusqu’au taux optimal, dans certains régimes pour lesquels le premier algorithme analysé restait sous-optimal. Enfin, la troisième contribution de la thèse consiste en l’extension du cadre étudié au delà de la perte des moindres carrés : l’algorithme de descente de gradient stochastiqueest analysé comme une chaine de Markov. Cette approche résulte en une interprétation intuitive, et souligne les différences entre le cadre quadratique et le cadre général. Une méthode simple permettant d’améliorer substantiellement la convergence est également proposée. / The goal of supervised machine learning is to infer relationships between a phenomenon one seeks to predict and “explanatory” variables. To that end, multiple occurrences of the phenomenon are observed, from which a prediction rule is constructed. The last two decades have witnessed the apparition of very large data-sets, both in terms of the number of observations (e.g., in image analysis) and in terms of the number of explanatory variables (e.g., in genetics). This has raised two challenges: first, avoiding the pitfall of over-fitting, especially when the number of explanatory variables is much higher than the number of observations; and second, dealing with the computational constraints, such as when the mere resolution of a linear system becomes a difficulty of its own. Algorithms that take their roots in stochastic approximation methods tackle both of these difficulties simultaneously: these stochastic methods dramatically reduce the computational cost, without degrading the quality of the proposed prediction rule, and they can naturally avoid over-fitting. As a consequence, the core of this thesis will be the study of stochastic gradient methods. The popular parametric methods give predictors which are linear functions of a set ofexplanatory variables. However, they often result in an imprecise approximation of the underlying statistical structure. In the non-parametric setting, which is paramount in this thesis, this restriction is lifted. The class of functions from which the predictor is proposed depends on the observations. In practice, these methods have multiple purposes, and are essential for learning with non-vectorial data, which can be mapped onto a vector in a functional space using a positive definite kernel. This allows to use algorithms designed for vectorial data, but requires the analysis to be made in the non-parametric associated space: the reproducing kernel Hilbert space. Moreover, the analysis of non-parametric regression also sheds some light on the parametric setting when the number of predictors is much larger than the number of observations. The first contribution of this thesis is to provide a detailed analysis of stochastic approximation in the non-parametric setting, precisely in reproducing kernel Hilbert spaces. This analysis proves optimal convergence rates for the averaged stochastic gradient descent algorithm. As we take special care in using minimal assumptions, it applies to numerous situations, and covers both the settings in which the number of observations is known a priori, and situations in which the learning algorithm works in an on-line fashion. The second contribution is an algorithm based on acceleration, which converges at optimal speed, both from the optimization point of view and from the statistical one. In the non-parametric setting, this can improve the convergence rate up to optimality, even inparticular regimes for which the first algorithm remains sub-optimal. Finally, the third contribution of the thesis consists in an extension of the framework beyond the least-square loss. The stochastic gradient descent algorithm is analyzed as a Markov chain. This point of view leads to an intuitive and insightful interpretation, that outlines the differences between the quadratic setting and the more general setting. A simple method resulting in provable improvements in the convergence is then proposed.