2021

Nystr\"omformer: A Nystr\"om-Based Algorithm for Approximating Self-Attention

Xiong, Yunyang, Zeng, Zhanpeng, Chakraborty, Rudrasis et al.

Understand

Transformers have emerged as a powerful tool for a broad range of natural language processing tasks.

A key component that drives the impressive performance of Transformers is the self-attention mechanism that encodes the influence or dependence of other tokens on each specific token.
While beneficial, the quadratic complexity of self-attention on the input sequence length has limited its application to longer sequences -- a topic being actively studied in the community.
To address this limitation, we propose Nystr\"{o}mformer -- a model that exhibits favorable scalability as a function of sequence length.

Built on

Generating long sequences with sparse transformers
Original
Child, R.; Gray, S.; Radford, A.; and Sutskever, I. 2019 · 1904
Earlier work this paper cites.
Nystr \ \backslash ” om landmark sampling and regularized Christoffel functions
Original
Fanuel, M.; Schreurs, J.; and Suykens, J. A. 2019 · 1905
Earlier work this paper cites.
RoBERTa: A robustly optimized BERT pretraining approach
Original
Liu, Y.; Ott, M.; Goyal, N.; Du, J.; Joshi, M.; Chen, D.; Levy, O.; Lewis, M.; Zettlemoyer, L.; and Stoyanov, V. 2019 · 1907
Earlier work this paper cites.
DistilBERT, a distilled version of BERT: smaller, faster, cheaper and lighter
Original
Sanh, V.; Debut, L.; Chaumond, J.; and Wolf, T. 2019 · 1910
Earlier work this paper cites.
The numerical treatment of integral equations
Baker, C. T. 1977 · 1977
Earlier work this paper cites.
An improved Newton iteration for the generalized inverse of a matrix, with applications
Pan, V.; and Schreiber, R. 1991 · 1991
Earlier work this paper cites.
Using the Nyström method to speed up kernel machines
Williams, C. K.; and Seeger, M. 2001 · 2001
Earlier work this paper cites.
Longformer: The Long-Document Transformer
Original
Beltagy, I.; Peters, M. E.; and Cohan, A. 2020 · 2004
Earlier work this paper cites.
Language models are few-shot learners
Original
Brown, T. B.; Mann, B.; Ryder, N.; Subbiah, M.; Kaplan, J.; Dhariwal, P.; Neelakantan, A.; Shyam, P.; Sastry, G.; Askell, A.; et al. 2020 · 2005
Earlier work this paper cites.
Automatically constructing a corpus of sentential paraphrases
Dolan, W. B.; and Brockett, C. 2005 · 2005
Earlier work this paper cites.
On the Nyström method for approximating a Gram matrix for improved kernel-based learning
Drineas, P.; and Mahoney, M. W. 2005 · 2005
Earlier work this paper cites.
Linformer: Self-Attention with Linear Complexity
Original
Wang, S.; Li, B.; Khabsa, M.; Fang, H.; and Ma, H. 2020 · 2006
Earlier work this paper cites.
Big bird: Transformers for longer sequences
Original
Zaheer, M.; Guruganesh, G.; Dubey, A.; Ainslie, J.; Alberti, C.; Ontanon, S.; Pham, P.; Ravula, A.; Wang, Q.; Yang, L.; et al. 2020 · 2007
Earlier work this paper cites.
Improved Nyström low-rank approximation and error analysis
Zhang, K.; Tsang, I. W.; and Kwok, J. T. 2008 · 2008
Earlier work this paper cites.
Rethinking attention with performers
Original
Choromanski, K.; Likhosherstov, V.; Dohan, D.; Song, X.; Gane, A.; Sarlos, T.; Hawkins, P.; Davis, J.; Mohiuddin, A.; Kaiser, L.; et al. 2020 · 2009
Earlier work this paper cites.
Learning multiple layers of features from tiny images
Krizhevsky, A.; Hinton, G.; et al. 2009 · 2009
Earlier work this paper cites.
Ensemble Nyström method
Kumar, S.; Mohri, M.; and Talwalkar, A. 2009 · 2009
Earlier work this paper cites.
Making large-scale Nyström approximation possible
Li, M.; Kwok, J. T.-Y.; and Lü, B. 2010 · 2010
Earlier work this paper cites.
Clustered Nyström method for large scale manifold learning and dimension reduction
Zhang, K.; and Kwok, J. T. 2010 · 2010
Earlier work this paper cites.
Learning word vectors for sentiment analysis
Maas, A.; Daly, R. E.; Pham, P. T.; Huang, D.; Ng, A. Y.; and Potts, C. 2011 · 2011
Earlier work this paper cites.
Long Range Arena: A Benchmark for Efficient Transformers
Original
Tay, Y.; Dehghani, M.; Abnar, S.; Shen, Y.; Bahri, D.; Pham, P.; Rao, J.; Yang, L.; Ruder, S.; and Metzler, D. 2020 · 2011
Earlier work this paper cites.

Similar

On the Nyström discretization of integral equations on planar curves with corners
Bremer, J. 2012 · 2012
Cited alongside, same era.
The ACL anthology network corpus
Radev, D. R.; Muthukrishnan, P.; Qazvinian, V.; and Abu-Jbara, A. 2013 · 2013
Cited alongside, same era.
Recursive deep models for semantic compositionality over a sentiment treebank
Socher, R.; Perelygin, A.; Wu, J.; Chuang, J.; Manning, C. D.; Ng, A. Y.; and Potts, C. 2013 · 2013
Cited alongside, same era.
Improving CUR matrix decomposition and the Nyström approximation via adaptive sampling
Wang, S.; and Zhang, Z. 2013 · 2013
Cited alongside, same era.
A new iterative method for finding approximate inverses of complex matrices
Razavi, M. K.; Kerayechian, A.; Gachpazan, M.; and Shateyi, S. 2014 · 2014
Cited alongside, same era.
Improving the modified nyström method using spectral shifting
Wang, S.; Zhang, C.; Qian, H.; and Zhang, Z. 2014 · 2014
Cited alongside, same era.
Aligning books and movies: Towards story-like visual explanations by watching movies and reading books
Zhu, Y.; Kiros, R.; Zemel, R.; Salakhutdinov, R.; Urtasun, R.; Torralba, A.; and Fidler, S. 2015 · 2015
Cited alongside, same era.
Training deep nets with sublinear memory cost
Original
Chen, T.; Xu, B.; Zhang, C.; and Guestrin, C. 2016 · 2016
Cited alongside, same era.
Matrix compression using the Nyström method
Nemtsov, A.; Averbuch, A.; and Schclar, A. 2016 · 2016
Cited alongside, same era.
SQuAD: 100,000+ Questions for Machine Comprehension of Text
Rajpurkar, P.; Zhang, J.; Lopyrev, K.; and Liang, P. 2016 · 2016
Cited alongside, same era.
Computationally efficient Nyström approximation using fast transforms
Si, S.; Hsieh, C.-J.; and Dhillon, I. 2016 · 2016
Cited alongside, same era.
Towards more efficient SPSD matrix approximation and CUR matrix decomposition
Wang, S.; Zhang, Z.; and Zhang, T. 2016 · 2016
Cited alongside, same era.

Then

ListOps: A Diagnostic Dataset for Latent Tree Learning
Nangia, N.; and Bowman, S. R. 2018 · 2018
Later among the works it cites.
Deep contextualized word representations
Peters, M. E.; Neumann, M.; Iyyer, M.; Gardner, M.; Clark, C.; Lee, K.; and Zettlemoyer, L. 2018 · 2018
Later among the works it cites.
Improving language understanding with unsupervised learning
Radford, A.; Narasimhan, K.; Salimans, T.; and Sutskever, I. 2018 · 2018
Later among the works it cites.
GLUE: A Multi-Task Benchmark and Analysis Platform for Natural Language Understanding
Wang, A.; Singh, A.; Michael, J.; Hill, F.; Levy, O.; and Bowman, S. R. 2018 · 2018
Later among the works it cites.
A Broad-Coverage Challenge Corpus for Sentence Understanding through Inference
Williams, A.; Nangia, N.; and Bowman, S. R. 2018 · 2018
Later among the works it cites.
ELECTRA: Pre-training Text Encoders as Discriminators Rather Than Generators
Clark, K.; Luong, M.-T.; Le, Q. V.; and Manning, C. D. 2019 · 2019
Later among the works it cites.
Transformer-XL: Attentive Language Models beyond a Fixed-Length Context
Dai, Z.; Yang, Z.; Yang, Y.; Carbonell, J. G.; Le, Q.; and Salakhutdinov, R. 2019 · 2019
Later among the works it cites.
BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding
Devlin, J.; Chang, M.-W.; Lee, K.; and Toutanova, K. 2019 · 2019
Later among the works it cites.
Gpipe: Efficient training of giant neural networks using pipeline parallelism
Huang, Y.; Cheng, Y.; Bapna, A.; Firat, O.; Chen, D.; Chen, M.; Lee, H.; Ngiam, J.; Le, Q. V.; Wu, Y.; et al. 2019 · 2019
Later among the works it cites.
Reformer: The Efficient Transformer
Kitaev, N.; Kaiser, L.; and Levskaya, A. 2019 · 2019
Later among the works it cites.
Large memory layers with product keys
Lample, G.; Sablayrolles, A.; Ranzato, M.; Denoyer, L.; and Jégou, H. 2019 · 2019
Later among the works it cites.
Set transformer: A framework for attention-based permutation-invariant neural networks
Lee, J.; Lee, Y.; Kim, J.; Kosiorek, A.; Choi, S.; and Teh, Y. W. 2019 · 2019
Later among the works it cites.
Are sixteen heads really better than one?
Michel, P.; Levy, O.; and Neubig, G. 2019 · 2019
Later among the works it cites.
Sampled softmax with random fourier features
Rawat, A. S.; Chen, J.; Yu, F. X. X.; Suresh, A. T.; and Kumar, S. 2019 · 2019
Later among the works it cites.
GLUE: A Multi-Task Benchmark and Analysis Platform for Natural Language Understanding
Wang, A.; Singh, A.; Michael, J.; Hill, F.; Levy, O.; and Bowman, S. R. 2019 · 2019
Later among the works it cites.
Q8BERT: Quantized 8bit BERT
Zafrir, O.; Boudoukh, G.; Izsak, P.; and Wasserblat, M. 2019 · 2019
Later among the works it cites.
Transformers are RNNs: Fast Autoregressive Transformers with Linear Attention
Katharopoulos, A.; Vyas, A.; Pappas, N.; and Fleuret, F. 2020 · 2020
Later among the works it cites.
ALBERT: A lite BERT for self-supervised learning of language representations
Lan, Z.; Chen, M.; Goodman, S.; Gimpel, K.; Sharma, P.; and Soricut, R. 2020 · 2020
Later among the works it cites.
BART: Denoising sequence-to-sequence pre-training for natural language generation, translation, and comprehension
Lewis, M.; Liu, Y.; Goyal, N.; Ghazvininejad, M.; Mohamed, A.; Levy, O.; Stoyanov, V.; and Zettlemoyer, L. 2020 · 2020
Later among the works it cites.
Fast transformers with clustered attention
Vyas, A.; Katharopoulos, A.; and Fleuret, F. 2020 · 2020
Later among the works it cites.
LambdaNetworks: Modeling long-range Interactions without Attention
Bello, I. 2021 · 2021
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…

Nystr\&#34;omformer: A Nystr\&#34;om-Based Algorithm for Approximating Self-Attention

Understand

Built on

Similar

Then

Beyond the bibliography

Built on

Similar

Then

Beyond the bibliography

Nystr\"omformer: A Nystr\"om-Based Algorithm for Approximating Self-Attention