mlsanityData to 14 Oct 2026

Solving Tensor Low Cycle Rank Approximation

arXiv 2304.06594 ↗First posted 13 Apr 2023cs.DS cs.LGcited by 8

Not on the map. Why?

Abstract (arXiv)

Large language models have become ubiquitous in modern life, finding applications in various domains such as natural language processing, language translation, and speech recognition. Recently, a breakthrough work [Zhao, Panigrahi, Ge, and Arora Arxiv 2023] explains the attention model from probabilistic context-free grammar (PCFG). One of the central computation task for computing probability in PCFG is formulating a particular tensor low rank approximation problem, we can call it tensor cycle rank. Given an n × n × n third order tensor A, we say that A has cycle rank-k if there exists three n × k2 size matrices U , V, and W such that for each entry in each beginalign* Aa,b,c = sumi=1k sumj=1k suml=1k Ua,i+k(j-1) otimes Vb, j + k(l-1) otimes Wc, l + k(i-1) endalign* for all a ∈ [n], b ∈ [n], c ∈ [n]. For the tensor classical rank, tucker rank and train rank, it has been well studied in [Song, Woodruff, Zhong SODA 2019]. In this paper, we generalize the previous ``rotation and sketch'' technique in page 186 of [Song, Woodruff, Zhong SODA 2019] and show an input sparsity time algorithm for cycle rank.

Key facts. Cited by 8 papers in the map (data through 14 Oct 2026). Builds on 45 of its 94 references that are in the map. First posted on arXiv 13 Apr 2023.

Builds on

45 of 94 references.

References · 45

  1. 2017Attention Is All You Needcited by 60,361
  2. 2018BERT: Pre-training of Deep Bidirectional Transformers for Language Understandingcited by 40,399
  3. 2020Language Models are Few-Shot Learnerscited by 32,419
  4. 2022PaLM: Scaling Language Modeling with Pathwayscited by 5,326
  5. 2022OPT: Open Pre-trained Transformer Language Modelscited by 3,512
  6. 2021Pre-train, Prompt, and Predict: A Systematic Survey of Prompting Methods in Natural Language Processingcited by 2,234
  7. 2019HuggingFace's Transformers: State-of-the-art Natural Language Processingcited by 2,218
  8. 2020Multilingual Denoising Pre-training for Neural Machine Translationcited by 1,035
  9. 2022Transformers learn in-context by gradient descentcited by 732
  10. 2023A Watermark for Large Language Modelscited by 725
  11. 2022What Can Transformers Learn In-Context? A Case Study of Simple Function Classescited by 715
  12. 2022What learning algorithm is in-context learning? Investigations with linear modelscited by 684
33 more
  1. 2020Beyond English-Centric Multilingual Machine Translationcited by 561
  2. 2020Pre-trained Models for Natural Language Processing: A Surveycited by 505
  3. 2014Sketching as a Tool for Numerical Linear Algebracited by 288
  4. 2023Fast Attention Requires Bounded Entriescited by 102
  5. 2018Solving Linear Programs in the Current Matrix Multiplication Timecited by 100
  6. 2019Neural Machine Translation: A Review and Surveycited by 100
  7. 2023How Do Transformers Learn Topic Structure: Towards a Mechanistic Understandingcited by 86
  8. 2021Training Multi-Layer Over-Parametrized Neural Network in Subquadratic Timecited by 62
  9. 2020Training (Overparametrized) Neural Networks in Near-Linear Timecited by 58
  10. 2023KDEformer: Accelerating Transformers via Kernel Density Estimationcited by 58
  11. 2020An Improved Cutting Plane Method for Convex Optimization, Convex-Concave Games and its Applicationscited by 57
  12. 2023Do Transformers Parse while Predicting the Masked Word?cited by 48
  13. 2017Relative Error Tensor Low Rank Approximationcited by 45
  14. 2023An Over-parameterized Exponential Regressioncited by 45
  15. 2023Solving Regularized Exp, Cosh and Sinh Regression Problemscited by 44
  16. 2019A Deterministic Linear Program Solver in Current Matrix Multiplication Timecited by 42
  17. 2021Approximating How Single Head Attention Learnscited by 38
  18. 2023Randomized and Deterministic Attention Sparsification Algorithms for Over-parameterized Feature Dimensioncited by 37
  19. 2021Fast Sketching of Polynomial Kernels of Polynomial Degreecited by 33
  20. 2014Optimal CUR Matrix Decompositionscited by 29
  21. 2017Sketching for Kronecker Product Regression and P-splinescited by 29
  22. 2019Optimal Sketching for Kronecker Product Regression and Low Rank Approximationcited by 29
  23. 2022Faster Algorithm for Structured John Ellipsoid Computationcited by 28
  24. 2015Optimal Principal Component Analysis in Distributed and Streaming Modelscited by 24
  25. 2019A near-optimal algorithm for approximating the John Ellipsoidcited by 23
  26. 2022Discrepancy Minimization in Input-Sparsity Timecited by 22
  27. 2022Dynamic Tensor Product Regressioncited by 17
  28. 2016Distributed Low Rank Approximation of Implicit Functions of a Matrixcited by 12
  29. 2018Towards a Zero-One Law for Column Subset Selectioncited by 12
  30. 2020Average Case Column Subset Selection for Entrywise ℓ1-Norm Losscited by 12
  31. 2023Convex Minimization with Integer Minima in widetilde O(n4) Timecited by 12
  32. 2019Dynamic Matrix Inverse: Improved Algorithms and Matching Conditional Lower Boundscited by 8
  33. 2022Near-Linear Time and Fixed-Parameter Tractable Algorithms for Tensor Decompositionscited by 4

Built on by

Cited by year

Citing papers per year: 2023: 6; 2024: 1; 2025: 1.

8 papers.

  1. 2023The Closeness of In-Context Learning and Weight Shifting for Softmax Regressioncited by 41
  2. 2024The Fine-Grained Complexity of Gradient Computation for Training Large Language Modelscited by 30
  3. 2023Why Softmax Attention Outperforms Linear Attentioncited by 15
  4. 2023Faster Robust Tensor Power Method for Arbitrary Ordercited by 8
  5. 2023A Theoretical Insight into Attack and Defense of Gradient Leakage in Transformercited by 6
  6. 2023One Pass Streaming Algorithm for Super Long Token Attention Approximation in Sublinear Spacecited by 6
  7. 2025Towards Sampling Data Structures for Tensor Products in Turnstile Streamscited by 1
  8. 2023Fast Heavy Inner Product Identification Between Weights and Inputs in Neural Network Trainingcited by 0