13 citations · 35 across the 15 of their papers we have counts for
16 papers
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…
When Do Transformers Outperform Feedforward and Recurrent Networks? A Statistical Perspective
Alireza Mousavi-Hosseini, Clayton Sanford, Denny Wu +1
Theoretical efforts to prove advantages of Transformers in comparison with classical architectures such as feedforward and recurrent neural networks have mostly focused on represen…
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…
Improving the predictions of ML-corrected climate models with novelty detection
Clayton Sanford, Anna Kwa, Oliver Watt-Meyer +4
While previous works have shown that machine learning (ML) can improve the prediction accuracy of coarse-grid climate models, these ML-augmented methods are more vulnerable to irre…
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…
Enabling equation-free modeling via diffusion maps
Tracy Chin, Jacob Ruth, Clayton Sanford +3
Equation-free modeling aims at extracting low-dimensional macroscopic dynamics from complex high-dimensional systems that govern the evolution of microscopic states. This algorithm…
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…
Uniform Convergence Bounds for Codec Selection
Clayton Sanford, Cyrus Cousins, Eli Upfal
We frame the problem of selecting an optimal audio encoding scheme as a supervised learning task. Through uniform convergence theory, we guarantee approximately optimal codec selec…