7 papers
The Surprising Expressivity of a Single Neuron with Autoregressive Chain-of-Thought
Roey Magen, Nirmit Joshi, Gal Vardi
The success of autoregressive language models trained with Chain-of-Thought~(CoT) supervision raises a fundamental question: How simple can a next-token predictor be while still en…
Learning to Think from Multiple Thinkers
Nirmit Joshi, Roey Magen, Nathan Srebro +2
We study learning with Chain-of-Thought (CoT) supervision from multiple thinkers, all of whom provide correct but possibly systematically different solutions, e.g., step-by-step so…
Transformers are almost optimal metalearners for linear classification
Roey Magen, Gal Vardi
Transformers have demonstrated impressive in-context learning (ICL) capabilities, raising the question of whether they can serve as metalearners that adapt to new tasks using only…
Benign Overfitting in Single-Head Attention
Roey Magen, Shuning Shang, Zhiwei Xu +3
The phenomenon of benign overfitting, where a trained neural network perfectly fits noisy training data but still achieves near-optimal test performance, has been extensively studi…
Are We Still Missing an Item?
Roey Magen
The missing item problem, as introduced by Stoeckl in his work at SODA 23, focuses on continually identifying a missing element in a stream of elements f…
Initialization-Dependent Sample Complexity of Linear Predictors and Neural Networks
Roey Magen, Ohad Shamir
We provide several new results on the sample complexity of vector-valued linear predictors (parameterized by a matrix), and more generally neural networks. Focusing on size-indepen…
Mirror Games Against an Open Book Player
Roey Magen, Moni Naor
Mirror games were invented by Garg and Schnieder (ITCS 2019). Alice and Bob take turns (with Alice playing first) in declaring numbers from the set {1,2, ...2n}. If a player picks…