Publications by Lenka Zdeborová

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

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

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

Lenka Zdeborová, Freya Behrens

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*

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

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

Lenka Zdeborová, Giovanni Piccioli

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, Luca Biggio, Vittorio Erba

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

Lenka Zdeborová, Freya Behrens

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

Lenka Zdeborová, Emanuele Troiani, Giovanni Piccioli

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