
The staircase property: How hierarchical structure can guide deep learning
This paper identifies a structural property of data distributions that e...
read it

On the Power of Differentiable Learning versus PAC and SQ Learning
We study the power of learning via minibatch stochastic gradient descen...
read it

Quantifying the Benefit of Using Differentiable Learning over Tangent Kernels
We study the relative power of learning with gradient descent on differe...
read it

Proof of the Contiguity Conjecture and Lognormal Limit for the Symmetric Perceptron
We consider the symmetric binary perceptron model, a simple model of neu...
read it

Stochastic block model entropy and broadcasting on trees with survey
The limit of the entropy in the stochastic block model (SBM) has been ch...
read it

Maximum Multiscale Entropy and Neural Network Regularization
A wellknown result across information theory, machine learning, and sta...
read it

An ℓ_p theory of PCA and spectral clustering
Principal Component Analysis (PCA) is a powerful tool in statistics and ...
read it

An AlonBoppana theorem for powered graphs and generalized Ramanujan graphs
The rth power of a graph modifies a graph by connecting every vertex pa...
read it

Learning Sparse Graphons and the Generalized KestenStigum Threshold
The problem of learning graphons has attracted considerable attention ac...
read it

Polarization in AttractionRepulsion Models
This paper introduces a model for opinion dynamics, where at each time s...
read it

AlmostReedMuller Codes Achieve Constant Rates for Random Errors
This paper considers 'δalmost ReedMuller codes', i.e., linear codes sp...
read it

ReedMuller Codes: Theory and Algorithms
ReedMuller (RM) codes are among the oldest, simplest and perhaps most u...
read it

Polytime universality and limitations of deep learning
The goal of this paper is to characterize function distributions that de...
read it

Entropic matroids and their representation
This paper investigates entropic matroids, that is, matroids whose rank ...
read it

Chaining Meets Chain Rule: Multilevel Entropic Regularization and Training of Neural Nets
We derive generalization and excess risk bounds for neural nets using a ...
read it

Subadditivity Beyond Trees and the ChiSquared Mutual Information
In 2000, Evans et al. [Eva+00] proved the subadditivity of the mutual in...
read it

Recursive projectionaggregation decoding of ReedMuller codes
We propose a new class of efficient decoding algorithms for ReedMuller ...
read it

ReedMuller codes polarize
ReedMuller (RM) codes and polar codes are generated by the same matrix ...
read it

Provable limitations of deep learning
As the success of deep learning reaches more grounds, one would like to ...
read it

Graph powering and spectral robustness
Spectral algorithms, such as principal component analysis and spectral c...
read it

Chaining Mutual Information and Tightening Generalization Bounds
Bounding the generalization error of learning algorithms has a long hist...
read it

An InformationPercolation Bound for Spin Synchronization on General Graphs
This paper considers the problem of reconstructing n independent uniform...
read it

CommunicationComputation Efficient Gradient Coding
This paper develops coding techniques to reduce the running time of dist...
read it

Estimation in the group action channel
We analyze the problem of estimating a signal from multiple measurements...
read it

Nonbacktracking Bounds on the Influence in Independent Cascade Models
This paper develops upper and lower bounds on the influence measure in a...
read it

Community detection and stochastic block models: recent developments
The stochastic block model (SBM) is a random graph model with planted cl...
read it
Emmanuel Abbe
is this you? claim profile