Raphaël Berthier

 

Briefly

I am a first-year Ph.D. student under the supervision of Francis Bach and Pierre Gaillard. I work in the SIERRA team in Paris, which is a joint team between INRIA Paris, ENS Paris and CNRS.

My research interests lie mainly within statistics, optimization and probability theory. More precisely, my current work focuses on developing polynomial-based iterative methods to accelerate the sharing of information in decentralized networks, using inspiration coming from numerical analysis. Before that, I worked under the supervision of Andrea Montanari to develop a rigorous analysis of the Approximate Message Passing algorithms in the case of non-separable denoisers.

Here is a short CV.

Contact

Publications and Preprints

  • R. Berthier, F. Bach, P. Gaillard. Accelerated Gossip in Networks of Given Dimension using Jacobi Polynomial Iterations.
    [hal, arXiv], 2019. [Show Abstract]

    Abstract: Consider a network of agents connected by communication links, where each agent holds a real value. The gossip problem consists in estimating the average of the values diffused in the network in a distributed manner. We develop a method solving the gossip problem that depends only on the spectral dimension of the network, that is, in the communication network set-up, the dimension of the space in which the agents live. This contrasts with previous work that required the spectral gap of the network as a parameter, or suffered from slow mixing. Our method shows an important improvement over existing algorithms in the non-asymptotic regime, i.e., when the values are far from being fully mixed in the network. Our approach stems from a polynomial-based point of view on gossip algorithms, as well as an approximation of the spectral measure of the graphs with a Jacobi measure. We show the power of the approach with simulations on various graphs, and with performance guarantees on graphs of known spectral dimension, such as grids and random percolation bonds. An extension of this work to distributed Laplacian solvers is discussed. As a side result, we also use the polynomial-based point of view to show the convergence of the message passing algorithm for gossip of Moallemi & Van Roy on regular graphs. The explicit computation of the rate of the convergence shows that message passing has a slow rate of convergence on graphs with small spectral gap.

  • R. Berthier, A. Montanari, P.-M. Nguyen. State Evolution for Approximate Message Passing with Non-Separable Functions.
    [arXiv], 2017, accepted for publication in Information and Inference: a Journal of the IMA. [Show Abstract]

    Abstract: Given a high-dimensional data matrix A in {rm I!R}^{n times m}, Approximate Message Passing (AMP) algorithms construct sequences of vectors u^t in {rm I!R}^n, v^t in {rm I!R}^m, indexed by t in {0,1,2,dots } by iteratively applying A or A^T, and suitable non-linear functions, which depend on the specific application. Special instances of this approach have been developed –among other applications– for compressed sensing reconstruction, robust regression, Bayesian estimation, low-rank matrix recovery, phase retrieval, and community detection in graphs. For certain classes of random matrices A, AMP admits an asymptotically exact description in the high-dimensional limit m,nto infty, which goes under the name of ‘state evolution.’ Earlier work established state evolution for separable non-linearities (under certain regularity conditions). Nevertheless, empirical work demonstrated several important applications that require non-separable functions. In this paper we generalize state evolution to Lipschitz continuous non-separable nonlinearities, for Gaussian matrices A. Our proof makes use of Bolthausen's conditioning technique along with several approximation arguments. In particular, we introduce a modified algorithm (called LAMP for Long AMP) which is of independent interest.