Learning Linear Attention in Polynomial Time

Morris Yau, Ekin Akyürek, Jiayuan Mao +3

Previous research has explored the computational expressivity of Transformer models in simulating Boolean circuits or Turing machines. However, the learnability of these simulators…