On the equivalence of Oja’s algorithm and GROUSE

Laura Balzano
Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, PMLR 151:7014-7030, 2022.

Abstract

The analysis of streaming PCA has gained significant traction through the analysis of an early simple variant: Oja’s algorithm, which implements online projected gradient descent for the trace objective. Several other streaming PCA algorithms have been developed, each with their own performance guarantees or empirical studies, and the question arises whether there is a relationship between the algorithms. We show that the Grassmannian Rank-One Subspace Estimation (GROUSE) algorithm is indeed equivalent to Oja’s algorithm in the sense that, at each iteration, given a step size for one of the algorithms, we may construct a step size for the other algorithm that results in an identical update. This allows us to apply all results on one algorithm to the other. In particular, we have (1) better global convergence guarantees of GROUSE to the global minimizer of the PCA objective with full data; and (2) local convergence guarantees for Oja’s algorithm with incomplete or compressed data.

Cite this Paper

BibTeX
@InProceedings{pmlr-v151-balzano22a, title = { On the equivalence of Oja’s algorithm and GROUSE }, author = {Balzano, Laura}, booktitle = {Proceedings of The 25th International Conference on Artificial Intelligence and Statistics}, pages = {7014--7030}, year = {2022}, editor = {Camps-Valls, Gustau and Ruiz, Francisco J. R. and Valera, Isabel}, volume = {151}, series = {Proceedings of Machine Learning Research}, month = {28--30 Mar}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v151/balzano22a/balzano22a.pdf}, url = {https://proceedings.mlr.press/v151/balzano22a.html}, abstract = { The analysis of streaming PCA has gained significant traction through the analysis of an early simple variant: Oja’s algorithm, which implements online projected gradient descent for the trace objective. Several other streaming PCA algorithms have been developed, each with their own performance guarantees or empirical studies, and the question arises whether there is a relationship between the algorithms. We show that the Grassmannian Rank-One Subspace Estimation (GROUSE) algorithm is indeed equivalent to Oja’s algorithm in the sense that, at each iteration, given a step size for one of the algorithms, we may construct a step size for the other algorithm that results in an identical update. This allows us to apply all results on one algorithm to the other. In particular, we have (1) better global convergence guarantees of GROUSE to the global minimizer of the PCA objective with full data; and (2) local convergence guarantees for Oja’s algorithm with incomplete or compressed data. } }
Endnote
%0 Conference Paper %T On the equivalence of Oja’s algorithm and GROUSE %A Laura Balzano %B Proceedings of The 25th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2022 %E Gustau Camps-Valls %E Francisco J. R. Ruiz %E Isabel Valera %F pmlr-v151-balzano22a %I PMLR %P 7014--7030 %U https://proceedings.mlr.press/v151/balzano22a.html %V 151 %X The analysis of streaming PCA has gained significant traction through the analysis of an early simple variant: Oja’s algorithm, which implements online projected gradient descent for the trace objective. Several other streaming PCA algorithms have been developed, each with their own performance guarantees or empirical studies, and the question arises whether there is a relationship between the algorithms. We show that the Grassmannian Rank-One Subspace Estimation (GROUSE) algorithm is indeed equivalent to Oja’s algorithm in the sense that, at each iteration, given a step size for one of the algorithms, we may construct a step size for the other algorithm that results in an identical update. This allows us to apply all results on one algorithm to the other. In particular, we have (1) better global convergence guarantees of GROUSE to the global minimizer of the PCA objective with full data; and (2) local convergence guarantees for Oja’s algorithm with incomplete or compressed data.
APA
Balzano, L.. (2022). On the equivalence of Oja’s algorithm and GROUSE . Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 151:7014-7030 Available from https://proceedings.mlr.press/v151/balzano22a.html.

Related Material