joint optimization on grassmann manifold

26 views
Skip to first unread message

grandowife

unread,
Mar 5, 2021, 12:23:00 AMMar 5
to Manopt
Hello,

I am trying to solve a joint optimization problem:
min_{W, U} f(V*;  W, U)
s.t. V*= argmin_{V} g(X; U)
The target U is required to be an element on the Grassmann manifold.

When I tried to update U with typical gradient-based update formulations, even if the derivative of the upper objective function f() w.r.t U can be obtained, its orthogonality can not be ensured. 

Do you have any suggestions to overcome this problem?
Thank you in advance.



Nicolas Boumal

unread,
Mar 5, 2021, 2:07:52 AMMar 5
to Manopt
Hello,

I'm not sure I understood the issue. If you are running a gradient step on U, and U is on the Grassmann manifold, then wouldn't the retraction enforce orthogonality?

Best,
Nicolas

grandowife

unread,
Mar 5, 2021, 2:22:47 AMMar 5
to Manopt
Hello, Mr. Boumal

I am sorry for letting you feel confused. 
My problem is to jointly optimize W and U by gradient-based algorithms (e.g., SGD).
Matrix U is required to be orthogonal and I do not put any requirement to matrix W.
To this end, I first need to calculate the derivative of the upper objective function f() w.r.t W and U.
Then, iteratively update these targets with their derivatives until converge.

However, I found it is not easy to run this process on Grassmann manifold, since there are two different objective functions (i.e. f, and, g).
And I do not know how to exactly define the 'cost' when using the solvers in the manopt.
Therefore, I failed to ensure the orthogonality of U.

Best,
Shi

Nicolas Boumal

unread,
Mar 5, 2021, 2:41:24 AMMar 5
to Manopt
Hello again,

If you have an explicit expression for V* as a function of U, and if you can differentiate that expression, then you could just substitute it in the upper objective function and reduce the problem to a standard optimization problem (albeit with a possibly rather complicated cost function).

If not (which I presume is the case), then perhaps it's easier to proceed with an alternating scheme, where you fix V*, optimize f for U, W in the usual way, then fix U, W and optimize g for V*, etc.

This seems to me not so much an issue about manifolds as it is a more general issue about bi-level optimization. I do not know much about that topic.

Best,
Nicolas

grandowife

unread,
Mar 5, 2021, 3:00:51 AMMar 5
to Manopt
It is indeed a bi-level optimization problem.
Thanks a lot.

Best,
Shi


Reply all
Reply to author
Forward
0 new messages