La découverte de motifs fréquents est un des problèmes en fouille de données. Afin de mieux comprendre l'influence des données sur les algorithmes, nous présentons une étude expérimentale des jeux de données communément utilisés par la communauté. Cette étude permet d'aboutir à une nouvelle classification des données en fonction des bordures : stable et en accord avec les performances des algorithmes. Malgré le grand nombre de travaux et un cadre théorique des problèmes d'extraction de motifs intéressants, l'utilisation de ces algorithmes pour résoudre des problèmes "équivalents" est peu répandue et reste délicate. Face à ces limites, nous proposons un algorithme générique de découverte des bordures des motifs intéressants, appelé ABS (Adaptive borders Search), adaptant dynamiquement sa stratégie en fonction des données. De plus, une librairie générique de composants C++ a été proposée pour faciliter le développement de solutions logicielles pour cette famille de problèmes.

Nous étudions le comportement des extensions linéaires au travers de deux invariants de comparabilité: le nombre de sauts et la dimension. La reconnaissance des ordres de Dilworth est montrée comme étant NP-complète, nous donnons des algorithmes polynomiaux pour résoudre ce problème sur deux sous-classes. Nous définissons les notions de dimension gloutonne et dimension dfgloutonne et étudions les cas d'égalité avec la dimension classique. Nous montrons la relation très étroite entre les extensions linéaires dfgloutonnes et les parcours en profondeur. Deux problèmes concernant les extensions linéaires dfgloutonnes sont montrés comme étant NP-difficiles.

La multiplication des sources d'information et le développement de nouvelles technologies ont engendré des bases données complexes, souvent caractérisées par un nombre de variables relativement élevé par rapport aux individus. En particulier, dans les études environnementales sur la pollution de l'air intérieur, la collecte des informations sur les individus se fait au regard de plusieurs thématiques, engendrant ainsi des données de grande dimension avec une structure multi-blocs définie par les thématiques. L'objectif de ce travail a été de développer des méthodes de classification adaptées à ces jeux de données de grande dimension et structurées en blocs de variables. La première partie de ce travail présente un état de l'art des méthodes de classification en général et dans le cas de la grande dimension. Dans la deuxième partie, trois nouvelles approches de classification d'individus décrits par des variables structurées en blocs ont été proposées. La méthode 2S-SOM (Soft Subspace-Self Organizing Map), une approche de type subspace clustering basée sur une modification de la fonction de coût de l'algorithme des cartes topologiques à travers un double système de poids adaptatifs défini sur les blocs et sur les variables. Nous proposons ensuite des approches CSOM (Consensus SOM) et Rv-CSOM de recherche de consensus de cartes auto-organisées basées sur un système de poids déterminés à partir des partitions initiales. Enfin, la troisième partie présente une application de ces méthodes sur le jeu de données réelles de la campagne nationale logement (CNL) menée par l'OQAI afin de définir une typologie des logements au regard des thématiques : qualité de l'air intérieur, structure du bâtiment, composition des ménages et habitudes des occupants.

Nous présentons ici nos résultats de recherche depuis 2001 sur l'algorithmique des graphes linéaires, la recherche de motif (avec ou sans topologie) dans les graphes, et la génomique comparative.

Cette thèse est dédiée à l'analyse probabiliste d'algorithmes de réduction des réseaux euclidiens. Un réseau euclidien est l'ensemble de combinaisons linéaires à coefficients entiers d'une base (b_1,..., b_n ) \subset R^n. La réduction d'un réseau consiste a en trouver une base formée de vecteurs assez courts et assez orthogonaux, à partir d'une base donnée en entrée. Le célèbre algorithme LLL résout ce problème de manière efficace en dimension arbitraire. Il est très utilisé, mais mal compris. Nous nous concentrons sur son analyse dans le cas n = 2, où LLL devient l'algorithme de Gauss, car cette instance est une brique de base pour le cas n>= 3. Nous analysons précisément l'algorithme de Gauss, tant du point de vue de son exécution (nombre d'itérations, complexité binaire, coûts "additifs") que de la géométrie de la base de sortie (défaut d'Hermite, premier minimum et deuxième minimum orthogonalisé). Nous travaillons dans un modèle probabiliste très général, qui permet d'étudier aussi bien les instances faciles que les instances difficiles. Ce modèle nous a permis d'étudier la transition vers l'algorithme d'Euclide, qui correspond au cas où les vecteurs de la base d'entrée sont colinéaires. Nous utilisons des méthodes dynamiques : les algorithmes sont vus comme des systèmes dynamiques, et les séries génératrices concernées s'expriment en fonction de l'opérateur de transfert. Ces résultats très précis en dimension 2 sont une première étape pour l'analyse de l'algorithme LLL dans le cas général.

Nous présentons une nouvelle méthode pour la restauration d'images sismiques. Quand on l'observe, une image sismique est le résultat d'un système de dépôt initial qui a été transformé par un ensemble de déformations géologiques successives (flexions, glissement de la faille, etc) qui se sont produites sur une grande période de temps. L'objectif de la restauration sismique consiste à inverser les déformations pour fournir une image résultante qui représente le système de dépôt géologique tel qu'il était dans un état antérieur. Classiquement, ce procédé permet de tester la cohérence des hypothèses d'interprétations formulées par les géophysiciens sur les images initiales. Dans notre contribution, nous fournissons un outil qui permet de générer rapidement des images restaurées et qui aide donc les géophysiciens à reconnaître et identifier les caractéristiques géologiques qui peuvent être très fortement modifiées et donc difficilement identifiables dans l'image observée d'origine. Cette application permet alors d'assister ces géophysiciens pour la formulation d'hypothèses d'interprétation des images sismiques. L'approche que nous introduisons est basée sur un processus de minimisation qui exprime les déformations géologiques en termes de contraintes géométriques. Nous utilisons une approche itérative de Gauss-Newton qui converge rapidement pour résoudre le système. Dans une deuxième partie de notre travail nous montrons différents résultats obtenus dans des cas concrets afin d'illustrer le processus de restauration d'image sismique sur des données réelles et de montrer comment la version restaurée peut être utilisée dans un cadre d'interprétation géologique.

<p>We start by slightly modifying the generic framework for solving online covering and packing linear programs (LP) proposed in the seminal work of Buchbinder and Naor (Mathematics of Operations Research, 34, 2009) to obtain efficient implementations in settings in which one has access to a separation oracle.</p> <p><br></p> <p>We then apply the generic framework to several online network connectivity problems with LP formulations, namely pairwise spanners and directed Steiner forests. Our results are comparable to the previous state-of-the-art results for these problems in the offline setting.</p> <p><br></p> <p>Further, we extend the generic frameworks to online optimization problems enhanced with <strong>machine-learning predictions</strong>. In particular, we present <strong>learning-augmented</strong> algorithms for online covering LPs and semidefinite programs (SDP), which outperform any optimal online algorithms when the prediction is accurate while maintaining reasonable guarantees when the prediction is misleading. Specifically, we obtain general online learning-augmented algorithms for covering LPs with fractional advice and general constraints and initiate the study of learning-augmented algorithms for covering SDPs.</p>

<p>Collecting user data is crucial for advancing machine learning, social science, and government policies, but the privacy of the users whose data is being collected is a growing concern. {\em Differential Privacy (DP)} has emerged as the most standard notion for privacy protection with robust mathematical guarantees. Analyzing such massive amounts of data in a privacy-preserving manner motivates the need to study differentially-private algorithms that are also super-efficient.  </p> <p><br></p> <p>This thesis initiates a systematic study of differentially-private sublinear-time and sublinear-space algorithms. The contributions of this thesis are two-fold. First, we design some of the first differentially private sublinear algorithms for many fundamental problems. Second, we develop general DP techniques for designing differentially-private sublinear algorithms. </p> <p><br></p> <p>We give the first DP sublinear algorithm for clustering by generalizing a subsampling framework from the non-DP sublinear-time literature. We give the first DP sublinear algorithm for estimating the maximum matching size. Our DP sublinear algorithm for estimating the average degree of the graph achieves a better approximation than previous works. We give the first DP algorithm for releasing $L_2$-heavy hitters in the sliding window model and a pure $L_1$-heavy hitter algorithm in the same model, which improves upon previous works.  </p> <p><br></p> <p>We develop general techniques that address the challenges of designing sublinear DP algorithms. First, we introduce the concept of Coupled Global Sensitivity (CGS). Intuitively, the CGS of a randomized algorithm generalizes the classical  notion of global sensitivity of a function, by considering a coupling of the random coins of the algorithm when run on neighboring inputs. We show that one can achieve pure DP by adding Laplace noise proportional to the CGS of an algorithm. Second, we give a black box DP transformation for a specific class of approximation algorithms. We show that such algorithms can be made differentially private without sacrificing accuracy, as long as the function has small global sensitivity. In particular, this transformation gives rise to sublinear DP algorithms for many problems, including triangle counting, the weight of the minimum spanning tree, and norm estimation.</p>

<p dir="ltr">Continuous optimization is a fundamental topic both in theoretical computer science and applications of machine learning. Meanwhile, an important idea in the development modern algorithms it the use of randomness to achieve empirical speedup and improved theoretical runtimes. Stochastic gradient descent (SGD) and matrix-multiplication time linear program solvers [1] are two important examples of such achievements. Matrix sketching and related ideas provide a theoretical framework for the behavior of random matrices and vectors that arise in these algorithms, thereby provide a natural way to better understand the behavior of such randomized algorithms. In this dissertation, we consider three general problems in this area.</p>

Contrairement aux modèles déterministes, le déroulement d'un modèle stochastique est conditionné par la réalisation de variables aléatoires. L'utilisation de hasard permet d'approcher un résultat le plus souvent incalculable de manière déterministe. En contrepartie, il est nécessaire d'estimer les paramètres des distributions associées aux quantités aléatoires en sortie du modèle stochastique. Ce calcul requiert l'exécution de multiples réplications indépendantes de la même expérience et de ce fait, d'une importante quantité de calcul. Toutes les simulations stochastiques comportent par conception un aspect naturellement parallèle. Elles représentent ainsi une des applications phares pour l'utilisation d'environnements de calculs distribués permettant de partager de la puissance de calcul à l'échelle mondiale, appelée grille de calcul. Bien que 50% des cycles des plus gros supercalculateurs de la planète soient consommés par des calculs stochastiques, les techniques de génération parallèle de nombres pseudoaléatoires sont méconnues. Il existe de ce fait un risque bien réel de produire et de publier des résultats de simulations stochastiques erronés. Cette thèse présente l'état de l'art des méthodes pour la distribution des réplications de simulations stochastiques et contribue à leur développement. Elle propose ainsi des méthodes novatrices permettant d'assurer une traçabilité dans le processus complexe de distribution de simulations stochastiques. Elle expose enfin des applications dans les domaines de l'imagerie médicale nucléaire et des simulations environnementales totalisant plus de 70 années de calcul sur un ordinateur séquentiel.