174 citations · 991 across the 46 of their papers we have counts for
4 papers · 1 filter
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.…
Spectrum Extraction and Clipping for Implicitly Linear Layers
Ali Ebrahimpour Boroojeny, Matus Telgarsky, Hari Sundaram
We show the effectiveness of automatic differentiation in efficiently and correctly computing and controlling the spectrum of implicitly linear operators, a rich family of layer ty…
Large Stepsize Gradient Descent for Logistic Loss: Non-Monotonicity of the Loss Improves Optimization Efficiency
Jingfeng Wu, Peter L. Bartlett, Matus Telgarsky +1
We consider gradient descent (GD) with a constant stepsize applied to logistic regression with linearly separable data, where the constant stepsize is so large that the loss in…