Abstract
Several recent empirical studies demonstrate that important machine learning tasks such as training deep neural networks, exhibit a low-rank structure, where most of the variation in the loss function occurs only in 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 $\epsilon$-approximate stationary point of a p-dimensional function by first identifying $r \leq 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 $\mathcal{O}(r \log(1/\epsilon) + rp)$ and $\mathcal{O}(r/\epsilon^2 + rp)$, respectively. Therefore, when $r \ll p$, LRGD provides significant improvement over the known complexities of $\mathcal{O}(p \log(1/\epsilon))$ and $\mathcal{O}(p/\epsilon^2)$ of GD in the strongly convex and non-convex settings, respectively. Furthermore, we formally characterize the classes of exactly and approximately low-rank functions. Empirically, using real and synthetic data, LRGD provides significant gains over GD when the data has low-rank structure, and in the absence of such structure, LRGD does not degrade performance compared to GD. This suggests that LRGD could be used in practice in any setting in place of GD.
Introduction
In large-scale machine learning, the "curse of dimensionality" makes standard Gradient Descent (GD) computationally expensive. To compute a full gradient in a $p$-dimensional space, one effectively needs to perform $p$ directional derivative computations. When $p$ is in the millions, as is common in deep learning, this becomes a massive bottleneck.
However, recent empirical research suggests that the "action" in many loss functions—like those of deep neural networks—is actually low-rank. This means that while the parameter space is huge, the gradient mostly lives in a much smaller $r$-dimensional subspace ($r \ll p$). This paper introduces Low-Rank Gradient Descent (LRGD), an optimization framework that exploits this structure to reduce "oracle complexity," defined as the total number of directional derivative evaluations.
The LRGD Framework
The core logic of LRGD follows a two-step process:
- Subspace Identification: The algorithm first identifies an "active subspace" $H$ of rank $r$. It does this by sampling $r$ gradients at random points, constructing a matrix $G$, and using Singular Value Decomposition (SVD) to find the $r$ dominant directions.
- Restricted Descent: In each subsequent iteration, instead of computing a full $p$-dimensional gradient, the algorithm only computes $r$ directional derivatives along the basis of the active subspace. It then updates the model parameters only within this subspace.
Because real-world functions aren't perfectly low-rank across the entire domain, the authors introduce two practical variants:
- Iterated LRGD: Re-evaluates and updates the active subspace whenever the descent stalls, allowing the algorithm to adapt to local low-rank structures.
- Adaptive LRGD: Gradually increases the rank $r$ from 1 up to $p$ as needed, ensuring the algorithm eventually converges even if the low-rank assumption is weak.
Experimental Evaluation
The paper validates LRGD using a mix of synthetic and real-world data, including linear and logistic regression tasks, UCI Handwritten Digits, and MNIST. As illustrated in Figure 6, LRGD demonstrates superior convergence properties compared to standard GD across different data structures.
Key Results
- Theoretical Speedup: For strongly convex functions, LRGD reduces oracle complexity from $O(p \log(1/\epsilon))$ to $O(r \log(1/\epsilon) + rp)$. When $r \ll p$, the savings are massive.
- Empirical Gains: On the digits recognition task, LRGD achieved the same accuracy as standard GD but required 10 times fewer oracle calls.
- Superiority in Full-Rank Settings: Surprisingly, LRGD often outperformed GD even on full-rank synthetic data. This is because LRGD’s subspace adaptation acts as a form of acceleration, focusing computational effort on the most productive directions at any given time.
Discussion and Key Insights
- Directional Oracle Complexity: The paper shifts the metric from "number of iterations" to "number of directional derivatives," providing a more accurate measure of computational cost in high-dimensional optimization.
- The "Waterfall" Effect: In experiments, LRGD often shows a "waterfall" convergence pattern. The error drops sharply as it exhausts the progress possible in the current active subspace, then drops again once the subspace is updated.
- Robustness to Rank Mismatch: A major finding is that LRGD doesn't perform worse than GD even when the function is full-rank. Because it adapts its subspace, it can be used as a drop-in replacement for GD without a performance penalty.
- Formalizing "Low-Rank": The authors provide a rigorous mathematical definition for $(\eta, \epsilon)$-approximately low-rank functions, bridging the gap between ridge functions and general smooth functions.
Conclusion and Future Work
LRGD demonstrates that exploiting low-rank structure can significantly improve optimization efficiency. While the current focus is on deterministic gradient descent, future research directions include adapting LRGD for Stochastic Gradient Descent (SGD) and integrating these ideas into quasi-Newton or second-order methods to yield even higher efficiency.
Summary updated