Linear Complexity Randomized Self-attention Mechanism

Lin Zheng; Chong Wang; Lingpeng Kong

ICML 2022spotlight46 citations

Linear Complexity Randomized Self-attention Mechanism

Abstract

Recently, random feature attentions (RFAs) are proposed to approximate the softmax attention in linear time and space complexity by linearizing the exponential kernel. In this paper, we first propose a novel perspective to understand the bias in such approximation by recasting RFAs as self-normalized importance samplers. This perspective further sheds light on an

BibTeX

@InProceedings{pmlr-v162-zheng22b,
  title = 	 {Linear Complexity Randomized Self-attention Mechanism},
  author =       {Zheng, Lin and Wang, Chong and Kong, Lingpeng},
  booktitle = 	 {Proceedings of the 39th International Conference on Machine Learning},
  pages = 	 {27011--27041},
  year = 	 {2022},
  editor = 	 {Chaudhuri, Kamalika and Jegelka, Stefanie and Song, Le and Szepesvari, Csaba and Niu, Gang and Sabato, Sivan},
  volume = 	 {162},
  series = 	 {Proceedings of Machine Learning Research},
  month = 	 {17--23 Jul},
  publisher =    {PMLR},
  pdf = 	 {https://proceedings.mlr.press/v162/zheng22b/zheng22b.pdf},
  url = 	 {https://proceedings.mlr.press/v162/zheng22b.html},
  abstract = 	 {Recently, random feature attentions (RFAs) are proposed to approximate the softmax attention in linear time and space complexity by linearizing the exponential kernel. In this paper, we first propose a novel perspective to understand the bias in such approximation by recasting RFAs as self-normalized importance samplers. This perspective further sheds light on an