14 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…
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 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…
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…
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…
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…