# Gradient Descent for Low-Rank Functions

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 47 references that are in the map.
- First posted on arXiv 16 Jun 2022.

## Builds on (most cited first, 22 of 22)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [Prevalence of Neural Collapse during the terminal phase of deep learning training](https://mlsanity.com/paper/2008.08186/) (2020)
- [FedPAQ: A Communication-Efficient Federated Learning Method with Periodic Averaging and Quantization](https://mlsanity.com/paper/1909.13014/) (2019)
- [Empirical Analysis of the Hessian of Over-Parametrized Neural Networks](https://mlsanity.com/paper/1706.04454/) (2017)
- [Gradient Descent Happens in a Tiny Subspace](https://mlsanity.com/paper/1812.04754/) (2018)
- [Exploring Deep Neural Networks via Layer-Peeled Model: Minority Collapse in Imbalanced Training](https://mlsanity.com/paper/2101.12699/) (2021)
- [Minimizing Finite Sums with the Stochastic Average Gradient](https://mlsanity.com/paper/1309.2388/) (2013)
- [Spectral Methods for Data Science: A Statistical Perspective](https://mlsanity.com/paper/2012.08496/) (2020)
- [Limitations of Neural Collapse for Understanding Generalization in Deep Learning](https://mlsanity.com/paper/2202.08384/) (2022)
- [Lower Bounds for Finding Stationary Points II: First-Order Methods](https://mlsanity.com/paper/1711.00841/) (2017)
- [Analytic Insights into Structure and Rank of Neural Network Hessian Maps](https://mlsanity.com/paper/2106.16225/) (2021)
- [Dissecting Hessian: Understanding Common Structure of Hessian in Neural Networks](https://mlsanity.com/paper/2010.04261/) (2020)
- [Training invariances and the low-rank phenomenon: beyond linear networks](https://mlsanity.com/paper/2201.11968/) (2022)
- [Low-rank Gradient Approximation For Memory-Efficient On-device Training of Deep Neural Network](https://mlsanity.com/paper/2001.08885/) (2020)
- [Active Subspace of Neural Networks: Structural Analysis and Universal Attacks](https://mlsanity.com/paper/1910.13025/) (2019)
- [Stochastic Subspace Descent](https://mlsanity.com/paper/1904.01145/) (2019)
- [Learning Non-Parametric Basis Independent Models from Point Queries via Low-Rank Methods](https://mlsanity.com/paper/1310.1826/) (2013)
- [Federated Optimization of Smooth Loss Functions](https://mlsanity.com/paper/2201.01954/) (2022)
- [Gradient-Based Empirical Risk Minimization using Local Polynomial Regression](https://mlsanity.com/paper/2011.02522/) (2020)

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

- [Unifying Low Dimensional Spectra in Deep Learning](https://mlsanity.com/paper/2404.06106/) (2024)
- [Low Rank Optimization for Efficient Deep Learning: Making A Balance between Compact Architecture and Fast Training](https://mlsanity.com/paper/2303.13635/) (2023)
- [The Order Is The Message](https://mlsanity.com/paper/2603.25047/) (2026)

## Abstract (arXiv)

Several recent empirical studies demonstrate that important machine learning tasks, e.g., training deep neural networks, exhibit low-rank structure, where the loss function varies significantly in only a few directions of the input space. In this paper, we leverage such low-rank structure to reduce the high computational cost of canonical gradient-based methods such as gradient descent (GD). Our proposed Low-Rank Gradient Descent (LRGD) algorithm finds an ε-approximate stationary point of a p-dimensional function by first identifying r ≤ p significant directions, and then estimating the true p-dimensional gradient at every iteration by computing directional derivatives only along those r directions. We establish that the "directional oracle complexities" of LRGD for strongly convex and non-convex objective functions are O(r log(1/ε) + rp) and O(r/ε2 + rp), respectively. When r ll p, these complexities are smaller than the known complexities of O(p log(1/ε)) and O(p/ε2) of gd in the strongly convex and non-convex settings, respectively. Thus, LRGD significantly reduces the computational cost of gradient-based methods for sufficiently low-rank functions. In the course of our analysis, we also formally define and characterize the classes of exact and approximately low-rank functions.