13 citations · 35 across the 15 of their papers we have counts for
12 papers · 1 filter
Next-Token Prediction and Regret Minimization
Mehryar Mohri, Clayton Sanford, Jon Schneider +2
We consider the question of how to employ next-token prediction algorithms in adversarial online decision-making environments. Specifically, if we train a next-token prediction mod…
Fast attention mechanisms: a tale of parallelism
Jingwen Liu, Hantao Yu, Clayton Sanford +2
Transformers have the representational capacity to simulate Massively Parallel Computation (MPC) algorithms, but they suffer from quadratic time complexity, which severely limits t…
One-layer transformers fail to solve the induction heads task
Clayton Sanford, Daniel Hsu, Matus Telgarsky
A simple communication complexity argument proves that no one-layer transformer can solve the induction heads task unless its size is exponentially larger than the size sufficient…
Transformers, parallel computation, and logarithmic depth
Clayton Sanford, Daniel Hsu, Matus Telgarsky
We show that a constant number of self-attention layers can efficiently simulate, and be simulated by, a constant number of communication rounds of Massively Parallel Computation.…
Representational Strengths and Limitations of Transformers
Clayton Sanford, Daniel Hsu, Matus Telgarsky
Attention layers, as commonly used in transformers, form the backbone of modern deep learning, yet there is no mathematical description of their benefits and deficiencies as compar…
Learning Single-Index Models with Shallow Neural Networks
Alberto Bietti, Joan Bruna, Clayton Sanford +1
Single-index models are a class of functions given by an unknown univariate ``link'' function applied to an unknown one-dimensional projection of the input. These models are partic…
On Scrambling Phenomena for Randomly Initialized Recurrent Networks
Vaggos Chatziafratis, Ioannis Panageas, Clayton Sanford +1
Recurrent Neural Networks (RNNs) frequently exhibit complicated dynamics, and their sensitivity to the initialization process often renders them notoriously hard to train. Recent w…
Intrinsic dimensionality and generalization properties of the -norm inductive bias
Navid Ardeshir, Daniel Hsu, Clayton Sanford
We study the structural and statistical properties of -norm minimizing interpolants of datasets labeled by specific target functions. The -norm is the bas…
Near-Optimal Statistical Query Lower Bounds for Agnostically Learning Intersections of Halfspaces with Gaussian Marginals
Daniel Hsu, Clayton Sanford, Rocco Servedio +1
We consider the well-studied problem of learning intersections of halfspaces under the Gaussian distribution in the challenging \emph{agnostic learning} model. Recent work of Diako…
Expressivity of Neural Networks via Chaotic Itineraries beyond Sharkovsky's Theorem
Clayton Sanford, Vaggos Chatziafratis
Given a target function , how large must a neural network be in order to approximate ? Recent works examine this basic question on neural network \textit{expressivity} from t…
Support vector machines and linear regression coincide with very high-dimensional features
Navid Ardeshir, Clayton Sanford, Daniel Hsu
The support vector machine (SVM) and minimum Euclidean norm least squares regression are two fundamentally different approaches to fitting linear models, but they have recently bee…
On the Approximation Power of Two-Layer Networks of Random ReLUs
Daniel Hsu, Clayton Sanford, Rocco A. Servedio +1
This paper considers the following question: how well can depth-two ReLU networks with randomly initialized bottom-level weights represent smooth functions? We give near-matching u…