5 papers
Learning with Shallow Neural Networks on Cluster-Structured Features
Elisabetta Cornacchia, Laurent Massoulié
The success of deep learning in high-dimensional settings is often attributed to the presence of low-dimensional structure in real-world data. While standard theoretical models typ…
The Benefits of Temporal Correlations: SGD Learns k-Juntas from Random Walks Efficiently
Elisabetta Cornacchia, Dan Mikulincer, Elchanan Mossel
We study how temporal correlations in the data can make certain sparse learning problems efficiently learnable by gradient-based methods. Our focus is on Boolean k-juntas, a canoni…
Positive Distribution Shift as a Framework for Understanding Tractable Learning
Marko Medvedev, Idan Attias, Elisabetta Cornacchia +3
We study a setting where the goal is to learn a target function f(x) with respect to a target distribution D(x), but training is done on i.i.d. samples from a different training di…
Low-dimensional Functions are Efficiently Learnable under Randomly Biased Distributions
Elisabetta Cornacchia, Dan Mikulincer, Elchanan Mossel
The problem of learning single index and multi index models has gained significant interest as a fundamental task in high-dimensional statistics. Many recent works have analysed gr…
Learning High-Degree Parities: The Crucial Role of the Initialization
Emmanuel Abbe, Elisabetta Cornacchia, Jan HÄ zÅa +1
Parities have become a standard benchmark for evaluating learning algorithms. Recent works show that regular neural networks trained by gradient descent can efficiently learn degre…