Anant Sahai

Training error is what we can observe on a training set; test error is the quantity we actually care about. We study linear regression with squared-error in a deterministic (d+1)-dimensional single-spike model. Each stylized training vector has the same informative spike coordinate, of amplitude √γ with γ > 1. The remaining directions are nuisance, and the nuisance components of distinct training vectors all have equal norm and are mutually orthogonal. The training labels are all 1. Fresh test points are drawn from x_test ∼ N(0, diag(γ, 1, …, 1)), with the noise-free test labels being the normalized spike coordinate x_test[1]/√γ. We focus on linear predictors in the span of the training vectors, the class naturally reached by zero-initialized linear gradient methods. We exhibit a range of training-set sizes n in which every span predictor that generalizes well must fit the training data worse than the zero predictor. We call this regime benign misfitting, or the fourth quadrant. The best span predictor begins to generalize when n ≫ d/γ², while interpolation does not generalize until the later threshold n ≫ d/γ. In the window d/γ² ≪ n ≪ d/γ, useful prediction within the linear span lies beyond interpolation: predictions on the training points overshoot the labels. We show that one-pass stochastic gradient descent (SGD), with a large constant learning rate, reaches small test error throughout this window—matching the best span predictor up to a logarithmic factor. We also verify directly that it indeed has large empirical training error (despite the descent premise in its name). Finally, we show that the unavoidable nuisance component responsible for the training misfit also controls the predictor's adversarial sensitivity.

Reinforcement learning has become the dominant paradigm for eliciting reasoning and self-correction capabilities in large language models, but its computational expense motivates exploration of alternatives. Inspired by techniques from autonomous driving and robotics, we investigate whether supervised learning with synthetic error injection can induce self-correction abilities in language models. Our approach inserts artificial errors into reasoning chains, masks them, and supervises the model to recognize and correct these mistakes. Despite the intuitive appeal of this method, we find that it fails to significantly improve performance even on simple synthetic tasks across multiple models. Moreover, even when the model catches its own error, it often parrots the original mistake. We find that the distribution shift of synthetic errors to on-policy errors significantly degrades the error-correction capabilities of the fine-tuned model, even with good synthetic coverage of on-policy errors. Our results help explain why on-policy reinforcement learning methods have proven uniquely effective for eliciting self-correction.

We introduce a new family of toy problems that combine features of linear-regression-style continuous in-context learning (ICL) with discrete associative recall. We pretrain transformer models on sample traces from this toy, specifically symbolically-labeled interleaved state observations from randomly drawn linear deterministic dynamical systems. We study if the transformer models can recall the state of a sequence previously seen in its context when prompted to do so with the corresponding in-context label. Taking a closer look at this task, it becomes clear that the model must perform two functions: (1) identify which system's state should be recalled and apply that system to its last seen state, and (2) continuing to apply the correct system to predict the subsequent states. Training dynamics reveal that the first capability emerges well into a model's training. Surprisingly, the second capability, of continuing the prediction of a resumed sequence, develops much earlier. Via out-of-distribution experiments, and a mechanistic analysis on model weights via edge pruning, we find that next-token prediction for this toy problem involves at least two separate mechanisms. One mechanism uses the discrete symbolic labels to do the associative recall required to predict the start of a resumption of a previously seen sequence. The second mechanism, which is largely agnostic to the discrete symbolic labels, performs a `Bayesian-style' prediction based on the previous token and the context. These two mechanisms have different learning dynamics. To confirm that this multi-mechanism (manifesting as separate phase transitions) phenomenon is not just an artifact of our toy setting, we used OLMo training checkpoints on an ICL translation task to see a similar phenomenon: a decisive gap in the emergence of first-task-token performance vs second-task-token performance.

The classic teacher-student model in machine learning posits that a strong teacher supervises a weak student to improve the student's capabilities. We instead consider the inverted situation, where a weak teacher supervises a strong student with imperfect pseudolabels. This paradigm was recently brought forth by Burns et al.'23 and termed weak-to-strong generalization. We theoretically investigate weak-to-strong generalization for binary and multilabel classification in a stylized overparameterized spiked covariance model with Gaussian covariates where the weak teacher's pseudolabels are asymptotically like random guessing. Under these assumptions, we provably identify two asymptotic phases of the strong student's generalization after weak supervision: (1) successful generalization and (2) random guessing. Our techniques should eventually extend to weak-to-strong multiclass classification. Towards doing so, we prove a tight lower tail inequality for the maximum of correlated Gaussians, which may be of independent interest. Understanding the multilabel setting reinforces the value of using logits for weak supervision when they are available.

We study the limiting behavior of the mixed strategies that result from optimal no-regret learning in a repeated game setting where the stage game is any 2x2 competitive game. We consider optimal no-regret algorithms that are mean-based and monotonic in their argument. We show that for any such algorithm, the limiting mixed strategies of the players cannot converge almost surely to any Nash equilibrium. This negative result is also shown to hold under a broad relaxation of these assumptions, including popular variants of Follow-the-Regularized Leader with optimism or adaptive step sizes. Finally, we provide partial evidence that the monotonicity and mean-based assumptions can be removed or relaxed. Our results identify the inherent stochasticity in players's realizations as a critical factor underlying this divergence, and demonstrate a crucial difference in outcomes between using the opponent's mixtures and realizations to make updates.