research
∙
09/21/2023
Boolformer: Symbolic Regression of Logic Functions with Transformers
In this work, we introduce Boolformer, the first Transformer architectur...
share
research
∙
06/29/2023
Provable Advantage of Curriculum Learning on Parity Targets with Mixed Inputs
Experimental results have shown that curriculum learning, i.e., presenti...
research
∙
06/12/2023
Transformers learn through gradual rank increase
We identify incremental learning dynamics in transformers, where the dif...
research
∙
04/05/2023
A proof that Reed-Muller codes achieve Shannon capacity on symmetric channels
Reed-Muller codes were introduced in 1954, with a simple explicit constr...
research
∙
02/21/2023
SGD learning on neural networks: leap complexity and saddle-to-saddle dynamics
We investigate the time complexity of SGD learning on fully-connected ne...
research
∙
01/30/2023
Generalization on the Unseen, Logic Reasoning and Degree Curriculum
This paper considers the learning of logical (Boolean) functions with fo...
research
∙
08/05/2022
On the non-universality of deep learning: quantifying the cost of symmetry
We prove computational limitations for learning with neural networks tra...
research
∙
05/26/2022
Learning to Reason with Neural Networks: Generalization, Unseen Data and Boolean Measures
This paper considers the Pointer Value Retrieval (PVR) benchmark introdu...
research
∙
02/25/2022
An initial alignment between neural network and target is needed for gradient descent to learn
This paper introduces the notion of "Initial Alignment" (INAL) between a...
research
∙
02/17/2022
The merged-staircase property: a necessary and nearly sufficient condition for SGD learning of sparse functions on two-layer neural networks
It is currently known how to characterize functions that neural networks...
research
∙
11/04/2021
Binary perceptron: efficient algorithms can find solutions in a rare well-connected cluster
It was recently shown that almost all solutions in the symmetric binary ...
research
∙
08/24/2021
The staircase property: How hierarchical structure can guide deep learning
This paper identifies a structural property of data distributions that e...
research
∙
08/09/2021
On the Power of Differentiable Learning versus PAC and SQ Learning
We study the power of learning via mini-batch stochastic gradient descen...
research
∙
03/01/2021
Quantifying the Benefit of Using Differentiable Learning over Tangent Kernels
We study the relative power of learning with gradient descent on differe...
research
∙
02/25/2021
Proof of the Contiguity Conjecture and Lognormal Limit for the Symmetric Perceptron
We consider the symmetric binary perceptron model, a simple model of neu...
research
∙
01/29/2021
Stochastic block model entropy and broadcasting on trees with survey
The limit of the entropy in the stochastic block model (SBM) has been ch...
research
∙
06/25/2020
Maximum Multiscale Entropy and Neural Network Regularization
A well-known result across information theory, machine learning, and sta...
research
∙
06/24/2020
An ℓ_p theory of PCA and spectral clustering
Principal Component Analysis (PCA) is a powerful tool in statistics and ...
research
∙
06/18/2020
An Alon-Boppana theorem for powered graphs and generalized Ramanujan graphs
The r-th power of a graph modifies a graph by connecting every vertex pa...
research
∙
06/13/2020
Learning Sparse Graphons and the Generalized Kesten-Stigum Threshold
The problem of learning graphons has attracted considerable attention ac...
research
∙
06/09/2020
Polarization in Attraction-Repulsion Models
This paper introduces a model for opinion dynamics, where at each time s...
research
∙
04/20/2020
Almost-Reed-Muller Codes Achieve Constant Rates for Random Errors
This paper considers 'δ-almost Reed-Muller codes', i.e., linear codes sp...
research
∙
02/09/2020
Reed-Muller Codes: Theory and Algorithms
Reed-Muller (RM) codes are among the oldest, simplest and perhaps most u...
research
∙
01/07/2020
Poly-time universality and limitations of deep learning
The goal of this paper is to characterize function distributions that de...
research
∙
09/26/2019
Entropic matroids and their representation
This paper investigates entropic matroids, that is, matroids whose rank ...
research
∙
06/26/2019
Chaining Meets Chain Rule: Multilevel Entropic Regularization and Training of Neural Nets
We derive generalization and excess risk bounds for neural nets using a ...
research
∙
02/06/2019
Subadditivity Beyond Trees and the Chi-Squared Mutual Information
In 2000, Evans et al. [Eva+00] proved the subadditivity of the mutual in...
research
∙
02/04/2019
Recursive projection-aggregation decoding of Reed-Muller codes
We propose a new class of efficient decoding algorithms for Reed-Muller ...
research
∙
01/31/2019
Reed-Muller codes polarize
Reed-Muller (RM) codes and polar codes are generated by the same matrix ...
research
∙
12/16/2018
Provable limitations of deep learning
As the success of deep learning reaches more grounds, one would like to ...
research
∙
09/13/2018
Graph powering and spectral robustness
Spectral algorithms, such as principal component analysis and spectral c...
research
∙
06/11/2018
Chaining Mutual Information and Tightening Generalization Bounds
Bounding the generalization error of learning algorithms has a long hist...
research
∙
06/08/2018
An Information-Percolation Bound for Spin Synchronization on General Graphs
This paper considers the problem of reconstructing n independent uniform...
research
∙
02/09/2018
Communication-Computation Efficient Gradient Coding
This paper develops coding techniques to reduce the running time of dist...
research
∙
01/13/2018
Estimation in the group action channel
We analyze the problem of estimating a signal from multiple measurements...
research
∙
05/24/2017
Nonbacktracking Bounds on the Influence in Independent Cascade Models
This paper develops upper and lower bounds on the influence measure in a...
research
∙
03/29/2017