# Structured and Fast Optimization: The Kronecker SGD Algorithm

arXiv: https://arxiv.org/abs/2305.08001 · HTML: https://mlsanity.com/paper/2305.08001/

## 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 (most cited first, 30 of 46)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [High-Resolution Image Synthesis with Latent Diffusion Models](https://mlsanity.com/paper/2112.10752/) (2021)
- [Very Deep Convolutional Networks for Large-Scale Image Recognition](https://mlsanity.com/paper/1409.1556/) (2014)
- [Going Deeper with Convolutions](https://mlsanity.com/paper/1409.4842/) (2014)
- [XLNet: Generalized Autoregressive Pretraining for Language Understanding](https://mlsanity.com/paper/1906.08237/) (2019)
- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [Deep Compression: Compressing Deep Neural Networks with Pruning, Trained Quantization and Huffman Coding](https://mlsanity.com/paper/1510.00149/) (2015)
- [Deep contextualized word representations](https://mlsanity.com/paper/1802.05365/) (2018)
- [Learning both Weights and Connections for Efficient Neural Networks](https://mlsanity.com/paper/1506.02626/) (2015)
- [A Convergence Theory for Deep Learning via Over-Parameterization](https://mlsanity.com/paper/1811.03962/) (2018)
- [Gradient Descent Provably Optimizes Over-parameterized Neural Networks](https://mlsanity.com/paper/1810.02054/) (2018)
- [Gradient Descent Finds Global Minima of Deep Neural Networks](https://mlsanity.com/paper/1811.03804/) (2018)
- [Deep Learning Recommendation Model for Personalization and Recommendation Systems](https://mlsanity.com/paper/1906.00091/) (2019)
- [Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Data](https://mlsanity.com/paper/1808.01204/) (2018)
- [Fast Attention Requires Bounded Entries](https://mlsanity.com/paper/2302.13214/) (2023)
- [Solving Linear Programs in the Current Matrix Multiplication Time](https://mlsanity.com/paper/1810.07896/) (2018)
- [On the Convergence Rate of Training Recurrent Neural Networks](https://mlsanity.com/paper/1810.12065/) (2018)
- [Training Multi-Layer Over-Parametrized Neural Network in Subquadratic Time](https://mlsanity.com/paper/2112.07628/) (2021)
- [Quadratic Suffices for Over-parametrization via Matrix Chernoff Bound](https://mlsanity.com/paper/1906.03593/) (2019)
- [Training (Overparametrized) Neural Networks in Near-Linear Time](https://mlsanity.com/paper/2006.11648/) (2020)
- [SGD Learns the Conjugate Kernel Class of the Network](https://mlsanity.com/paper/1702.08503/) (2017)
- [Solving Empirical Risk Minimization in the Current Matrix Multiplication Time](https://mlsanity.com/paper/1905.04447/) (2019)
- [A Faster Interior Point Method for Semidefinite Programming](https://mlsanity.com/paper/2009.10217/) (2020)
- [Deep Kronecker neural networks: A general framework for neural networks with adaptive activation functions](https://mlsanity.com/paper/2105.09513/) (2021)
- [A Theoretical Analysis on Feature Learning in Neural Networks: Emergence from Inputs and Advantage over Fixed Features](https://mlsanity.com/paper/2206.01717/) (2022)
- [Attention Scheme Inspired Softmax Regression](https://mlsanity.com/paper/2304.10411/) (2023)
- [Deep Learning in Bioinformatics](https://mlsanity.com/paper/1603.06430/) (2016)
- [SLIDE : In Defense of Smart Algorithms over Hardware Acceleration for Large-Scale Deep Learning Systems](https://mlsanity.com/paper/1903.03129/) (2019)
- [An Over-parameterized Exponential Regression](https://mlsanity.com/paper/2303.16504/) (2023)

## Built on by (most cited first, 5 of 5)

- [Deja Vu: Contextual Sparsity for Efficient LLMs at Inference Time](https://mlsanity.com/paper/2310.17157/) (2023)
- [Exploring the Frontiers of Softmax: Provable Optimization, Applications in Diffusion Model, and Beyond](https://mlsanity.com/paper/2405.03251/) (2024)
- [Differential Privacy Mechanisms in Neural Tangent Kernel Regression](https://mlsanity.com/paper/2407.13621/) (2024)
- [An Automatic Learning Rate Schedule Algorithm for Achieving Faster Convergence and Steeper Descent](https://mlsanity.com/paper/2310.11291/) (2023)
- [Convergence of Two-Layer Regression with Nonlinear Units](https://mlsanity.com/paper/2308.08358/) (2023)

## 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.