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

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

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

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

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

Uncertainty quantification is a central challenge in reliable and trustworthy machine learning. Naive measures such as last-layer scores are well-known to yield overconfident estimates in the context of overparametrized neural networks. Several methods, ra ...

Signal recovery under generative neural network priors has emerged as a promising direction in statistical inference and computational imaging. Theoretical analysis of reconstruction algorithms under generative priors is, however, challenging. For generati ...

In this review article we discuss connections between the physics of disordered systems, phase transitions in inference problems, and computational hardness. We introduce two models representing the behavior of glassy systems, the spiked tensor model and t ...

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

We consider a class of spreading processes on networks, which generalize commonly used epidemic models such as the SIR model or the SIS model with a bounded number of reinfections. We analyze the related problem of inference of the dynamics based on its pa ...

Noiseless compressive sensing is a protocol that enables undersampling and later recovery of a signal without loss of information. This compression is possible because the signal is usually sufficiently sparse in a given basis. Currently, the algorithm off ...

We prove closed-form equations for the exact high-dimensional asymptotics of a family of first-order gradient-based methods, learning an estimator (e.g., M-estimator, shallow neural network) from observations on Gaussian data with empirical risk minimizati ...

The advent of comprehensive synaptic wiring diagrams of large neural circuits has created the field of connectomics and given rise to a number of open research questions. One such question is whether it is possible to reconstruct the information stored in ...

The Sherrington-Kirkpatrick model is a prototype of a complex non-convex energy landscape. Dynamical processes evolving on such landscapes and locally aiming to reach minima are generally poorly understood. Here, we study quenches, i.e. dynamics that local ...

p>We study the dynamics of optimization and the generalization properties of one-hidden layer neural networks with quadratic activation function in the overparametrized regime where the layer width m is larger than the input dimension d. We conside ...

We consider a commonly studied supervised classification of a synthetic dataset whose labels are generated by feeding a one-layer non-linear neural network with random iid inputs. We study the generalization performances of standard classifiers in the high ...

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

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

In this paper we investigate how gradient-based algorithms such as gradient descent (GD), (multi-pass) stochastic GD, its persistent variant, and the Langevin algorithm navigate non-convex loss-landscapes and which of them is able to reach the best general ...

Factorization of matrices where the rank of the two factors diverges linearly with their sizes has many applications in diverse areas such as unsupervised representation learning, dictionary learning or sparse coding. We consider a setting where the two fa ...

Lenka Zdeborová

Chat with Graph Search

On the atypical solutions of the symmetric binary perceptron

Gaussian universality of perceptrons with random labels

Phase Diagram of Compressed Sensing with l0-norm Regularization

Universality laws for Gaussian mixtures in generalized linear models

Bayes-optimal Learning of Deep Random Networks of Extensive-width

On double-descent in uncertainty quantification in overparametrized models

Multi-layer State Evolution Under Random Convolutional Design

Disordered systems insights on computational hardness

Statistical mechanics of the maximum-average submatrix problem

Bayes-optimal inference for spreading processes on random networks

Compressed sensing with ℓ 0-norm: statistical physics analysis & algorithms for signal recovery

Rigorous Dynamical Mean-Field Theory for Stochastic Gradient Descent Methods

Bayesian reconstruction of memories stored in neural networks from their connectivity

Quenches in the Sherrington-Kirkpatrick model

Optimization and Generalization of Shallow Neural Networks with Quadratic Activation Functions

Generalization error in high-dimensional perceptrons: Approaching Bayes error with convex optimization

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

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

Stochasticity helps to navigate rough landscapes: comparing gradient-descent-based algorithms in the phase retrieval problem

Perturbative construction of mean-field equations in extensive-rank matrix factorization and denoising