Gradient descent uses memory to improve optimization in random subspaces
Gradient Descent with Stochastic Subspaces via Persistence of Memory
Machine Learning
Summary
When computers use gradient descent to find the best solutions, they often pick random directions to explore. This paper shows that keeping a kind of 'memory' or guide helps pick better directions for longer times, making the search more efficient. The authors also found a way to create this guide cheaply using the problem’s structure, especially when dealing with sparse data or mini-batches. Their work helps methods that search in random subspaces become both faster and more reliable.
What this means in practice
- •For machine learning engineers: Improve training of large-scale sparse models by using a persistent guidance vector for more efficient gradient subspace updates.
- •For distributed system engineers: Enhance distributed optimization by reducing refresh frequency of guiding vectors in random subspace descent, saving communication and computation costs.
Authors
Subhroshekhar Ghosh, Clement Z. Q. Ng, Pierre-Louis Poirion, Akiko Takeda
Abstract
Stochastic subspace methods have gained popularity as gradient descent based techniques for large scale optimisation problems, especially in distributed settings. In this paper, we introduce the technique of "persistence of memory" to greatly extend and improve the random subspace methods. To this end, we leverage a vector that is only weakly correlated with the gradient in order to provide a guiding structure to the generative process of the random subspace along which the descent is going to take place. This guidance vector may be fixed for a large number of iterations, only to be refreshed at wide intervals (on whose size we can provide guarantees in terms of problem parameters). In important machine learning settings, such as optimisation problems embodying sparsity or a minibatch structure, we show that the guidance vector can be obtained in an effective and computationally inexpensive manner by leveraging the structured properties of the problem. En route, we establish to our knowledge the first theoretical analysis of classical SSD methods for sparse functions. In a local neighbourhood of the optimum, we demonstrate an alignment phenomenon of our gradient estimates with a low-lying eigenvector of the Hessian, allowing a once-for-all computation of the guidance vector which renders the method computationally favourable even in scenarios with unstructured objectives.