Gal Vardi

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…

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…

The Implicit Bias of Adam and Muon on Smooth Homogeneous Neural Networks

Eitan Gronich, Gal Vardi

We study the implicit bias of momentum-based optimizers on smooth homogeneous models. We show that \textit{momentum steepest descent} algorithms like Muon (spectral norm), Momentum…

To Grok Grokking: Provable Grokking in Ridge Regression

Mingyue Xu, Gal Vardi, Itay Safran

We study grokking, the onset of generalization long after overfitting, in a classical ridge regression setting. We prove end-to-end grokking results for learning over-parameterized…

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…

Provable Unlearning with Gradient Ascent on Two-Layer ReLU Neural Networks

Odelia Melamed, Gilad Yehudai, Gal Vardi

Machine Unlearning aims to remove specific data from trained models, addressing growing privacy and ethical concerns. We provide a theoretical analysis of a simple and widely used…

On the Hardness of Learning Regular Expressions

Idan Attias, Lev Reyzin, Nathan Srebro +1

Despite the theoretical significance and wide practical use of regular expressions, the computational complexity of learning them has been largely unexplored. We study the computat…

ImpMIA: Leveraging Implicit Bias for Membership Inference Attack

Yuval Golbari, Navve Wasserman, Gal Vardi +1

Determining which data samples were used to train a model, known as Membership Inference Attack (MIA), is a well-studied and important problem with implications on data privacy. So…

Temperature is All You Need for Generalization in Langevin Dynamics and other Markov Processes

Itamar Harel, Yonathan Wolanowsky, Gal Vardi +2

We analyze the generalization gap (gap between the training and test errors) when training a potentially over-parametrized model using a Markovian stochastic training algorithm, in…

Provable Tempered Overfitting of Minimal Nets and Typical Nets

Itamar Harel, William M. Hoza, Gal Vardi +3

We study the overfitting behavior of fully connected deep Neural Networks (NNs) with binary weights fitted to perfectly classify a noisy training set. We consider interpolation usi…

Flavors of Margin: Implicit Bias of Steepest Descent in Homogeneous Neural Networks

Nikolaos Tsilivis, Eitan Gronich, Julia Kempe +1

We study the implicit bias of the general family of steepest descent algorithms with infinitesimal learning rate in deep homogeneous neural networks. We show that: (a) an algorithm…

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…

Provable Privacy Attacks on Trained Shallow Neural Networks

Guy Smorodinsky, Gal Vardi, Itay Safran

We study what provable privacy attacks can be shown for trained 2-layer ReLU neural networks, focusing on two types of attacks: membership inference and data reconstruction. We pro…

Trained Transformer Classifiers Generalize and Exhibit Benign Overfitting In-Context

Spencer Frei, Gal Vardi

Transformers have the capacity to act as supervised learning algorithms: by properly encoding a set of labeled training ("in-context") examples and an unlabeled test example into a…

Overfitting Behaviour of Gaussian Kernel Ridgeless Regression: Varying Bandwidth or Dimensionality

Marko Medvedev, Gal Vardi, Nathan Srebro

We consider the overfitting behavior of minimum norm interpolating solutions of Gaussian kernel ridge regression (i.e. kernel ridgeless regression), when the bandwidth or input dim…

Approaching Deep Learning through the Spectral Dynamics of Weights

David Yunis, Kumar Kshitij Patel, Samuel Wheeler +5

We propose an empirical approach centered on the spectral dynamics of weights -- the behavior of singular values and vectors during optimization -- to unify and clarify several phe…