193 citations · 274 across the 24 of their papers we have counts for
4 papers · 1 filter
Transformers Learn Two Competing Sorting Algorithms, and Only One Length-Generalizes
Khashayar Gatmiry, Nathan W. Henry, Chloe H. Su +5
We show that two-layer transformers trained to near-zero loss on a sorting task converge to one of two mechanistically distinct solution classes depending on their initialization.…
Matrix Completion in Almost-Verification Time
Jonathan A. Kelner, Jerry Li, Allen Liu +2
We give a new framework for solving the fundamental problem of low-rank matrix completion, i.e., approximating a rank- matrix (where $m…
On the Power of Preconditioning in Sparse Linear Regression
Jonathan Kelner, Frederic Koehler, Raghu Meka +1
Sparse linear regression is a fundamental problem in high-dimensional statistics, but strikingly little is known about how to efficiently solve it without restrictive conditions on…
Learning Some Popular Gaussian Graphical Models without Condition Number Bounds
Jonathan Kelner, Frederic Koehler, Raghu Meka +1
Gaussian Graphical Models (GGMs) have wide-ranging applications in machine learning and the natural and social sciences. In most of the settings in which they are applied, the numb…