Laboratoire d'informatique de l'École polytechnique

Events

Exposé par Marie Kerjean: «Typing differentiable programming»

Speaker: Marie Kerjean
Location: Salle Claude Shannon
Date: Mar. 25 févr. 2020, 14h00-15h00

Pour le prochain séminaire de l’équipe Cosynus, nous aurons le plaisir d’accueillir Marie Kerjean pour son exposé intitulé Typing differentiable programming.

Résumé: Differentiable programming is a recent research area: its objective is to express differentiation as a modular algorithmic transformation on rich programming languages. It is in particular motivated by the various applications of automatic differentiation in machine learning or formal calculus. In this talk I will present joint work with Pierre-Marie Pédrot, focusing on the typing system used to express differentiation.

We will first review a few examples of differentiable languages recently exhibited in the literature. This allows to identity the linear Dialectica transformation as a reverse automated differentiation transformation on a higher-order lambda-calculus with positive types. Building on the intuitions provided by Dialectica and distribution theory, we construct a lambda-calculus with an internal differentiation operator. This calculus is typed by a type system inspired by Differential Linear Logic. Noticeably, we are able to express backward automatic differentiation as a call-by-name strategy and forward automatic differentiation as a call-by-value strategy.

Talk by Mathieu Carrière: «Statistics and Machine Learning in Topological Data Analysis with Applications to Biology»

Speaker: Mathieu Carrière
Location: Room Gilles Kahn
Date: Mon, 24 Feb 2020, 14:30-15:30

Mathieu Carrière, currently PostDoc at Columbia University, will give a talk next Monday 24th at 2:30pm in Gilles Kahn, on Statistics and Machine Learning in Topological Data Analysis with Applications to Biology.

Abstract: Topological Data Analysis (TDA) is an area of data science which aims at characterizing data sets with their topological features in various dimensions. Examples of such features include the connected components, the loops or the cavities that are present in the data, and which are encoded in the two main descriptors of TDA, the so-called persistence diagram and Mapper. Even though these descriptors have proved useful in many applications, it is not straightforward to include them in automated processes, which are common in statistics and machine learning, mainly because the space of these descriptors lacks a lot of required properties, such as a well-defined addition or barycenter. In this talk, I will recall the basics of TDA and review the current solutions that have been proposed in the past few years to merge TDA descriptors (persistence diagram and Mapper) with statistics and Machine Learning. Then, I will introduce some questions that remain open in this topic, and that are active fields of research as of today, such that the question of persistence diagram differentiability for deep learning, or the statistical analysis of the Mapper in the multivariate case. In the process, I will also illustrate these problems by providing applications on biological data, such as immunofluorescence images for breast cancer pathology and single-cell RNA sequencing for understanding the spinal cord cellular diversity.

Talk by Nguyễn Kim Thắng: «Online Non-monotone Submodular Maximization: Approximation and Regret Guarantees»

Speaker: Nguyễn Kim Thắng
Location: Room Grace Hopper, Alan Turing building
Date: Thu, 6 Feb 2020, 14:30-15:30

There will be a seminar on Thursday 6 February at 14:30 at LIX, room Grace Hopper with a talk given by Nguyễn Kim Thắng (IBISC).

Title: Online Non-monotone Submodular Maximization: Approximation and Regret Guarantees

Abstract: Submodular and diminishing-returns (DR) submodular optimization are important optimization problems with many real-world applications in machine learning, economics and communication systems. Moreover, DR-submodular optimization captures a subclass of non-convex optimization that provides both practical and theoretical guarantees.

In this talk, we present algorithms with performance guarantees for the fundamental problems of maximizing non-monotone submodular and DR-submodular functions over convex sets in the online environment. In several settings, these guarantees match the currently best-known ones in the offline environment.

Talk by Johannes Lutzeyer: «Extending the Davis-Kahan theorem for the comparison of embedding spaces spanned by eigenvectors»

Speaker: Johannes Lutzeyer
Location: Room Henri Poincaré
Date: Tue, 4 Feb 2020, 14:30-15:30

Dr. Johannes Lutzeyer, new postdoctoral researcher in DaSciM, will give a presentation at 14:30 entitled: Extending the Davis-Kahan theorem for the comparison of embedding spaces spanned by eigenvectors

Abstract: In this talk I will introduce the Davis-Kahan theorem, which is commonly used to upper bound the distance of two embedding spaces. It often forms an essential part of consistency proofs of algorithms based on spectral graph embeddings and variants of principal component analysis (PCA). However, the Davis-Kahan theorem has several weaknesses, which is why work on it continues. In this talk I present an extended version of the Davis-Kahan theorem which addresses these weaknesses and give a few proof of concept examples such as covariance embedding spaces in the context of the PCA algorithm and graph shift operator embedding spaces in the context of the spectral clustering algorithm. The work presented is joint work with Andrew Walden.

Exposé par Nathan Noiry: «L'algorithme de parcours en profondeur dans un modèle de configuration»

Speaker: Nathan Noiry
Location: Salle Philippe Flajolet, LIX
Date: Mer. 29 janv. 2020, 10h30-11h30

La prochaine séance du séminaire Combi du Plateau de Saclay aura lieu ce mercredi à 10h30 dans la salle Philippe Flajolet du LIX. Nathan Noiry (Modal’X, Université Paris Nanterre) nous parlera de «L’algorithme de parcours en profondeur dans un modèle de configuration».

Le programme du séminaire est disponible ici : https://galac.lri.fr/pages/combi-seminar.html

Résumé: Dans cet exposé, issu d’un travail en collaboration avec Nathanaël Enriquez, Gabriel Faraud et Laurent Ménard, nous nous intéresserons à des graphes aléatoires dont la suite des degrés est fixée. Nous verrons que ce modèle présente une transition de phase concernant l’existence d’une composante connexe de taille macroscopique. Dans le régime surcritique, nous nous intéresserons à l’algorithme de parcours en profondeur sur cette composante géante, qui en construit un arbre couvrant. Notre résultat principal établit la convergence du processus de contour renormalisé associé à cet arbre, vers un profil explicite. Une conséquence de ce résultat est l’existence de chemins simples macroscopiques dans le graphe. Nous aborderons ensuite quelques éléments de preuve et verrons qu’au cours de l’exploration, l’évolution de la mesure empirique des degrés au sein du graphe induit par les sommets non-explorés admet une limite fluide. Celle-ci est décrite par un système infini d’équations différentielles qui, de manière inattendue, admet une solution unique et explicite en fonction de la série génératrice de la loi initiale des degrés.