Open Access
- 13 September 2023
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Open Journal of Control Systems
- Vol. 2, 380-395
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 ≤ 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\ {\rm{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\ \rm{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.Keywords
Funding Information
- ONR (N00014-20-1-2394)
- MIT-IBM Watson AI Lab and MIT-IBM project on Time Series Anomaly Detection
This publication has 28 references indexed in Scilit:
- Minimizing finite sums with the stochastic average gradientMathematical Programming, 2016
- Learning non-parametric basis independent models from point queries via low-rank methodsApplied and Computational Harmonic Analysis, 2014
- Active Subspace Methods in Theory and Practice: Applications to Kriging SurfacesSIAM Journal on Scientific Computing, 2014
- Hybrid Deterministic-Stochastic Methods for Data FittingSIAM Journal on Scientific Computing, 2012
- Robust Stochastic Approximation Approach to Stochastic ProgrammingSIAM Journal on Optimization, 2009
- Approximation theory of the MLP model in neural networksActa Numerica, 1999
- Projection-Based Approximation and a Duality with Kernel MethodsThe Annals of Statistics, 1989
- A Note on the Use of Principal Components in RegressionJournal of the Royal Statistical Society Series C: Applied Statistics, 1982
- Optimal reconstruction of a function from its projectionsDuke Mathematical Journal, 1975
- Some methods of speeding up the convergence of iteration methodsUSSR Computational Mathematics and Mathematical Physics, 1964