Implicit Riemannian Optimism with Applications to Min-Max Problems

We want to thank the reviewer for their time taken revising our manuscript, as well as the appendix and the experimental section.

For online Riemannian optimization, the authors apparently remove a spurious curvature-dependent term from the upper bound in previous analyses. However, curvature-dependent terms re-appear in the time-complexity in the inner steps of their algorithm.

Note that in the online setting, the computational or gradient oracle complexity is a metric independent from the regret. That being said, in minmax and other applications, both metrics translate to computational or gradient oracle complexity, since they are multiplied to obtain the final complexity.

The implementation using our CRGD subroutine has an oracle complexity which does not introduce curvature terms, except in a mild logarithmic term. This showcases the power of CRGD when it comes to reducing the subproblem complexity. We provided the time complexity of PRGD as well, for comparison, since it is a widely used and natural subroutine, this one does have curvature terms.

It appears that the main improvement relative to previous work is the removal of pre-existing assumptions that circularly linked the curvature and the step-sizes, those being difficult to verify.

We would like to note that beyond the contribution mentioned by the reviewer we also improve in the following:

• Our method can explicitly handle bounded in-manifold constraints, which are interesting in their own right, since constraints are also critical for online optimization algorithms, even in the Euclidean setting.

• We further obtain important new results in min-max optimization.

  • Our methods reduce the computational complexity with respect to other constrained methods, it obtains a near optimal gradient oracle complexity, and does not require the knowledge of the initial distance to a solution $R$ and the Lipschitz constant $G$ (see table 2).
  • It was previously unknown if achieving our rate was possible, since in fact in g-convex and $L$-smooth minimization, nearly matching Euclidean upper bounds is impossible due to lower bounds implying an inherent hardness coming from the geometry, but we showed that the minmax problems are of a different nature.

this paper does not have experiments.

We note that as we stated in the paper, we did provide experiments in Appendix E to validate our theory, with an implementation of our method in a constrained problem setting, for an application that only one other method (RAMMA, an impractical method) could tackle before.

to implement the proposed algorithm we need to solve two optimization problems at each round, which requires multiple queries of the gradients, and it makes the setting not truly "online"

The action $\tilde{x}_t$ which RIOD chooses at time $t$ is computed based on an implicit step on the hint function $\tilde{\ell}_t$ and the loss from the previous round $\ell_{t-1}$ (this dependence is implicit via the iterate $x_{t}$). RIOD does not require the knowledge of the loss function $\ell_t$ before choosing its action. Therefore, our algorithm fits in the classical online optimization setting, which assumes that after choosing an action, the agent observes the full loss function $\ell_{t-1}$ and does not specify what the agent does with it: querying the gradient more than once is always permitted.

Note that one of the previous optimistic methods in Riemannian optimization Hu et al. (2023) also queries the gradient more than once per round.

In fact, in many other online learning settings exact minimization of the previous loss plus possibly some regularizer is assumed, and some other online learning papers studied implicit updates where several gradients are taken Kivinen & Warmuth (1997), Campolongo & Orabona (2020) Chen & Orabona (2023) with some advantages over explicit methods. Note however that no work obtained an optimistic online learning algorithm using implicit updates.

However, in this paper (i.e., lines 4 and 6 of Algorithm 1), to implement the proposed algorithm we need to solve two optimization problems at each round, which [...] [introduces] extra dependence on $L$ and $\zeta$

The error criteria of the updates in lines 4 and 6 of Algorithm 1 depend on $L$ and $\zeta$, but this only introduces a logarithmic dependence when using CRGD. In any case, the regret metric is independent of the gradient complexity so this does not imply a dependence on $L$ and $\zeta$ in the regret bounds, not even a logarithmic one.

Finally, in Corollary 2, it says that the number of implements depend on $\eta$;, so I am not sure how to set the number of implements if eta is not known (since $eta=1/sqrt{V_T}$ and $V_T$ is not known).

In general, RIOD works for any $\eta>0$ in contrast to the previous explicit optimistic methods, which require $\eta\lesssim 1/L$ (and possibly require some geometric terms in the Riemannian setting) in order to show the regret bound, that matches the OOMD Rakhlin et al. (2013). As for Rakhlin et al. (2013), in this work we do not focus on adapting for the best value of \eta. But we note that (A) we did not require this to obtain optimal convergence for smooth g-convex g-concave optimization and (B) in the general case, when $V_T$ is not known in advance, we can follow the method laid out in Theorem 3, Zhao et al, (2020), which is based on using an expert meta-algorithm, that is not dependent on the type of algorithm being run. This methods was shown to work in the Riemannian setting in Hu et al. (2023).

Since in the sub-problems, the number of iterations depend on $\zeta$, I think the final "real" regret should also depend on zeta, as the total number of iterations is not $T$ (but $T$ times the number of inner iterations).

In the online setting, the computational or gradient complexity is an independent metric from the regret, so there is no extra factor. But indeed in the minmax problem both metrics multiply in order to obtain the total gradient complexity, that yields our rates in Table 2, which contain a dependence on $\zeta$ for PRGD or RGD, but only a logarithmic factor for CRGD. This showcases the power of CRGD when it comes to reducing the subproblem complexity.

We appreciate that the reviewer found the paper well-written and valued our results in Riemannian online learning and minmax problems, overcoming several difficulties in existing work. If you now have a better opinion of our work, we kindly ask you to consider increasing your score.

Experimental results

We note that as stated in the paper, we did provide experiments in Appendix E with an implementation of our method, in a constrained problem setting, an application that only one other method (RAMMA, an impractical method) could tackle before, showing that now it is possible to efficiently solve such problems.

The Hadamard assumption is standard in the field and quite general (accelerated minimization algorithms [1], lower bounds, [2], [3], online learning [4], [5], [6], among many others [7], [8], [9], [10], [11], [12]).

The Hadamard case is challenging enough, note that besides other optimization problems listed above, 7 papers before ours study our minmax problem and none of them could achieve our parameter freeness, or working with constraints or achieving the optimal convergence rates. Similarly, for the online learning case, prior work could not achieve the optimal regret, while at the same time they had unreasonable assumptions, like some circularity between the step sizes (requiring a specific bound on the iterates a prior) and where the iterates lied.

Experiments in online learning settings would strengthen the paper

We note that the online learning setting assumes an adversarial agent generating losses against our algorithm. This means that in order to empirically validate the bound, we would need to craft a worst-case adversary to play against our algorithm. This is not only impractical, but it is also undesirable since online learning is a framework that says that we perform well with respect to the best fixed action, and so one also wants to see if it also performs well in favorable scenarios.

In the literature, typical ways of validating online learning bounds in practice are settings where losses are unpredictable, just as the landscape of min max optimization losses.

One of the main contributions emphasized by the authors is the removal of dependence on geometric constants (e.g., $\zeta$ ) from complexity bounds. Could the authors provide intuitive explanations regarding why the proposed framework successfully circumvents this geometric hurdle, whereas previous methods have not?

There are several independent factors that made our final result possible. We found that (A) implicit (proximal) approaches make the outer loop of our algorithms be free of these constants if used with optimism, as opposed to most of prior work that uses explicit methods and have to rely on the use of Riemannian Cosine-Law Inequalities introducing $\zeta$ factors (Appendix D.1). Then (B), achieving such implicit optimism requires a careful structure where losses are not linearized since the linearizations are not g-convex (unlike in the Euclidean space). Finally (C) the use of a subroutine such as CRGD as opposed to the most commonly used Riemannian Gradient Descent ones makes the inner problem be also free of these constants, up to a log factor.

The comparison presented in Table 2 clearly outlines the superiority of this work over existing methods. It would be insightful to experimentally compare the CRGD-based version and other proposed methods with some of the algorithms listed in Table 2.

We focused on showcasing that we can effectively optimize problems with in-manifold constraints, which was not possible to optimize before, except with RAMMA in Martínez-Rubio et al. (2023). While this method is of theoretical interest, as it establishes new upper bounds, it is highly complex and consists of 5 loops, making it impractical.

In line 225 (right column)...

Thanks for pointing this typo out, it should have been $\sum_{i=1}^{t}\ell_i(x) +\tilde{\ell}_t(x) + \frac{1}{2\eta}d(x_t,x)^2$.

Corollary 2 reveals that implementing the proposed framework with PRGD still introduces dependence on the geometric constant while using CRGD does not. Is the removal of geometric constants primarily due to the choice of the optimization subroutine (CRGD) rather than the proposed framework (RIOD) itself?

Note that in the online setting, the regret depends only on the cumulative cost $\sum_{t=1}^T \ell_t(x_t)$ paid for the agent's actions, and is independent of the oracle complexity. Hence, the improved regret guarantees (table 1) are independent of the oracle complexity of the optimization subroutine used to compute the actions.

The improvement in terms of the regret is achieved via our inexact implicit optimistic technique. Corollary 2 only discusses the oracle complexity of implementing the subproblems up to the specified precision, which is orthogonal to the regret. Removing the geometric constant in the subroutine is mostly due to CRGD. On the other hand, when applying our method to optimization, the complexities do multiply, making necessary to be free of these constants at both levels, but CRGD only adds a log factor.

The design of the subroutine with our implicit approach has other advantages orthogonal to the use of CRGD or any other subroutine, such as removing the need to know the initial distance a priori or the Lipschitz constant (see table 2).

We appreciate that the reviewer found the paper well-written and valued our results in Riemannian online learning and minmax problems, overcoming several difficulties in existing work. If you now have a better opinion of our work, we kindly ask you to consider increasing your score.