mlsanityData to 14 Oct 2026

Structured and Fast Optimization: The Kronecker SGD Algorithm

arXiv 2305.08001 ↗First posted 13 May 2023cs.LGcited by 5

Not on the map. Why?

Abstract (arXiv)

Stochastic gradient descent (SGD) now acts as a fundamental part of optimization in current machine learning. Meanwhile, deep learning architectures have shown outstanding performance in a wide range of fields, such as natural language processing, bioinformatics, and computer vision. Nevertheless, as the parameter size d increases, these models encounter serious efficiency challenges. Previous studies show that the per step calculation expense scales linearly with the input size d. To mitigate this, our paper explores inherent patterns, such as Kronecker products within the training examples. We consider input data points that can be represented as tensor products of lower-dimensional vectors. We introduce a novel stochastic optimization method where the computational load for every update scales sublinearly with d, assuming moderate structural properties of the inputs. We believe our research is the first work achieving this result, representing a significant step forward for efficient deep learning optimization. Our theoretical findings are supported by a formal theorem, demonstrating that the proposed algorithm can train a two-layer fully connected neural network with a per-iteration cost independent of d.

Key facts. Cited by 5 papers in the map (data through 14 Oct 2026). Builds on 46 of its 86 references that are in the map. First posted on arXiv 13 May 2023.

Builds on

46 of 86 references.

References · 46

  1. 2015Deep Residual Learning for Image Recognitioncited by 52,096
  2. 2018BERT: Pre-training of Deep Bidirectional Transformers for Language Understandingcited by 40,399
  3. 2021High-Resolution Image Synthesis with Latent Diffusion Modelscited by 18,863
  4. 2014Very Deep Convolutional Networks for Large-Scale Image Recognitioncited by 15,364
  5. 2014Going Deeper with Convolutionscited by 4,241
  6. 2019XLNet: Generalized Autoregressive Pretraining for Language Understandingcited by 2,811
  7. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,621
  8. 2015Deep Compression: Compressing Deep Neural Networks with Pruning, Trained Quantization and Huffman Codingcited by 2,329
  9. 2018Deep contextualized word representationscited by 2,290
  10. 2015Learning both Weights and Connections for Efficient Neural Networkscited by 2,031
  11. 2018A Convergence Theory for Deep Learning via Over-Parameterizationcited by 787
  12. 2018Gradient Descent Provably Optimizes Over-parameterized Neural Networkscited by 659
34 more
  1. 2018Gradient Descent Finds Global Minima of Deep Neural Networkscited by 574
  2. 2019Deep Learning Recommendation Model for Personalization and Recommendation Systemscited by 327
  3. 2018Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Datacited by 261
  4. 2023Fast Attention Requires Bounded Entriescited by 102
  5. 2018Solving Linear Programs in the Current Matrix Multiplication Timecited by 100
  6. 2018On the Convergence Rate of Training Recurrent Neural Networkscited by 82
  7. 2021Training Multi-Layer Over-Parametrized Neural Network in Subquadratic Timecited by 62
  8. 2019Quadratic Suffices for Over-parametrization via Matrix Chernoff Boundcited by 59
  9. 2020Training (Overparametrized) Neural Networks in Near-Linear Timecited by 58
  10. 2017SGD Learns the Conjugate Kernel Class of the Networkcited by 54
  11. 2019Solving Empirical Risk Minimization in the Current Matrix Multiplication Timecited by 53
  12. 2020A Faster Interior Point Method for Semidefinite Programmingcited by 53
  13. 2021Deep Kronecker neural networks: A general framework for neural networks with adaptive activation functionscited by 49
  14. 2022A Theoretical Analysis on Feature Learning in Neural Networks: Emergence from Inputs and Advantage over Fixed Featurescited by 49
  15. 2023Attention Scheme Inspired Softmax Regressioncited by 49
  16. 2016Deep Learning in Bioinformaticscited by 48
  17. 2019SLIDE : In Defense of Smart Algorithms over Hardware Acceleration for Large-Scale Deep Learning Systemscited by 46
  18. 2023An Over-parameterized Exponential Regressioncited by 45
  19. 2023Solving Regularized Exp, Cosh and Sinh Regression Problemscited by 44
  20. 2019A Deterministic Linear Program Solver in Current Matrix Multiplication Timecited by 42
  21. 2023Algorithm and Hardness for Dynamic Attention Maintenance in Large Language Modelscited by 37
  22. 2023Randomized and Deterministic Attention Sparsification Algorithms for Over-parameterized Feature Dimensioncited by 37
  23. 2022A Faster Small Treewidth SDP Solvercited by 36
  24. 2023An Iterative Algorithm for Rescaled Hyperbolic Functions Regressioncited by 35
  25. 2021Solving SDP Faster: A Robust IPM Framework and Efficient Implementationcited by 33
  26. 2021Does Preprocessing Help Training Over-parameterized Neural Networks?cited by 32
  27. 2022Faster Algorithm for Structured John Ellipsoid Computationcited by 28
  28. 2022Speeding Up Sparsification using Inner Product Search Data Structurescited by 22
  29. 2022A Sublinear Adversarial Training Algorithmcited by 22
  30. 2022Sketching Meets Differential Privacy: Fast Algorithm for Dynamic Kronecker Projection Maintenancecited by 22
  31. 2022Discrepancy Minimization in Input-Sparsity Timecited by 22
  32. 2020Kronecker Attention Networkscited by 9
  33. 2019Dynamic Matrix Inverse: Improved Algorithms and Matching Conditional Lower Boundscited by 8
  34. 2022Deep Kronecker Networkcited by 2

Built on by

Cited by year

Citing papers per year: 2023: 3; 2024: 2.

5 papers.

  1. 2023Deja Vu: Contextual Sparsity for Efficient LLMs at Inference Timecited by 252
  2. 2024Exploring the Frontiers of Softmax: Provable Optimization, Applications in Diffusion Model, and Beyondcited by 15
  3. 2024Differential Privacy Mechanisms in Neural Tangent Kernel Regressioncited by 14
  4. 2023An Automatic Learning Rate Schedule Algorithm for Achieving Faster Convergence and Steeper Descentcited by 9
  5. 2023Convergence of Two-Layer Regression with Nonlinear Unitscited by 6