Publications by Lenka Zdeborová

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

We address the problem of denoising data from a Gaussian mixture using a twolayer non-linear autoencoder with tied weights and a skip connection. We consider the high-dimensional limit where the number of training samples and the input dimension jointly te ...

Path optimization is a fundamental concern across various real-world scenarios, ranging from traffic congestion issues to efficient data routing over the Internet. The traffic assignment problem (TAP) is a classic continuous optimization problem in this fi ...

We investigate popular resampling methods for estimating the uncertainty of statistical models, such as subsampling, bootstrap and the jackknife, and their performance in high-dimensional supervised regression tasks. We provide a tight asymptotic descripti ...

Being able to reliably assess not only the accuracy but also the uncertainty of models' predictions is an important endeavor in modern machine learning. Even if the model generating the data and labels is known, computing the intrinsic uncertainty after le ...

In semisupervised community detection, the membership of a set of revealed nodes is known in addition to the graph structure and can be leveraged to achieve better inference accuracies. While previous works investigated the case where the revealed nodes ar ...

In this manuscript, we investigate the problem of how two-layer neural networks learn features from data, and improve over the kernel regime, after being trained with a single gradient descent step. Leveraging the insight from (Ba et al., 2022), we model t ...

In this paper, we study sampling from a posterior derived from a neural network. We propose a new probabilistic model consisting of adding noise at every pre- and post-activation in the network, arguing that the resulting posterior can be sampled using an ...

We consider the problem of recovering an unknown k-factor, hidden in a weighted random graph. For k = 1 this is the planted matching problem, while the k = 2 case is closely related to the planted traveling salesman problem. The inference problem is solved ...

A simple model to study subspace clustering is the high-dimensional k -Gaussian mixture model where the cluster means are sparse vectors. Here we provide an exact asymptotic characterization of the statistically optimal reconstruction error in this model i ...

We analyze in a closed form the learning dynamics of the stochastic gradient descent (SGD) for a single-layer neural network classifying a high-dimensional Gaussian mixture where each cluster is assigned one of two labels. This problem provides a prototype ...

The problem of aligning Erdos-Renyi random graphs is a noisy, average-case version of the graph isomorphism problem, in which a pair of correlated random graphs is observed through a random permutation of their vertices. We study a polynomial time message- ...

Recent years witnessed the development of powerful generative models based on flows, diffusion, or autoregressive neural networks, achieving remarkable success in generating data from examples with applications in a broad range of areas. A theoretical anal ...

Current progress in artificial intelligence is centered around so-called large language models that consist of neural networks processing long sequences of high-dimensional vectors called tokens. Statistical physics provides powerful tools to study the fun ...

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 ...

Understanding the impact of data structure on the computational tractability of learning is a key challenge for the theory of neural networks. Many theoretical works do not explicitly model training data, or assume that inputs are drawn component-wise inde ...

The dynamical cavity method and its backtracking version provide a powerful approach to studying the properties of dynamical processes on large random graphs. This work extends these methods to hypergraphs, enabling the analysis of interactions involving m ...

We analyze in a closed form the learning dynamics of stochastic gradient descent (SGD) for a single layer neural network classifying a high-dimensional Gaussian mixture where each cluster is assigned one of two labels. This problem provides a prototype of ...

Discrete dynamical systems can exhibit complex behavior from the iterative application of straightforward local rules. A famous class of examples comes from cellular automata whose global dynamics are notoriously challenging to analyze. To address this, we ...

Contact tracing is an essential tool to mitigate the impact of a pandemic, such as the COVID-19 pandemic. In order to achieve efficient and scalable contact tracing in real time, digital devices can play an important role. While a lot of attention has been ...

Lenka Zdeborová

Chat with Graph Search

High-dimensional Asymptotics of Denoising Autoencoders

Integer traffic assignment problem: Algorithms and insights on random graphs

Analysis of Bootstrap and Subsampling in High-dimensional Regularized Regression

Theoretical characterization of uncertainty in high-dimensional linear classification

Large deviations of semisupervised learning in the stochastic block model

Asymptotics of feature learning in two-layer networks after one gradient-step

Gibbs sampling the posterior of neural networks

The planted k-factor problem

Subspace clustering in high-dimensions: Phase transitions & Statistical-to-Computational gap

Dynamical mean-field theory for stochastic gradient descent in Gaussian mixture classification*

Aligning random graphs with a sub-tree similarity message-passing algorithm

Sampling with flows, diffusion, and autoregressive neural networks from a spin-glass perspective

Bilinear Sequence Regression: A Model for Learning from Long Sequences of High-Dimensional Tokens

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

Machine learning and statistical physics: preface

The Gaussian equivalence of generative models for learning with shallow neural networks

Dynamical cavity method for hypergraphs and its application to quenches in the k-XOR-SAT problem

Dynamical mean-field theory for stochastic gradient descent in Gaussian mixture classification

Dynamical phase transitions in graph cellular automata

Epidemic mitigation by statistical inference from contact tracing data