1 citations · 2 across the 6 of their papers we have counts for
7 papers
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…
Learning Under Graphical Models
Gautam Chandrasekaran, Jason Gaitonde, Ankur Moitra +1
In a landmark result, Linial, Mansour and Nisan (J. ACM 1993) gave a quasipolynomial-time algorithm for learning constant-depth circuits given labeled i.i.d. samples under the unif…
On Algorithmic Robustness of Corrupted Markov Chains
Jason Gaitonde, Elchanan Mossel
We study the algorithmic robustness of general finite Markov chains in terms of their stationary distributions to general, adversarial corruptions of the transition matrix. We show…
Comparison Theorems for the Mixing Times of Systematic and Random Scan Dynamics
Jason Gaitonde, Elchanan Mossel
A popular method for sampling from high-dimensional distributions is the \emph{Gibbs sampler}, which iteratively resamples sites from the conditional distribution of the desired me…
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…
Sample-Efficient Linear Regression with Self-Selection Bias
Jason Gaitonde, Elchanan Mossel
We consider the problem of linear regression with self-selection bias in the unknown-index setting, as introduced in recent work by Cherapanamjeri, Daskalakis, Ilyas, and Zampetaki…
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…