This research investigated the concept of a sparsity method inspired by the principles of structural plasticity in the brain in order to create a sparse model of the Bayesian Confidence Propagation Neural Networks (BCPNN) during the training phase. This was done by extending the structural plasticity in the implementation of the BCPNN. While the initial algorithm presented two synaptic states (Active and Silent), this research extended it to three synaptic states (Active, Silent and Absent) with the aim to enhance sparsity configurability and emulate a more brain-like algorithm, drawing parallels with synaptic states observed in the brain. Benchmarking was conducted using the MNIST and Fashion-MNIST dataset, where the proposed threestate model was compared against the previous two-state model in terms of representational learning. The findings suggest that the three-state model not only provides added configurability but also, in certain low-sparsity settings, showcases similar representational learning abilities as the two-state model. Moreover, in high-sparsity settings, the three-state model demonstrates a commendable balance between accuracy and sparsity trade-off. / Denna forskning undersökte en konceptuell metod för gleshet inspirerad av principerna för strukturell plasticitet i hjärnan för att skapa glesa BCPNN. Forskningen utvidgade strukturell plasticitet i en implementering av BCPNN. Medan den ursprungliga algoritmen presenterade två synaptiska tillstånd (Aktiv och Tyst), utvidgade denna forskning den till tre synaptiska tillstånd (Aktiv, Tyst och Frånvarande) med målet att öka konfigurerbarheten av sparsitet och efterlikna en mer hjärnliknande algoritm, med paralleller till synaptiska tillstånd observerade i hjärnan. Jämförelse gjordes med hjälp av MNIST och Fashion-MNIST datasetet, där det föreslagna tre-tillståndsmodellen jämfördes med den tidigare tvåtillståndsmodellen med avseende på representationslärande. Resultaten tyder på att tre-tillståndsmodellen inte bara ger ökad konfigurerbarhet utan också, i vissa lågt glesa inställningar, visar samma inlärningsförmåga som två-tillståndsmodellen. Dessutom visar den tre-tillståndsmodellen i högsparsamma inställningar en anmärkningsvärd balans mellan noggrannhet och avvägningen mellan sparsitet.

Random matrix theory (RMT) is a mathematical framework that has found profound applications in physics, particularly in the study of many-body systems. Its success lies in its ability to predict universal statistical properties of complex systems, independent of the specific details. This thesis explores the application of RMT to two classes of many-body systems: quantum and stochastic many-body systems. Within the quantum framework, this work focuses on the Bose-Hubbard system, which is paradigmatic for modeling ultracold atoms in optical traps. According to RMT and the Eigenstate Thermalization Hypothesis (ETH), eigenstate-to-eigenstate fluctuations of expectation values of local observables decay rapidly with the system size in the thermodynamic limit at sufficiently large temperatures. Here, we study these fluctuations in the classical limit of fixed lattice size and increasing boson number. We find that the fluctuations follow the RMT prediction for large system sizes but deviate substantially for small lattices. Partly motivated by these results, the Bose-Hubbard model on three sites is studied in more detail. On few sites, the Bose-Hubbard model is known to be a mixed system, being neither fully chaotic nor integrable. We compare energy-resolved classical and quantum measures of chaos, which show a strong agreement. Deviations from RMT predictions are attributed to the mixed nature of the few-site model. In the context of stochastic systems, generators of Markov processes are studied. The focus is on the spectrum. We present results from two investigations of Markov spectra. First, we investigate the effect of sparsity on the spectrum of random generators. Dense random matrices previously used as a model for generic generators led to very large spectral gaps and therefore to unphysically short relaxation times. In this work, a model of random generators with adjustable sparsity — number of zero matrix elements — is presented, extending the dense framework. It is shown that sparsity leads to longer, more physically realistic relaxation times. Second, the generator spectrum of the Asymmetric Simple Exclusion Process (ASEP), a quintessential model in non-equilibrium statistical mechanics, is analyzed. We investigate the spectral boundary, which is characterized by pronounced spikes. The emergence of these spikes is analyzed from several points of view, including RMT. The results presented in this thesis contribute to the understanding of the applicability of RMT to many-body systems. This thesis highlights successes such as the explanation of “ETH fluctuations” in Bose-Hubbard models, the improvement of random matrix descriptions by introducing sparsity, and the emergence of spikes in the spectral boundary of the ASEP. The latter is a notable case where RMT provides insights even though the ASEP is a Bethe-integrable system. Furthermore, this thesis shows examples of the limits of RMT, exemplified by the results presented for the Bose-Hubbard model with a few sites.

Les systèmes de communications sans fil ne cessent de se multiplier pour devenir incontournables de nos jours. Cette croissance cause une augmentation de la demande des ressources spectrales, qui sont devenues de plus en plus rares. Afin de résoudre ce problème de pénurie de fréquences, Joseph Mitola III, en 2000, a introduit l'idée de l'allocation dynamique du spectre. Il définit ainsi le terme « Cognitive Radio » (Radio Intelligente), qui est largement pressenti pour être le prochain Big Bang dans les futures communications sans fil [1]. Dans le cadre de ce travail on s'intéresse à la problématique du spectrum sensing qui est la détection de présence des Utilisateurs Primaires dans un spectre sous licence, dans le contexte de la radio intelligente. L'objectif de ce travail est de proposer des méthodes de détection efficaces à faible complexité et/ou à faible temps d'observation et ceci en utilisant le minimum d'information a priori sur le signal à détecter. Dans la première partie on traite le problème de détection d'un signal aléatoire dans le bruit. Deux grandes méthodes de détection sont utilisées : la détection d'énergie ou radiomètre et la détection cyclostationnaire. Dans notre contexte, ces méthodes sont plus complémentaires que concurrentes. Nous proposons une architecture hybride de détection des bandes libres, qui combine la simplicité du radiomètre et la robustesse des détecteurs cyclostationnaires. Deux méthodes de détection sont proposées qui se basent sur cette même architecture. Grâce au caractère adaptatif de l'architecture, la détection évolue au cours du temps pour tendre vers la complexité du détecteur d'énergie avec des performances proches du détecteur cyclostationnaire ou du radiomètre selon la méthode utilisée et l'environnement de travail. Dans un second temps on exploite la propriété parcimonieuse de la Fonction d'Autocorrelation Cyclique (FAC) pour proposer un nouvel estimateur aveugle qui se base sur le compressed sensing afin d'estimer le Vecteur d'Autocorrelation Cyclique (VAC), qui est un vecteur particulier de la Fonction d'Autocorrelation Cyclique pour un délai fixe. On montre par simulation que ce nouvel estimateur donne de meilleures performances que celles obtenues avec l'estimateur classique, qui est non aveugle et ceci dans les mêmes conditions et en utilisant le même nombre d'échantillons. On utilise l'estimateur proposé, pour proposer deux détecteurs aveugles utilisant moins d'échantillons que nécessite le détecteur temporel de second ordre de [2] qui se base sur l'estimateur classique de la FAC. Le premier détecteur exploite uniquement la propriété de parcimonie du VAC tandis que le second détecteur exploite en plus de la parcimonie la propriété de symétrie du VAC, lui permettant ainsi d'obtenir de meilleures performances. Ces deux détecteurs outre qu'ils sont aveugles sont plus performants que le détecteur non aveugle de [2] dans le cas d'un faible nombre d'échantillons. / The wireless communications systems continue to grow and has become very essential nowadays. This growth causes an increase in the demand of spectrum resources, which have become more and more scarce. To solve this problem of spectrum scarcity, Joseph Mitola III, in the year 2000, introduced the idea of dynamic spectrum allocation. Mitola defines the term “Cognitive Radio”, which is widely expected to be the next Big Bang in wireless communications [1]. In this work we focus on the problem of spectrum sensing which is the detection of the presence of primary users in licensed spectrum, in the context of cognitive radio. The objective of this work is to propose effective detection methods at low-complexity and/or using short observation time, using minimal a priori information about the signal to be detected. In the first part of this work we deal with the problem of detecting a random signal in noise. Two main methods of detection are used: energy detection or radiometer and cyclostationary detection. In our context, these methods are more complementary than competitive. We propose a hybrid architecture for detecting free bands, which combines the simplicity of the radiometer and the robustness of the cyclostationary detection. Two detection methods are proposed that are based on this same hybrid architecture. Thanks to the adaptive nature of the architecture, the complexity of the detector decreases over time to tend to the one of an energy detector with close performance to the cyclostationary detector or to the performance of a radiometer, depending on the used method and on the working environment. In the second part of this work we exploit the sparse property of the Cyclic Autocorrelation Function (CAF) to propose a new blind estimator based on compressed sensing that estimates the Cyclic Autocorrelation Vector (CAV) which is a particular vector of the CAF for a given lag. It is shown by simulation that this new estimator gives better performances than those obtained with the classical estimator, which is non-blind, under the same conditions and using the same number of samples. Using the new estimator, we propose two blind detectors that require fewer samples than the second order time domain detector of [2] which is based on the classical estimator of the CAF. The first detector uses only the sparse property of the CAV while the second detector exploits the symmetry property of the CAV in addition to its sparse property, resulting in better performances. Both detectors, although they are blind, are more efficient than the non-blind detector of [2] in the case of a small number of samples.

Cette thèse s’intéresse à la création de nouvelles approches algorithmiques pour la résolution du problème inverse en biophysiques. Dans un premier temps, on vise l’application RMN de type DOSY: une nouvelle approche de régularisation hybride a été proposée avec un nouvel algorithme PALMA (http://palma.labo.igbmc.fr/). Cet algorithme permet d’analyser des données réelles DOSY avec une précision importante quelque soit leur type. Dans un deuxième temps, notre intérêt s’est tourné vers l’application de spectrométrie de masse. Nous avons proposé une nouvelle approche par dictionnaire dédiée à l’analyse protéomique en utilisant le modèle averagine et une stratégie de minimisation sous contraintes d'une pénalité de parcimonie. Afin d’améliorer la précision de l’information obtenue, nous avons proposé une nouvelle méthode SPOQ, basée sur une nouvelle fonction de pénalisation, résolue par un nouvel algorithme Forward-Backward à métrique variable localement ajustée. Tous nos algorithmes bénéficient de garanties théoriques de convergence, et ont été validés expérimentalement sur des spectres synthétisés et des données réelles / This thesis aims at proposing new approaches to solve the inverse problem in biophysics. Firstly, we study the DOSY NMR experiment: a new hybrid regularization approach has been proposed with a novel PALMA algorithm (http://palma.labo.igbmc.fr/). This algorithm ensures the efficient analysis of real DOSY data with a high precision for all different type. In a second time, we study the mass spectrometry application. We have proposed a new dictionary based approach dedicated to proteomic analysis using the averagine model and the constrained minimization approach associated with a sparsity inducing penalty. In order to improve the accuracy of the information, we proposed a new SPOQ method based on a new penalization, solved with a new Forward-Backward algorithm with a variable metric locally adjusted. All our algorithms benefit from sounded convergence guarantees, and have been validated experimentally on synthetics and real data.

This thesis is concerned with methods for Bayesian inference and their applications in astrophysics. We principally discuss two related themes: advances in nested sampling (Chapters 3 to 5), and Bayesian sparse reconstruction of signals from noisy data (Chapters 6 and 7). Nested sampling is a popular method for Bayesian computation which is widely used in astrophysics. Following the introduction and background material in Chapters 1 and 2, Chapter 3 analyses the sampling errors in nested sampling parameter estimation and presents a method for estimating them numerically for a single nested sampling calculation. Chapter 4 introduces diagnostic tests for detecting when software has not performed the nested sampling algorithm accurately, for example due to missing a mode in a multimodal posterior. The uncertainty estimates and diagnostics in Chapters 3 and 4 are implemented in the $\texttt{nestcheck}$ software package, and both chapters describe an astronomical application of the techniques introduced. Chapter 5 describes dynamic nested sampling: a generalisation of the nested sampling algorithm which can produce large improvements in computational efficiency compared to standard nested sampling. We have implemented dynamic nested sampling in the $\texttt{dyPolyChord}$ and $\texttt{perfectns}$ software packages. Chapter 6 presents a principled Bayesian framework for signal reconstruction, in which the signal is modelled by basis functions whose number (and form, if required) is determined by the data themselves. This approach is based on a Bayesian interpretation of conventional sparse reconstruction and regularisation techniques, in which sparsity is imposed through priors via Bayesian model selection. We demonstrate our method for noisy 1- and 2-dimensional signals, including examples of processing astronomical images. The numerical implementation uses dynamic nested sampling, and uncertainties are calculated using the methods introduced in Chapters 3 and 4. Chapter 7 applies our Bayesian sparse reconstruction framework to artificial neural networks, where it allows the optimum network architecture to be determined by treating the number of nodes and hidden layers as parameters. We conclude by suggesting possible areas of future research in Chapter 8.

Είναι γνωστό από τη Θεωρία της Πληροφορίας, πως η δειγματοληψία σημάτων ακολουθεί το Θεώρημα των Shannon-Nyquist. Σύμφωνα με το θεώρημα αυτό, για την εκτέλεση της δειγματοληψίας ενός σήματος χωρίς απώλεια πληροφορίας, ο ρυθμός δειγματοληψίας αυτού θα πρέπει να είναι τουλάχιστον δύο φορές μεγαλύτερος από τη μεγαλύτερη συχνότητα που εμφανίζεται στο φάσμα του σήματος. Αυτή τη θεωρία κατάφερε – κατά κάποιο τρόπο - να ανατρέψει το 2006 μια νέα, αυτή της Συμπιεσμένης Καταγραφής που ξεκίνησε από δύο επιστημονικές εργασίες των Donoho, Candes, Romberg και Tao και η οποία έρχεται να αλλάξει τα έως σήμερα δεδομένα. Σήμερα, λίγα έτη αργότερα, μια αφθονία θεωρητικών πτυχών της συμπιεσμένης καταγραφής εξερευνάται ήδη σε περισσότερες από 1000 δημοσιεύσεις. Οι εφαρμογές αυτής της τεχνικής εκτείνονται και σε άλλα πεδία όπως η επεξεργασία εικόνας, η μαγνητική τομογραφία, η ανάλυση γεωφυσικών δεδομένων, η επεξεργασία εικόνας radar, η αστρονομία κ.α. Η μέθοδος της συμπιεσμένης καταγραφής ή αλλιώς Compressed Sensing ή Compressed Sampling, όπως αυτή είναι γνωστή στη βιβλιογραφία, στηρίζεται στη δυνατότητα ανακατασκευής αραιών σημάτων από πλήθος δειγμάτων αισθητά κατώτερο από αυτό που προβλέπει το θεωρητικό όριο του Nyquist. Έχει αποδειχθεί ότι, η ανακατασκευή αυτή είναι δυνατή όταν το σήμα ή έστω κάποιος μετασχηματισμός του περιέχει λίγα μη μηδενικά στοιχεία σε σχέση με το μήκος του. Στα πλαίσια αυτής της εργασίας παρουσιάζονται οι βασικές αρχές που διέπουν την ανακατασκευή αραιών σημάτων μέσω της επίλυσης υπο-ορισμένων συστημάτων γραμμικών εξισώσεων. Στη συγκεκριμένη εργασία, γίνεται μία προσπάθεια εφαρμογής της εν λόγω μεθόδου στα ανερχόμενα Cognitive Radio δίκτυα (Cognitive Radio Networks - CRN) τα οποία εμφανίζουν την ιδιότητα Spectrum Sharing. Σύμφωνα με αυτή την ιδιότητα, δηλαδή, το διαμοιρασμό του διαθέσιμου φάσματος, ο πρωταρχικός στόχος, είναι η ανίχνευση και η αναγνώριση των λεγόμενων spectrum holes σε ασύρματο περιβάλλον. Πιο συγκεκριμένα, παρουσιάζεται μια Distributed (κατανεμημένη) προσέγγιση συμπιεσμένης καταγραφής φάσματος για (τα ultra-) Wideband Cognitive Radio δίκτυα. Η τεχνική Compressed Sensing εφαρμόζεται σε τοπικά CRs του δικτύου, προκειμένου να ανιχνεύσει το υπερ-ευρύ φάσμα (ultra-wideband) με ρεαλιστική πολυπλοκότητα ανάκτησης του αρχικού σήματος. Οι φασματικές εκτιμήσεις από πολλαπλούς τοπικούς CRs του δικτύου «συνενώνονται» για να αποκομίσουν το χωρικό κέρδος ποικιλομορφίας (spatial diversity gain), το οποίο όσο αυξάνεται, βελτιώνει την ποιότητα ανίχνευσης, ειδικά στην περίπτωση των υπό εξασθένιση καναλιών (channel fading effect). Αρχικά, μελετάται ένας κατανεμημένος αλγόριθμος πλειοψηφίας (Distributed Consensus Algorithm) για να επιτευχθεί η συνεργασία κατά το στάδιο της ανίχνευσης της πληροφορίας που μεταφέρεται στο δίκτυο και έπειτα η αποστολή αυτής σε ένα fusion center. Αυτού του είδους ο distributed αλγόριθμος που χρησιμοποιεί μόνο one-hop επικοινωνία, συγκλίνει γρήγορα σε συνολικά βέλτιστες λύσεις που λειτουργούν με χαμηλό φόρτο επικοινωνίας και υπολογισμού που είναι ανάλογο του μεγέθους του δικτύου. Ένα σενάριο που εξετάζεται στο πλαίσιο αυτής της εργασίας, είναι η συγκεντρωτική ανίχνευση φάσματος ευρείας ζώνης με επικαλυπτόμενες συχνότητες ή αλλιώς κανάλια που είναι κοινά (frequency overlapping) σε Cognitive Radio δίκτυα και τα οποία, χρησιμοποιούν την τεχνική Compressed Sensing καθώς επίσης και την από κοινού ανακατασκευή (Joint Reconstruction) του αρχικού σήματος. Τέλος, προτείνεται ένα σενάριο, μιας κατανεμημένης αυτή τη φορά, τεχνικής ανίχνευσης φάσματος, που βασίζεται σε κανόνες πλειοψηφίας. Τα αποτελέσματα της προσομοίωσης, σε περιβάλλον Matlab, επιβεβαιώνουν την αποτελεσματικότητα αυτής της προτεινόμενης προσέγγισης, δηλαδή την ανίχνευση φάσματος, από συνδυασμό Cognitive Radio δικτύων με αραιά επικαλυπτόμενες συχνότητες. / It is well known from Information Theory, that the sampling of signals should be performed as dictated by the celebrated Shannon – Nyquist theorem. According to this theorem, in order to fully recover a signal from its samples, it must be sampled at a sampling rate that should be at least twice the bandwidth of the signal. This theory has been significantly extended over the past few years by the advent of the so-called Compressed Sensing theory, which first appeared in seminal scientific articles of Donoho, Candes, Romberg and Tao in 2006. Nowadays, an abundance of theoretical aspects of compressed sensing is already explored in more than 1000 articles. Τhis technique has been applied in various fields such as image processing, magnetic tomography, analysis of geophysical data, radar image processing, astronomy etc. The method of Compressed Sensing, also known as Compressed Sampling, is related to the reconstruction of sparse signals from far fewer samples or measurements than what the theoretical limit of Nyquist suggests. It has been proved that, this reconstruction is possible when the signal or a transformation of it, contains just a few non-zero elements with respect to its length. In this work, we firstly summarize the basic principles that condition the reconstruction of sparse signals via the solution of underdetermined systems of linear equations. Next, in this Master Thesis we aim at implementing Compressed Sensing method in emerging Cognitive Radio (CR) networks with spectrum sharing. The first cognitive task preceding any dynamic spectrum access is the sensing and identification of spectral holes in wireless environments. In more detail, this work is mainly concerned with a distributed compressed spectrum sensing approach for (ultra-)wideband CR networks. Compressed sensing is performed at local CRs to scan the very wide spectrum at practical signal-acquisition complexity. Meanwhile, spectral estimates from multiple local CR detectors are fused to collect spatial diversity gain, which improves the sensing quality especially under fading channels. Initially, a distributed consensus algorithm is analyzed for collaborative sensing and fusion in a scenario where all nodes are estimating the same spectral bands. Using only one-hop local communications, this distributed algorithm converges fast to the globally optimal solutions, at low communication and computation load scalable to the network size. Another scenario that has been investigated in this thesis is the joint wideband spectrum sensing in frequency overlapping cognitive radio networks, using centralized compressive sensing techniques. Finally, for the latter scenario, a distributed compressive sensing technique, based on consensus, has been proposed. Simulation results in Matlab environment verify the effectiveness of proposed joint spectrum sensing approach in jointly sparse frequency overlapping cognitive radio networks.

Nous proposons deux nouvelles approches pour les systèmes de recommandation et les réseaux. Dans la première partie, nous donnons d’abord un aperçu sur les systèmes de recommandation avant de nous concentrer sur les approches de rang faible pour la complétion de matrice. En nous appuyant sur une approche probabiliste, nous proposons de nouvelles fonctions de pénalité sur les valeurs singulières de la matrice de rang faible. En exploitant une représentation de modèle de mélange de cette pénalité, nous montrons qu’un ensemble de variables latentes convenablement choisi permet de développer un algorithme espérance-maximisation afin d’obtenir un maximum a posteriori de la matrice de rang faible complétée. L’algorithme résultant est un algorithme à seuillage doux itératif qui adapte de manière itérative les coefficients de réduction associés aux valeurs singulières. L’algorithme est simple à mettre en œuvre et peut s’adapter à de grandes matrices. Nous fournissons des comparaisons numériques entre notre approche et de récentes alternatives montrant l’intérêt de l’approche proposée pour la complétion de matrice à rang faible. Dans la deuxième partie, nous présentons d’abord quelques prérequis sur l’approche bayésienne non paramétrique et en particulier sur les mesures complètement aléatoires et leur extension multivariée, les mesures complètement aléatoires composées. Nous proposons ensuite un nouveau modèle statistique pour les réseaux creux qui se structurent en communautés avec chevauchement. Le modèle est basé sur la représentation du graphe comme un processus ponctuel échangeable, et généralise naturellement des modèles probabilistes existants à structure en blocs avec chevauchement au régime creux. Notre construction s’appuie sur des vecteurs de mesures complètement aléatoires, et possède des paramètres interprétables, chaque nœud étant associé un vecteur représentant son niveau d’affiliation à certaines communautés latentes. Nous développons des méthodes pour simuler cette classe de graphes aléatoires, ainsi que pour effectuer l’inférence a posteriori. Nous montrons que l’approche proposée peut récupérer une structure interprétable à partir de deux réseaux du monde réel et peut gérer des graphes avec des milliers de nœuds et des dizaines de milliers de connections. / We propose two novel approaches for recommender systems and networks. In the first part, we first give an overview of recommender systems and concentrate on the low-rank approaches for matrix completion. Building on a probabilistic approach, we propose novel penalty functions on the singular values of the low-rank matrix. By exploiting a mixture model representation of this penalty, we show that a suitably chosen set of latent variables enables to derive an expectation-maximization algorithm to obtain a maximum a posteriori estimate of the completed low-rank matrix. The resulting algorithm is an iterative soft-thresholded algorithm which iteratively adapts the shrinkage coefficients associated to the singular values. The algorithm is simple to implement and can scale to large matrices. We provide numerical comparisons between our approach and recent alternatives showing the interest of the proposed approach for low-rank matrix completion. In the second part, we first introduce some background on Bayesian nonparametrics and in particular on completely random measures (CRMs) and their multivariate extension, the compound CRMs. We then propose a novel statistical model for sparse networks with overlapping community structure. The model is based on representing the graph as an exchangeable point process, and naturally generalizes existing probabilistic models with overlapping block-structure to the sparse regime. Our construction builds on vectors of CRMs, and has interpretable parameters, each node being assigned a vector representing its level of affiliation to some latent communities. We develop methods for simulating this class of random graphs, as well as to perform posterior inference. We show that the proposed approach can recover interpretable structure from two real-world networks and can handle graphs with thousands of nodes and tens of thousands of edges.

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.

Cette thèse porte sur l'utilisation du BLASSO, un problème d'optimisation convexe en dimension infinie généralisant le LASSO aux mesures, pour la super-résolution de sources ponctuelles. Nous montrons d'abord que la stabilité du support des solutions, pour N sources se regroupant, est contrôlée par un objet appelé pré-certificat aux 2N-1 dérivées nulles. Quand ce pré-certificat est non dégénéré, dans un régime de petit bruit dont la taille est contrôlée par la distance minimale séparant les sources, le BLASSO reconstruit exactement le support de la mesure initiale. Nous proposons ensuite l'algorithme Sliding Frank-Wolfe, une variante de l'algorithme de Frank-Wolfe avec déplacement continu des amplitudes et des positions, qui résout le BLASSO. Sous de faibles hypothèses, cet algorithme converge en un nombre fini d'itérations. Nous utilisons cet algorithme pour un problème 3D de microscopie par fluorescence en comparant trois modèles construits à partir des techniques PALM/STORM. / This thesis studies the noisy sparse spikes super-resolution problem for positive measures using the BLASSO, an infinite dimensional convex optimization problem generalizing the LASSO to measures. First, we show that the support stability of the BLASSO for N clustered spikes is governed by an object called the (2N-1)-vanishing derivatives pre-certificate. When it is non-degenerate, solving the BLASSO leads to exact support recovery of the initial measure, in a low noise regime whose size is controlled by the minimal separation distance of the spikes. In a second part, we propose the Sliding Frank-Wolfe algorithm, based on the Frank-Wolfe algorithm with an added step moving continuously the amplitudes and positions of the spikes, that solves the BLASSO. We show that, under mild assumptions, it converges in a finite number of iterations. We apply this algorithm to the 3D fluorescent microscopy problem by comparing three models based on the PALM/STORM technics.

L’apprentissage adaptatif distribué sur les réseaux permet à un ensemble d’agents de résoudre des problèmes d’estimation de paramètres en ligne en se basant sur des calculs locaux et sur des échanges locaux avec les voisins immédiats. La littérature sur l’estimation distribuée considère essentiellement les problèmes à simple tâche, où les agents disposant de fonctions objectives séparables doivent converger vers un vecteur de paramètres commun. Cependant, dans de nombreuses applications nécessitant des modèles plus complexes et des algorithmes plus flexibles, les agents ont besoin d’estimer et de suivre plusieurs vecteurs de paramètres simultanément. Nous appelons ce type de réseau, où les agents doivent estimer plusieurs vecteurs de paramètres, réseau multitâche. Bien que les agents puissent avoir différentes tâches à résoudre, ils peuvent capitaliser sur le transfert inductif entre eux afin d’améliorer les performances de leurs estimés. Le but de cette thèse est de proposer et d’étudier de nouveaux algorithmes d’estimation distribuée sur les réseaux multitâches. Dans un premier temps, nous présentons l’algorithme diffusion LMS qui est une stratégie efficace pour résoudre les problèmes d’estimation à simple-tâche et nous étudions théoriquement ses performances lorsqu’il est mis en oeuvre dans un environnement multitâche et que les communications entre les noeuds sont bruitées. Ensuite, nous présentons une stratégie de clustering non-supervisé permettant de regrouper les noeuds réalisant une même tâche en clusters, et de restreindre les échanges d’information aux seuls noeuds d’un même cluster / Distributed adaptive learning allows a collection of interconnected agents to perform parameterestimation tasks from streaming data by relying solely on local computations and interactions with immediate neighbors. Most prior literature on distributed inference is concerned with single-task problems, where agents with separable objective functions need to agree on a common parameter vector. However, many network applications require more complex models and flexible algorithms than single-task implementations since their agents involve the need to estimate and track multiple objectives simultaneously. Networks of this kind, where agents need to infer multiple parameter vectors, are referred to as multitask networks. Although agents may generally have distinct though related tasks to perform, they may still be able to capitalize on inductive transfer between them to improve their estimation accuracy. This thesis is intended to bring forth advances on distributed inference over multitask networks. First, we present the well-known diffusion LMS strategies to solve single-task estimation problems and we assess their performance when they are run in multitask environments in the presence of noisy communication links. An improved strategy allowing the agents to adapt their cooperation to neighbors sharing the same objective is presented in order to attain improved learningand estimation over networks. Next, we consider the multitask diffusion LMS strategy which has been proposed to solve multitask estimation problems where the network is decomposed into clusters of agents seeking different