53 citations · 315 across the 37 of their papers we have counts for
38 papers
Learning When to Stop: Selective Imitation Learning Under Arbitrary Dynamics Shift
Surbhi Goel, Jonathan Pei, James Wang
Behavior cloning provides strong imitation learning guarantees when training and test environments share the same dynamics. However, in many deployment settings the test environmen…
Weight Clipping for Robust Conformal Inference under Unbounded Covariate Shifts
James Wang, Surbhi Goel
Conformal prediction (CP) provides powerful, distribution-free prediction sets, but its guarantees rely on the exchangeability of training and test data, which is often violated in…
Less Data, Faster Training: repeating smaller datasets speeds up learning via sampling biases
Jingwen Liu, Ezra Edelman, Surbhi Goel +1
This work investigates the ``small-vs-large gap'', where repeating on fewer samples can lead to compute saving during training compared to using a larger dataset. This is observed…
Reliable Abstention under Adversarial Injections: Tight Lower Bounds and New Upper Bounds
Ezra Edelman, Surbhi Goel
We study online learning in the adversarial injection model introduced by [Goel et al. 2017], where a stream of labeled examples is predominantly drawn i.i.d.\ from an unknown dist…
Testing Noise Assumptions of Learning Algorithms
Surbhi Goel, Adam R. Klivans, Konstantinos Stavropoulos +1
We pose a fundamental question in computational learning theory: can we efficiently test whether a training set satisfies the assumptions of a given noise model? This question has…
Tolerant Algorithms for Learning with Arbitrary Covariate Shift
Surbhi Goel, Abhishek Shetty, Konstantinos Stavropoulos +1
We study the problem of learning under arbitrary distribution shift, where the learner is trained on a labeled set from one distribution but evaluated on a different, potentially a…
The Evolution of Statistical Induction Heads: In-Context Learning Markov Chains
Benjamin L. Edelman, Ezra Edelman, Surbhi Goel +2
Large language models have the ability to generate text that mimics patterns in their inputs. We introduce a simple Markov Chain sequence modeling task in order to study how this i…
Pareto Frontiers in Neural Feature Learning: Data, Compute, Width, and Luck
Benjamin L. Edelman, Surbhi Goel, Sham Kakade +2
In modern deep learning, algorithmic choices (such as width, depth, and learning rate) are known to modulate nuanced resource tradeoffs. This work investigates how these complexiti…
Adversarial Resilience in Sequential Prediction via Abstention
Surbhi Goel, Steve Hanneke, Shay Moran +1
We study the problem of sequential prediction in the stochastic setting with an adversary that is allowed to inject clean-label adversarial (or out-of-distribution) examples. Algor…
Exposing Attention Glitches with Flip-Flop Language Modeling
Bingbin Liu, Jordan T. Ash, Surbhi Goel +2
Why do large language models sometimes output factual inaccuracies and exhibit erroneous reasoning? The brittleness of these models, particularly when executing long chains of reas…
Learning Narrow One-Hidden-Layer ReLU Networks
Sitan Chen, Zehao Dou, Surbhi Goel +2
We consider the well-studied problem of learning a linear combination of ReLU activations with respect to a Gaussian distribution on inputs in dimensions. We give the first…
Transformers Learn Shortcuts to Automata
Bingbin Liu, Jordan T. Ash, Surbhi Goel +2
Algorithmic reasoning requires capabilities which are most naturally understood through recurrent models of computation, like the Turing machine. However, Transformer models, while…
Recurrent Convolutional Neural Networks Learn Succinct Learning Algorithms
Surbhi Goel, Sham Kakade, Adam Tauman Kalai +1
Neural networks (NNs) struggle to efficiently solve certain problems, such as learning parities, even when there are simple learning algorithms for those problems. Can NNs discover…
Hidden Progress in Deep Learning: SGD Learns Parities Near the Computational Limit
Boaz Barak, Benjamin L. Edelman, Surbhi Goel +3
There is mounting evidence of emergent phenomena in the capabilities of deep learning methods as we scale up datasets, model sizes, and training times. While there are some account…
Understanding Contrastive Learning Requires Incorporating Inductive Biases
Nikunj Saunshi, Jordan Ash, Surbhi Goel +5
Contrastive learning is a popular form of self-supervised learning that encourages augmentations (views) of the same input to have more similar representations compared to augmenta…
Anti-Concentrated Confidence Bonuses for Scalable Exploration
Jordan T. Ash, Cyril Zhang, Surbhi Goel +2
Intrinsic rewards play a central role in handling the exploration-exploitation trade-off when designing sequential decision-making algorithms, in both foundational theory and state…
Inductive Biases and Variable Creation in Self-Attention Mechanisms
Benjamin L. Edelman, Surbhi Goel, Sham Kakade +1
Self-attention, an architectural motif designed to model long-range interactions in sequential data, has driven numerous recent breakthroughs in natural language processing and bey…
Statistical Estimation from Dependent Data
Yuval Dagan, Constantinos Daskalakis, Nishanth Dikkala +2
We consider a general statistical estimation problem wherein binary labels across different observations are not independent conditioned on their feature vectors, but dependent, ca…
Investigating the Role of Negatives in Contrastive Representation Learning
Jordan T. Ash, Surbhi Goel, Akshay Krishnamurthy +1
Noise contrastive learning is a popular technique for unsupervised representation learning. In this approach, a representation is obtained via reduction to supervised learning, whe…
Gone Fishing: Neural Active Learning with Fisher Embeddings
Jordan T. Ash, Surbhi Goel, Akshay Krishnamurthy +1
There is an increasing need for effective active learning algorithms that are compatible with deep neural networks. This paper motivates and revisits a classic, Fisher-based active…
Acceleration via Fractal Learning Rate Schedules
Naman Agarwal, Surbhi Goel, Cyril Zhang
In practical applications of iterative first-order optimization, the learning rate schedule remains notoriously difficult to understand and expensive to tune. We demonstrate the pr…
Tight Hardness Results for Training Depth-2 ReLU Networks
Surbhi Goel, Adam Klivans, Pasin Manurangsi +1
We prove several hardness results for training depth-2 neural networks with the ReLU activation function; these networks are simply weighted sums (that may include negative coeffic…
From Boltzmann Machines to Neural Networks and Back Again
Surbhi Goel, Adam Klivans, Frederic Koehler
Graphical models are powerful tools for modeling high-dimensional data, but learning graphical models in the presence of latent variables is well-known to be difficult. In this wor…
Statistical-Query Lower Bounds via Functional Gradients
Surbhi Goel, Aravind Gollakota, Adam Klivans
We give the first statistical-query lower bounds for agnostically learning any non-polynomial activation with respect to Gaussian marginals (e.g., ReLU, sigmoid, sign). For the spe…