Solving hidden monotone variational inequalities with surrogate losses

Thank you for you comments and questions, they will improve the paper. Below we have addressed all your raised concerns and look forward to your response.

Certain parts lack clarity. Condition 2 in Theorem 3.2 seems unnecessary and needs refinement. (See question and comments).

We address condition 2 in more detail below.

The paper lacks larger scale experiments. For example Deep RL experiments (with bigger underlying neural networks) could be included to demonstrate the claimed scalability of the method.

For our Mujoco RL experiments we selected a standard network architecture (2 hidden layer MLP) [3,4,5]. Our intention was not to select a small model but to demonstrate our approach in a standard Mujoco setup. However, we have included an experiment with 16 layers in stead of 2 to demonstrate the scalability of our approach, see Figure 10 in the appendix. Since in RL the bottleneck is mostly due to environment interaction we see comparable runtimes to the 2 layer experiments. Additionally the performance is similar, as expected due two-layers being sufficient.

We would also like to emphasize that the scalability of our approach highly depends on the inner-loop optimizer. Since in practice GD with a small number of steps is sufficient (as demonstrated in our experiments and previous works), the surrogate loss approach is on the same order of complexity as SGD without a surrogate.

You claim that Sakos et al. (2024) assumes bounded implicitly in their main lemma. Can you clarify which lemma, where it is assumed and which results are affected?

The set of predictions $\mathcal{Z}$ or as refered to by Sakos et al. the set of latent variables $\mathcal{X}$ is assumed to be bounded in Lemma 4, their "template inequality". More precisely, in the proof of Lemma 4 the existence of a constant $D = diam(\mathcal{X})$ (i.e. $\mathcal{X}$ is a set with bounded diameter) is used in equation B.20 in Appendix B. Lemma 4 is then used in Theorems 1,2,3,4.

The second condition on in theorem 3.2 seems to be always satisfied by setting $p=1$ and $C=\alpha/\eta$. From the proof it appears that there is an hidden dependency between $\eta$, $C$, $p$, and $\alpha$. The statement should either include such dependency or at least clarify this aspect.

Thank you for this comment, we will clarify more precisely. What we meant exactly by this condition is that $\alpha$ can be made smaller by making $\eta$ smaller. That is $\exists C, p > 0$ such that $\forall \eta > 0$ it holds $\alpha < C\eta^p$.

While the first condition is independent of $\eta$ the second one is more subtle. The example given above would not satisfy the condition since we require the inequality to hold for all $\eta$ (or more generally for all $\eta$ small enough). The intuition behind this condition is that the surrogate loss $\ell_t(\theta) = \frac{1}{2}\||g(\theta) - (g(\theta_t)-\eta F(g(\theta_t)))\||^2$ becomes easier as $\eta$ gets smaller allowing the current predictions $z_t=g(\theta_t)$ to start close to the exact PGD step $z_t^\ast$. We suspect some quasi-Newton methods may be able to take advantage of this structure and thought it to be useful to present this alternative condition on $\alpha$ as one way to quantify this.

The use of the term “gradient step” contrasts with the Variational inequality formulation where in general is not a gradient. A possible alternative could be "proximal step".

We agree that this terminology can sometimes be confusing however it is common practice to refer to the update rule $z_{t+1} = z_t - \eta F(z_t)$ as the "gradient method" in the VI context. One example is the infamous extragradient (EG) method by Korpelevich. EG is mostly used in the VI context where there may not be a "gradient." In fact, in Korpelevich's seminal paper he refers to the update above as the "gradient method" [1]. We disagree that the proximal method would be an appropriate description as it is usually meant to represent the following update rule: $z_{t+1}= z_t -\eta F(z_{t+1}).$ See for example [2].

The related work paragraph in the introduction should probably be a subsection or its name should be removed or changed.

We agree that this paragraph should be renamed, it would be more accurate and informative to specifically mention that this paragraph corresponds to surrogate losses in scalar minimization.

The PL condition is not properly defined in the main text. It could be defined close to Line 345 or at least in the appendix.

Thanks for this comment we will add the PL definition in the appendix.

Thank you for the response. I am still dubious about some parts of the submission.

What we meant exactly by this condition is that $\alpha$ can be made smaller by making $\eta$ smaller. That is $\exists C, p > 0$ such that $\forall \eta > 0$ it holds $\alpha < C\eta^p$.

Theorem 3.2 mentions at the start "there exist a stepsize $\eta$" so the condition holding for all $\eta$ is misleading. Moreover, the proposed condition seems never satisfied: for every $\alpha, C, p > 0$ there exist $\eta > 0$ such that $\alpha > C \eta^p$, for example if we take $\eta = (\alpha/(2C))^{1/p}$, then $C \eta^p = \alpha/2 < \alpha$.

From looking at the proof it seems that $\eta$ and $\alpha$ are linked and should satisfy some conditions depending on the problem, why do you not directly state those conditions in the theorem statement? Alternatively, I suggest you to remove the second condition, also because Line 830-836 in the proofs are not clear and seems that a step is missing: verifying that $\eta$ is not so small to violate the inequality $\alpha < C\eta^p$ assumed at the start of the derivation.

The set of predictions $\mathcal{Z}$ or as refered to by Sakos et al. the set of latent variables $\mathcal{X}$ is assumed to be bounded in Lemma 4, their "template inequality". More precisely, in the proof of Lemma 4 the existence of a constant...

Could you include this statement in the manuscript? I think this is subtle, while should be clear to readers.

For our Mujoco RL experiments we selected a standard network architecture (2 hidden layer MLP) [3,4,5]. Our intention was not to select a small model but to demonstrate our approach in a standard Mujoco setup. However, we have included an experiment with 16 layers in stead of 2 to demonstrate the scalability of our approach, see Figure 10 in the appendix. Since in RL the bottleneck is mostly due to environment interaction we see comparable runtimes to the 2 layer experiments. Additionally the performance is similar, as expected due two-layers being sufficient.

Thank you for providing additional experiments. However, as you also mention, this setup looks very artificial and 2 layers are already enough. I would have preferred more challenging problems really taking advantage of the larger networks, sorry for not having specified this in the review. This part remans still a minor weakness of the work.

Thank you for your review. Below we address your comments and concerns in detail. We believe surrogate losses have played an important role in modern ML such as in policy gradient methods in reinforcement learning and we are excited to bring this approach to the VI setting. Despite the limitations that we have outlined in the paper we believe our results to be an important contribution to:

1. understand why surrogate loss methods work with a small number of gradient steps
2. understand why we should or shouldn't expect them to work in the VI setting if at all

In doing so we have shown:

1. An optimizer agnostic approach to reducing VI problems to scalar minimization problems with convergence guarantees. Our approach does not assume what optimizer is used and is compatible with any deep learning optimizer. We discuss methods like Gauss-Newton to show how existing methods are a special case of our approach.
2. Provide a novel surrogate loss approach to learning value functions in RL and demonstrated a significant improvement over data efficiency when compared to TD(0), a standard approach to value learning
3. We have provided a non-trivial example to show that surrogate losses in VI problems are strictly more difficult than scalar minimization

The paper is challenging to follow, particularly in its transition from problem (1) to the construction of the surrogate model, where additional discussion would be beneficial.

We devote most of Section 2 "Surrogate Loss Background" to discuss how problem (1) is related to different examples like supervised learning and min-max problems. In this section, we also discuss the intuitions behind the surrogate approach (i.e. approximating a gradient step in the prediction space) and why this is beneficial when there is hidden structure. We also connect all of the different components in problem (1) to these applications (e.g. $g$, $\mathcal{Z}$, and $F$).

The assumptions also seem overly restrictive. For instance, while assuming convexity of the loss with respect to the model's output is reasonable for most loss functions, the assumption that the constrained domain is convex feels unnecessarily limiting, even though the authors provide a few narrow examples.

Thank you for this comment, indeed this is a restriction of our analysis as we have outlined in Section 2. However, we would like to highlight a few points regarding this assumption and believe that our results even with this assumption are an important step to extending the surrogate approach to VI problems.

• We linked to two interesting extreme cases when $\mathcal{Z}$ is convex: (1) when a linear model is used, and (2) when the model is large enough to interpolate any dataset. In fact (2) has been shown to not be so extreme where large capacity neural networks are able to interpolate random noise [2].
• We provide the first extension of surrogate methods to VI problems with convergence to the global solution of the VI. In contrast, previous works that achieved similar results are only in the scalar minimization case where they also assume the set of predictions is convex [1].
• This assumption in fact strengthens our negative result since even when $\mathcal{Z}$ is convex, divergence is possible for $\alpha<1$
  • This is surprising since $\alpha <1$ is enough for convergence in scalar minimization even without convexity of the loss or the set of predictions! This demonstrates how much more difficult it is to theoretically analyze a surrogate approach in the VI case.

Furthermore, the alpha-descent condition (5) requires closer examination, as it appears to be a stringent requirement. Specifically, it requires a single constant alpha that holds uniformly across all t

The alpha condition indeed needs to hold for all $t$, however, we believe it is actually less stringent than existing approaches that require the error $\ell_t(\theta_{t+1})-\ell_t^\ast < \epsilon$ to be bounded by a small constant $\epsilon$ across all $t$ (e.g. [1]). Our $\alpha$ descent condition provides an improvement on multiple fronts:

• The $\alpha$-descent condition is a more accurate model than just bounding the error when a moderate amount of optimization is used at each $t$ (e.g. a small number of gradient steps). In Section 4 we highlight some cases.
• We achieve convergence to the solution $z_\ast$ without assuming the errors $\||z_{t+1}-z_t^\ast\||$ to be summable or going to zero a priori, which is common even in the scalar minimization case (see the related work paragraph in Section 2 lines 146-155 for discussion).

We are happy to hear that you found our paper interesting, well-written and our contribution both original and nontrivial. We also appreciate the detailed questions and potential directions for future work. We are hoping to set a foundation for which others can build better algorithms for difficult VI problems, and are excited to see many directions that we have not considered.

I think it's very interesting that sometimes more inner loop iterations damage the performance as a whole! (I once did some empirics for boosting weak learners in RL, where I saw a similar thing that I attributed to overfitting...). Do you have any explanations/intuitions for why this could happen (ie is it a general phenomenon in surrogate learning, or an artifact of these small-scale game experiments)?

Thank you for this comment, reviewer LPnR also highlighted this observation. We also found it surprising and believe it to be important to investigate further as future work. As we mentioned to reviewer LPnR, we believe this behaviour to highly depend on the problem and might be an artifact of our small dimensional toy problems. Given our current black box treatment of the inner loop it is difficult to understand theorertically from our analysis why such a phenomenon would occur. As mentioned by reviewer LPnR, it is possible a different descent condition could explain this behaviour. On the other hand, it is also possible that the performance is explainable via the $\alpha$-descent condition but with respect to a different method that is faster than the projected gradient method.

do you suspect that there can be any theoretical insight/proofs on synthetic settings for how surrogate losses get a provable advantage in terms of number of diverse samples? Certainly one can make claims about decreasing the # of outer loop iterations, but I would be very interested if the extra regularity of your simple surrogate loss trajectory (ie the GD trajectory on $z_t$) can manifest as more efficient exploration?

In our experiments we focused on value prediction i.e. learning a value function. Where the behavioural policy used to collect the trajectories is fixed. In this case the methods used would not change the trajectories. There is some mention in [2] on how surrogate losses can affect exploration in policy gradient methods, however, in general this seems to be an open question.

would it be possible for you to do GAN training?

We think GANs are an interesting direction for future work. However, from our understanding, most GAN losses do not admit a tractable hidden monotone structure (i.e. a hidden convex-concave game). Let us provide more details. Given a disciminator $D_w$ and a generator $G_\theta$, the standard GAN minimax loss is: $\min_\theta \max_w E_{x\sim p_{data}(x)}\log D_w(x) + E_{z\sim p_z(z)}\log (1- D_w(G_\theta(x))$ which is concave with respect to the discriminator $D$ but not convex with respect to the generator function $G$ but can be seen as a convex-concave minimax loss with respect the the generated distribution $p_G$:

However, we cannot compute $\nabla_\theta E_{x'\sim p_{G_\theta}(x')}\log (1- D_w(x'))$ easily with the standard reinforce trick because it require to compute $\nabla_\theta \log p_{G_\theta}(x')$ which is not tractable for most GAN as they do not have explicit density function (which is considered to be one of their important features: https://arxiv.org/pdf/1701.00160). Thus, developping GANs that allow for a tractable surogate-based optimization leveraging their hidden convex-concave formulation is outside of the scope of this paper. Instead we decided to focus on RL applications.

Meanwhile, minimizing projected Bellman error was shown by Bersekas [1] to be a hidden smooth and strongly monotone problem, the exact setting we study in our paper. Additionally, given the constraints of a conference paper, we believe it was important to share Bertsekas' VI perspective of projected Bellman error to the deept RL community and show:

1. that it naturally allows for a surrogate approach similar to standard policy gradient methods like PPO [3]
2. draw connections to our perspective by showing it as a special case of the PHGD method and more generally using Gauss-Newton as an inner-loop optimizer. Note that the surrogate interpretations of this method as given by equation (13) is novel.

We are pleased to hear that you found our paper well-written and our contributions significant. We are hoping that our work opens the door to new methods in solving difficult modern VI problems and at the same time provides new insights to existing approaches.

Thank you for your comments and feedback. We address your comments and questions below in detail.

The empirical finding of better optimization of the inner problem not leading to better optimization of the outer loop is very interesting but unfortunately not examined in more detail. Both a more in-depth experimental investigation and a theoretical justification for this effect could strongly improve the paper, see also the questions below.

Thank you for this comment. We indeed found this surprising and interesting. However, we did not see such behaviour in our larger scale experiments where more inner loop iterations resulted in better performance (with respect to the outer loop). Similarly, for supervised learning [1] also observed that more inner steps improved performance. Therefore, this behaviour observed in our experiments may be due to the small dimensionality of the toy problems in Section 5.

Since we believe this behaviour is both instance and optimizer specific (i.e. depending on the problem and the optimizer), we believe it to be out of the scope of this paper. Our current focus and approach is optimizer agnostic -- with any optimizer being used in the inner loop. However we agree that potential insight might be possible by considering a new descent like conditions (see below).

How does that tie in with the $\alpha$-descent rule? If not a low loss value, what makes a "good" solution to the inner problem that improves convergence of the outer loop?

Since our approach has been to consider the inner loop as a black-box and we do not use any knowledge of the algorithm inside to derive our convergence guarantees, it is difficult to pinpoint how exactly this phenomenon corresponds to $\alpha$-descent. It is possible that in these examples the methods are related to $\alpha$-descent but with respect to a different method that is faster than the projected gradient method. Alternatively, as you mention, $\alpha$-descent may not be the best way to measure a good solution of the inner loop. We believe however that the $\alpha$-descent condition is a natural choice and an important starting point since it corresponds to the "gap" of the scalar loss in the inner loop that is often studied in convex or non-convex optimization. In addition, we believe that the $\alpha$-descent condition is an important step in analyzing surrogate methods since existing approaches require bounding the errors or gap by a small constant (e.g. [1]) instead of using a relative descent condition like ours. In comparison we believe our approach is a more accurate model of what is used in practice e.g. a moderate amount of gradient steps without forcing a small loss value in each inner loop (see more details below).

Has this effect also been observed in the scalar minimization case? If yes, how does it compare?

[1] did not observe this behaviour in supervised learning. [2] looked at surrogate losses for policy gradient methods in RL and showed that more gradient steps in the inner-loop can hurt performance in some environments. However, we do not know if the surrogate loss value was smaller when more steps were used since this statistic was not reported. Furthermore, the surrogate loss is stochastic and is biased, an issue not present in our small scale deterministic setting. Therefore we don't know if (1) more steps is actually better minimizing the loss like in our case or (2) if this is an issue due to bias. For more details about this bias see [1] or our Section 5.2.2.

The authors write: "In general may not be zero and so this condition cannot be verified directly, however, this condition can often be met via first-order methods for a fixed number of steps or can be approximated with." (line 171) I am wondering how practical $\alpha$-descent condition is, is it possible to verify this condition in the presented experiments in section 5?

In general without knowing $\ell_t^\ast$ it is not possible to verify the $\alpha$-descent condition directly. However, in some cases a fixed number of GD steps is sufficient to guarantee $\alpha$-descent. In Section 4 we provide some discussion on when a fixed number of inner loop gradient descent steps can be used to satisfy any $\alpha$-descent condition. In practice, surrogate methods are used with gradient descent and tuned with a fixed small number of inner loop steps (e.g. [1,2]). Currently, there are no other works or analysis even in the scalar minimization case that explain why a small number of gradient descent should suffice. We believe the $\alpha$-descent condition in this regard to be very practical as it does not require full optimization of the inner loop like other approaches (e.g. [1]).