2 citations · 2 across the 14 of their papers we have counts for
19 papers
Phase Transition in Convex Relaxations for Graph Alignment
Laurent Massoulié, Sushil Mahavir Varma, Louis Vassaux +1
We study the graph alignment problem for correlated Gaussian Orthogonal Ensemble (GOE) matrices, where the goal is to recover a hidden vertex permutation given two correlated symme…
Learning with Shallow Neural Networks on Cluster-Structured Features
Elisabetta Cornacchia, Laurent Massoulié
The success of deep learning in high-dimensional settings is often attributed to the presence of low-dimensional structure in real-world data. While standard theoretical models typ…
Unbiased Approximate Vector-Jacobian Products for Efficient Backpropagation
Killian Bakong, Laurent Massoulié, Edouard Oyallon +1
In this work we introduce methods to reduce the computational and memory costs of training deep neural networks. Our approach consists in replacing exact vector-jacobian products b…
Improved Analysis of the Accelerated Noisy Power Method with Applications to Decentralized PCA
Pierre Aguié, Mathieu Even, Laurent Massoulié
We analyze the Accelerated Noisy Power Method, an algorithm for Principal Component Analysis in the setting where only inexact matrix-vector products are available, which can arise…
The value of random zero-sum games
Romain Cosson, Laurent Massoulié
We study the value of a two-player zero-sum game on a random matrix , defined by . In the setting where $n…
Performance of Gaussian Boson Sampling on Planted Bipartite Clique Detection
Yu-Zhen Janice Chen, Laurent Massoulié, Don Towsley
We investigate whether Gaussian Boson Sampling (GBS) can provide a computational advantage for solving the planted biclique problem, which is a graph problem widely believed to be…
Computational thresholds in high-dimensional statistics: the case of graph alignment
Laurent Massoulié
In this article we consider the graph alignment problem from the perspective of high-dimensional statistics: we aim to estimate an unknown permutation from the observation of…
Asynchronous Collective Tree Exploration: a Distributed Algorithm, and a new Lower Bound
Romain Cosson, Laurent Massoulié
We study the problem of collective tree exploration in which a team of mobile agents must collectively visit all nodes of an unknown tree in as few moves as possible. The agent…
Adaptive collaboration for online personalized distributed learning with heterogeneous clients
Constantin Philippenko, Batiste Le Bars, Kevin Scaman +1
We study the problem of online personalized decentralized learning with statistically heterogeneous clients collaborating to accelerate local training. An important challenge i…
Asymmetric graph alignment and the phase transition for asymmetric tree correlation testing
Jakob Maier, Laurent Massoulié
Graph alignment - identifying node correspondences between two graphs - is a fundamental problem with applications in network analysis, biology, and privacy research. While substan…
Graph Alignment via Birkhoff Relaxation
Sushil Mahavir Varma, Irène Waldspurger, Laurent Massoulié
We consider the graph alignment problem, wherein the objective is to find a vertex correspondence between two graphs that maximizes the edge overlap. The graph alignment problem is…
Meta-learning of shared linear representations beyond well-specified linear regression
Mathieu Even, Laurent Massoulié
Motivated by multi-task and meta-learning approaches, we consider the problem of learning structure shared by tasks or users, such as shared low-rank representations or clustered s…
The feasibility of multi-graph alignment: a Bayesian approach
Louis Vassaux, Laurent Massoulié
We establish thresholds for the feasibility of random multi-graph alignment in two models. In the Gaussian model, we demonstrate an "all-or-nothing" phenomenon: above a critical th…
In-depth Analysis of Low-rank Matrix Factorisation in a Federated Setting
Constantin Philippenko, Kevin Scaman, Laurent Massoulié
We analyze a distributed algorithm to compute a low-rank matrix factorization on clients, each holding a local dataset , mathematica…
Aligning Embeddings and Geometric Random Graphs: Informational Results and Computational Approaches for the Procrustes-Wasserstein Problem
Mathieu Even, Luca Ganassali, Jakob Maier +1
The Procrustes-Wasserstein problem consists in matching two high-dimensional point clouds in an unsupervised setting, and has many applications in natural language processing and c…
Barely Random Algorithms and Collective Metrical Task Systems
Romain Cosson, Laurent Massoulié
We consider metrical task systems on general metric spaces with points, and show that any fully randomized algorithm can be turned into a randomized algorithm that uses only $2…
Collective Tree Exploration via Potential Function Method
Romain Cosson, Laurent Massoulié
We study the problem of collective tree exploration (CTE) where a team of agents is tasked to traverse all the edges of an unknown tree as fast as possible, assuming complete c…
Asynchronous SGD on Graphs: a Unified Framework for Asynchronous Decentralized and Federated Optimization
Mathieu Even, Anastasia Koloskova, Laurent Massoulié
Decentralized and asynchronous communications are two popular techniques to speedup communication complexity of distributed machine learning, by respectively removing the dependenc…
Breadth-First Depth-Next: Optimal Collaborative Exploration of Trees with Low Diameter
Romain Cosson, Laurent Massoulié, Laurent Viennot
We consider the problem of collaborative tree exploration posed by Fraigniaud, Gasieniec, Kowalski, and Pelc where a team of agents is tasked to collectively go through all the…