Publications by Lenka Zdeborová

A phase transition between positional and semantic learning in a solvable model of dot-product attention

Freya Behrens, Hugo Chao Cui, Florent Gérard Krzakala, Lenka Zdeborová

Many empirical studies have provided evidence for the emergence of algorithmic mechanisms (abilities) in the learning of language models, that lead to qualitative improvements in the model capabilities. Yet, a theoretical characterization of how such mecha ...

2025

Estimating Rank-One Matrices with Mismatched Prior and Noise: Universality and Large Deviations

Florent Gérard Krzakala, Lenka Zdeborová

We prove a universality result that reduces the free energy of rank-one matrix estimation problems in the setting of mismatched prior and noise to the computation of the free energy for a modified Sherrington–Kirkpatrick spin glass. Our main result is an a ...

2025

Phase Diagram of Compressed Sensing with l0-norm Regularization

Florent Gérard Krzakala, Lenka Zdeborová

Noiseless compressive sensing is a two-step setting that allows for undersampling a sparse signal and then reconstructing it without loss of information. The LASSO algorithm, based on l(1) regularization, provides an efficient and robust way to address thi ...

IOP Publishing Ltd2025

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

Freya Behrens, Lenka Zdeborová

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

2025

Bayes-optimal learning of deep random networks of extensive-width*

Hugo Chao Cui, Florent Gérard Krzakala, Lenka Zdeborová

We consider the problem of learning a target function corresponding to a deep, extensive-width, non-linear neural network with random Gaussian weights. We consider the asymptotic limit where the number of samples, the input dimension and the network width ...

IOP Publishing Ltd2025

Low-rank matrix estimation with inhomogeneous noise

Florent Gérard Krzakala, Lenka Zdeborová

We study low-rank matrix estimation for a generic inhomogeneous output channel through which the matrix is observed. This generalizes the commonly considered spiked matrix model with homogeneous noise to include for instance the dense degree-corrected stoc ...

2025

Integer traffic assignment problem: Algorithms and insights on random graphs

Giovanni Piccioli, Lenka Zdeborová

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

2025

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

Lenka Zdeborová, Emanuele Troiani, Vittorio Erba, Luca Biggio

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

American Physical Society2025

Dynamical phase transitions in graph cellular automata

Freya Behrens, Lenka Zdeborová

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

American Physical Society (APS)2024

Gibbs sampling the posterior of neural networks

Giovanni Piccioli, Lenka Zdeborová, Emanuele Troiani

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

Iop Publishing Ltd2024

Analysis of Bootstrap and Subsampling in High-dimensional Regularized Regression

Adrien Vandenbroucque, Florent Gérard Krzakala, Lenka Zdeborová, Bruno Loureiro, Lucas Andry Clarte

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

ACM2024

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

Yue Lu, Hugo Chao Cui, Florent Gérard Krzakala, Lenka Zdeborová, Bruno Loureiro, Luca Pesce

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

2024

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

The Benefits of Reusing Batches for Gradient Descent in Two-Layer Networks: Breaking the Curse of Information and Leap Exponents

Florent Gérard Krzakala, Lenka Zdeborová, Emanuele Troiani, Luca Pesce

We investigate the training dynamics of two-layer neural networks when learning multi-index target functions. We focus on multi-pass gradient descent (GD) that reuses the batches multiple times and show that it significantly changes the conclusion about wh ...

JMLR2024

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

On the atypical solutions of the symmetric binary perceptron

Florent Gérard Krzakala, Lenka Zdeborová

We study the random binary symmetric perceptron problem, focusing on the behavior of rare high-margin solutions. While most solutions are isolated, we demonstrate that these rare solutions are part of clusters of extensive entropy, heuristically correspond ...

Iop Publishing Ltd2024

Statistical mechanics of the maximum-average submatrix problem

Florent Gérard Krzakala, Lenka Zdeborová, Vittorio Erba

We study the maximum-average submatrix problem, wherein given an N x N matrix J, one needs to find the k x k submatrix with the largest average number of entries. We investigate the problem for random matrices J, whose entries are i.i.d. random variables, ...

Iop Publishing Ltd2024

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

Florent Gérard Krzakala, Lenka Zdeborová

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

Proceedings of the National Academy of Sciences2024

Les Houches 2022 Special Issue: Editorial

Florent Gérard Krzakala, Lenka Zdeborová

IOP Publishing Ltd2024

Counting and hardness-of-finding fixed points in cellular automata on random graphs

Freya Behrens, Lenka Zdeborová

We study the fixed points of outer-totalistic cellular automata on sparse random regular graphs. These can be seen as constraint satisfaction problems, where each variable must adhere to the same local constraint, which depends solely on its state and the ...

IOP Publishing2024