mlsanityData to 7 Oct 2026

Sketching for Kronecker Product Regression and P-splines

arXiv 1712.09473 ↗First posted 27 Dec 2017cs.DS cs.LG stat.MLcited by 29

Not on the map. Why?

Abstract (arXiv)

TensorSketch is an oblivious linear sketch introduced in Pagh'13 and later used in Pham, Pagh'13 in the context of SVMs for polynomial kernels. It was shown in Avron, Nguyen, Woodruff'14 that TensorSketch provides a subspace embedding, and therefore can be used for canonical correlation analysis, low rank approximation, and principal component regression for the polynomial kernel. We take TensorSketch outside of the context of polynomials kernels, and show its utility in applications in which the underlying design matrix is a Kronecker product of smaller matrices. This allows us to solve Kronecker product regression and non-negative Kronecker product regression, as well as regularized spline regression. Our main technical result is then in extending TensorSketch to other norms. That is, TensorSketch only provides input sparsity time for Kronecker product regression with respect to the 2-norm. We show how to solve Kronecker product regression with respect to the 1-norm in time sublinear in the time required for computing the Kronecker product, as well as for more general p-norms.

Key facts. Cited by 29 papers in the map (data through 7 Oct 2026). First posted on arXiv 27 Dec 2017.

Builds on

No reference list yet.

Built on by

Cited by year

Citing papers per year: 2021: 8; 2022: 2; 2023: 11; 2024: 5; 2025: 3.

29 papers.

Sort:

  1. 2021Training Multi-Layer Over-Parametrized Neural Network in Subquadratic Timecited by 62
  2. 2023Solving Regularized Exp, Cosh and Sinh Regression Problemscited by 44
  3. 2023How to Capture Higher-order Correlations? Generalizing Matrix Softmax Attention to Kronecker Computationcited by 44
  4. 2021Fast Sketching of Polynomial Kernels of Polynomial Degreecited by 33
  5. 2023In-Context Learning for Attention Scheme: from Single Softmax Regression to Multiple Softmax Regression via a Tensor Trickcited by 32
  6. 2023Low Rank Matrix Completion via Robust Alternating Minimization in Nearly Linear Timecited by 31
  7. 2024Computational Limits of Low-Rank Adaptation (LoRA) Fine-Tuning for Transformer Modelscited by 31
  8. 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
  9. 2024The Fine-Grained Complexity of Gradient Computation for Training Large Language Modelscited by 30
  10. 2023A Mathematical Abstraction for Balancing the Trade-off Between Creativity and Reality in Large Language Modelscited by 29
  11. 2023GradientCoin: A Peer-to-Peer Decentralized Large Language Modelscited by 23
  12. 2023Solving Attention Kernel Regression Problem via Pre-conditionercited by 20
17 more
  1. 2022Dynamic Tensor Product Regressioncited by 17
  2. 2023A Nearly-Optimal Bound for Fast Regression with ℓ_∞ Guaranteecited by 14
  3. 2021Fast and Accurate Randomized Algorithms for Low-rank Tensor Decompositionscited by 11
  4. 2023Efficient Alternating Minimization with Applications to Weighted Low Rank Approximationcited by 9
  5. 2023Solving Tensor Low Cycle Rank Approximationcited by 8
  6. 2021More Efficient Sampling for Tensor Decomposition With Worst-Case Guaranteescited by 7
  7. 2024Fast John Ellipsoid Computation with Differential Privacy Optimizationcited by 7
  8. 2025Only Large Weights (And Not Skip Connections) Can Prevent the Perils of Rank Collapsecited by 7
  9. 2022Subquadratic Kronecker Regression with Applications to Tensor Decompositioncited by 6
  10. 2021Fast Low-Rank Tensor Decomposition by Ridge Leverage Score Samplingcited by 5
  11. 2025Tensor Sketch: Fast and Scalable Polynomial Kernel Approximationcited by 4
  12. 2021Fast Graph Neural Tangent Kernel via Kronecker Sketchingcited by 2
  13. 2021Rademacher Random Projections with Tensor Networkscited by 1
  14. 2024Quantum Speedup for Spectral Approximation of Kronecker Productscited by 1
  15. 2024Log-concave Sampling from a Convex Body with a Barrier: a Robust and Unified Dikin Walkcited by 1
  16. 2025Towards Sampling Data Structures for Tensor Products in Turnstile Streamscited by 1
  17. 2021Efficient Tensor Contraction via Fast Count Sketchcited by 0