research
∙
06/12/2023
Transformers learn through gradual rank increase
We identify incremental learning dynamics in transformers, where the dif...
share
research
∙
05/22/2023
The NTK approximation is valid for longer than you think
We study when the neural tangent kernel (NTK) approximation is valid for...
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
∙
10/12/2022
GULP: a prediction-based metric between representations
Comparing the representations learned by different neural networks has r...
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
∙
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
∙
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
∙
06/07/2021
Chow-Liu++: Optimal Prediction-Centric Learning of Tree Ising Models
We consider the problem of learning a tree-structured Ising model from d...
research
∙
01/04/2021
Wasserstein barycenters are NP-hard to compute
The problem of computing Wasserstein barycenters (a.k.a. Optimal Transpo...
research
∙
12/10/2020
Hardness results for Multimarginal Optimal Transport problems
Multimarginal Optimal Transport (MOT) is the problem of linear programmi...
research
∙
08/07/2020
Polynomial-time algorithms for Multimarginal Optimal Transport problems with structure
Multimarginal Optimal Transport (MOT) has recently attracted significant...
research
∙
06/14/2020
High-precision Wasserstein barycenters in polynomial time
Computing Wasserstein barycenters is a fundamental geometric problem wit...
research
∙
02/12/2020
The Multiplayer Colonel Blotto Game
We initiate the study of the natural multiplayer generalization of the c...
research
∙
12/09/2019
Approximating the Determinant of Well-Conditioned Matrices by Shallow Circuits
The determinant can be computed by classical circuits of depth O(log^2 n...
research
∙
03/19/2019
The Average-Case Complexity of Counting Cliques in Erdős-Rényi Hypergraphs
The complexity of clique problems on Erdos-Renyi random graphs has becom...
research
∙
02/06/2019