Orthogonal Directions Constrained Gradient Method: from non-linear equality constraints to Stiefel manifold

Sholom Schechtman, Daniil Tiapkin, Michael Muehlebach, Éric Moulines
Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:1228-1258, 2023.

Abstract

We consider the problem of minimizing a non-convex function over a smooth manifold M. We propose a novel algorithm, the Orthogonal Directions Constrained Gradient Method (ODCGM), which only requires computing a projection onto a vector space. ODCGM is infeasible but the iterates are constantly pulled towards the manifold, ensuring the convergence of ODCGM towards M. ODCGM is much simpler to implement than the classical methods which require the computation of a retraction. Moreover, we show that ODCGM exhibits the near-optimal oracle complexities O(1/ε^{-2}) and O(1/ε^{-4}) in the deterministic and stochastic cases, respectively. Furthermore, we establish that, under an appropriate choice of the projection metric, our method recovers the landing algorithm of Ablin and Peyré (2022), a recently introduced algorithm for optimization over the Stiefel manifold. As a result, we significantly extend the analysis of Ablin and Peyré (2022), establishingnear-optimal rates both in deterministic and stochastic frameworks. Finally, we perform numerical experiments, which shows the efficiency of ODCGM in a high-dimensional setting.

Cite this Paper

BibTeX
@InProceedings{pmlr-v195-schechtman23a, title = {Orthogonal Directions Constrained Gradient Method: from non-linear equality constraints to Stiefel manifold}, author = {Schechtman, Sholom and Tiapkin, Daniil and Muehlebach, Michael and Moulines, {\'E}ric}, booktitle = {Proceedings of Thirty Sixth Conference on Learning Theory}, pages = {1228--1258}, year = {2023}, editor = {Neu, Gergely and Rosasco, Lorenzo}, volume = {195}, series = {Proceedings of Machine Learning Research}, month = {12--15 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v195/schechtman23a/schechtman23a.pdf}, url = {https://proceedings.mlr.press/v195/schechtman23a.html}, abstract = {We consider the problem of minimizing a non-convex function over a smooth manifold M. We propose a novel algorithm, the Orthogonal Directions Constrained Gradient Method (ODCGM), which only requires computing a projection onto a vector space. ODCGM is infeasible but the iterates are constantly pulled towards the manifold, ensuring the convergence of ODCGM towards M. ODCGM is much simpler to implement than the classical methods which require the computation of a retraction. Moreover, we show that ODCGM exhibits the near-optimal oracle complexities O(1/ε^{-2}) and O(1/ε^{-4}) in the deterministic and stochastic cases, respectively. Furthermore, we establish that, under an appropriate choice of the projection metric, our method recovers the landing algorithm of Ablin and Peyré (2022), a recently introduced algorithm for optimization over the Stiefel manifold. As a result, we significantly extend the analysis of Ablin and Peyré (2022), establishingnear-optimal rates both in deterministic and stochastic frameworks. Finally, we perform numerical experiments, which shows the efficiency of ODCGM in a high-dimensional setting.} }
Endnote
%0 Conference Paper %T Orthogonal Directions Constrained Gradient Method: from non-linear equality constraints to Stiefel manifold %A Sholom Schechtman %A Daniil Tiapkin %A Michael Muehlebach %A Éric Moulines %B Proceedings of Thirty Sixth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2023 %E Gergely Neu %E Lorenzo Rosasco %F pmlr-v195-schechtman23a %I PMLR %P 1228--1258 %U https://proceedings.mlr.press/v195/schechtman23a.html %V 195 %X We consider the problem of minimizing a non-convex function over a smooth manifold M. We propose a novel algorithm, the Orthogonal Directions Constrained Gradient Method (ODCGM), which only requires computing a projection onto a vector space. ODCGM is infeasible but the iterates are constantly pulled towards the manifold, ensuring the convergence of ODCGM towards M. ODCGM is much simpler to implement than the classical methods which require the computation of a retraction. Moreover, we show that ODCGM exhibits the near-optimal oracle complexities O(1/ε^{-2}) and O(1/ε^{-4}) in the deterministic and stochastic cases, respectively. Furthermore, we establish that, under an appropriate choice of the projection metric, our method recovers the landing algorithm of Ablin and Peyré (2022), a recently introduced algorithm for optimization over the Stiefel manifold. As a result, we significantly extend the analysis of Ablin and Peyré (2022), establishingnear-optimal rates both in deterministic and stochastic frameworks. Finally, we perform numerical experiments, which shows the efficiency of ODCGM in a high-dimensional setting.
APA
Schechtman, S., Tiapkin, D., Muehlebach, M. & Moulines, É.. (2023). Orthogonal Directions Constrained Gradient Method: from non-linear equality constraints to Stiefel manifold. Proceedings of Thirty Sixth Conference on Learning Theory, in Proceedings of Machine Learning Research 195:1228-1258 Available from https://proceedings.mlr.press/v195/schechtman23a.html.

Related Material