Solving hidden monotone variational inequalities with surrogate losses

## Abstract

Abstract Deep learning has proven to be effective in a wide variety of loss minimization problems.
However, many applications of interest, like minimizing projected Bellman error and min-max optimization, cannot be modelled as minimizing a scalar loss function but instead correspond to solving a variational inequality (VI) problem.
This difference in setting has caused many practical challenges as naive gradient-based approaches from supervised learning tend to diverge and cycle in the VI case.
In this work, we propose a principled surrogate-based approach compatible with deep learning to solve VIs.
We show that our surrogate-based approach has three main benefits: (1) under assumptions that are realistic in practice (when hidden monotone structure is present, interpolation, and sufficient optimization of the surrogates), it guarantees convergence, (2) it provides a unifying perspective of existing methods, and (3) is amenable to existing deep learning optimizers like ADAM.
Experimentally, we demonstrate our surrogate-based approach is effective in min-max optimization and minimizing projected Bellman error. Furthermore, in the deep reinforcement learning case, we propose a novel variant of TD(0) which is more compute and sample efficient.

## 1 Introduction

Most machine learning approaches learn from data by minimizing a loss function with respect to model parameters.
Despite the lack of global convergence guarantees in deep learning, losses can often still be minimized with an appropriately tuned first-order adaptive method such as ADAM (Kingma, ).
Unfortunately, outside of scalar loss minimization, deep learning becomes more challenging: the dynamics of variational inequality (VI) problems (e.g., min-max) are often plagued with rotations and posses no efficient stationary point guarantees (Daskalakis et al., ).
Thus, the additional challenges posed by VI problems do not allow one to easily plug in existing techniques from deep learning.

We propose a practical and provably convergent algorithm for solving VI problems in deep learning.
Importantly, our approach is compatible with any black-box optimizer, including ADAM and its variants (Kingma, ), so long as they are effective at descending a scalar loss.
Our approach guarantees convergence by leveraging the hidden structure commonly found in machine learning.
More precisely, many applications admit a hidden structure corresponding to the following problem:

$$ $\displaystyle\text{find }z_{\ast}\text{ such that }\langle F(z_{\ast}),z-z_{ \ast}\rangle\geq 0\quad\forall z\in\mathcal{Z}=\operatorname{cl}\{g(\theta): \theta\in\mathbb{R}^{d}\},$ (1) $$

where the mapping $g:\mathbb{R}^{d}\to\mathcal{Z}\subseteq\mathbb{R}^{n}$ maps model parameters to model outputs, and the set $\mathcal{Z}$ encodes the closure of the set of realizable outputs from the chosen model.
Since $F$ is defined over model outputs, it will often be structured, e.g., monotone and smooth.

In order to leverage the hidden structure in VI problems, we employ surrogate losses, which have been studied in the scalar minimization case by Johnson & Zhang () and Vaswani et al. (), among others.
The surrogate loss approach has been shown to be scalable with deep learning and has been used in modern reinforcement learning policy gradient methods (Schulman et al., ; ; Abdolmaleki et al., ).
Moreover, these surrogate loss approaches have been shown to improve data efficiency in cases where evaluating $F$ is expensive like interacting with a simulator in reinforcement learning (Vaswani et al., ; Lavington et al., ).

Our approach reduces the VI in (1) to the approximate minimization of a sequence of surrogate losses $\{\ell_{t}\}_{t\in\mathbb{N}}$, which are then used to produce a sequence of parameters $\{\theta_{t}\}_{t\in\mathbb{N}}$.
To ensure convergence we propose a new $\alpha$-descent condition on $\ell_{t}$, allowing for a dynamic inner-loop that makes no assumption on how the surrogate losses are minimized, thereby allowing for any deep-learning optimizer to minimize the scalar loss $\ell_{t}$.
With our $\alpha$-descent condition we provide convergence guarantees to a solution in the space of model predictions $\{z_{t}=g(\theta_{t})\}_{t\in\mathbb{N}}\to z_{\ast}$ for a sufficiently small $\alpha$.
Our general method is summarized in Algorithm 1.

Figure: Algorithm 1 $\alpha$-descent on surrogate

In summary, we propose a novel algorithm to solve VI problems by exploiting the hidden structure of common loss functions. We demonstrate the efficacy of our method with a variety of experiments, which themselves make further connections and innovations on prior work. Our specific contributions are as follow:

- •
We provide the first extension of surrogate losses to VI problems.
We also show a clear separation in difficulty of using surrogate methods in VI problems when compared to scalar minimization; specifically, we show that divergence is possible in a strongly monotone VI problem where in contrast convergence is guaranteed in the non-convex scalar minimization case.
- •
We propose the $\mathbf{\alpha}$-descent condition with convergence guarantees.
This condition allows for global convergence while avoiding common assumptions such as enforcing errors to be summable or globally upper-bounded.
- •
Unifying perspective of pre-conditioning methods.
With our surrogate loss approach, we unify existing pre-conditioning methods  (Bertsekas, ; Mladenovic et al., ; Sakos et al., ) by showing they are equivalent to using the Gauss-Newton method as the optimizer $\mathcal{A}$ in Algorithm 1 to minimize the surrogate losses.
We demonstrate the value of this new perspective by providing natural extensions of their methods with better empirical robustness.
- •
Experimental results and new TD variants. We demonstrate the performance and versatility of surrogate loss-based optimization in a variety of VI problems. In Sections 5.1 and 5.2 we complete experiments in min-max optimization and value prediction tasks, respectively. Importantly, we propose a new data-efficient variant to TD(0) which significantly outperforms prior approaches.

## 2 Background and Related Work

##### Notation.

We use $\langle x,y\rangle=\sum_{i=1}^{n}x^{i}y^{i}$ to denote the standard inner product over $\mathbb{R}^{n}$ and $\|x\|=\sqrt{\langle x,x\rangle}$ to be the Euclidean norm.
We write $\|x\|^{2}_{\Xi}$ to mean $\langle x,\Xi x\rangle$, and $\|x\|_{\Xi}$ is a norm if and only if $\Xi$ is positive definite.
For a set $\mathcal{X}$ we denote $\operatorname{cl}\mathcal{X}$ its closure and $\operatorname{ri}\mathcal{X}$ its relative interior.
For a given set, which will be clear from context, we denote $\Pi(x)$ as the Euclidean projection of $x$ onto the set and similarly $\Pi_{\Xi}(x)$ the projection with respect to $\|x\|_{\Xi}$.
We use $\operatorname{Id}$ to denote the identity matrix.
A matrix $A$ has lower and upper bounded singular values if
there exists $\sigma_{\min},\sigma_{\max}\in(0,\infty)$ such that for any $x$ we have $\sigma_{\min}^{2}\|x\|^{2}\leq\langle x,A^{\top}Ax\rangle\leq\sigma_{\max}^{2}
\|x\|^{2}$.
If a matrix $A$ is invertible we write $A^{-1}$ otherwise we denote the pseudo-inverse as $A^{{\dagger}}$.
For a given function $g:\mathbb{R}^{d}\to\mathbb{R}^{n}$ we write $Dg(\theta)$ as its Jacobian evaluated at $\theta$.
We say $Dg$ has uniformly lower and upper bounded singular values if there is a constant upper and lower bound to the singular values of $Dg(\theta)$ for all $\theta\in\mathbb{R}^{d}$.

##### Surrogate Loss Background.

In the scalar minimization case such as supervised learning, a non-convex loss function of the form $f(g(\theta))$ is minimized where the non-convexity is due to the model parametrization as represented by the model predictions: $g(\theta)=\left[g^{1}(\theta),\cdots,g^{n}(\theta)\right]^{\top}\in\mathbb{R}^
{n}$. In supervised learning, each prediction is $z^{i}=g^{i}(\theta)=h(x_{i},\theta)$, for some feature vector $x_{i}$ and fixed model architecture $h$.
Despite the non-convexity in parameter space $\theta\in\mathbb{R}^{d}$ due to $g$, the loss function is often convex and smooth with respect to the closure of the predictions $\mathcal{Z}=\operatorname{cl}\{g(\theta):\theta\in\mathbb{R}^{d}\}$.(^1^11We consider the closure of the predictions to include cases such as softmax paramerizations, where the predictions only lie within the relative interior of the simplex but its closure includes the whole simplex.)
The optimization problem can then be reframed as a constrained optimization problem,

$$ $\displaystyle\min_{\theta}f(g(\theta))=\underset{z\in\mathcal{Z}}{\min}f(z).$ (2) $$

If $\mathcal{Z}$ is convex then projected gradient descent $z_{t+1}=\Pi(z_{t}-\eta\nabla f(z_{t}))$ is guaranteed to converge (Beck, ).
However, the projection $\Pi$ is expensive since it is with respect to the set $\mathcal{Z}\subseteq\mathbb{R}^{n}$.
In general, the model-dependent constraint $\mathcal{Z}$ may not be convex. Yet, this assumption is essential since we require convergence of the projected gradient method; we leave relaxing this assumption for future work.
Nevertheless, this assumption is satisfied in two important extreme cases, when a model is linear or with large capacity neural networks that can interpolate any dataset e.g. $\mathcal{Z}=\mathbb{R}^{n}$ (Zhang et al., ).

Beyond supervised learning, similar hidden structure exists in losses within machine learning such as: generative models and min max optimization (Gidel et al., ), robust reinforcement learning (RL) (Pinto et al., ), and minimizing projected Bellman error (Bertsekas, ).
However, in these applications the problem cannot be written as minimizing a loss and we must instead consider the VI problem (1).
For example, in the min-max case, the min and max players’ strategies may be given by two separate networks $h^{1}(\theta^{1}),h^{2}(\theta^{2})$, respectively,
with the following objective:

$$ $\displaystyle\min_{\theta^{1}}\max_{\theta^{2}}f(h^{1}(\theta^{1}),h^{2}( \theta^{2})),$ (3) $$

where $f$ is convex-concave.
Similar to (2) we can rewrite the problem in parameter space as a constrained problem with respect to model predictions but instead within the VI (1);
where $\theta=(\theta^{1},\theta^{2})$, and $g(\theta)=(h^{1}(\theta^{1}),h^{2}(\theta^{2}))$, with operator $F(z)=F(g(\theta))=[\nabla_{z^{1}}f(z^{1},z^{2}),-\nabla_{z^{2}}f(z^{1},z^{2})]
^{\top}$ where $z^{1}=h^{1}(\theta^{1})$ and $z^{2}=h^{2}(\theta^{2})$.
The solution with respect to model outputs is then equivalent to solving the constrained VI (1).
If $F$ is well-conditioned (e.g. smooth and strongly monotone) and $\mathcal{Z}$ is closed and convex, then the projected gradient method $z_{t+1}=\Pi(z_{t}-\eta F(z_{t}))$ converges to a solution $z_{\ast}$ with an appropriate stepsize $\eta$ (Facchinei & Pang, ).

To solve problems of the form (1) and take advantage of the structure given by $g$ and $F$, we extend the idea of surrogate losses (Johnson & Zhang, ; Vaswani et al., ), where parameters are selected by
descending a sequence of surrogates $\ell_{t}(\theta)$ that approximate the exact projected gradient method.
More precisely, at iteration $t$, $\theta_{t+1}$ is selected by descending the surrogate loss:

$$ $\displaystyle\ell_{t}(\theta)$ $\displaystyle=\frac{1}{2}\big{\|}g(\theta)-[g(\theta_{t})-\eta F(g(\theta_{t}) )]\big{\|}^{2}.$ (4) $$

Importantly, this loss and its gradient are easily constructed via automatic differentiation packages as a non-linear squared error loss.
Minimizing the loss exactly gives $z_{t+1}=g(\theta_{t+1})=\Pi(z_{t}-\eta F(z_{t}))$, the exact projected gradient step, and guarantees convergence of $\{z_{t}=g(\theta_{t})\}_{t\in\mathbb{N}}$ to $z_{\ast}$.

##### Related work.

The surrogate losses proposed by Johnson & Zhang () and Vaswani et al. (), apply to supervised learning and RL respectively.(^2^22We note that Johnson & Zhang () and Vaswani et al. () provide a more general loss using Bregman divergences.)
They did not study the VI case, nor do they exploit any convexity properties in the scalar minimization case.
Lavington et al. () also study the scalar minimization case and provide convergence to a neighbourhood of a global minimum of (2) and allow for stochasticity.
The neighbourhood of convergence depends on an upperbound on the errors $\epsilon_{t}=\|z_{t+1}-z_{t}^{\ast}\|$, where $z_{t}^{\ast}$ is an exact projected gradient step.
Therefore, the neighbourhood of convergence scales with the worst error $\epsilon_{t}$ across the trajectory $\{z_{t}=g(\theta_{t})\}_{t\in\mathbb{N}}$.
Shrinking the neighbourhood necessitates a double loop algorithm that might spend too much time optimizing the surrogate.
Similar results can also be found within the analysis of quasi-Fejér monotone sequences (Franci & Grammatico, ).
For example, if $z_{t}^{\ast}=T(z_{t})$ where $T$ is a contraction, then $\epsilon_{t}\to 0$ is sufficient to guarantee convergence (see Proposition A.5).

In contrast to the existing surrogate loss approaches, we propose a simple $\alpha$-descent condition on $\ell_{t}$ (Definition 2.1) that does not require all errors to be bounded or summable apriori.
This condition allows for convergence without fully minimizing $\ell_{t}$ and better models implementations in practice where a fixed number of gradient descent steps are used for each $\ell_{t}$.

###### Definition 2.1 ( $\alpha$ -descent) .

Let $\ell_{t}$ be the surrogate defined in (4) and $\ell_{t}^{\ast}=\inf_{\theta\in\mathbb{R}^{d}}\ell_{t}(\theta)$.
The trajectory $\{\theta_{t}\}_{t\in\mathbb{N}}$ satisfies the $\alpha$-descent condition if at each step $t$ the following holds

$$ $\displaystyle\ell_{t}(\theta_{t+1})-\ell_{t}^{\ast}\leq\alpha^{2}\left(\ell_{t }(\theta_{t})-\ell_{t}^{\ast}\right),\quad\alpha\in[0,1).$ (5) $$

Given the $\alpha$-descent condition we can define a general purpose algorithm (Algorithm 1).
With any black-box optimizer update $\mathcal{A}$ and a double-loop structure, we can construct a trajectory that satisfies the condition so long as $\mathcal{A}$ can effectively descend the loss $\ell_{t}$.
In general $\ell_{t}^{\ast}$ 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 $\ell_{t}^{\ast}=0$.

From a theoretical perspective, we show that the $\alpha$-descent condition guarantees the following:

$$ $\displaystyle\|z_{t+1}-z_{t}^{\ast}\|\leq\alpha\eta\|F(z_{t})-F(z_{\ast})\|,$ (6) $$

for a proof see Lemma A.2.
As expected, the errors are controlled by $\alpha$ and the stepsize $\eta$ in the surrogate. However, the error also scales with the distance to the solution if $F$ is smooth.

In the unconstrained scalar minimization case, inequality (6) is similar to the relative error condition $\|p_{t}-\nabla f(z_{t})\|\leq\alpha\|\nabla f(z_{t})\|$ used in biased gradient descent, where $p_{t}$ is the biased direction $(z_{t+1}=z_{t}-p_{t})$ (Ajalloeian & Stich, ; Drusvyatskiy & Xiao, ).
Similar to biased gradient descent, our assumption with any $\alpha<1$ is sufficient to guarantee convergence in scalar minimization with any $L$-smooth non-convex loss $f$ (see Proposition A.3).
However, for VIs, $\alpha<1$ can still lead to divergence due to possible rotations in the dynamics of $z_{t}^{\ast}$ (see Proposition 3.3).

Within the context of solving VI problems, Solodov & Svaiter () proposed a similar condition to approximate the proximal point algorithm where $z_{t}^{\ast}=z_{t}-\eta F(z_{t}^{\ast})$.(^3^33They assume $\|z_{t+1}-(z_{t}-\eta F(z_{t+1}))\|\leq\alpha\|z_{t+1}-z_{t}\|$.)
However, verifying their condition would induce an inner loop with multiple evaluations of $F$, which can be expensive in many applications such as reinforcement learning (Vaswani et al., ).
They also show that divergence is still possible under their condition unless an extra-gradient like step is performed.
Unfortunately, such a step is impractical in our setting as it requires minimizing a surrogate loss exactly.

###### Definition 2.1 ( α 𝛼 \alpha italic_α -descent) .

##### Hidden monotone problems and preconditioning methods.

In scalar minimization problems, hidden monotone structure has been studied under hidden convexity (Bach, ; Xia, ; Chancelier & De Lara, ; Fatkhullin et al., ).
In zero-sum games with hidden monotonicity, Gidel et al. () study the existence of equilibria and establish approximate min-max theorems but do not propose an algorithm to take advantage of the hidden structure.
For games that admit a hidden strictly convex-concave structure, Vlatakis-Gkaragkounis et al. () prove global convergence of continuous time gradient descent-ascent.
Similarly, Mladenovic et al. () propose natural hidden gradient dynamics (NHGD) with continuous time global convergence guarantees in hidden convex-concave games.
A more general and descritized version of NHGD was studied by Sakos et al. (), the preconditioned hidden gradient descent method (PHGD), to solve VIs of the form (1). One step of PHGD corresponds to the update:

$$ $\displaystyle\theta_{t+1}=\theta_{t}-\eta(Dg(\theta_{t})^{\top}Dg(\theta_{t})) ^{{\dagger}}Dg(\theta_{t})^{\top}F(z_{t}).$ (7) $$

PHGD and stochastic variants were also studied in the linear case by Bertsekas ().
PHGD can be viewed as a discretization of a continuous flow that guarantees $z_{t+1}=z_{t}-\eta F(z_{t})$ as $\eta\downarrow 0$ (Sakos et al., ).
Interestingly, in Section 4 we show that PHGD is also equivalent to taking one step of the Gauss-Newton method (GN) (Björck, ) on the surrogate loss.

## 3 Convergence analysis under α 𝛼 \alpha italic_α -descent on surrogate losses

In this section we provide analysis in both the deterministic and stochastic settings.
In both settings we make the following assumption on the hidden structure in the VI (1).

###### Assumption 3.1 .

In the VI (1), $\mathcal{Z}$ is convex. There exists a solution within the relative interior, $z_{\ast}\in\operatorname{ri}\mathcal{Z}$.
$F$ is both $L$-smooth $\|F(x)-F(y)\|\leq L\|x-y\|$ and $\mu$-strongly monotone $\langle F(x)-F(y),x-y\rangle\geq\mu\|x-y\|^{2}$ for any $x,y\in\mathcal{Z}$ and some $\mu>0$.

This assumption is commonly used in the VI literature to establish linear convergence of the projected gradient method $z_{t}=\Pi(z_{t}-\eta F(z_{t}))$ (Facchinei & Pang, ).
In the scalar minimization case this assumptions implies $F(z)=\nabla f(z)$ for a scalar loss function $f$ that is $\mu$-strongly-convex and $L$-smooth.
In min-max optimization with hidden structure, such as (3), Assumption (3.1) is satisfied if $f(z^{1},z^{2})$ is strongly-convex-concave and smooth (each players’ gradient is Lipschitz with respect to all players, e.g. see  Bubeck et al. ()). It corresponds to many practical cases as the losses used in machine learning applications are often strongly convex *with respect to the model predictions $z$*. note that $\mathcal{Z}$ is convex for many classes of models used in practice, e.g., linear models or models that can interpolate any noisy labels on the train set ($\mathcal{Z}=[0,1]^{n}$). The latter has been reported with large enough neural networks (Zhang et al., ) and kernels (Belkin et al., ).

###### Assumption 3.1 .

### 3.1 Convergence and divergence in the deterministic case

##### Convergence for sufficiently small α 𝛼 \alpha italic_α .

Below we provide a linear convergence result if $\alpha$ is small enough by controlling the stepsize $\eta$ in the surrogate loss $\ell_{t}$.
Note that the convergence is with respect to $z_{t}=g(\theta_{t})$ and is linear in the number of outer loop iterations of Algorithm 1.

###### Theorem 3.2 .

Let Assumption 3.1 hold. Then, there exists a fixed stepsize $\eta$ for the the surrogate losses $\{\ell_{t}\}_{t\in\mathbb{N}}$ such that the iterates $\{z_{t}=g(\theta_{t})\}_{t\in\mathbb{N}}$ produced by Algorithm 1 converge linearly to the solution $z_{\ast}$ if either of the following conditions hold:

$$ $1)\;\;\alpha<\frac{\mu}{L}\,,\qquad\text{or}\qquad 2)\;\;\alpha\leq C\eta^{p} \,,\,C,p>0.$ $$

Note that, to obtain a practical convergence rate (e.g., bounding the number of gradient computations), we need to bound the number of inner-loop steps in Algorithm 1 required to obtain the condition (5). In general, we cannot provide any global guarantee as it is well established that, in general, finding a global minima of a smooth non-convex optimization function like (4) can be intractable (Murty & Kabadi, ; Nemirovskij & Yudin, ). However, many classes of overparametrized models are known to be able to *interpolate* random labels (e.g., neural networks (Zhang et al., ), kernels (Belkin et al., ), or boosting (Bartlett et al., )) which is strong evidence that, in practice, the condition (5) can be obtained with a few gradient steps. The latter is also supported by our experiments in Section 5.

###### Theorem 3.2 .

##### Divergence with α < 1 𝛼 1 \alpha<1 italic_α < 1 .

In *non-convex* smooth scalar minimization, $\alpha<1$ is sufficient for convergence (Proposition A.3).
However, despite our strong monotonicity assumption we show that $\alpha<1$ can still give divergence in the VI setting.
This shows that $\alpha$ being small enough is not only sufficient but is necessary for convergence.
Our example demonstrates the additional challenges of using a surrogate loss in the VI setting.
Our construction uses the min-max problem $\min_{x}\max_{y}\frac{1}{2}x^{2}+xy-\frac{1}{2}y^{2}$ and showing that gradient descent-ascent on the loss $f(x,y)=xy$ satisfies the $\alpha$-descent condition with $\alpha=\nicefrac{{1}}{{\sqrt{2}}}$ but diverges for any $\eta$.

###### Proposition 3.3 .

There exists an $L$-smooth and $\mu$-strongly monotone $F$, and a sequence of iterates $\{z_{t}\}_{t\in\mathbb{N}}$ verifying the alpha descent condition with $\alpha<1$ such that $z_{t}$ diverges for any $\eta$.

###### Proposition 3.3 .

### 3.2 Unconstrained Stochastic Case

For the stochastic case we assume $\mathcal{Z}=\mathbb{R}^{n}$, the predictions can represent all of $\mathbb{R}^{n}$.
Although this assumption is strong it can be satisfied for large capacity neural networks that can interpolate any dataset.
The stochastic case is more challenging as our setup corresponds to solving VIs with bias, for which we show can diverge even in the deterministic case (Proposition 3.3).

Since $\mathcal{Z}=\mathbb{R}^{n}$, no projection is needed for $z_{t}^{\ast}$, and the minimum of the surrogate $\ell_{t}$ is the gradient step $z_{t}^{\ast}=z_{t}-\eta F(z_{t})$.
We also assume the standard setup, the possibility to generate independent and identically distributed realizations $(\xi_{1},\xi_{2},\cdots)$ of a random variable $\xi$ such that $F_{\xi}(z)$ is an unbiased estimator of $F(z)$.
For the noise, we define $\sigma^{2}=\mathbb{E}_{\xi}\left[\|F_{\xi}(z_{\ast})\|^{2}\right]$ and use the expected co-coercive assumption from  Loizou et al. ():

###### Assumption 3.4 (expected co-coercivity 4 4 4 Note that this is not exactly expected co-coercivity as defined in Loizou et al. ( 2021 ) but a direct consequence (Loizou et al., 2021 , Lemma 3.4) . ) .

$\mathbb{E}_{\xi}\left[\|F_{\xi}(z)\|^{2}\right]\leq 2L\langle F(z),z-z_{\ast}
\rangle+2\sigma^{2},$ for all $z\in\mathcal{Z}$.

Without access to the true operator $F$ in the stochastic case, a different $\alpha$-descent condition is required using the stochastic estimate $F_{\xi_{t}}(z_{t})$.
Instead of $\ell_{t}$ (4), we will use the loss $\tilde{\ell}_{t}$, an approximation of a projected stochastic gradient step, $\tilde{\ell}_{t}(\theta)=\frac{1}{2}\|g(\theta)-(g(\theta_{t})-\eta F_{\xi_{t}
}(z_{t}))\|^{2}$, or equivalently

$$ $\displaystyle\tilde{\ell}_{t}(\theta)=\frac{\eta^{2}}{2}\|F_{\xi_{t}}(z_{t})\| ^{2}+\eta\langle F_{\xi_{t}}(z_{t}),g(\theta)-g(\theta_{t})\rangle+\frac{1}{2} \|g(\theta)-g(\theta_{t})\|^{2}.$ (8) $$

In practice, minimizing $\tilde{\ell}_{t}$ exactly is impractical if $n$ is very large due to the sum of squares $\|g(\theta)-g(\theta_{t})\|^{2}$ in (8). Therefore we assume it can be minimized efficiently on expectation with an $\alpha$-expected descent condition (Definition 3.5).

###### Definition 3.5 ( $\alpha$ -expected descent) .

The trajectory $\{\theta_{t}\}_{t\in\mathbb{N}}$ is said to satisfy the $\alpha$-expected descent condition if at each step $t$ the following holds:
given the estimate $F_{\xi_{t}}(z_{t})$,
the parameter $\theta_{t+1}$ is generated such that

$$ $\mathbb{E}\left[\tilde{\ell}_{t}(\theta_{t+1})-\tilde{\ell}_{t}^{\ast}\right] \leq\alpha^{2}(\tilde{\ell}_{t}(\theta_{t})-\tilde{\ell}_{t}^{\ast}).$ $$

Similar to the deterministic case, we can prove linear convergence to a neighbourhood.

###### Theorem 3.6 .

Let $\mathcal{Z}=\mathbb{R}^{n}$, and Assumption (3.4) hold.
If $F_{\xi}(x)$ is $L$-smooth and $\eta\leq\frac{1}{2(1+c)L}$ where $c\geq 2(1+\alpha^{2})$ then any trajectory $\{\theta_{t}\}_{t\in\mathbb{N}}$
satisfying the $\alpha$-expected descent condition guarantees:

$$ $\mathbb{E}\left[\tfrac{1}{2}\|z_{t+1}-z_{\ast}\|^{2}\right]\leq\mathbb{E}\left [\tfrac{1}{2}\|z_{t}-z_{\ast}\|^{2}\right]\left(1-\eta\mu+\alpha^{2}\right)+ \eta^{2}(1+c)\sigma^{2}.$ $$

If we take $c=4$ and $\eta\leq\nicefrac{{1}}{{10L}}$ then we have convergence to a neighbourhood if $\alpha<\sqrt{\eta\mu}$.
Theorem 3.6 provides a generalization of Loizou et al. ()[Theorem 4.1] where $z_{t+1}$ follows a random biased direction $p_{t}$ that on expectation guarantees $\mathbb{E}\left[\|p_{t}-\eta F_{\xi_{t}}(z_{t})\|^{2}\right]\leq\alpha^{2}\eta
^{2}\|F_{\xi_{t}}(z_{t})\|^{2}$.
In comparison to the stochastic results of Lavington et al. (), they avoid the assumption $\mathcal{Z}=\mathbb{R}^{n}$ by using a different surrogate. However, their result only applies to scalar minimization.

###### Assumption 3.4 (expected co-coercivity 4 4 4 Note that this is not exactly expected co-coercivity as defined in Loizou et al. ( 2021 ) but a direct consequence (Loizou et al., 2021 , Lemma 3.4) . ) .

###### Definition 3.5 ( α 𝛼 \alpha italic_α -expected descent) .

###### Theorem 3.6 .

## 4 A Nonlinear Least Squares Perspective on Surrogate Minimization

The surrogate loss perspective and our $\alpha$-descent condition allows for convergence so long as the surrogate losses $\{\ell_{t}\}_{t\in\mathbb{N}}$ are sufficiently minimized.
One approach to minimizing $\ell_{t}$ is to view it as the following non-linear least-squares problem

$$ $\displaystyle\min_{\theta}f(\theta)=\min_{\theta}\frac{1}{2}\|r(\theta)\|^{2},$ (9) $$

with a residual function $r:\mathbb{R}^{d}\to\mathbb{R}^{n}$,
where $\ell_{t}(\theta)=f(\theta)$ if $r(\theta)=g(\theta)-g(\theta_{t})+\eta F(g(\theta_{t}))$.
Due to the specific structure of $f$ we can consider specialized methods such as Gauss-Newton (GN), Damped Gauss-Newton (DGN), and Levenbergh-Marquardt (LM) (Björck, ; Nocedal & Wright, ).
These methods can be viewed as quasi-Newton methods that use a linear approximation of $r$, $r(\theta)\approx r(\theta_{t})+Dr(\theta_{t})(\theta-\theta_{t})$.

The GN method is defined by the update rule $\theta_{t+1}=\theta_{t}-(Dr(\theta_{t})^{\top}Dr(\theta_{t}))^{\dagger}Dr(
\theta_{t})^{\top}r(\theta_{t})$.
GN inherits the same local quadratic convergence properties as Newton’s method
when the Hessian at the minimum $\nabla^{2}f(\theta_{\ast})\approx Dr(\theta_{\ast})^{\top}Dr(\theta_{\ast})$.
However, GN is known to struggle with highly non-linear problems, those with large residuals, or if $Dr(\theta_{t})$ is nearly rank-deficient (Björck, ).
Fortunately, the GN direction is a descent direction of $f$, the DGN method takes steps in the GN direction with a stepsize parameter $\eta_{GN}$ and converges for a sufficiently small stepsize or with line search (Björck, ).
In cases where $Dr(\theta_{t})$ is nearly rank deficient the LM method can be used.

To minimize the surrogate we can consider taking multiple steps of gradient descent (Surr-GD), DGN or LM.
Denoting $\theta_{t}^{s}$ as $s$^th intermediate step between $\theta_{t+1}$ and $\theta_{t}$ we have the following:

$$ $\displaystyle\theta_{t}^{s+1}$ $\displaystyle=\theta_{t}^{s}-\eta_{GD}Dg(\theta_{t}^{s})^{\top}(g(\theta_{t}^{ s})-g(\theta_{t})+\eta F(g(\theta_{t}))$ (Surr-GD) $\displaystyle\theta_{t}^{s+1}$ $\displaystyle=\theta_{t}^{s}-\eta_{GN}(Dg(\theta_{t}^{s})^{\top}Dg(\theta_{t}^ {s}))^{{\dagger}}Dg(\theta_{t}^{s})^{\top}(g(\theta_{t}^{s})-g(\theta_{t})+ \eta F(g(\theta_{t}))$ (DGN) $\displaystyle\theta_{t}^{s+1}$ $\displaystyle=\theta_{t}^{s}-(Dg(\theta_{t}^{s})^{\top}Dg(\theta_{t}^{s})+ \lambda\operatorname{Id})^{-1}Dg(\theta_{t}^{s})^{\top}(g(\theta_{t}^{s})-g( \theta_{t})+\eta F(g(\theta_{t})).$ (LM) $$

Note that we used the fact that $Dr(\theta)=Dg(\theta)$, and if $\eta_{GN}=1$ then DGN is the same as GN.
Also, note that one step of GN recovers exactly the PHGD method proposed by Sakos et al. ().

### 4.1 Favourable conditions for gradient descent

Several conditions allow for fast linear convergence of gradient descent for $\ell_{t}(\theta)-\ell_{t}^{\ast}$; see for example  Guille-Escuret et al. ().
Under linear convergence, $s$-steps of gradient descent guarantees $\alpha=\rho^{s}$ for some $\rho\in[0,1)$, therefore any target value of $\alpha$ is achievable in a finite number of steps that depends only logarithmically in $\alpha$.
In this section we show how assumptions used in Sakos et al. () imply two common assumptions for fast convergence of GD: the Polyak-Łojasiewicz (PL) condition (Polyak, ; Łojasiewicz, ) and $L$-smoothness.

The four assumptions made by Sakos et al. () to study the behaviour of PHGD are: (1-2) $Dg^{\top}$ has both uniformly lower bounded and upper bounded singular values, (3) each component function $g_{i}$ is $\beta$-smooth, (4) and that $\mathcal{Z}$ is bounded.(^5^55Although $\mathcal{Z}$ being bounded is not explicitly stated as an assumption it is used within the their main Lemma.)
In Proposition 4.1 we show that globally lower bounding the singular values of $Dg^{\top}$ guarantees that the composition of a PL function $f$ with $g$ is still PL.

###### Proposition 4.1 .

Assume $f$ satisfies the $\mu$-PL condition, and let $\sigma_{\min}$ be a lower bound on the singular values of $Dg(\theta)^{\top}$. Then, $f\circ g$ is $\mu\sigma^{2}_{\min}$-PL.

This implies that the surrogate loss $\ell_{t}$ is PL since $\ell_{t}=f_{t}\circ g$ where $f_{t}(z)=\nicefrac{{1}}{{2}}\|z-v_{t}\|^{2}$ is $1$-PL.
Similarly, $\ell_{t}$ can be shown to be $L$-smooth if $Dg^{\top}$ has uniformly upper bounded singular values, each $g_{i}$ is $\beta$-smooth, and $\mathcal{Z}$ is bounded (see Lemma B.1).
However, these 4 assumptions cannot hold all at once. In Prop. 4.2 we show that if the first three assumptions (1-3) hold, then $\mathcal{Z}$ is unbounded.

###### Proposition 4.2 .

If $g:\mathbb{R}^{d}\to\mathbb{R}^{n}$ is differentiable where $g_{i}$ is $\beta$-smooth and $Dg(\theta)^{\top}$ has globally lower and upper bounded singular values, then $\{g(\theta):\theta\in\mathbb{R}^{d}\}$ is unbounded.

This contradiction suggests that the lower bounded singular value assumption is strong.
Indeed, it forces the dimension of the parameter space $d$ to be larger than the dimension of the prediction space $n$, and if $g$ is linear it must be surjective $\mathcal{Z}=\mathbb{R}^{n}$.
In the case $n=d$ it enforces $Dg$ to be invertible everywhere, which is violated in important cases such as softmax.

###### Proposition 4.1 .

###### Proposition 4.2 .

## 5 Experiments

We consider min-max optimization and policy evaluation to demonstrate the behaviour and convergence of surrogate based methods with hidden monotone structure.
For min-max optimization we compare different approaches from Section 4 on two domains from Sakos et al. (): hidden matching pennies and hidden rock-paper scissors.
For RL policy evaluation we consider the problem of minimizing projected Bellman error (PBE) with linear and non-linear approximation.

### 5.1 Min-max Experiments

Figure: Figure 1: Convergence of various algorithms from Section 4 on the hidden matching pennies game. PHGD and GDA as presented in Sakos et al. () are compared against GN, DGN, LM, and GD. (left) Linear convergence to the equilbrium is observed for several methods with LM and GD outperforming the rest. (middle) Trajectories for some methods are plotted in both the parameter and prediction space. (right) The loss ratio $\ell_{t}(\theta_{t+1})/\ell_{t}(\theta_{t})$ is illustrated for the considered methods.
Refer to caption: x1.png

We compare four different approaches from Section  4: GN, DGN, LM, and Surr-GD.
Taking only one inner step for GN and Surr-GD gives PHGD and gradient descent-ascent (GDA), respectively.

Figure: Figure 2: Convergence in the hidden rps game.
Refer to caption: x2.png

##### Hidden Matching Pennies.

The hidden matching pennies game is a zero-sum game of the form (3), where each player has the parameterization $h^{i}(\theta)=\operatorname{sigmoid}(\alpha_{2}^{i}\operatorname{CELU}(\alpha^
{i}_{1}\theta))$.
The convex-concave objective $f$ is given by $f(z^{1},z^{2})=-(2z^{1}-1)(2z^{2}-1)+\frac{0.75}{2}\left((z^{1}-\nicefrac{{1}}
{{2}})^{2}+(z^{2}-\nicefrac{{1}}{{2}})^{2}\right)$.
The parameters $\alpha_{j}^{i}$ are chosen to approximately replicate the trajectory of PHGD presented in Sakos et al. (, Figure 4) (see Appendix C.1 for more details).
In Figure 1, we observe that PHGD converges linearly in the squared distance to the equilibrium, but performs poorly if multiple inner steps are taken (GN with 5 inner steps).
If $\eta$ is increased by an order of magnitude, PHGD is observed to diverge; however, convergence is possible via DGN with the same $\eta$, with multiple iterations and an appropriate choice of $\eta_{DGN}$.
In contrast to GN, LM is more stable with a larger $\eta$ and converges faster than PHGD/GN.
Finally we tested GD for a different number of inner steps with $\eta=0.1$.
Convergence is observed for GDA albeit slow.
The benefit of multiple steps is clear, with 10 inner steps outperforming PHGD and only surpassed by LM.
Although more inner steps increases the computational cost, it is marginal when compared to evaluating $F$ (see Fig. 5).
Interestingly, Fig. 1 (right) shows that spending more compute to minimize the surrogate at each iteration does not necessarily translate to faster overall convergence with respect to the outer loop (left).
GD with 10 inner steps has a larger loss ratio than GD with 100 steps but converges faster to the equilibrium.

##### Hidden rock-paper-scissors.

In the hidden rps game each player’s mixed strategy in rock-paper-scissors is parameterized.
Where player $i$’s strategy $z^{i}$ is given by the function $h^{i}(\theta)=\operatorname{softmax}(A_{2}^{i}\operatorname{CELU}(A_{1}^{i}
\theta^{i}))$, with $\theta^{i}\in\mathbb{R}^{5}$ and randomly initialized matrices: $A_{1}^{i}\in\mathbb{R}^{4\times 5}$, and $A_{2}^{i}\in\mathbb{R}^{3\times 4}$.
Figure 2 demonstrates the behaviour of various algorithms for a fixed initialization of $\theta=(\theta^{1},\theta^{2})$ and the matrices $A^{i}_{j}$.
We observe that PHGD and LM with one inner step achieve linear convergence while GDA performs poorly with an unstable behaviour.
Like in the hidden matching pennies game, increasing the number of inner steps for GD improves stability and performance, with the best performance not necessarily corresponding to the methods with the lowest loss ratio.
Both LM and GD degrade in performance if too many inner steps are taken, with one and 10 inner steps outperforming 5 and 100 steps for LM and GD respectively.

### 5.2 Minimizing Projected Bellman error

For our RL experiments we consider the policy evaluation problem of approximating a value vector $v_{\pi}\in\mathbb{R}^{n}$, representing the expected discounted return over $n$ states for a given policy $\pi$ and Markov decision process (MDP).
To this end, we consider a common approach to policy evaluation: minimizing the projected Bellman error, which is a fixed point problem associated with temporal difference learning (TD) (Sutton, ). Despite the widespread practical success of TD and its variants, the analysis and behaviour of TD has proven challenging since it cannot be modeled as a scalar minimizing problem and is known not to follow the gradient of any objective (Baird, ; Antos et al., ).
Bertsekas () showed that minimizing PBE is equivalent to solving a smooth and strongly monotone VI problem of the form (1) where $F(z)=\Xi(z-T_{\pi}(z))$ (Bertsekas, ). $T_{\pi}:\mathbb{R}^{n}\to\mathbb{R}^{n}$ is the linear Bellman policy evaluation operator defined over all $n$ states $(s^{1},\cdots,s^{n})$ in a given MDP and is defined as $T_{\pi}(z)=r_{\pi}+\gamma P_{\pi}z$,
where $r_{\pi}$ is the associated expected reward vector at each state and $P_{\pi}$ is the state to state probability transition matrix as given by the MDP and $\pi$.
$\Xi$ is the diagonal matrix with entries corresponding to the stationary distribution $\xi\in\mathbb{R}^{n}$ of states according to $\pi$.
The constraint $\mathcal{Z}$ in this case is the set of all representable value functions.
With respect to $\theta$, solving the VI associated with minimizing PBE is equivalent to finding the fixed point:

$$ $\displaystyle\theta_{\ast}\in\underset{\theta}{\arg\min}\left[BE(\theta,\theta _{\ast})=\frac{1}{2}\sum_{i=1}^{n}\xi^{i}(v_{\theta}(s^{i})-(r_{\pi}(s^{i})- \gamma\mathbb{E}_{s^{\prime}\sim P_{\pi}}\left[v_{\theta_{\ast}}(s^{\prime})|s ^{i}\right])^{2}\right],$ (10) $$

where $v_{\theta}$ is the predicted value vector given parameters $\theta$.
Notice that $BE(\theta,\theta^{\prime})$ is the surrogate loss $\nicefrac{{1}}{{2}}\|v_{\theta}-T_{\pi}(v_{\theta^{\prime}})\|^{2}_{\Xi}$.
See Appendix D for more details and background.

#### 5.2.1 Linear Approximation

Figure: Figure 3: The average approximation error between GD on the surrogate (13, Surr-GD) and the update (12) are plotted over 10,000 runs in a slow mixing 100-state Markov chain from Bertsekas () and Yu & Bertsekas (, Example 3). Surr-GD is observed to converge to the exact update (12) with faster convergence observed as the number of inner steps increase.
Refer to caption: x3.png

For our linear RL experiments, we consider a slow-mixing 100-state Markov chain from Bertsekas () and Yu & Bertsekas ().
Using a linear model, $z=g(\theta)=\Phi\theta$ with $\theta\in\mathbb{R}^{d}$, $\Phi\in\mathbb{R}^{n\times d}$ and $d\ll n$.
Bertsekas () proposed several methods to leverage the hidden structure in $F$.
Similar to Sakos et al. (), the proposed methods are presented via preconditioning schemes that approximate a projected gradient step in the space of representable value functions $\mathcal{Z}$.
Bertsekas () suggests performing the deterministic and stochastic PHGD-like updates:

$$ $\displaystyle\theta_{t+1}$ $\displaystyle=\theta_{t}-(\Phi^{\top}\Xi\Phi)^{-1}\Phi^{\top}F(z_{t}),$ (11) $\displaystyle\theta_{t+1}$ $\displaystyle=\theta_{t}-\hat{D}_{t}^{-1}(\hat{C}_{t}\theta_{t}-\hat{r}_{t}).$ (12) $$

The deterministic update is expensive, requiring the full feature matrix $\Phi$. Hence, Bertsekas () constructs an online sequence of estimators $\{\hat{D}_{t}\}_{t\in\mathbb{N}}$, $\{\hat{C}_{t}\}_{t\in\mathbb{N}}$, and $\{\hat{r}_{t}\}$ from a trajectory and suggests the stochastic update (12).

Equivalently, update (11) can be seen as one step of the generalized Gauss-Newton method (Ortega & Rheinboldt, ) on the surrogate $\ell_{t}(\theta)=\nicefrac{{1}}{{2}}\|\Phi\theta-T_{\pi}(\Phi\theta_{t})\|^{2}
_{\Xi}$.
Since the model is linear, the update is the minimizer of the surrogate, and corresponds to an exact projected gradient step in the space of value functions, which is known to be a contraction (Bertsekas, ).

Similar to the deterministic update, we show that the stochastic version can be shown to be the minimizer of a surrogate loss $\tilde{\ell}_{t}(\theta)$, whose minimizer is the exact update (12).
The stochastic surrogate $\tilde{\ell}_{t}$ and its gradient, derived in Proposition D.1, are

$$ $\displaystyle\begin{aligned} \tilde{\ell}_{t}(\theta)=\frac{1}{2}\|\Phi\theta- \hat{T}_{\pi}(z_{t})\|^{2}_{\hat{\Xi}},\end{aligned}$ $\displaystyle\begin{aligned} \nabla\tilde{\ell}_{t}(\theta)=\hat{C}_{t}\theta_ {t}-\hat{r}_{t}+\hat{D}_{t}(\theta-\theta_{t}),\end{aligned}$ (13) $$

where $\hat{\Xi}$ and $\hat{T}_{\pi}$ correspond to the natural estimators using the empirical distribution (see Appendix  D.1 for more details). Instead of minimizing the loss exactly it can be approximated with GD, thus avoiding the matrix inversion $\hat{D}^{-1}_{t}$, which can make (12) intractable.
Figure 3 demonstrates the effectiveness of approximating Bertsekas’ method (12) via GD on the surrogate $\tilde{\ell}_{t}$ (13) in a slow mixing 100-state Markov chain.

#### 5.2.2 Non-linear Projected Bellman Error

Figure: Figure 4: Comparison of average performance of TD(0) and surrogate methods in minimizing the value prediction error for RL tasks with nonlinear function approximation in Ant (top) and HalfCheetah (bottom) environments, measured by outer loop iterations (left) and wallclock time (right). The average value prediction error across 20 runs along with 95% confidence intervals are computed from a fixed test set. The red dashed line represents the lowest value prediction error achieved by any of the algorithms.
Refer to caption: x4.png

For the non-linear setting, we approximate the value function of a fixed reference policy with a two-layer neural network in two Mujoco environments, Ant and Half Cheetah (Todorov et al., ). These environments are characterized by continuous state and action spaces, where the agent must control high-dimensional, physics-based simulations to achieve locomotion tasks. The reference policy is derived by training a policy network with the soft-actor-critic algorithm (Haarnoja et al., ).
For each environment, we consider two different surrogate-based methods with TD(0) as a special case.
Similar to the linear case, we aim to find the fixed point (10), and consider the surrogate $\ell_{t}(\theta)=\nicefrac{{1}}{{2}}\|v_{\theta}-T_{\pi}(v_{\theta_{t}})\|_{
\Xi}^{2}$.
However, due to the large state spaces we must instead consider miniziming the stochastic surrogate $\tilde{\ell}_{t}$ (8) from Section 3.2.
Notice that $\tilde{\ell}_{t}$ consists of two main parts: an inner product term that is linear in $v_{\theta}=g(\theta)$, and a squared error term $\|v_{\theta}-v_{\theta_{t}}\|^{2}$.
Our two surrogate methods combine AdamW (Loshchilov, )
with two different approaches to approximate these terms.

The first method, Surr-GD, uses the same batch of data to approximate both the inner product part and the squared error term.
This fixed batch approach was proposed in Lavington et al. () for scalar minimization, and introduces bias due to approximating the squared error term across all states with a subset of states seen in the batch.
Given this approximation we perform either a fixed number of steps (denoted as inner = $\#$ steps) or an adaptive number of steps depending on a loss ratio (Thresholded Surr-GD).
Taking one gradient step recovers a batch version of TD(0), for more details see Algorithms 2, and 4.

The second method, surrogate with double sampling, uses a fixed batch to approximate the inner product term but resamples a new batch to approximate the squared error part at each gradient step.
By resampling a new batch for the squared error we have removed the bias from the first method at the cost of increased variance in the gradient.
For more details see Algorithm 3.

All methods are evaluated with value prediction error, the squared error across a test sample of states visited by a fixed reference policy.
The values in these test states are approximated by 100 Monte-Carlo roll-outs.
As shown in Figure 4, surrogate methods significantly outperformed TD(0) in both data efficiency (outer loop iterations) and wall-clock time.
Interestingly, the surrogate methods converge to a lower prediction error than TD(0), as indicated by the red dashed line being lower than TD(0)’s error curve.

Although the inner loop in the surrogate methods requires more gradient computations, the computational overhead is marginal when compared to environment interactions, a common bottleneck in RL tasks (Vaswani et al., ).
We observe that increasing the inner loop size improves data efficiency at the trade-off of a potentially slower convergence in wall-clock time.
An inner loop count, such as $50$, seems to balance both data efficiency and wall-clock time.

## 6 Conclusion

In this work we proposed a principled and scalable surrogate loss approach to solving variational inequality problems with hidden monotone structure.
We have presented a novel $\alpha$-descent condition that is optimizer agnostic and quantifies sufficient progress on the surrogate for convergence.
We have proved linear convergence in both the deterministic and stochastic settings. We have also shown that surrogate losses in VI problems are strictly more difficult to analyze than in scalar minimization.
Furthermore, we have demonstrated the generality of our approach by showing how existing methods can be viewed as special cases of our general framework.
Empirically, we have demonstrated the effectiveness of using surrogate losses in both min-max optimization and minimizing projected Bellman error. Finally, by using surrogate losses, we have proposed novel variants of TD(0) that are more data and run-time efficient in the deep reinforcement learning setting.

#### Acknowledgments

We thank Nicolas Le Roux, Iosif Sakos, Andrew Patterson, Khurram Javed, and Arushi Jain, for helpful discussions
and feedback. This work was supported by Borealis AI through the Borealis AI
Global Fellowship Award.

## Appendix A Proofs

###### Remark A.1 .

If $g$ is continuous, and $\{g(\theta):\theta\in\mathbb{R}^{d}\}$ is convex with $\mathcal{Z}$ as its closure, then the least-squares surrogate loss $\ell_{t}(\theta)=\frac{1}{2}\|g(\theta)-z_{t}+\eta F(z_{t})\|^{2}$ admits a unique point $z_{t}^{\ast}\in\mathcal{Z}$ such that

$$ $\ell_{t}^{\ast}=\frac{1}{2}\|z_{t}^{\ast}-z_{t}+\eta F(z_{t})\|^{2},$ $$

and for any $\theta$

$$ $\frac{1}{2}\|g(\theta)-z_{t}^{\ast}\|^{2}\leq\ell_{t}(\theta)-\ell_{t}^{\ast},$ $$

where $\ell_{t}^{\ast}=\inf_{\theta\in\mathbb{R}^{d}}\ell_{t}(\theta)$.

###### Proof.

Let $f(z)=\frac{1}{2}\|z-z_{t}+\eta F(z_{t})\|^{2}$ be the surrogate loss with respect to the predictions $z=g(\theta)$.
We have that $f(z)=\ell_{t}(\theta)$ for all $\theta\in\mathbb{R}^{d}$.
Now consider the set $\mathcal{Z}=\operatorname{cl}\{g(\theta):\theta\in\mathbb{R}^{d}\}$, since it is closed and convex, we have that $f$ has a unique minimum $z_{t}^{\ast}$ because it is 1-strongly convex.
Furthermore, we have

$$ $\frac{1}{2}\|z-z_{t}^{\ast}\|^{2}\leq f(z)-f(z_{t}^{\ast}).$ $$

Now since $z_{t}^{\ast}\in\mathcal{Z}$ and $\mathcal{Z}$ is the closure of $\{g(\theta):\theta\in\mathbb{R}^{d}\}$, there exists a sequence of parameters $\{\theta_{t}\}_{t\in\mathbb{N}}$ such that
$\{z_{t}=g(\theta_{t})\}_{t\in\mathbb{N}}\to z_{t}^{\ast}$.
Therefore we have that,

$$ $\displaystyle f(z_{t}^{\ast})=\lim_{t\to\infty}f(z_{t})=\lim_{t\to\infty}\ell_ {t}(\theta_{t})\geq\ell_{t}^{\ast}\geq f(z_{t}^{\ast}).$ $$

Where we have used the continuity of $f$ and $g$. The last inequality follows because $\{g(\theta):\theta\in\mathbb{R}^{d}\}\subseteq\mathcal{Z}$.
Therefore $\ell_{t}^{\ast}=f(z_{t}^{\ast})$ and the result follows.
∎

###### Lemma A.2 .

If $F$ is monotone and $z_{\ast}$ is in the relative interior of the constraint $\mathcal{Z}$, then

$$ $\ell_{t}(\theta_{t})-\ell_{t}^{\ast}\leq\frac{\eta^{2}}{2}\|F(z_{t})-F(z_{\ast })\|^{2}.$ $$

Furthermore, under the $\alpha$-descent condition (Definition 2.1) we have

$$ $\|z_{t+1}-z_{t}^{\ast}\|\leq\alpha\eta\|F(z_{t})-F(z_{\ast})\|.$ $$

###### Proof.

If $z_{\ast}$ is a solution then we have

$$ $\langle F(z_{\ast}),z-z_{\ast}\rangle\geq 0\,,\;\forall z\in\mathcal{Z}.$ $$

If $z_{\ast}$ is in the relative interior then for any $z\in\mathcal{Z}$ there exists a $\lambda>1$ such that $z^{\prime}=(1-\lambda)z+\lambda z_{\ast}\in\mathcal{Z}$ (Rockafellar, )[Theorem 6.4].
Therefore by optimality we have

$$ $\displaystyle 0$ $\displaystyle\leq\langle F(z_{\ast}),z^{\prime}-z_{\ast}\rangle=\langle F(z_{ \ast}),(1-\lambda)z+\lambda z_{\ast}-z_{\ast}\rangle=(1-\lambda)\langle F(z_{ \ast}),z-z_{\ast}\rangle\leq 0.$ $$

Where the last inequality follows from $\lambda>1$. Altogether we have

$$ $\langle F(z_{\ast}),z-z_{\ast}\rangle=0\,,\;\forall z\in\mathcal{Z}.$ $$

Moreover, as a consequence we have that for any two points $z,z^{\prime}\in\mathcal{Z}$

$$ $\langle F(z_{\ast}),z-z^{\prime}\rangle=\langle F(z_{\ast}),z-z_{\ast}\rangle+ \langle F(z_{\ast}),z_{\ast}-z^{\prime}\rangle=0.$ $$

Letting $z_{t}^{\ast}$ be the exact projected gradient step and $z_{t}=g(\theta_{t})$ the current iterate we have

$$ $\displaystyle\ell_{t}(\theta_{t})-\ell_{t}^{\ast}$ $\displaystyle=\frac{1}{2}\|\eta F(z_{t})\|^{2}-\left(\frac{1}{2}\|z_{t}^{\ast} -z_{t}+\eta F(z_{t})\|^{2}\right)$ $\displaystyle=\eta\langle F(z_{t}),z_{t}-z_{t}^{\ast}\rangle-\frac{1}{2}\|z_{t }^{\ast}-z_{t}\|^{2}$ $\displaystyle=\eta\langle F(z_{t})-F(z_{\ast}),z_{t}-z_{t}^{\ast}\rangle+\eta \langle F(z_{\ast}),z_{t}-z_{t}^{\ast}\rangle-\frac{1}{2}\|z_{t}^{\ast}-z_{t} \|^{2}$ $\displaystyle=\eta\langle F(z_{t})-F(z_{\ast}),z_{t}-z_{t}^{\ast}\rangle-\frac {1}{2}\|z_{t}^{\ast}-z_{t}\|^{2}$ $\displaystyle\leq\frac{\eta^{2}}{2}\|F(z_{t})-F(z_{\ast})\|^{2}.$ $$

Where the last two inequalities follow by: $z_{\ast}$ being within the relative interior, and the inequality $\langle u,v\rangle\leq\frac{\rho}{2}\|u\|^{2}+\frac{1}{2\rho}\|v\|^{2}$ for any $\rho>0$.

By Remark A.1 and the $\alpha$-decent condition,

$$ $\frac{1}{2}\|z_{t+1}-z_{t}^{\ast}\|^{2}\leq\ell_{t}(\theta_{t+1})-\ell_{t}^{ \ast}\leq\alpha^{2}(\ell_{t}(\theta_{t})-\ell_{t}^{\ast})\leq\alpha^{2}\frac{ \eta^{2}}{2}\|F(z_{t})-F(z_{\ast})\|^{2}.$ $$

∎

###### Proposition A.3 .

Let $f:\mathbb{R}^{n}\to\mathbb{R}$ be $L$-smooth.
For some $g:\mathbb{R}^{d}\to\mathbb{R}^{n}$ define the surrogate loss $\ell_{t}(\theta)=\frac{1}{2}\|g(\theta)-z_{t}+\frac{1}{L}\nabla f(z_{t})\|^{2}$,
where $z_{t}=g(\theta_{t})$.
Then the $\alpha$-descent condition (Definition 2.1) guarantees

$$ $f(z_{t+1})\leq f(z_{t})-L(1-\alpha^{2})(\ell_{t}(\theta_{t})-\ell_{t}^{\ast}).$ $$

If $f$ is bounded below then $\{z_{t}-z_{t}^{\ast}\}_{t\in\mathbb{N}}\to 0$, where $z_{t}^{\ast}=\Pi(z_{t}-\frac{1}{L}\nabla f(z_{t}))$.

###### Proof.

Let $\hat{z_{t}}=z_{t}-\frac{1}{L}\nabla f(z_{t})$.

$$ $\displaystyle f(z_{t+1})-f(z_{t})$ $\displaystyle\leq\langle\nabla f(z_{t}),z_{t+1}-z_{t}\rangle+\frac{L}{2}\|z_{t +1}-z_{t}\|^{2}$ $\displaystyle=L\langle z_{t}-\hat{z}_{t},z_{t+1}-z_{t}\rangle+\frac{L}{2}\|z_{ t+1}-z_{t}\|^{2}$ $\displaystyle=L\left(-\|\hat{z}_{t}-z_{t}\|^{2}+\langle z_{t}-\hat{z}_{t},z_{t +1}-\hat{z}_{t}\rangle+\frac{1}{2}\|z_{t+1}-z_{t}\|^{2}\right)$ $\displaystyle=L\left(\frac{1}{2}\|\hat{z}_{t}-z_{t+1}\|^{2}-\frac{1}{2}\|\hat{ z}_{t}-z_{t}\|^{2}\right)$ $\displaystyle=L\left(\ell_{t}(\theta_{t+1})-\ell_{t}(\theta_{t})\right).$ $$

The second to last equality follows from expanding $\frac{1}{2}\|z_{t+1}-z_{t}\|^{2}=\frac{1}{2}\|z_{t+1}-\hat{z}_{t}+\hat{z}_{t}-
z_{t}\|^{2}$.
Using the $\alpha$-descent condition we have

$$ $\ell_{t}(\theta_{t+1})-\ell_{t}(\theta_{t})\leq(\alpha^{2}-1)(\ell_{t}(\theta_ {t})-\ell_{t}^{\ast}),$ $$

yielding the first result.

If $f$ is bounded below by some constant $c$ then we have:

$$ $\displaystyle\sum_{t=1}^{T}L(1-\alpha^{2})(\ell_{t}(\theta_{t})-\ell_{t}^{\ast })\leq f(z_{1})-f(z_{T})\leq f(z_{1})-c.$ $$

Therefore the series $\sum_{t=1}^{\infty}\ell_{t}(\theta_{t})-\ell_{t}^{\ast}$ converges with $\ell_{t}(\theta_{t})-\ell_{t}^{\ast}\to 0$.
By Remark A.1 we have $\frac{1}{2}\|z_{t}-z_{t}^{\ast}\|^{2}\leq\ell_{t}(\theta_{t})-\ell_{t}^{\ast}$ implying the result $z_{t}-z_{t}^{\ast}\to 0$.
∎

###### Theorem 3.2 .

Let Assumption 3.1 hold, then there exists a fixed stepsize $\eta$ for the the surrogate losses $\{\ell_{t}\}_{t\in\mathbb{N}}$ such that the iterates $\{z_{t}=g(\theta_{t})\}_{t\in\mathbb{N}}$ produced by Algorithm 1 converge linearly to the solution $z_{\ast}$ if either of the following conditions hold:

$$ $1)\;\;\alpha<\frac{\mu}{L}\,,\qquad\text{or}\qquad 2)\;\;\alpha\leq C\eta^{p} \,,\,C,p>0.$ $$

###### Proof.

First note that by definition of Algorithm 1, the iterates ${z_{t}=g(\theta_{t})}_{t\in\mathbb{N}}$ satisfy the $\alpha$-descent property (Definition 2.1), therefore Lemma A.2 holds.
Recall that $z_{t}^{\ast}$, the exact projection update, is a contraction if $\eta<\frac{2\mu}{L}$ since

$$ $\|z_{t}^{\ast}-z_{\ast}\|^{2}\leq\kappa^{2}\|z_{t}-z_{\ast}\|^{2}$ (14) $$

where $\kappa^{2}=1-2\eta\mu+\eta^{2}L^{2}$(Facchinei & Pang, , Theorem 12.1.2).
For the remainder, assume that $\eta<\frac{2\mu}{L}$ so that $\kappa\in[0,1)$.
Denoting $F_{t}=F(z_{t})$ and $F_{\ast}=F(z_{\ast})$, we have

$$ $\displaystyle\|z_{t+1}-z_{\ast}\|^{2}$ $\displaystyle=\|z_{t}^{\ast}-z_{\ast}+z_{t+1}-z_{t}^{\ast}\|^{2}$ $\displaystyle=\|z_{t}^{\ast}-z_{\ast}\|^{2}+2\langle z_{t+1}-z_{t}^{\ast},z_{t }^{\ast}-z_{\ast}\rangle+\|z_{t+1}-z_{t}^{\ast}\|^{2}$ $\displaystyle\leq\|z_{t}^{\ast}-z_{\ast}\|^{2}+2\|z_{t+1}-z_{t}^{\ast}\|\|z_{t }^{\ast}-z_{\ast}\|+\|z_{t+1}-z_{t}^{\ast}\|^{2}\qquad\qquad\text{(Cauchy– Schwarz)}$ $\displaystyle\leq\|z_{t}^{\ast}-z_{\ast}\|^{2}+2\alpha\eta\kappa\|F_{t}-F_{ \ast}\|\|z_{t}-z_{\ast}\|+\alpha^{2}\eta^{2}\|F_{t}-F_{\ast}\|^{2}\qquad\qquad \text{(Lemma~{}\ref{thm:bias})}$ $\displaystyle\leq\|z_{t}^{\ast}-z_{\ast}\|^{2}+2\alpha\eta L\|z_{t}-z_{\ast}\| ^{2}+\alpha^{2}\eta^{2}L^{2}\|z_{t}-z_{\ast}\|^{2}\;\;\text{(Smoothness of $F$ and $\kappa<1$)}$ $\displaystyle\leq\kappa^{2}\|z_{t}-z_{\ast}\|^{2}+2\alpha\eta L\|z_{t}-z_{\ast }\|^{2}+\alpha^{2}\eta^{2}L^{2}\|z_{t}-z_{\ast}\|^{2}\qquad\qquad\qquad\qquad \;\,\text{(Eq.~{}\ref{eq:proj:contract})}$ $\displaystyle=\|z_{t}-z_{\ast}\|^{2}\left(1-2\eta\mu+2\alpha\eta L+(1+\alpha^{ 2})\eta^{2}L^{2}\right).$ $$

If $\alpha<\frac{\mu}{L}$ then

$$ $\displaystyle\|z_{t+1}-z_{\ast}\|^{2}\leq\|z_{t}-z_{\ast}\|^{2}\left(1-2\eta \underbrace{(\mu-\alpha L)}_{>0}+(1+\alpha^{2})\eta^{2}L^{2}\right).$ $$

Taking $\eta<\frac{2(\mu-\alpha L)}{(1+\alpha^{2})L^{2}}$ would guarantee a contraction.

If $\alpha\leq C\eta^{p}$,
we require

$$ $\displaystyle 1-2\eta\mu+2C\eta^{1+p}L+\eta^{2}L^{2}+C\eta^{2p+2}L^{2}<1$ $\displaystyle\Leftrightarrow\,$ $\displaystyle 2C\eta^{1+p}L+\eta^{2}L^{2}+C\eta^{2p+2}L^{2}<2\eta\mu$ $\displaystyle\Leftrightarrow\,$ $\displaystyle 2C\eta^{p}L+\eta L^{2}+C\eta^{2p+1}L^{2}<2\mu,$ $$

which holds for sufficiently small $\eta$.
∎

###### Proposition A.5 .

Take $\theta_{t+1}$ to be an approximate minima of $\ell_{t}(\theta)$.
Suppose $T=\Pi\circ(\operatorname{Id}-\eta F)$ is a contraction, if $\ell_{t}(\theta_{t+1})-\ell_{t}^{\ast}\to 0$ then the induced sequence $\{z_{t}=g(\theta_{t})\}_{t\in\mathbb{N}}$ converges, $z_{t}\to z_{\ast}$ where $z_{\ast}$ is the unique solution to $\operatorname{VI}(\mathcal{Z},F)$.

###### Proof.

Let $\epsilon_{t}=z_{t+1}-z_{t}^{\ast}$ be the approximation error between $z_{t+1}$ and $z_{t}^{\ast}$ the minimum of the surrogate $\ell_{t}$ (exact projected gradient step).

$$ $\displaystyle\frac{1}{2}\|z_{t+1}-z_{\ast}\|^{2}$ $\displaystyle=\frac{1}{2}\|z_{t}^{\ast}-z_{\ast}+\epsilon_{t}\|^{2}$ $\displaystyle=\frac{1}{2}\|z_{t}^{\ast}-z_{\ast}\|^{2}+\langle z_{t}^{\ast}-z_ {\ast},\epsilon_{t}\rangle+\frac{1}{2}\|\epsilon_{t}\|^{2}$ $\displaystyle{\leq}\frac{1}{2}\|z_{t}^{\ast}-z_{\ast}\|^{2}+\frac{\rho}{2}\|z_ {t}^{\ast}-z_{\ast}\|^{2}+\frac{1}{2\rho}\|\epsilon_{t}\|^{2}+\frac{1}{2}\| \epsilon_{t}\|^{2}$ $\displaystyle{\leq}\frac{\kappa(1+\rho)}{2}\|z_{t}-z_{\ast}\|^{2}+(1+\frac{1}{ \rho})(\ell_{t}(\theta_{t+1})-\ell_{t}^{\ast}).$ $$

Where we use the fact that $\frac{1}{2}\|\epsilon_{t}\|^{2}=\frac{1}{2}\|z_{t+1}-z_{t}^{\ast}\|^{2}\leq
\ell_{t}(\theta_{t+1})-\ell_{t}^{\ast}$ from Remark A.1.
Take any $\rho$ such that $\kappa(1+\rho)<1$ then apply Lemma 3.9 in Franci & Grammatico ().
∎

###### Proposition 3.3 .

There exists an $L$-smooth and $\mu$-strongly monotone $F$, and a sequence of iterates $\{z_{t}\}_{t\in\mathbb{N}}$ verifying the alpha descent condition with $\alpha<1$ such that $z_{t}$ diverges for any $\eta$.

###### Proof.

Let us consider the simple min max example with loss

$$ $\min_{x}\max_{y}\frac{1}{2}x^{2}+xy-\frac{1}{2}y^{2}.$ $$

This problem can be written as VIP where $z=(x,y)$ and the operator $F$ is linear given by the matrix

$$ $F=\begin{bmatrix}1&1\\ -1&1\end{bmatrix}.$ $$

It is well-known that $F$ is both smooth and strongly monotone with $z_{t+1}=z_{t}-\eta F(z_{t})$ being a contraction for small enough $\eta$ (Facchinei & Pang, ).
Now if we consider a biased direction given by a matrix $P$, that is $z_{t+1}=z_{t}-Pz_{t}$, then using the fact that $\ell_{t}^{\ast}=0$ the $\alpha$-descent on the surrogate corresponds to the following bound

$$ $\displaystyle\|z_{t+1}-z_{t}+\eta Fz_{t}\|=\|(\eta F-P)z_{t}\|\leq\alpha\|\eta Fz _{t}\|.$ $$

Despite being a contraction when we follow the true gradient $F$, the above min max loss causes rotations in the dynamics that are inherent to the adversarial nature of the problem. These rotations are carefully controlled by the stepsize and strong convexity/concavity of the loss.
Our counterexample simply adds a bit of rotation that ensures $\alpha<1$ but yet is detrimental to the convergence.
Mathematically, we take $P=(\operatorname{Id}-\alpha Q)\eta F$ where $Q$ is the rotation matrix

$$ $Q=\begin{bmatrix}\frac{1}{\sqrt{2}}&-\frac{1}{\sqrt{2}}\\ \frac{1}{\sqrt{2}}&\frac{1}{\sqrt{2}}.\end{bmatrix}$ $$

With this construction we are guaranteed that $\alpha<1$ since

$$ $\displaystyle\|(\eta F-P)z_{t}\|=\|\alpha Q\eta Fz_{t}\|=\alpha\eta\|Fz_{t}\|,$ $$

where the last equality is due the the fact that $Q$ is an orthogonal matrix and therefore does not change the Euclidean norm of a vector.

Now taking $\alpha=\nicefrac{{1}}{{\sqrt{2}}}$ gives

$$ $\displaystyle P$ $\displaystyle=\left(\operatorname{Id}-\alpha\begin{bmatrix}\frac{1}{\sqrt{2}}& -\frac{1}{\sqrt{2}}\\ \frac{1}{\sqrt{2}}&\frac{1}{\sqrt{2}}\end{bmatrix}\right)\begin{bmatrix}\eta& \eta\\ -\eta&\eta\end{bmatrix}.$ $\displaystyle=\begin{bmatrix}\frac{1}{2}&\frac{1}{2}\\ -\frac{1}{2}&\frac{1}{2}\end{bmatrix}\begin{bmatrix}\eta&\eta\\ -\eta&\eta\end{bmatrix}=\begin{bmatrix}0&\eta\\ -\eta&0.\end{bmatrix}$ $$

We have that $z_{t+1}=z_{t}-Pz_{t}=\begin{bmatrix}1&-\eta\\
\eta&1\end{bmatrix}z_{t}$ has an $\alpha=\nicefrac{{1}}{{\sqrt{2}}}$ but yet diverges for any $\eta>0$ since the Eigenvalues of the linear system are $\lambda=1\pm i\eta$ therefore the spectral radius is strictly greater than one.
Note that these dynamics are equivalent to gradient descent ascent on the bilinear loss $f(x,y)=xy$, which is known to diverge for any stepsize.

∎

###### Theorem 3.6 .

Let $\mathcal{Z}=\mathbb{R}^{n}$, and Assumption (3.4) hold.
If $F_{\xi}(x)$ is $L$-smooth and $\eta\leq\frac{1}{2(1+c)L}$ where $c\geq 2(1+\alpha^{2})$ then any trajectory $\{\theta_{t}\}_{t\in\mathbb{N}}$
satisfying the $\alpha$-expected descent condition guarantees:

$$ $\mathbb{E}\left[\tfrac{1}{2}\|z_{t+1}-z_{\ast}\|^{2}\right]\leq\mathbb{E}\left [\tfrac{1}{2}\|z_{t}-z_{\ast}\|^{2}\right]\left(1-\eta\mu+\alpha^{2}\right)+ \eta^{2}(1+c)\sigma^{2}.$ $$

###### Proof.

For convenience let $F_{\xi_{t}}(z_{t})=\hat{F}_{t}$.
Let $z_{t}^{\ast}=z_{t}-\eta\hat{F}_{t}$ and $p_{t}=z_{t}-z_{t+1}$, $\mathbb{E}_{\theta_{t+1}}\left[\cdot\right]$ denote the expectation over $z_{t+1}=g(\theta_{t+1})$ given $z_{t}$, and $\xi_{t}$.
The expected $\alpha$-descent condition in the unconstrained case is equivalent to

$$ $\mathbb{E}_{\theta_{t+1}}\left[\|z_{t+1}-z_{t}+\eta\hat{F}_{t}\|^{2}\right] \leq\alpha^{2}\eta^{2}\|\hat{F}_{t}\|^{2}.$ $$

By concavity of the square root and the expected $\alpha$-descent condition we have $\mathbb{E}\left[\sqrt{X}\right]\leq\sqrt{\mathbb{E}\left[X\right]}$ and

$$ $\displaystyle\mathbb{E}_{\theta_{t+1}}\left[\|z_{t+1}-z_{t}+\eta\hat{F}_{t}\|\right]$ $\displaystyle=\mathbb{E}_{\theta_{t+1}}\left[\sqrt{\|z_{t+1}-z_{t}+\eta\hat{F} _{t}\|^{2}}\right]$ (15) $\displaystyle\leq\sqrt{\mathbb{E}\left[\|z_{t+1}-z_{t}+\eta\hat{F}_{t}\|^{2} \right]}$ (16) $\displaystyle\leq\alpha\eta\|\hat{F}_{t}\|.$ (17) $$

We also have the following bound

$$ $\displaystyle\mathbb{E}_{\theta_{t+1}}\left[\|z_{t+1}-z_{t}\|^{2}\right]$ $\displaystyle=\mathbb{E}_{\theta_{t+1}}\left[\|z_{t+1}-z_{t}+\eta\hat{F}_{t}- \eta\hat{F}_{t}\|^{2}\right]$ (18) $\displaystyle\leq\mathbb{E}_{\theta_{t+1}}\left[2\|z_{t+1}-z_{t}+\eta\hat{F}_{ t}\|^{2}+2\|\eta\hat{F}_{t}\|^{2}\right]$ (19) $\displaystyle\leq 2(1+\alpha^{2})\eta^{2}\|\hat{F}_{t}\|^{2}.$ (20) $$

Next we expand and bound the distance $\frac{1}{2}\|z_{t+1}-z_{\ast}\|^{2}$.

$$ $\displaystyle\frac{1}{2}\|z_{t+1}-z_{\ast}\|^{2}$ $\displaystyle=\frac{1}{2}\|z_{t}-p_{t}-z_{\ast}\|^{2}$ $\displaystyle=\frac{1}{2}\|z_{t}-z_{\ast}\|^{2}-\langle p_{t},z_{t}-z_{\ast} \rangle+\frac{1}{2}\|p_{t}\|^{2}$ $\displaystyle=\frac{1}{2}\|z_{t}-z_{\ast}\|^{2}-\eta\langle\hat{F}_{t},z_{t}-z _{\ast}\rangle+\langle\eta\hat{F}_{t}-p_{t},z_{t}-z_{\ast}\rangle+\frac{1}{2} \|p_{t}\|^{2}$ $\displaystyle\leq\frac{1}{2}\|z_{t}-z_{\ast}\|^{2}-\eta\langle\hat{F}_{t},z_{t }-z_{\ast}\rangle+\|\eta\hat{F}_{t}-p_{t}\|\|z_{t}-z_{\ast}\|+\frac{1}{2}\|p_{ t}\|^{2}$ $\displaystyle=\frac{1}{2}\|z_{t}-z_{\ast}\|^{2}-\eta\langle\hat{F}_{t},z_{t}-z _{\ast}\rangle+\|z_{t+1}-z_{t}+\eta\hat{F}_{t}\|\|z_{t}-z_{\ast}\|+\frac{1}{2} \|z_{t+1}-z_{t}\|^{2}$ $$

Taking an expectation over $z_{t+1}$ given $z_{t}$, and $\xi_{t}$ we have

$$ $\displaystyle\mathbb{E}_{\theta_{t+1}}\left[\frac{1}{2}\|z_{t+1}-z_{\ast}\|^{2 }\right]$ $\displaystyle{\leq}\frac{1}{2}\|z_{t}-z_{\ast}\|^{2}-\eta\langle\hat{F}_{t},z_ {t}-z_{\ast}\rangle+\eta\alpha\|\hat{F}_{t}\|\|z_{t}-z_{\ast}\|+\frac{2(1+ \alpha^{2})\eta^{2}}{2}\|\hat{F}_{t}\|^{2}$ $\displaystyle\leq\frac{1}{2}\|z_{t}-z_{\ast}\|^{2}-\eta\langle\hat{F}_{t},z_{t }-z_{\ast}\rangle+\eta\alpha\|\hat{F}_{t}\|\|z_{t}-z_{\ast}\|+\frac{c\eta^{2}} {2}\|\hat{F}_{t}\|^{2}$ $\displaystyle\leq\frac{1}{2}\|z_{t}-z_{\ast}\|^{2}-\eta\langle\hat{F}_{t},z_{t }-z_{\ast}\rangle+\frac{\alpha^{2}}{2}\|z_{t}-z_{\ast}\|^{2}+\frac{\eta^{2}(1+ c)}{2}\|\hat{F}_{t}\|^{2}$ $$

where in the inequality we used (17, 20) and in the second inequality $c\geq 2(1+\alpha^{2})$.
Taking an expectation given information up to time $t$ and using the expected co-coercivity assumption gives,

$$ $\displaystyle\mathbb{E}_{t}\left[\frac{1}{2}\|z_{t+1}-z_{\ast}\|^{2}\right]$ $\displaystyle\leq\frac{1}{2}\|z_{t}-z_{\ast}\|^{2}-\eta\langle F_{t},z_{t}-z_{ \ast}\rangle+\frac{\alpha^{2}}{2}\|z_{t}-z_{\ast}\|^{2}+\frac{\eta^{2}(1+c)}{2 }\mathbb{E}_{t}\left[\|\hat{F}_{t}\|^{2}\right]$ $\displaystyle{\leq}\frac{1}{2}\|z_{t}-z_{\ast}\|^{2}-\eta\langle F_{t},z_{t}-z _{\ast}\rangle+\frac{\alpha^{2}}{2}\|z_{t}-z_{\ast}\|^{2}+\eta^{2}(1+c)L \langle F_{t},z_{t}-z_{\ast}\rangle+\eta^{2}(1+c)\sigma^{2}$ $\displaystyle=\frac{1}{2}\|z_{t}-z_{\ast}\|^{2}-\eta\left(1-\eta(1+c)L\right) \langle F_{t},z_{t}-z_{\ast}\rangle+\frac{\alpha^{2}}{2}\|z_{t}-z_{\ast}\|^{2} +\eta^{2}(1+c)\sigma^{2}$ $\displaystyle{\leq}\frac{1}{2}\|z_{t}-z_{\ast}\|^{2}-\eta\mu\left(1-\eta(1+c)L \right)\|z_{t}-z_{\ast}\|^{2}+\frac{\alpha^{2}}{2}\|z_{t}-z_{\ast}\|^{2}+\eta^ {2}(1+c)\sigma^{2}$ $$

If we take $\eta<\frac{1}{2(1+c)L}$ then we have the following recursion

$$ $\mathbb{E}_{t}\left[\frac{1}{2}\|z_{t+1}-z_{\ast}\|^{2}\right]\leq\frac{1}{2} \|z_{t}-z_{\ast}\|^{2}\left(1-\eta\mu+\alpha^{2}\right)+\eta^{2}(1+c)\sigma^{2}.$ $$

Taking an expectation over $z_{t}$ gives the result.
∎

###### Remark A.1 .

###### Proof.

###### Lemma A.2 .

###### Proof.

###### Proposition A.3 .

###### Proof.

###### Theorem 3.2 .

###### Proof.

###### Proposition A.5 .

###### Proof.

###### Proposition 3.3 .

###### Proof.

###### Theorem 3.6 .

###### Proof.

## Appendix B Non-linear least-squares

###### Lemma B.1 .

Let $f(\theta)=\frac{1}{2}\|r(\theta)\|^{2}$ where $r:\mathbb{R}^{d}\to\mathbb{R}^{n}$, $r(\theta)=(r_{i}(\theta),\cdots,r_{n}(\theta))^{\top}$.
Suppose $r_{i}(\theta)$ is $\beta$-smooth and $Dr(\theta)^{\top}$ has singular values that are globally upper bounded by $\sigma_{\max}>0$.
If $r$ is bounded, then $f$ is $L$-smooth: there exists $L\geq 0$ such that $\|\nabla f(\theta)-\nabla f(\theta^{\prime})\|\leq L\|\theta-\theta^{\prime}\|$ for any $\theta,\theta^{\prime}\in\mathbb{R}^{d}$.

###### Proof.

Since each $r_{i}$ is $\beta$-smooth we have that

$$ $\displaystyle\|Dr(\theta)^{\top}-Dr(\theta^{\prime})^{\top}\|_{1,2}$ $\displaystyle=\sup\{\|(Dr(\theta)^{\top}-Dr(\theta^{\prime})^{\top})v\|_{1}:v \in\mathbb{R}^{n},\|v\|_{2}\leq 1\}$ $\displaystyle=\max_{i}\|\nabla g_{i}(\theta)-\nabla g_{i}(\theta^{\prime})\| \leq L\|\theta-\theta^{\prime}\|.$ $$

$$ $\displaystyle\|\nabla f(\theta)-\nabla f(\theta^{\prime})\|$ $\displaystyle=\|Dr(\theta)^{\top}r(\theta)-Dr(\theta^{\prime})^{\top}r(\theta^ {\prime})\|$ $\displaystyle=\|Dr(\theta)^{\top}r(\theta)-Dr(\theta)^{\top}r(\theta^{\prime}) +Dr(\theta)^{\top}r(\theta^{\prime})-Dr(\theta^{\prime})^{\top}r(\theta^{ \prime})\|$ $\displaystyle\leq\|Dr(\theta)^{\top}r(\theta)-Dr(\theta)^{\top}r(\theta^{ \prime})\|+\|Dr(\theta)^{\top}r(\theta^{\prime})-Dr(\theta^{\prime})^{\top}r( \theta^{\prime})\|$ $\displaystyle\leq\sigma_{\max}\|r(\theta)-r(\theta^{\prime})\|+\|Dr(\theta)^{ \top}-Dr(\theta^{\prime})^{\top}\|_{1,2}\|r(\theta^{\prime})\|_{1}$ $\displaystyle\leq\sigma_{\max}^{2}\|\theta-\theta^{\prime}\|+\beta C\|\theta- \theta^{\prime}\|.$ $$

Where the last inequality follows from $r$ being $\sigma_{\max}$ Lipschitz since $\|r(\theta)-r(\theta^{\prime})\|\leq\|Dr(\theta)\|\|\theta-\theta^{\prime}\|$ by the mean value inequality (Hörmander, ) and by the fact that $\|Dr(\theta)^{\top}\|\leq\sigma_{\max}$.
Since $r$ is bounded it follows that there exists $\|r(\theta)\|_{1}\leq C$ for all $\theta$.
∎

###### Proposition 4.1 .

Assume $f$ satisfies the $\mu$-PL condition, and let $\sigma_{\min}$ be a lower bound on the singular values of $Dg(\theta)^{\top}$. Then, we have $f\circ g$ is $\mu\sigma^{2}_{\min}$-PL.

###### Proof.

We have that

$$ $\displaystyle||\nabla f\circ g(\theta)||^{2}$ $\displaystyle=||Dg(\theta)^{\top}\nabla_{z=g(\theta)}f(z)||^{2}$ $\displaystyle=\nabla f(z)^{\top}D(g(\theta))D(g(\theta))^{\top}\nabla f(z)$ $\displaystyle\geq\sigma_{\min}^{2}||\nabla f(z)||^{2}$ $\displaystyle\geq\sigma_{\min}^{2}\mu(f(z)-\inf_{z^{\prime}}f(z^{\prime}))$ $\displaystyle\geq\sigma_{\min}^{2}\mu(f(z)-\min_{z^{\prime}\in\mathcal{Z}}f(z^ {\prime}))$ $\displaystyle=\sigma_{\min}^{2}\mu(f(g(\theta))-\inf_{\theta^{\prime}}f(g( \theta^{\prime}))).$ $$

∎

###### Proposition B.3 .

If $g:\mathbb{R}^{d}\to\mathbb{R}^{n}$ $g(\theta)=(g_{1}(\theta),\cdots,g_{n}(\theta))^{\top}$ is differentiable where $g_{i}$ is $\beta$-smooth and $Dg(\theta)^{\top}$ has globally lower and upper bounded singular values, then $\{g(\theta):\theta\in\mathbb{R}^{d}\}$ is unbounded.

###### Proof.

We prove by contradiction. Suppose $\{g(\theta):\theta\in\mathbb{R}^{d}\}$ is bounded and denote $\mathcal{Z}$ as its closure which is also bounded. Then there exists $v\in\mathbb{R}^{n}\notin\mathcal{Z}$.
Consider the function $f(\theta)=\frac{1}{2}\|g(\theta)-v\|^{2}$.
Taking $r(\theta)=g(\theta)-v$, we have $Dr=Dg$, and $r_{i}$ are still $\beta$-smooth, therefore by Lemma B.1 $f$ is $L$-smooth. Since $f$ is continuous and $\mathcal{Z}$ is compact, its minimum is attained, and thus there exists $z_{\ast}\in\mathcal{Z}$ such that

$$ $\frac{1}{2}\|z_{\ast}-v\|^{2}=\inf_{\theta\in\mathbb{R}^{d}}f(\theta).$ $$

Moreover, there exists a sequence $\{\theta_{t}\}_{t\in\mathbb{N}}$ such that $g(\theta_{t})\to z_{\ast}$ since $\mathcal{Z}$ is closed.
By the smoothness of $f$ it also follows that

$$ $\frac{\|\nabla f(\theta_{t})\|^{2}}{2L}\leq f(\theta_{t})-\inf_{\theta\in \mathbb{R}^{d}}f(\theta).$ $$

Since singular values of $Dg(\theta)^{\top}$ are lower-bounded, there exists $\sigma_{\min}>0$ such that $\|Dg(\theta)^{\top}v\|\geq\sigma_{\min}\|v\|$.
Therefore we have

$$ $\displaystyle 0=\lim_{t}f(\theta_{t})-\inf_{\theta\in\mathbb{R}^{d}}f(\theta)$ $\displaystyle\geq\lim_{t}\frac{\|\nabla f(\theta_{t})\|^{2}}{2L}$ $\displaystyle=\lim_{t}\frac{\|Dg(\theta_{t})^{\top}(g(\theta_{t})-v)\|^{2}}{2L }\geq\lim_{t}\frac{\sigma_{\min}^{2}}{2L}\|g(\theta_{t})-v\|^{2},$ $$

which implies that $z_{\ast}=\lim_{t}g(\theta_{t})=v$ and that $v$ is indeed within $\mathcal{Z}$ a contradiction!

∎

###### Lemma B.1 .

###### Proof.

###### Proposition 4.1 .

###### Proof.

###### Proposition B.3 .

###### Proof.

## Appendix C Min max experiments

Figure: Figure 5: Time in seconds for performing 10,000 iterations of each method. The number in parenthesis correspond to number of inner steps taken. As a special case we have PHGD and GDA are equivalent to GN(1) and Surr-GD(1) respectively.
Refer to caption: x5.png

Figure: Figure 6: Average convergence for various surrogate methods from Section 4 in the hidden matching pennies game. The average was computed over 1,000 trajectories each with randomly sampled parameters $\alpha_{j}^{i}$ and $\theta_{0}$.
Refer to caption: x6.png

### C.1 Hidden Matching Pennies

In the hidden matching pennies game each player $i$ has the parameterization $h^{i}(\theta)=\operatorname{sigmoid}(\alpha_{2}^{i}\operatorname{CELU}(\alpha^
{i}_{1}\theta))$.
The parameters for each player are:

$$ $\displaystyle\alpha_{1}^{1}=0.5,\text{ and }\alpha_{2}^{1}=1\text{ for player }1,$ $\displaystyle\alpha_{1}^{2}=0.7,\text{ and }\alpha_{2}^{2}=1\text{ for player }2.$ $$

The parameters $\alpha_{1}^{i},\alpha_{2}^{i}$, were chosen to approximately replicate the trajectory of PHGD presented in Sakos et al. (, Figure 4).
The initial parameters $\theta_{1}$ were selected to be the same as those selected by Sakos et al. (), $\theta_{1}=(\theta_{1}^{1},\theta_{1}^{2})=(1.25,2.25)$.

In Figure 5 we report the runtime for different surrogate algorithms and number of inner steps.
In Figure 6, the average distance across 100 random initializations is observered.
$\theta_{0}$ was randomly sampled from two independent Gaussians with standard deviation of $4$. Similarly, each $\alpha_{j}^{i}$ was randomly sampled from a uniform random variable with support $[-1,1]$.

Figure: Figure 7: Average convergence for various surrogate methods from Section 4 in the hidden rock-paper-scissors game. The average was computed over 1,000 trajectories each with randomly sampled parameters $A_{j}^{i}$ and $\theta_{0}$.
Refer to caption: x7.png

### C.2 Hidden Rock-Paper-Scissors

Each player i’s mixed strategy in the hidden rock-paper-scissors game is parameterized by the function $h^{i}(\theta)=\operatorname{softmax}(A_{2}^{i}\operatorname{CELU}(A_{1}^{i}
\theta^{i}))$, with $\theta^{i}\in\mathbb{R}^{5}$.
The min-max objective is $f(z^{1},z^{2})=\langle z^{1},Az^{2}\rangle+\frac{0.2}{2}\|z-z_{\ast}\|^{2}$, where $z=(z^{1},z^{2})$ and $z_{\ast}$ is the equilibrium of rock-paper-scissors (sample rock, paper, and scissors with equal probability) (Sakos et al., ).
In Figure 7 we observe the average convergence across 100 random initializations of $\theta_{1}\in\mathbb{R}^{5}$ and matrixes $A_{j}^{i}$ for various surrogate based methods.
$\theta_{1}$ was sampled from a 5-dimensional isotropic Gaussian while each element of $A_{j}^{i}$ was sampled from a uniform random variable with support $[-1,1]$.

## Appendix D Policy Evaluation and Projected Bellman Error

In this section we provide some background on minimizing projected Bellman error (PBE) and the stochastic methods proposed by Bertsekas ().
For a given MDP with $n$ states $(s^{1},\cdots,s^{n})$, and policy $\pi$, we denote the expected reward $r_{\pi}\in\mathbb{R}^{n}$, discount factor $\gamma\in(0,1)$, and state to state probability transition matrix $P_{\pi}\in\mathbb{R}^{n\times n}$.
The associated linear Bellman operator is $T_{\pi}(z)=r_{\pi}+\gamma P_{\pi}z$ and is contraction Bertsekas (). The value vector $v_{\pi}\in\mathbb{R}^{n}$ is the unique fixed point of $T_{\pi}$, with i^th component $v^{i}$ equals to the discounted return starting from state $s^{i}$, $\mathbb{E}_{\tau=(s_{1},s_{2},\cdots)}\left[\sum_{t=1}^{\infty}\gamma^{t}r_{
\pi}(s_{t})|s_{1}=s^{i}\right]$, where we use $r_{\pi}(s)$ to mean $r_{\pi}^{i}$ such that $s^{i}=s$, and the expectation is over possible trajectories $\tau=(s_{1},s_{2},\cdots)$.

Under function approximation it may not be possible to find a fixed point of $T_{\pi}$ and find the true value function.
Instead we can consider the projected fixed point,

$$ $\displaystyle z_{\ast}=\Pi_{\Xi}(T_{\pi}(z_{\ast})).$ (21) $$

Where the projection is on to the set of realizable value functions $\mathcal{Z}=\{v_{\theta}:\theta\in\mathbb{R}^{d}\}$.
We use the notation $v_{\theta}$ in place of $g(\theta)$ to be consistent with the RL literature, the prediction for state $s^{i}$ is $v_{\theta}(s^{i})=g(\theta)^{i}$.
$\Xi$ is the diagonal matrix with entries corresponding to the stationary distribution $\xi=(\xi^{1},\cdots,\xi^{n})$ of $P_{\pi}$.

As pointed out by Bertsekas (), finding the fixed point (21) is equivalent to solving a VI of the form (1)
with constraint $\mathcal{Z}$ and operator

$$ $\displaystyle F(z)=\Xi(z-T_{\pi}(z)).$ (22) $$

Additionally, Bertsekas () showed that $F$ is both smooth and strongly monotone and therefore satisfies our hidden structure Assumption 3.1.

This fixed point can then be equivalently mapped to the minimum of the projected Bellman error with respect to the parameters, i.e. a TD fixed point.
The fixed point $z_{\ast}=v_{\theta_{\ast}}$ corresponds to finding parameters $\theta_{\ast}$ such that

$$ $\displaystyle\theta_{\ast}\in\underset{\theta}{\arg\min}\left[BE(\theta,\theta _{\ast})=\frac{1}{2}\sum_{i=1}^{n}\xi^{i}(v_{\theta}(s^{i})-(r_{\pi}(s^{i})- \gamma\mathbb{E}_{s^{\prime}\sim P_{\pi}}\left[v_{\theta_{\ast}}(s^{\prime})|s ^{i}\right])^{2}\right].$ (23) $$

Note this is not a scalar minimization problem since the loss is not directly minimized through the next state prediction, doing so would result in minimizing the Bellman error, $\min_{\theta}BE(\theta,\theta)$ and not PBE.
The fixed points of these objectives need not coincide even with linear function approximation (Sutton & Barto, ).

Using the function $BE$ and the stationary condition (23) we can define the following natural gap function

$$ $\displaystyle BE_{\text{gap}}(\theta)=BE(\theta,\theta)-\inf_{\theta^{\prime}} BE(\theta^{\prime},\theta).$ (24) $$

Notice that $BE_{\text{gap}}(\theta)\geq 0$ for all $\theta$ and is zero if and only if $\theta$ is a fixed point of (23).

Since $\Pi_{\Xi}\circ T_{\pi}$ is known to be a contraction  (Bertsekas, ) but is expensive to compute exactly, we can devise a surrogate loss that approximates it.
The operator $\Pi_{\Xi}\circ T_{\pi}$ is equivalent to the scaled projected gradient method $z_{t+1}=\Pi(z_{t}-\Xi^{-1}F(z_{t}))$, where $z_{t}=v_{\theta_{t}}$, and is minimum of the surrogate loss

$$ $\displaystyle\ell_{t}(\theta)$ $\displaystyle=\frac{1}{2}\|v_{\theta}-\left(v_{\theta_{t}}-\Xi^{-1}F(v_{\theta _{t}})\right)\|_{\Xi}^{2}$ (25) $\displaystyle=\frac{1}{2}\|v_{\theta}-T_{\pi}(v_{\theta_{t}})\|_{\Xi}^{2}.$ (26) $$

Note that if $\Xi=\operatorname{Id}$ than this is the same surrogate loss (4) with $\eta=1$.

### D.1 The Linear Case

In this section we assume that predicted values are linear, $g(\theta)=\Phi\theta$, with some feature matrix

$$ $\Phi=\begin{bmatrix}&\phi^{\top}(s^{1})\\ &\vdots\\ &\phi^{\top}(s^{n})\end{bmatrix}\in\mathbb{R}^{n\times d}.$ $$

In this case we have that the operator $F$ is also linear in $\theta$

$$ $F(z)=F(\Phi\theta)=\Xi(\Phi\theta-\gamma P_{\pi}\Phi\theta-r_{\pi})=\Xi(\Phi- \gamma P_{\pi}\Phi)\theta-\Xi r_{\pi}.$ $$

Since $g$ linear, there exists a preconditioning scheme that can generate a sequence of parameters $\{\theta_{t}\}_{t\in\mathbb{N}}$ such that $\{z_{t+1}=\Phi\theta_{t+1}=\Pi_{\Xi}(T_{\pi}(z_{t}))\}$ and therefore is guaranteed to converge linearly.
This preconditioning scheme is simply the minimizer of the weighted least-squares surrogate loss $\ell_{t}(\theta)=\nicefrac{{1}}{{2}}\|\Phi\theta-T_{\pi}(\theta_{t})\|^{2}_{\Xi}$,

$$ $\theta_{t+1}=\theta_{t}-(\Phi^{\top}\Xi\Phi)^{-1}\Phi^{\top}F(z_{t}).$ $$

If there is no unique minimizer then the pseudo-inverse $(\Phi^{\top}\Xi\Phi)^{{\dagger}}$ can be used.
To approximate the iteration Bertsekas () suggests using estimators that depend only on the history states $(s_{1},s_{2},\cdots,s_{t},s_{t+1})$ and rewards $(r_{1},\cdots,r_{t})$ to approximate the conditioning matrix $\Phi^{\top}\Xi\Phi$ and gradient $\Phi^{\top}F(z_{t})$.
The following estimators are proposed:

- •
$\hat{D}_{t}=\frac{1}{t}\sum_{i=1}^{t}\phi(s_{i})\phi^{\top}(s_{i})$
- •
$\hat{C}_{t}=\frac{1}{t}\sum_{i=1}^{t}\phi(s_{i})(\phi(s_{i})-\gamma\phi(s_{i+1
}))^{\top}$
- •
$\hat{r}_{t}=\frac{1}{t}\sum_{i=1}^{t}\phi(s_{i})r_{i}$.

If the chain is fully mixed then the sampled states are drawn according to $\xi$ making the above estimators unbiased:

$$ $\displaystyle\Phi^{\top}\Xi\Phi=\sum_{i}^{n}\xi^{i}\phi(s^{i})\phi(s^{i})^{ \top}=\mathbb{E}\left[\hat{D}_{t}\right],$ $\displaystyle\Phi^{\top}F(z)=\sum_{i}\xi^{i}\phi(s^{i})(\phi(s^{i})^{\top} \theta-\sum_{s^{\prime}}(P_{\pi})_{s^{i},s}\phi(s)^{\top}\theta-r_{\pi}(s^{i}) )=\mathbb{E}\left[\hat{C}_{t}\theta-\hat{r}_{t}\right].$ $$

Where $(P_{\pi})_{s,s^{\prime}}$ is the transition probability to state $s^{\prime}$ when in state $s$.
Therefore the iteration

$$ $\theta_{t+1}=\theta_{t}-(\hat{D}_{t})^{-1}(\hat{C}_{t}\theta_{t}-\hat{r}_{t}),$ $$

eventually converges to exact deterministic iteration.
Interestingly, the stochastic version can be shown to be the minimmum of the surrogate

$$ $\tilde{\ell}_{t}(\theta)=\frac{1}{2}\|\Phi\theta-\hat{T}_{\pi}(z_{t})\|^{2}_{ \hat{\Xi}}.$ $$

Where $\hat{T}_{\pi}(z)=\bar{r}+\gamma\bar{P}_{\pi}(z)$, with $\Xi$, $r$, and $P_{\pi}$ being estimated with the empirical distribution.
More precisely, denoting the number of times that a state $s$ is visited in a trajectory of length $t$ as $n(s)$, and the number of times $s^{\prime}$ is visited after $s$ as $n(s,s^{\prime})$, then the empirical distribution over states is $\hat{\xi}=(\nicefrac{{n(s^{1})}}{{t}},\cdots,n(s^{n})/t)$ and $\hat{\Xi}$ is the diagonal matrix with diagonal $\hat{\xi}$.
Similarly, the transition matrix is estimated by $(\bar{P}_{\pi})_{s,s^{\prime}}=n(s,s^{\prime})/n(s)$ if $n(s)>0$, and arbitrary otherwise.
For convenience, we write $\hat{\xi}(s^{i})=\hat{\xi}^{i}$.

###### Proposition D.1 .

The gradient of the surrogate loss $\tilde{\ell}_{t}(\theta)=\frac{1}{2}\|\Phi\theta-\hat{T}_{\pi}(z_{t})\|^{2}_{
\hat{\Xi}}$ is

$$ $\nabla\tilde{\ell}_{t}(\theta)=\hat{C}_{t}\theta_{t}-\hat{r}+\hat{D}_{t}( \theta-\theta_{t}).$ $$

If $\hat{D}_{t}$ is invertible then its minimum is

$$ $\theta_{t+1}=\theta_{t}-(\hat{D}_{t})^{-1}(\hat{C}_{t}\theta_{t}-\hat{r}_{t}).$ $$

###### Proof.

By definition of $\hat{\Xi}$, we have that $\hat{D}_{t}=\frac{1}{t}\sum_{i}\phi(s_{i})\phi(s_{i})^{\top}=\Phi^{\top}\hat{
\Xi}\Phi$.
Similarly, we have that $\hat{C}_{t}=\frac{1}{t}\sum_{i=1}^{t}\phi(s_{i})(\phi(s_{i})-\gamma\phi(s_{i+1
}))^{\top}=\Phi^{\top}\hat{\Xi}\Phi-\gamma\frac{1}{t}\sum_{i=1}^{t}\phi(s_{i})
\phi(s_{i+1})^{\top}$.
Where

$$ $\displaystyle\frac{1}{t}\sum_{i=1}^{t}\phi(s_{i})\phi(s_{i+1})^{\top}$ $\displaystyle=\frac{1}{t}\sum_{s,s^{\prime}}n(s,s^{\prime})\phi(s)\phi(s^{ \prime})^{\top}$ (27) $\displaystyle=\frac{1}{t}\sum_{s}\phi(s)\sum_{s^{\prime}}n(s,s^{\prime})\phi(s ^{\prime})^{\top}$ (28) $\displaystyle=\frac{1}{t}\sum_{s}n(s)\phi(s)\sum_{s^{\prime}}\frac{n(s,s^{ \prime})}{n(s)}\phi(s^{\prime})^{\top}$ (29) $\displaystyle=\frac{1}{t}\sum_{s}n(s)\phi(s)\sum_{s^{\prime}}(\bar{P}_{\pi})_{ s,s^{\prime}}\phi(s^{\prime})^{\top}$ (30) $\displaystyle=\sum_{s}\hat{\xi}(s)\phi(s)\sum_{s^{\prime}}(\bar{P}_{\pi})_{s,s ^{\prime}}\phi(s^{\prime})^{\top}$ (31) $\displaystyle=\Phi^{\top}\hat{\Xi}\bar{P}_{\pi}\Phi.$ (32) $$

Therefore $\hat{C}_{t}=\Phi^{\top}\hat{\Xi}(\Phi-\gamma\bar{P}_{\pi}\Phi)$.
Similarly, $\hat{r}_{t}=\frac{1}{t}\sum_{i=1}^{t}\phi(s_{i})r_{i}=\Phi^{\top}\Xi\bar{r}_{\pi}$.

Now consider the weighted least squares loss

$$ $\tilde{\ell}_{t}(\theta)=\frac{1}{2}\|\Phi\theta-\hat{T}_{\pi}(\Phi\theta_{t}) \|^{2}_{\hat{\Xi}}.$ $$

The gradient of $\ell_{t}$ is

$$ $\displaystyle\nabla\ell_{t}(\theta)$ $\displaystyle=\Phi^{\top}\hat{\Xi}(\Phi\theta-\hat{T}_{\pi}(\Phi\theta_{t}))= \Phi^{\top}\hat{\Xi}(\Phi\theta-\gamma\bar{P}_{\pi}\Phi\theta_{t}-\bar{r}_{\pi})$ (33) $\displaystyle=\Phi^{\top}\hat{\Xi}(\Phi\theta-\Phi\theta_{t}+\Phi\theta_{t}- \gamma\bar{P}_{\pi}\Phi\theta_{t}-\bar{r}_{\pi})$ (34) $\displaystyle=\Phi^{\top}\hat{\Xi}(\Phi\theta-\Phi\theta_{t})+\Phi^{\top}\hat{ \Xi}(\Phi\theta_{t}-\gamma\bar{P}_{\pi}\Phi\theta_{t}-\bar{r}_{\pi})$ (35) $\displaystyle=\hat{D}_{t}(\theta-\theta_{t})+\hat{C}_{t}\theta_{t}-\hat{r}_{t}$ (36) $$

Setting the gradient to zero gives the minimum of $\tilde{\ell}_{t}$.
∎

###### Proposition D.1 .

###### Proof.

### D.2 The Nonlinear Case

Figure: Figure 8: Comparison of Bellman gap during training of TD(0) and surrogate methods in the offline full-batch setting with nonlinear function approximation in Ant (top) and HalfCheetah (bottom) environments, measured by gradient computations (left) and wallclock time (right). The average Bellman gap (39) across 20 runs along with 95% confidence intervals are computed from a fixed training set. The red dashed line represents the lowest Bellman gap achieved by any of the algorithms.
Refer to caption: x8.png

Figure: Figure 9: Comparison of average performance of TD(0) and surrogate methods in minimizing the value prediction error in the offline full-batch setting with nonlinear function approximation in Ant (top) and HalfCheetah (bottom) environments, measured by gradient computations (left) and wallclock time (right). The average value prediction error across 20 runs along with 95% confidence intervals are computed from a fixed test set. The red dashed line represents the lowest value prediction error achieved by any of the algorithms.
Refer to caption: x9.png

In this section, we detail the surrogate algorithms used for the nonlinear setting, as outlined in Algorithms 2, 3 and 4.
As a complement to Section 5.2, we compare the convergence properties of TD(0) with the surrogate methods under a an offline, full-batch setting, where the training data is pre-collected from the reference policy.
This experiment provides insight on two important fronts: how well can the methods solve the hidden monotone VI problem, and how the performance of the different algorithms are affected when there is no environment interaction.

In our deep learning/nonlinear setting, the state space is too large to verify if we have solved the VI (22) by the $BE_{\text{gap}}$(24) or other metrics.
To test the effectiveness of our methods at solving this VI and minimizing PBE we consider an empirical approximation given a fixed batch of data (i.e. offline).
In this setting, $n$ tuples of state, reward and next state are collected $\{(s_{t},r_{t},s_{t+1})\}_{t=1}^{n}$ from a fixed reference policy $\pi$.
Using these observations we construct an empirical estimate of $BE$ (23),

$$ $\displaystyle\widehat{BE}(\theta,\theta^{\prime})=\frac{1}{n}\sum_{t=1}^{n}(v_ {\theta}(s_{t})-(r_{t}-\gamma v_{\theta^{\prime}}(s_{t+1})))^{2}.$ (37) $$

We can then define the following fixed point problem:
find $\theta_{\ast}$ such that

$$ $\displaystyle\theta_{\ast}\in\underset{\theta}{\arg\min}\,\widehat{BE}(\theta, \theta_{\ast}).$ (38) $$

Given this new empirical approximation of PBE we can define a gap analogous to (24),

$$ $\displaystyle\widehat{BE}_{\text{gap}}(\theta)=\widehat{BE}(\theta,\theta)- \inf_{\theta^{\prime}}\widehat{BE}(\theta^{\prime},\theta).$ (39) $$

In practice we approximate the infimum in $\widehat{BE}$ by 500 steps of AdamW, with a learning rate of $1\times 10^{-4}$ and exponential annealing at a decay rate of $\gamma=0.995$.
In the offline setting we consider deterministic algorithms like in the min-max experiments of Section 5.1, and therefore we do not consider the double sampling algorithm (Algorithm 3) but only full-batch versions of Algorithm 2 and Algorithm 4.
We compare different algorithms with $\widehat{BE}_{\text{gap}}$ (39), giving a measure of how much the fixed point condition (38) is violated.
Given enough data this fixed point is a proxy for the fixed point (23).

Since no environment interaction is required during training, we compare the performance of the methods in terms of gradient computations and wall-clock time, with the former being the dominant factor in computational cost, unlike the setting in Section 5.2 where environment interaction plays a larger role.

As shown in Figure 8, increasing the number of inner loop steps significantly reduces the Bellman gap, suggesting that the model approaches the fixed point more effectively. Notably, the surrogate method with $10$ inner steps is more efficient than TD(0) in terms of gradient computations, while both inner steps = $10$ and $50$ outperform TD(0) in wall-clock time.

As presented in Figure 9, we also evaluate the value prediction error on a test set to further assess the performance of the algorithms in the full batch and deterministic setting. In all cases, at least one variant of the surrogate method converges faster than TD(0), both in terms of gradient computations and wall-clock time. This demonstrates that, with an appropriate choice of inner loop steps and alpha threshold, the surrogate method not only outperforms TD(0) in terms of stability but also in computational efficiency.

Figure: Algorithm 2 Surrogate Method with Inner Loop

Figure: Algorithm 3 Surrogate Method with Double Sampling

Figure: Algorithm 4 Thresholded Surrogate Method

## Appendix E Applications to Performative Prediction

Minimizing Projected Bellman error can be viewed as a special case of finding a stable point in performative prediction (Perdomo et al., ).
In performative prediction or more generally optimization under decision dependent distributions (Drusvyatskiy & Xiao, ), the model predictions $z=g(\theta)$ influence the targets $y$.
With moving targets it is of interest to find model predictions that are performatively stable; such models are optimal under the shifting targets and are stable under repeated applications of empirical risk minimization.

For simplicity, we stay within the finite dimensional case where a model’s prediction function is given by the $n$-dimensional vector, $z=g(\theta)\in\mathbb{R}^{n}$.
Where each prediction is $z^{i}=g^{i}(\theta)=h(x_{i},\theta)$, for some feature vector $x_{i}$ and fixed model architecture $h$.
Given an error function $\ell(z,y)$, quantifying error between predictions $z\in\mathbb{R}^{n}$ and targets $y\in\mathbb{R}^{n}$, the performatively stable models satisfy

$$ $\displaystyle\theta_{\ast}\in\underset{\theta}{\arg\min}\,\mathbb{E}_{y\sim D( g(\theta_{\ast}))}\left[\ell(g(\theta),y)\right].$ (40) $$

The prediction dependent shift in targets is represented by the distribution $D(\cdot)$ being a function of the model predictions $g(\theta)$.
Note that we have used the formulation of performative prediction with respect to model predictions Mofakhami et al. () instead of parameters.

The problem of minimizng projected Bellman error is a special case of (40) with $\ell(z,y)=||z-y||^{2}_{\Xi}$ and $D(z)$ is the distribution with full weight on $T_{\pi}(z)$.

The problem of finding a performatively stable point can more generally be expressed as the following decision-dependent optimization problem:

$$ $\displaystyle\theta_{\ast}\in\underset{\theta}{\arg\min}f_{g(\theta_{\ast})}(g (\theta)).$ (41) $$

Or equivalently a constrained optimization problem with constraint $\mathcal{Z}=\operatorname{cl}\{g(\theta):\theta\in\mathbb{R}^{d}\}$:

$$ $\displaystyle\theta_{\ast}$ $\displaystyle\in\underset{\theta}{\arg\min}f_{g(\theta_{\ast})}(g(\theta)) \Leftrightarrow z_{\ast}\in\underset{z\in\mathcal{Z}}{\arg\min}f_{z_{\ast}}(z).$ $$

If $Z$ is closed convex and $f_{z^{\prime}}(z)$ is convex and differentiable with respect to $z$, then the above constrainted formulation is equivalent to the fixed point problem:

$$ $\displaystyle z_{\ast}=\Pi\circ T(z_{\ast})=\Pi(z_{\ast}-\eta\nabla f_{z_{\ast }}(z_{\ast})),$ (42) $$

where we denote the gradient of $f_{z^{\prime}}(z)$ with respect to $z$ as simply $\nabla f_{z^{\prime}}(z)$.
As mentioned in Section D, Bertsekas () showed that solving (42) is equivalent to solving a strongly monotone and smooth VI if either $T$ or $\Pi\circ T$ is a contraction.
Therefore, under these contraction conditions (42) is a hidden strongly monotone and smooth VI problem of the form (1)!
Thankfully, (Drusvyatskiy & Xiao, ; Cheng et al., ) showed that $\Pi\circ T$ is a contraction if $f_{z^{\prime}}(z)$ is $\mu$ strongly convex with respect to $z$ and $\nabla f_{z^{\prime}}(z)$ is $\beta$-Lipschitz with respect to $z^{\prime}$ and if $\nicefrac{{\beta}}{{\mu}}<1$.
Therefore, under standard performative prediction assumptions such as those found in Drusvyatskiy & Xiao (), the performatively stable point (40) is equivalent to solving a hidden strongly monotone and smooth VI problem where our surrogate loss approach (Algorithm (1)) applies and converges to the stable point under Theorems (3.2,3.6,A.5).

## Peer Reviews

confidence: 3
contribution: 3
initial_rating: 8
presentation: 3
questions: - It is very interesting that better convergence of the inner loop does not necessarily translate to better convergence of the outer loop, i.e. more iterations are not necessarily useful (e.g. LM, Sur-GD, GN, Gig 1 & 2). Is there a theoretical justification? 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? Has this effect also been observed in the scalar minimization case? If yes, how does it compare?
- The authors write: "In general $\ell_t^*$ 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 $\ell_t^*=0$." (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?

Style:
- Fig 1: It is hard to tell the methods apart, maybe use different line styles.
soundness: 4
strengths: - The extension of iterative surrogate optimization from the scalar to the variational inequality case is a significant contribution.
- Paper offers a rigorous theoretical analysis.
- Strong performance of the method compared to the TD0 baseline.
- Well-written and relatively easy to follow.
summary: This paper introduces a new method for optimizing variational inequalities with hidden structure by optimizing a series of surrogate losses, thereby extending previous methods for optimizing scalar loss functions. The authors provide a new $\alpha$-descent condition on the sequence of inner surrogate optimization problems which is used to derive linear convergence rates for the outer optimziation in the deterministic and unconstrained stochastic setting. Specific choices of optimizer for the inner surrogate loss are shown to generalize previous works. Additionally, the authors provide conditions under which linear convergence is achieved.

Experimentally, the method is tested on optimizing min-max games and projected Bellman error. In the min-max setting different variants of the method are compared, showing that the choice of the inner optimizer matters by improving on the special cases treated in previous work. In the RL setting, the surrogate loss perspective is connected to computationally expensive preconditioning methods which is shown to be approximated in the linear case via the presented iterative scheme. In the non-linear case the policy evaluation problem is tackled for two mujoco environments, where different versions of the method are shown to improve over the special case of TD(0) in terms of wall-clock time and sample efficiency.
weaknesses: - 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.

---

confidence: 4
contribution: 4
initial_rating: 8
presentation: 3
questions: 1. 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)?

2. The results on improved sample complexity in the RL value prediction tasks are very compelling in my opinion! I think it fits neatly into an overarching philosophy that blind RL is wasteful (in terms of samples/environment interactions), and that some form of guidance really helps. There are whole fields (search goal-conditioned RL, contrastive RL, etc) that attempt to figure out how to learn the right flavor of guidance, and it seems to me that your form of (not-learned!) surrogate losses can be seen as a particularly simple form of this. From your work and the related literature (which you know 1000x better than I), 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?

3. Probably not a valuable question, but I have to ask: would it be possible for you to do GAN training? It would be convincing to deep learning practitioners and theorists alike!

3. This is more a question of personal interest regarding this style of surrogate losses (i.e. ones where you take a step in output space, use inner loop to make the model catch up, repeat) and perhaps not specific to VIs, but here goes: *is there any understanding of how this framework assists/counteracts the implicit biases of either (1) optimization methods in the inner loop or (2) architectural choices in the model $g$?* I ask because, particularly in deep learning theory, there is often the vibe that the natural dynamics induced by such design parameters actually can help (see this paper https://arxiv.org/pdf/1802.06509 for a cool result on GD acceleration caused by model depth, for example). I could imagine some settings where the rigidity of the outer loop dynamics on $z_t$ prevent these complicated phenomena (for example, in the linked paper I suspect surrogate losses could prevent the acceleration for adversarial choices of $F$). Conversely, I can certainly imagine settings where the structure of the outer loop drives the optimization more usefully, in a similar fashion to how surrogate rewards in RL help orient an agent in a sparse-reward environment (see Question 2). Is there any understanding of this tradeoff, and perhaps more importantly do you imagine any differences to this tradeoff in the VI setting?
soundness: 4
strengths: This paper has a strong originality in that it appears to be the first to extend this type of surrogate losses to VIs, and it does so in a way that provably takes advantage of hidden monotonicity/convexity structure. Importantly, this extension is nontrivial -- there is a simple and solid adversarial example the authors provide (Prop. 3.3) that shows a difficulty gap in comparison with surrogate losses in the scalar optimization case. I think there is the extra strength (though perhaps it isn't highlighted enough, see my "Weaknesses" section) that it appears the framework, broad proof techniques, and main takeaways seem rather robust to choice of inner optimization routine (i.e. robust to assumptions, rates of convergence, etc.). In my eyes, the authors have constructed a fairly general methodology to reduce VIs with hidden structure to scalar optimization in a way that directly leverages that hidden structure -- this is very cool, and in general such reduction results tend to be quite powerful (such as online-to-batch reduction, nonconvex-to-convex reduction such as Algorithm 3 in https://arxiv.org/pdf/1806.02958, etc). 

The analysis is also quite clear, proceeding along similar lines to many optimization papers and doing a fantastic job of contextualizing results, definitions, and assumptions in prior works. In particular, Section 4 (before subsection 4.1) skillfully highlights the flexibility of choices of inner loop optimizers in an organized way, noting equivalence to prior methods (such as PHGD) where applicable. This is a good transition to the experiments, which compare different setups of the inner loop routine in various minimax and RL value-prediction environments. Overall, I think this presentation is clear, the assumptions are obvious, and the experimental apparatus seems right for the general framework (though it would have been cool to see a slightly larger-scale experiment, and I think GAN training is the perfect low-hanging fruit if the authors have the resources!). Lovely stuff :)
summary: In this paper, the authors introduce a surrogate-loss-based framework for optimization of variational inequality (VI) systems, such as min-max. 

This paper is the first to extend the surrogate methodology to (strongly-monotone) VIs, where the inner loop calls a scalar optimization routine black-box. Importantly, they demonstrate with an elementary adversarial example that surrogate methods in these VIs are qualitatively more complex than surrogate methods in traditional scalar optimization (the inner loop progress needs to be strong enough to counteract the effects of $F$ to ensure outer convergence, as opposed to just $<1$ in scalar case). They show that (under sufficient inner loop optimization assumptions, quantified in the form of the $\alpha$-descent condition) the overall VI optimization succeeds in deterministic and stochastic regimes, with rates matching what is to be expected of strongly-convex optimization (ie geometric convergence). Lastly, they observe that an existing VI optimization method (PHGD) can be seen as a particular choice of inner loop optimization routine, and they investigate the benefits and consequences of alternative choices of inner loop algorithm and number of steps. 

Experimentally, the authors test the surrogate method for VI optimization in previously-investigated small-scale games, as well as on value prediction in fairly substantial RL settings. They observe interesting consequences of certain choices of inner loop algorithm and number of steps, and they demonstrate the value of the surrogate framework. In the RL experiments they see a significant improvement in environment sample complexity due to multiple inner loop iterations -- this matches some related work, but importantly does not require complex learned surrogate reward signals!

To summarize, the paper introduces the surrogate framework (outer loop over outputs and inner loop over model parameters) to a class of VI problems, demonstrates the nontrivial result that scalar optimization can (under some assumptions) be used black-box as a subroutine, and empirically investigate the associated phenomena on tasks of increasing complexity. Very cool!
weaknesses: I think the main (and only, to be honest) weakness of this paper is a weakness of presentation -- in particular, I feel that (as outlined in the "Strengths" section of my review above), the main contribution of this paper is that it clarifies and formalizes a framework where black-box scalar non convex optimization guarantees can be bootstrapped up to hidden-structure VI guarantees. However, at many points I felt that the presentation did not highlight this strongly enough, and instead chose to focus on particular rates/modes of convergence and substantiating particular assumptions. 

To be specific, I would argue that the $\alpha$-descent condition for inner loop progress is a bit of a red herring. As you mention, such convergence can only be shown in specific situations under the usual non convex optimization assumptions (PL condition, for example), which can often be difficult to justify. However, I feel that it's even unnecessary for you to justify it! It seems to me that, for example, Lemma A.2 and Prop A.3 would go through (perhaps with significantly more work) for weaker/more exotic types of inner loop guarantee -- the vibe of the proofs is moreso that (strongly-monotone) VIs allow you to push through the classic optimization proofs (the [Sakos '24] paper offers a similar takeaway in terms of bootstrapping convex VI guarantees up to hidden-convex VI guarantees, see their statements on p. 11). I bet there is a way to turn this into a strength of your paper: maybe something more like "we prove things under the $\alpha$-descent condition for clarity, but our meta-point is a more general reduction from VI optimization to scalar optimization via surrogate losses". I am not recommending you to do the analysis under all kinds of crazy inner loop guarantees, but instead to reweight the presentation a bit to highlight the robustness to inner loop method.

I will say that the $\alpha$-descent setting is a fantastic choice of inner loop guarantee to demonstrate the difficulty gap between scalar vs VI surrogate methods; it makes the presentation of the adversarial example very clear. However, I would have liked to see it used more as a presentation tool/particular instantiation of a more general phenomenon, whereas it often felt like you were keeping it around as a core part of your results. If the impact of this condition was qualitatively different in the VI setting than in scalar surrogate optimization then that would be one thing, but I am unsure of this (note: I am not too familiar with this style of surrogate losses via hidden convexity/monotonicity -- if I am wrong about this perhaps a toy example exemplifying the difference would be cool!). 

To really hammer this point home (sorry, but I don't really see any other weaknesses to write about), I feel like over-indexing on this particular criterion forces you to get stuck in the muck of justifying assumptions such as spectrally bounding input-output Jacobians of neural networks -- to some this may be a losing battle (models on complex, high-dim data will be likely to disregard features dynamically and hopefully learn lower-rank representations), but one I don't think you need to be fighting! Certain hypothesis classes/optimizers/datasets/etc will have different choices of inner loop routine that make sense, and the beauty of what you've shown here is that surrogate methods in VIs appear flexible to these choices. The language of reductions feels much more natural for such a result: I give you a VI problem with hidden monotone structure, you reduce it to a sequence of scalar non convex problems, and the practitioner/domain expert figures out the right inner loop soup (choosing between first-order or second-order methods, bias-variance tradeoffs, etc) to make it work. 

To sum up, it is my opinion that if you are going to use non convex optimization as a black-box for the inner loop, treat it like a black-box (not just in terms of whether to use ADAM as the optimizer, but even in a broader sense). Aside from this (and some questions that I put in the "Questions" section), I have nothing else to say but awesome paper!

---

confidence: 3
contribution: 4
initial_rating: 6
presentation: 2
questions: (1) In the basic case of supervised learning with a scalar loss, can we expect the proposed method perform better than off-the-shelf optimizers that work directly in the parameter space, i.e., Adam?

(2) The condition in the while loop of Algorithm 1 can not be verified. How could we let alpha be the user-defined parameter?
soundness: 2
strengths: The considered problem is important in the classical optimization context (i.e., constrained optimization, complementarity) and mordern ML where the loss is structured. The problem is also more general than minimizing a scalar loss usually showing up in supervised learning. The experiments show that the proposed method work fine in practice.
summary: The paper proposes an algorithm using some type of surrogate approximation to solve variational inequality (VI) problems. Those problems can be seen as finding first-order stationary points of a constrained optimization problem, but probably the setting in this paper is more general than that since the vector-valued function F is not necessarily a gradient (e.g. max-min game). The main idea is that "composite" (between the model and the loss) optimization problems in machine learning normally exhibit some structure, e.g., the loss w.r.t. to the model's output is convex (but the whole optimization function is not convex w.r.t. the model's parameters), one can push the "difficulty part" relating to model into the constraint to make the objective function convex. The authors then design a sequence of surrogate functions to minimize this reformulation problem and show convergence under a condition called "alpha-descent". To minimize the surrogate functions, they employ classical methods like Gaussian-Newton or Levenbergh-Marquardt. Numerical experiments are performed for some toy min-max games and in the reinforcement learning context.
weaknesses: 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. 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. 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.

---

confidence: 3
contribution: 3
initial_rating: 6
presentation: 2
questions: Questions:
1. You claim that Sakos et al. (2024) assumes $\mathcal{Z}$ bounded implicitly in their main lemma. Can you clarify which lemma, where it is assumed and which results are affected? I could not easily find it and I think this is an important point since it uncovers a fallacy in a previous analysis.

Comments:
- The second condition on $\alpha$ 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.
- The use of the term “gradient step” contrasts with the Variational inequality formulation where in general $F$ is not a gradient. A possible alternative could be "proximal step".
- The related work paragraph in the introduction should probably be a subsection or its name should be removed or changed.
- 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.

References:

Sakos, Iosif, et al. "Exploiting hidden structures in non-convex games for convergence to Nash equilibrium." Advances in Neural Information Processing Systems 36 (2024).
soundness: 3
strengths: 1. The theoretical analysis is quite thorough, considering  deterministic and stochastic cases and also addressing an issue with a previous analysis. The authors also explain how previous methods fit in their framework and discuss assumptions and potential limitations.
2. Promising experiments showing that the method can achieve faster convergence with more than one inner step iteration also in practical settings such as reinforcement learning with MLP value functions.
summary: This paper studies the problem of solving variational inequalities with deep learning methods with a hidden monotone structure. The authors present an iterative optimization algorithm with two nested loops, where In the outer loop, a surrogate square loss is constructed and partially minimized in the inner loop (until a sufficient decrease condition called $\alpha$-descent is satisfied) using an optimiser such as a quasi-newton method or ADAM. When $\alpha$ is sufficiently smaller than $1$, The authors prove linear (in the outer iterations) convergence guarantees in deterministic and stochastic settings, where in latter, the algorithm converges to a neighbourhood of the solution. They also prove that, when considering general variational inequalities, $\alpha < 1$ is not sufficient to guarantee convergence. Further, they show how several methods can be seen as special cases of their algorithm. They also present experimental results on min-max optimization and reinforcement learning.
weaknesses: 1. Certain parts lack clarity. Condition 2 in Theorem 3.2 seems unnecessary and needs refinement. (See question and comments).
2. 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.

Meta-review: This paper studies a class of variational inequalities by assuming hidden monotonicity. The paper proposes a surrogate-based approach by constructing a surrogate and employ any optimizer to ensure a sufficient decrease condition. The paper provides some convergence analysis under deterministic and stochastic settings. The experiments on done for some toy problems and RL problems. All reviewers agreed the paper has made some nice contributions and recommend an acceptance.

Decision: Accept (Poster)