Publications by Ludovic Théo Stephan

Sparse random hypergraphs: non-backtracking spectra and community detection

We consider the community detection problem in a sparse q-uniform hypergraph G, assuming that G is generated according to the Hypergraph Stochastic Block Model (HSBM). We prove that a spectral method based on the non-backtracking operator for hypergraphs w ...

OXFORD UNIV PRESS2024

Universality laws for Gaussian mixtures in generalized linear models

Florent Gérard Krzakala, Lenka Zdeborová, Bruno Loureiro, Ludovic Théo Stephan

A recent line of work in high-dimensional statistics working under the Gaussian mixture hypothesis has led to a number of results in the context of empirical risk minimization, Bayesian uncertainty quantification, separation of kernel methods and neural ne ...

2024

Gaussian universality of perceptrons with random labels

Florent Gérard Krzakala, Lenka Zdeborová, Bruno Loureiro, Ludovic Théo Stephan

While classical in many theoretical settings-and in particular in statistical physics-inspired works-the assumption of Gaussian i.i.d. input data is often perceived as a strong limitation in the context of statistics and machine learning. In this study, we ...

Amer Physical Soc2024

Computational complexity of deep learning: fundamental limitations and empirical phenomena

Alessandro Favero, Ludovic Théo Stephan

This manuscript is the lecture notes of B. Barak’s course in the Les Houches ‘Statistical Physics and Machine Learning’ summer school in 2022. It surveys various proxies for computational hardness in random planted problems, from the low-degree likelihood ...

2024

How Two-Layer Neural Networks Learn, One (Giant) Step at a Time

Florent Gérard Krzakala, Bruno Loureiro, Luca Pesce, Ludovic Théo Stephan

For high-dimensional Gaussian data, we investigate theoretically how the features of a two-layer neural network adapt to the structure of the target function through a few large batch gradient descent steps, leading to an improvement in the approximation c ...

2024

Online Learning and Information Exponents: On The Importance of Batch size, and Time/Complexity Tradeoffs

Florent Gérard Krzakala, Bruno Loureiro, Luca Pesce, Ludovic Théo Stephan

We study the impact of the batch

n_b

on the iteration time

T

of training two-layer neural networks with one-pass stochastic gradient descent (SGD) on multi-index target functions of isotropic covariates. We characterize the optimal batch size minimizin ...

JMLR2024

Phase diagram of stochastic gradient descent in high-dimensional two-layer neural networks

Florent Gérard Krzakala, Lenka Zdeborová, Ludovic Théo Stephan

Despite the non-convex optimization landscape, over-parametrized shallow networks are able to achieve global convergence under gradient descent. The picture can be radically different for narrow networks, which tend to get stuck in badly-generalizing local ...

Iop Publishing Ltd2023

Are Gaussian data all you need? the extents and limits of universality in high-dimensional generalized linear estimation

Florent Gérard Krzakala, Luca Pesce, Ludovic Théo Stephan

In this manuscript we consider the problem of generalized linear estimation on Gaussian mixture data with labels given by a single-index model. Our first result is a sharp asymptotic expression for the test and training errors in the high-dimensional regim ...

PMLR2023

Sparse random hypergraphs: Non-backtracking spectra and community detection

Ludovic Théo Stephan

We consider the community detection problem in a sparse q-uniform hypergraph G, assuming that G is generated according to the Hypergraph Stochastic Block Model (HSBM). We prove that a spectral method based on the non-backtracking operator for hypergraphs w ...

IEEE COMPUTER SOC2022

Phase diagram of Stochastic Gradient Descent in high-dimensional two-layer neural networks

Florent Gérard Krzakala, Lenka Zdeborová, Bruno Loureiro, Bruno Loureiro, Ludovic Théo Stephan

Despite the non-convex optimization landscape, over-parametrized shallow networks are able to achieve global convergence under gradient descent. The picture can be radically different for narrow net-works, which tend to get stuck in badly-generalizing loca ...

2022