658 citations · 2.2k across the 187 of their papers we have counts for
25 papers · 1 filter
Stochastic Autoregressive Learning
Ilan Doron-Arad, Idan Mehalel, Elchanan Mossel
Motivated by LLMs, which generate outputs by iteratively sampling from next-token distributions, we introduce a PAC-learning model for binary stochastic autoregressive learning. Th…
A Hierarchical Language Model with Predictable Scaling Laws and Provable Benefits of Reasoning
Jason Gaitonde, Frederic Koehler, Elchanan Mossel +2
We introduce a family of synthetic languages with hierarchical structure -- generated by a broadcast process on trees -- for which the role of context length and reasoning in autor…
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…
A Theory of Online Learning with Autoregressive Chain-of-Thought Reasoning
Ilan Doron-Arad, Idan Mehalel, Elchanan Mossel
Autoregressive generation lies at the heart of the mechanism of large language models. It can be viewed as the repeated application of a next-token generator: starting from an inpu…
Some Theoretical Limitations of t-SNE
Rupert Li, Elchanan Mossel
t-SNE has gained popularity as a dimension reduction technique, especially for visualizing data. It is well-known that all dimension reduction techniques may lose important feature…
Why ReLU? A Bit-Model Dichotomy for Deep Network Training
Ilan Doron-Arad, Elchanan Mossel
Theoretical analyses of Empirical Risk Minimization (ERM) are standardly framed within the Real-RAM model of computation. In this setting, training even simple neural networks is k…
Online Realizable Regression and Applications for ReLU Networks
Ilan Doron-Arad, Idan Mehalel, Elchanan Mossel
Realizable online regression can behave very differently from online classification. Even without any margin or stochastic assumptions, realizability may enforce horizon-free (fini…
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…
Bypassing the Noisy Parity Barrier: Learning Higher-Order Markov Random Fields from Dynamics
Jason Gaitonde, Ankur Moitra, Elchanan Mossel
We consider the problem of learning graphical models, also known as Markov random fields (MRFs) from temporally correlated samples. As in many traditional statistical settings, fun…
Reconstructing the Geometry of Random Geometric Graphs
Han Huang, Pakawut Jiradilok, Elchanan Mossel
Random geometric graphs are random graph models defined on metric spaces. Such a model is defined by first sampling points from a metric space and then connecting each pair of samp…
A Unified Approach to Learning Ising Models: Beyond Independence and Bounded Width
Jason Gaitonde, Elchanan Mossel
We revisit the problem of efficiently learning the underlying parameters of Ising models from data. Current algorithmic approaches achieve essentially optimal sample complexity whe…
A Mathematical Model for Curriculum Learning for Parities
Elisabetta Cornacchia, Elchanan Mossel
Curriculum learning (CL) - training using samples that are generated and presented in a meaningful order - was introduced in the machine learning context around a decade ago. While…
Spoofing Generalization: When Can't You Trust Proprietary Models?
Ankur Moitra, Elchanan Mossel, Colin Sandon
In this work, we study the computational complexity of determining whether a machine learning model that perfectly fits the training data will generalizes to unseen data. In partic…
Learning to Sample from Censored Markov Random Fields
Ankur Moitra, Elchanan Mossel, Colin Sandon
We study learning Censor Markov Random Fields (abbreviated CMRFs). These are Markov Random Fields where some of the nodes are censored (not observed). We present an algorithm for l…
Seeded Graph Matching via Large Neighborhood Statistics
Elchanan Mossel, Jiaming Xu
We study a well known noisy model of the graph isomorphism problem. In this model, the goal is to perfectly recover the vertex correspondence between two edge-correlated Erdős-Rény…
Learning Restricted Boltzmann Machines via Influence Maximization
Guy Bresler, Frederic Koehler, Ankur Moitra +1
Graphical models are a rich language for describing high-dimensional distributions in terms of their dependence structure. While there are algorithms with provable guarantees for l…
The Vertex Sample Complexity of Free Energy is Polynomial
Vishesh Jain, Frederic Koehler, Elchanan Mossel
We study the following question: given a massive Markov random field on nodes, can a small sample from it provide a rough approximation to the free energy $\mathcal{F}_n = \log…
The Mean-Field Approximation: Information Inequalities, Algorithms, and Complexity
Vishesh Jain, Frederic Koehler, Elchanan Mossel
The mean field approximation to the Ising model is a canonical variational tool that is used for analysis and inference in Ising models. We provide a simple and optimal bound for t…
Approximating Partition Functions in Constant Time
Vishesh Jain, Frederic Koehler, Elchanan Mossel
We study approximations of the partition function of dense graphical models. Partition functions of graphical models play a fundamental role is statistical physics, in statistics a…
Coalescent-based species tree estimation: a stochastic Farris transform
Gautam Dasarathy, Elchanan Mossel, Robert Nowak +1
The reconstruction of a species phylogeny from genomic data faces two significant hurdles: 1) the trees describing the evolution of each individual gene--i.e., the gene trees--may…
Deep Learning and Hierarchal Generative Models
Elchanan Mossel
It is argued that deep learning is efficient for data that is generated from hierarchal generative models. Examples of such generative models include wavelet scattering networks, f…
MCMC Learning
Varun Kanade, Elchanan Mossel
The theory of learning under the uniform distribution is rich and deep, with connections to cryptography, computational complexity, and the analysis of boolean functions to name a…
Agnostically Learning Juntas from Random Walks
Jan Arpe, Elchanan Mossel
We prove that the class of functions g:{-1,+1}^n -> {-1,+1} that only depend on an unknown subset of k<<n variables (so-called k-juntas) is agnostically learnable from a random wal…
Multiple Random Oracles Are Better Than One
Jan Arpe, Elchanan Mossel
We study the problem of learning k-juntas given access to examples drawn from a number of different product distributions. Thus we wish to learn a function f : {-1,1}^n -> {-1,1} t…