mlsanityData to 14 Oct 2026

Dynamic Tensor Product Regression

arXiv 2210.03961 ↗First posted 8 Oct 2022cs.DS cs.LGcited by 17

Not on the map. Why?

Abstract (arXiv)

In this work, we initiate the study of Dynamic Tensor Product Regression. One has matrices A1∈ ℝn1× d1,ldots,Aq∈ ℝnq× dq and a label vector b∈ ℝn1ldots nq, and the goal is to solve the regression problem with the design matrix A being the tensor product of the matrices A1, A2, dots, Aq i.e. min_x∈ ℝd1ldots dq~|(A1otimes ldotsotimes Aq)x-b|2. At each time step, one matrix Ai receives a sparse change, and the goal is to maintain a sketch of the tensor product A1otimesldots otimes Aq so that the regression solution can be updated quickly. Recomputing the solution from scratch for each round is very slow and so it is important to develop algorithms which can quickly update the solution with the new design matrix. Our main result is a dynamic tree data structure where any update to a single matrix can be propagated quickly throughout the tree. We show that our data structure can be used to solve dynamic versions of not only Tensor Product Regression, but also Tensor Product Spline regression (which is a generalization of ridge regression) and for maintaining Low Rank Approximations for the tensor product.

Key facts. Cited by 17 papers in the map (data through 14 Oct 2026). Builds on 34 of its 85 references that are in the map. First posted on arXiv 8 Oct 2022.

Builds on

34 of 85 references.

References · 34

  1. 2014Convex Optimization: Algorithms and Complexitycited by 575
  2. 2021Training Multi-Layer Over-Parametrized Neural Network in Subquadratic Timecited by 62
  3. 2020Training (Overparametrized) Neural Networks in Near-Linear Timecited by 58
  4. 2020An Improved Cutting Plane Method for Convex Optimization, Convex-Concave Games and its Applicationscited by 57
  5. 2020A Refined Laser Method and Faster Matrix Multiplicationcited by 56
  6. 2019Solving Empirical Risk Minimization in the Current Matrix Multiplication Timecited by 53
  7. 2020A Faster Interior Point Method for Semidefinite Programmingcited by 53
  8. 2014Dimensionality Reduction for k-Means Clustering and Low Rank Approximationcited by 48
  9. 2017Relative Error Tensor Low Rank Approximationcited by 45
  10. 2020Faster Dynamic Matrix Inverse for Faster LPscited by 44
  11. 2021Solving SDP Faster: A Robust IPM Framework and Efficient Implementationcited by 33
  12. 2021Fast Sketching of Polynomial Kernels of Polynomial Degreecited by 33
22 more
  1. 2021Does Preprocessing Help Training Over-parameterized Neural Networks?cited by 32
  2. 2014Optimal CUR Matrix Decompositionscited by 29
  3. 2017Sketching for Kronecker Product Regression and P-splinescited by 29
  4. 2019Optimal Sketching for Kronecker Product Regression and Low Rank Approximationcited by 29
  5. 2015Optimal Principal Component Analysis in Distributed and Streaming Modelscited by 24
  6. 2018BourGAN: Generative Networks with Metric Embeddingscited by 22
  7. 2016Sharper Bounds for Regularized Data Fittingcited by 19
  8. 2018Subspace Embedding and Linear Regression with Orlicz Normcited by 19
  9. 2021Breaking the Linear Iteration Cost Barrier for Some Well-known Conditional Gradient Methods Using MaxIP Data-structurescited by 19
  10. 2021Dynamic Algorithms Against an Adaptive Adversary: Generic Constructions and Lower Boundscited by 17
  11. 2016Online Row Samplingcited by 15
  12. 2019Sample-Optimal Low-Rank Approximation of Distance Matricescited by 15
  13. 2021Sublinear Least-Squares Value Iteration via Locality Sensitive Hashingcited by 15
  14. 2016Distributed Low Rank Approximation of Implicit Functions of a Matrixcited by 12
  15. 2018Towards a Zero-One Law for Column Subset Selectioncited by 12
  16. 2020Average Case Column Subset Selection for Entrywise ℓ1-Norm Losscited by 12
  17. 2017Near Optimal Sketching of Low-Rank Tensor Regressioncited by 11
  18. 2013Navigating Central Path with Electrical Flows: from Flows to Matchings, and Backcited by 7
  19. 2022Subquadratic Kronecker Regression with Applications to Tensor Decompositioncited by 6
  20. 2016Computing Maximum Flow with Augmenting Electrical Flowscited by 5
  21. 2021Symmetric Sparse Boolean Matrix Factorization and Applicationscited by 3
  22. 2021Improved Algorithms for Low Rank Approximation from Sparsitycited by 2

Built on by

Cited by year

Citing papers per year: 2022: 1; 2023: 11; 2024: 2; 2025: 3.

17 papers.

Sort:

  1. 2023Randomized and Deterministic Attention Sparsification Algorithms for Over-parameterized Feature Dimensioncited by 37
  2. 2023Low Rank Matrix Completion via Robust Alternating Minimization in Nearly Linear Timecited by 31
  3. 2023A Fast Optimization View: Reformulating Single Layer Attention in LLM Based on Tensor and SVM Trick, and Solving It in Matrix Multiplication Timecited by 30
  4. 2024The Fine-Grained Complexity of Gradient Computation for Training Large Language Modelscited by 30
  5. 2022Sketching for First Order Method: Efficient Algorithm for Low-Bandwidth Channel and Vulnerabilitycited by 25
  6. 2023GradientCoin: A Peer-to-Peer Decentralized Large Language Modelscited by 23
  7. 2023Solving Attention Kernel Regression Problem via Pre-conditionercited by 20
  8. 2023A Nearly-Optimal Bound for Fast Regression with ℓ_∞ Guaranteecited by 14
  9. 2023Efficient Alternating Minimization with Applications to Weighted Low Rank Approximationcited by 9
  10. 2025Fast RoPE Attention: Combining the Polynomial Method and Fast Fourier Transformcited by 9
  11. 2023Solving Tensor Low Cycle Rank Approximationcited by 8
  12. 2023Faster Robust Tensor Power Method for Arbitrary Ordercited by 8
5 more
  1. 2023The Expressibility of Polynomial based Attention Schemecited by 7
  2. 2025Only Large Weights (And Not Skip Connections) Can Prevent the Perils of Rank Collapsecited by 7
  3. 2024Advancing the Understanding of Fixed Point Iterations in Deep Neural Networks: A Detailed Analytical Studycited by 4
  4. 2025Towards Sampling Data Structures for Tensor Products in Turnstile Streamscited by 1
  5. 2023Online Adaptive Mahalanobis Distance Estimationcited by 0