Solving hidden monotone variational inequalities with surrogate losses
Authors: Ryan D'Orazio
Danilo Vucetic
Zichu Liu
Junhyung Lyle Kim
Ioannis Mitliagkas
Gauthier Gidel
Venue: ICLR 2025 Poster (2025)
Keywords: Variational Inequality
Optimization
Surrogate
Projected Bellman Error
Min-max Optimization
Primary area: optimization
TL;DR: A novel surrogate loss approach to solving variational inequalities with function approximation. Both theoretical guarantees and empirical analysis is provided.

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.

Published as a conference paper at ICLR 2025
SOLVING HIDDEN MONOTONE VARIATIONAL EQUALITIES WITH SURROGATE LOSSES
IN-
Ryan D'Orazio, Danilo Vucetic & Zichu Liu Mila Québec Al Institute, Université de Montréal Montréal, QC, Canada
(ryan.dorazio, danilo. vucetic, zichu. (arnu queeeee
Junhyung Lyle Kim
Department of Computer Science, Rice University Houston, TX, USA
Seyyleki@rice..ee.
Ioannis Milliagkas & Gauthier Gidel
Mila Québec Al Institute, Université de Montréal, CIFAR Al Chair Montréal, QC, Canada
[icannis, gidelgau] @mi la. quebec
ABSTRACT
Deep learning has proven to be effective in wide variety of loss minimization problems. However, many applications of interest, like minimizing projected Bellman eтror and min-mas optimization, cannot be modelled minimizing scalar loss function but instead correspond to solving a variational inequality (VI) problem. This difference in setting has caused many practical challenges naive gradient-baad based approaches from supervised learning tend to diverge and cycle in the VI case. this work, we propose principled surrogate-based approach com- patible with deep learning to solve VIs. We show that our surrogate-basee based ap- proach has three main benefits: (1) under assumptions that are realistic practice (when hidden monotone structure is present, interpolation, and sufficient opti- mization of the surrogates), guarantees convergence, (2) provides a unifying perspective of existing methods, and (3) is amenable to existing deep learning optimizers like ADAM. Experimentally, we demonstrate our surrogate-bart based ap- proach is effective in min-max optimization and minimizing projected Bellman error. Furthermore, the deep reinforcement learning case, we propose a novel variant of TD(O) which is more compute and sample efficient.
INTRODUCTION
Most machine learning approaches learn from data by minimizing loss function with respect 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| 2014). Unfortunately, outside of scalar loss minimization, deep learning becomes more challenging: the dynamics of variational inequality (VT) problems (e.g., min-max) are often plagued with rotations and posses efficient stationary point guarantees (Daskalakis et al., 2021 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 problemss in deep learning. Importantly, approach is compatible with any black-box optimizer, including ADAM and its variants (Kingmal 2014), so long as they are effective at descending scalar loss. Our approach guarantees convergence by leveraging the hidden structure commonly found in machine learning.

---

Published as a conference paper at ICLR 2025
More precisely, many applications admit hidden structure corresponding to the following problem: find 2, such that (F(.,). =2.) 2 0 A2 E = cl(g(() : A R
(1) where the mapping g : IR + 2 C T maps model parameters to model outputs, and the set 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 Lipschitz.
In order to leverage the hidden structure in VI problems, we employ surrogate losses, which have been studied the scalar minimization case by Johnson Zhang (2020) and Vaswani et al. (202T), 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. 2015 2017 Abdolmaleki et al. 2018). Moreover, these surrogate loss approaches have been shown to improve data efficiency cases where evaluating F is expensive like interacting with simulator in reinforcement learning (Vaswani et al. 202T Lavington al. 2023)
Our approach reduces the VI in (T) to the approximate minimization of a sequence of surrogate losses {Le Hee, which are then used to produce sequence of parameters (0,)een: To ensure con- vergence we propose a new a-descent condition on l, allowing for 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 f,- With our a-descent condition we provide convergence guarantees to solution in the space of model predictions {2+ g(O:))eN + z, for sufficiently small o. Our general method is summarized in Algorithm [
Algorithm 1: a-descent surrogate
Input: Outer loop interactions T, initial parameters 01 E R&, step size 17 for surrogate loss, a' E (0, 1). optimizer update A L Rd - Rdd
for / f- to T do
Compute VI operator: (()()))
Set surrogate loss: (0) / (0) (g(0.) ((((0)))
0g +
while (0,) -> a² fj) do
Update parameters with optimizer: 0g + O(),,0.)
0.41 60, O,
return 0r+1
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 variety of experi- ments, 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 clear separa- problems when compared scalar minimiza-
tion in difficulty of using surrogate methods tion; specifically, we show that divergence is possible in strongly monotone VI problem where in contrast convergence is guaranteed the non-convex scalar minimization case.
We propose the a-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-hounded.
Unifying perspective of pre-conditioning methods. With our surrogate loss approach, we unify existing pre-conditioning methods (Bertsekas) 2009; Mladenovic al. 2022 Sakos et al. 2024) by showing they are equivalent to using the Gauss-
method as the optimizer A in Algo-
rithm D 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 and 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.
BACKGROUND AND RELATED WORK
Notation. We use (z, v) = Em x'y" to denote the standard inner product over R and ||ع||| = / 2)) 2)) to be the Euclidean norm. We write | mean Ex), and ||a||| ta is norm if and only
2

---

Published as a conference paper at ICLR 2025
if E is positive definite. For set X' we denote X its closure and X' its relative interior. For given set, which will be clear from context, we denote [I(x)) as the Euclidean projection of onto the set and similarly II=(x) the projection with respect to || |z=|æ. We use Id to denote the identity matrix. A matrix A has lower and upper bounded singular values if there exists min- maax E (0, oo) such that for any we have o min ||al? I (ar, A Ax) S o max | If matrix A is invertible we write A otherwise we denote the pseudo-inverse Dg(0) as its Jacobian evaluated at f. We say Dg has uniformly lower and upper bounded singular values if there a constant upper and lower bound to the singular values of Dg(0) for all 0 E Rd.
At. For given function g I - I" we write
Surrogate Loss Background. In the scalar minimization case such as supervised learning, a non- convex loss function of the form (((()) is minimized where the non-convexity is due to the model parametrization as represented by the model predictions: g(0) (0). ... g0
E RR.. In supervised learning, each prediction is 2' (0) h( 8), for some feature vector 2; and fixed model architecture h. Despite the non-convexity in parameter space O E Rd due to g. the loss function is often convex and smooth with respect the closure of the predictions 2 = clg(()) 0 E " [1 The optimization problem can then be reframed as a constrained optimization problem,
min f()(O))
(2). =E2
(2)
If Z is convex then projected gradient descent 2t-1 [ f is guaranteed to con- verge (Beck 2017). However, the projection II is expensive since it is with respect to the set 2 S R". In general, the model-dependent constraint Z may not be convex. Yet, this assump- tion 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 model is linear or with large capacity neural networks that can interpolate any dataset e.g. 2 = R" (Zhang et al. 2017).
Beyond supervised learning, similar hidden structure exists in losses within machine learning such as: generative models and min max optimization (Gidel et al. 2021). robust reinforcement learning (RL) (Pinto al., (017), and minimizing projected Bellman error (Bertsekas) 2009). However, in these applications the problem cannot be written as minimizing a loss and we must instead consider the VI problem ( For example, in the min-max case, the min and max players' strategies may be given by two separate networks h² (0') (62), respectively, with the following objective:
min max f(h (0*). (22)))) Ø:
(3)
02
where f is coneex-c Similar to 2 we can rewrite the problem in parameter space as a con-
strained problem with respect to model predictions but instead within the VI where 0 (01, 02)
and g(0) = (1- (,))),,,, (Q2)), with operator F(z)= (()(0) = [ f(z
V V. f(= ) where = h (0') and 22 h02)). The solution with respect to model outputs is then equivalent
to solving the constrained VI (I). If F is well-conditioned (e.g. Lipschitz and strongly monotone)
and Z is closed and convex, then the projected gradient method 2441 11(z - (z))) converges
to solution 2, with an appropriate stepsize 1) (Facchinei & Pang 2003
To solve problems of the form and take advantage of the structure given by 9 and F, we extend the idea of surrogate losses (Johnson & Zhang] 20200] Vaswani et al. 202T). where parameters are selected by descending a sequence of surrogates (0) that approximate the exact projected gradient
method. More precisely, at iteration i, l.+1 is selected by descending the surrogate loss:
(0)) - - | 1l - (o(0)) ())(())))
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 2++1 = g(((=1) = II(:: r/ (=x)), the exact projected gradient step, and guarantees convergence of (=+ ((0,)) to Z..
Surrogate losses in scalar minimization. The surrogate losses proposed by Johnson & Zhang 2020 and Vaswani et al. (002)), apply to supervised learning and RL respectively P
They did not
We 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 hut its closure includes the whole simplex.
Note that Johnson & Zhang (200)) and Vaswani al. 2021) more generally use Bregman divergences.
3

---

Published as a conference paper at ICLR 2025
study the VI case, nor do they exploit any convexity properties in the scalar minimization case. Lavington et al. (202)) also study the scalar minimization case and provide convergence to a neigh- bourhood of global minimum of 2 and allow for stochasticity. The neighbourhood of convergence depends on an upperbound on the errors et = | 2/ ll. where 2 is an exact projected gradient step. Therefore, the neighbourhood of convergence scales with the worst emor 6 across the trajec- tory { = ((.))) 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 2022). For example, if 2 = T(2)) where T is a contraction, then c - is sufficient to guarantee convergence (see Proposition (A.5).
In contrast to the existing surrogate loss approaches, we propose simple a-descent condition on & (Definition 2.1 that does not require all errors to be bounded or summable apriori. This condition allows for convergence without fully minimizing l and better models implementations in practice where a fixed number of gradient descent steps are used for each l.-
Definition 2.1 (a-descent). Let & be the surrogate defined in 4 and E inf oe 4()). The
trajectory {0, TEE satisfies the a-descent condition if at each step the following holds
(((++))) a² (l)(0)) ft) a a (0.1).
(5)
Given the a-descent condition we can define a general purpose algorithm (Algorithm D black-box optimizer update A and double-loop structure, we construct trajectory that satisfies the condition so long as A can effectively descend the loss l. In general E may not be zero and so this condition cannot be verified directly, however, this condition can often be met via first-order methods for fixed number of steps or can be approximated with f =0. 0.
With any
From a theoretical perspective, we show that the a-descent condition guarantees the following:
|| - =f S anl] F(z.)ll,
(6)
for a proof see Lemma A.2 As expected, the errors are controlled by a and the stepsize n in the surrogate. However, the eтror also scales with the distance to the solution if F is Lipschitz.
In the unconstrained scalar minimization case, inequality (6) is similar to the relative error condi- tion llp: (2))l < {f()) used in biased gradient descent, where pt is the biased direction (2++1 = 2, 1---) p.) (Ajalloeian & Stich 2020 Drusvyatskiy Xiao 2023). Similar to biased gradient descent, our assumption with any < 1 sufficient to guarantee convergence in scalar minimiza- tion with any L-smooth non-convex loss ʃ (see Proposition A.3). However, for VIs, a < can still
lead to divergence due to possible rotations in the dynamics of 27 (see Proposition 3.3
Within the context of solving VI probleems, approximate the proximal point algorithm where 2? dition would induce an inner loop with multiple evaluations of F, which can be expensive in many applications such as reinforcement learning /Vaswani al.) (222). They also show that divergence is still possible under their condition unless an extra-gradient like step is performed. Unfortunately. such step is impractical in our setting it requires minimizing a surrogate loss exactly.
& Svaiter (1999) proposed a similar condition to
7 (27 However, verifying their con-
Hidden monotone problems and preconditioning methods. In scalar minimization problems, hidden monotone structure has been studied under hidden convexity (Bach) 2017; Xia 2020
Chancelier De Lara 202T, Fatkhullin al., 2023). In zero-sum games with hidden monotonicity, Gidel et al. (022)) 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 hidden strictly convex-concave structure,
et al. (202T) prove global con- vergence of continuous time gradient descent-ascent Similarly, MMadenovic et al.] (2022) 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. (2024), the preconditioned hidden gradient descent method (PHGD), to solve VIs of the form
One step of PHGD corresponds to the update:
8.41 0, n(D(((.)) Dg(B)) F(x).
Thhe assume ||=++1
(z+ 1)((2++)))I < al|z++1 zell-
4

---

Published as a conference paper at ICLR 2025
PHGD and stochastic variants were also studied in the linear case by Bertsekas 2009 PHGD can
be viewed as a discretization of a continuous flow that guarantees 2t+1 = 24 (2) as 4
(Sakos et al. 2024). Interestingly, in Section 4 we show that PHGD is also equivalent to taking one
step of the Gauss-Newton method (GN) (Björck 1996) on the surrogate loss.
CONVERGENCE ANALYSIS UNDER a-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 (T.
Assumption 3.1. In the VI (T), E is convex. There exists a solution within the relative interior, 2, E ri 2. F both L-Lipschitz [| F(y)ll S L| - yll and j--troogly monotone (F(x)- F(y), v) p y/1 for any z, Z and some μ >> 0.
This assumption is commonly used in the VI literature establish linear convergence of the pro- jected gradient method 2 = [1 (24)) (Facchinei & Pang, 2003). In the scalar minimization case this assumptions implies F(z) = f=()) for a scalar loss function f 'that is j--stronglycoovee and L-smooth. In min-max optimization with hidden structure, such as (3), Assumption (3.1) is sat- and smooth (each players' gradient is Lipschitz with respect to all players, e.g. see Bubeck et al. (2015)). 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 2 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 (2 = [0, 1j"). The latter has been reported with large enough neural networks (Zhang al. 2017) and kernels (Belkin et al. 2019).
isfied if [(= =²) is groongy--conve--cnne.
3.1 CONVERGENCE AND DIVERGENCE IN THE DETERMINISTIC CASE
Convergence for sufficiently small a. Below we provide a linear convergence result if a small enough by controlling the stepsize 7) in the surrogate loss l. Note that the convergence is with respect to 21 .g(+)) and is linear in the number of outer loop iterations of Algorithm |
Theorem 3.2. Let Assumption 3.1 hold and let {2r g(0)) be the iterates produced by Algo- rithm 7 a and are picked such that p= == 1 2n111 - aL) + (1 a 1,2 < then, z converge linearly the solution 2. the following linear rate:
|| - 20 S 11 2.1
(8)
2(m=oL) then p < 1 and if a S # and n Particularly, i < I. and n (1+a3)13
24 512
then p S 1
#²a
512-
Note that, to obtain practical convergence rate (e.g., bounding the number of gradient compu- tations), we need to bound the number of inner-loop steps in Algorithm ! required to obtain the condition (5). In general, we cannot provide any global guarantee 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 1985 Nemirovskij & Yudin 1983). However, many classes of over- parametrized models are known to be able to interpolate random labels (e.g., neural networks (Zhang al. 2017). kernels (Belkin et al., 2019), or boosting (Bartlett al. 1998)) which is strong evi- dence that, in practice, the condition (5) can be obtained with few gradient steps. The latter is also supported by our experiments in Section
Divergence with convergence (Proposition A..3). D. However, despite our strong monotonicity assumption we show that < 1 can still give divergence in the VI setting. This shows that a being small enough not only sufficient but is necessary for convergence. Our example demonstrates the additional challenges of using surrogate loss in the VI setting. Our construction uses the min-max problem min, max, f + xy fy² and showing that gradient descent-ascent on the loss f(z, v) zy satisfies the a-descent condition with 1/v2 but diverges for any 1).
1. In non-comve smooth scalar minimization, a < 1 is sufficient for
Proposition 3.3. There exists an L-Liscchitz and ststoonglyy monotone F, and a sequence of iterates {Ee)IeN verifying the alpha descent condition with < such that 2t diverges for any 1)
5

---

Published as a conference paper at ICLR 2025
3.2 UNCONSTRAINED STOCHASTIC CASE
For the stochastic case we assume Z = R", the predictions can represent all of IR.. 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 2 = R", no projection is needed for 27, and the minimum of the surrogate & is the gradient step 27 = 2, nf (z)). We also assume the standard setup, the possibility to generate independent and identically distributed realizations (21,E2,-..) of a random variable & such that Fş(z) is an unbiased estimator of F(z). For the noise, we define o² = Ee (e )]"]] and use the expected co-coercive assumption from Loizou al. (202I):
Assumption 3.4 (expected co-coercivityf. Be [[]]((=)1P]] S
2222 for all = E Z.
Without access to the true operator in the stochastic case, a different a-descent condition is re- quired using the stochastic estimate Fs, (z+). Instead & 4 we will use the loss l, an approxima- tion of projected stochastic gradient step, (,(0) = (lla(0) (o(O0) - FFFe (=+ or equivalently
112 (,(0) = 11 (z)I1 + (Fe. o(o,) + [lo(00) g(
2
In practice, minimizing & exactly is impractical if is very large due to the sum of squares (lx(0) (00,)ll² in ( Therefore we assume it can be minimized on expectation with the following assumption.
Definition 3.5 (a-expected descent). The trajectory {0s heN satisfies the a-expected descent condi- tion if at for each t the following holds: given Fs, (21), the parameter 0141 is generated such that
E (0((0+)) - 83] s a² (ē.(0))) - (7)
Similar to the deterministic case, can prove linear convergence to neighbourhood.
Theorem 3.6. Let Z = IR",, and Assumption (3.4) hold. Fe(x) is L-Lipschitz and 17 S 2(1- where 2(1 + 2²) then any trajectory {0. (ee) satisfying the o-expected descent condition guar- antees:
[ Ze41 2. [] E [+ z.
nn (1- + +
If we take 4 and 17 < 1/10z then have convergence neighbourhood if VTJ.. Theorem 3.6 provides a generalization of Loizou et al. (202I) 4.1] where 2+41 follows a random biased direction P. that on expectation guarantees E pp F2 (=(] < a² (2))l. In comparison to the stochastic results of Lavington et al. (2023. , they avoid the assumption = R" by using a different surrogate. However, their result only applies scalar minimization.
4 A NONLINEAR LEAST SQUARES PERSPECTIVE
The surrogate loss perspective and our a-descent condition allows for convergence so long as the surrogate losses (eE are sufficiently minimized. One approach to minimizing & is to view it as the following non-linear least-squares problem
min f(0) = min 1 2 [|(()))
(10)
with residual function Rdd - RR, where (,) f(0) if rf g() ((.)) ()
Due to the specific structure of ff we can consider specialized methods such as Gauss- Newton (GN), Damped Gauss-Newton (DGN), and Levenbergh-Marquurl
(LM) (Björck 1996: Nocedal
& Wright 1999). These methods can be viewed as quasi-Newton methods that use a linear approx- imation r. r(0) r(0.) + (r(0.)(0- Ot).
The GN method is defined by the update rule 0,+1 = 0, (Dr(O.) (r.)))) Tr()). GN inherits the same local quadratic convergence properties as Newton's method when the Hessian at
Note that this is exactly expected co-coercivity but implied by Loizou et al. 2021 Lemma 3.4).

---

Published as a conference paper at ICLR 2025
the minimum f(0.) = Dr(0.)TDr((e However, GN is known to struggle with highly non- linear problems, those with large residuals, or if Dr(0t) is nearly rank-deficient (Björck 1996). Fortunately, the GN direction is a descent direction of f, the DGN method takes steps the GN direction with a stepsize parameter JGNN and converges for a sufficiently small stepsize or with line search (Björck 1996). In cases where Dr(Ot) 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 0f as It intermediate step between 0c+1 and Og we have the following:
g-+1 f Dg()) (g(0)) g(O,) + (F((())))
(Surr-GD)
0,+1 1 = f TaN Now (Dg( Dg((t))) ( (g(0t)
g(0.) + ()(()(())
(DGN)
0f+1 O2 (Do(0f) Dg(Of) (y()) (o(0?) - g(0,) + ())((())
(LMM)
Note that we used the fact that Dr = Dg( and if JGN = then DGN is the same as GN, Also, note that one step of GN recovers exactly the PHGD method proposed by Sakos al. (2024).
4.1 FAVOURABLE CONDITIONS FOR GRADIENT DESCENT
Several conditions allow for fast linear convergence of gradient descent for (e() -f; see for exam- ple Guille-Esccreet et al. (202T) Under linear convergence, s-steps of gradient descent guarantees p for some p E [0, 1), therefore any target value of a is achievable in a finite number of steps that depends only logarithmically in a. In this section, we show how assumptions used in Sakos itt al. (2024) imply two common assumptions for fast convergence of GD: the Lojyykk--ojsiwiizzz (PL. condition (Polyak 1964 Eojasiewiez 1963 Definition B.2) and T-ssmothhness.
The four assumptions made by Sakos et al. (2024) to study the behaviour of PHGD are: (1-2) D9 has both uniformly lower bounded and upper bounded singular values, (3) each component function is 3-smooth, (4) and that Z is bounded In Proposition 4.1 we show that globally lower bounding the singular values of Dy" guarantees that the composition of a PL function I with g is still PL.
Proposition 4.1. Assume f satisfies the J-PL condition, and let T be a lower bound on the singular values of Dg(0) Then, f fog g is mimm"""
This implies that the surrogate loss l, is PL since l = ft g where ft(z) 1/21== 1/ Similarly, & can be shown to be L-smooth if Dg" has uniformly upper bounded singular values, each 9: is 3-smooth, and Z is bounded (see Lemma B.I However, these 4 assumptions cannot hold all at once. In Prop. 4.2, we show that the first three assumptions (1-3) hold, then Z is unbounded. Proposition 4.2. If ddd + IR" is differentiable where is 3-smooth and Dg(0)T has globally lower and upper bounded singular values, then {g(0)= 0 E 12d) is unbounded.
ue is L-PL.
This contradiction suggests that the lower bounded singular value assumption is strong. Indeed, forces the dimension of the parameter space d to be larger than the dimension of the prediction space n, and if is linear then it must be surjective 2 = R". In the case n = d, it enforces Dg to be invertible everywhere, which is violated in important cases such as softmax.
5 EXPERIMENTS
We consider min-max optimization and policy evaluation to demonstrate the behaviour and con- vergence of surrogate based methods with hidden monotone structure. For min- max optimization we compare different approaches from Section 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.
X on two domains from Sakos et al. (2024): hidden
5.1 MIN-MAX EXPERIMENTS
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.
'The set Z (note that Z is the "set of latent variables" denoted as X' in Sakos et al. 2024 ) is assumed to be bounded in their I Lemma 4 "template inequality". More precisely, the existence of a constant D = diam(X)
(i.e. X' is bounded) is used in equation B.20 in Appendix Lemma 4 is then used in Theorems 1-4.
7

---

Published as a conference paper at ICLR 2025
PHGD
-DMimwcllze01100000 -DD
DGN 73,-0011,,,000000 - -M
Suur CDximer-5p-0.)
Sum GDinner-- 100.g-
0, trajectory
((Or) trajectory
1c(0c1))/1(00
0.8
10
0.8
0.6
16-11
0.4
0.2
0.0
S06
1600
2 0.4 0.6 0.8
1000
Outer loop itcrations
Outer loop iterations
Figure 1: Convergence of various algorithms from Section 4 on the hidden matching pennies game. PHGD and GDA as presented in Sakos et al. (024) are compared against GN, DGN, LM, and GD. (left) Linear con- vergence 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
((..)) is illustrated the considered methods.
Hidden Matching Pennies. The hid- den matching pennies game is zero- sum game the form (3). where each player has the parameterization (0) = sigmoid(aa CELU(a)()), The convex-concave objective f is given by f(z 22) = (2z 1)(22² 1) + 0.75
Sun www.iiiimmmnnimm. (0pee Sun-t
Player
Player 2
(,(% F.((00)
(( 1/2)2 (=²-1/2)9)) The pa-
1/2)²).
2.112
10-1
100
rameters af are chosen to approximately replicate the trajectory of PHGD presented in Sakos et al.] (2024) Figure 4) (see Ap- pendix [.I for more details). In Figure I we observe that PHGD converges linearly in the squared distance the equilibrium, but performs poorly if multiple inner steps are taken (GN with 5 inner steps). If is increased by order of magnitude, PHGD is observed to diverge; how- ever, convergence possible via DGN with the same n), with multiple iterations and an appropriate choice of JJDGN- In contrast to GN, LM is more stable with a larger 7 and converges faster than PHGD/GN. Finally we tested GD for a different number of inner steps with v) = 0.1. Convergence observed for GDA albeit slow. The benefit of multiple steps is clear, with 10 inner steps outperform- ing PHGD and only surpassed by LM. Although more inner steps increases the computational cost, it is marginal when compared evaluating F (see Fig. Interestingly, Fig. (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 larger loss ratio than GD with 100 steps but converges faster to the equilibrium.
0.5
16-1
500
1000
500
1000
Outer loop iterations
Outer loop iterations
Figure 2: Convergence in the hidden rps game.
Hidden rock- pakk--ppp--scsoors.... In the hidden rps game each player's mixed strategy in rock- paper-scissors is parameterized. Where player i's strategy 2* is given by the function h²(() softmax( AG CELU(A)
with 0² E R and randomly initialized matrices: Ai E R4x5, and A IR 1x Figure demonstrates the behaviour of various algorithms for fixed initialization of (0', 0²) and the matrices A3. 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 LM and GD degrade in performance if too many inner steps are taken, with one and 10 inner steps outperforming and 100 steps for LM and GD respectively.
necessarily corresponding to the methods with the lowest loss ratio. Both
5.2 MINIMIZING PROJECTED BELLMAN ERROR
For our RL experiments we consider the policy evaluation problem of approximating value vec- tor U2 E IR", representing the expected discounted return over n states for a given policy æ and Markov decision process (MDP). To this end, we consider common approach policy evaluation: minimizing the projected Bellman error, which a fixed point problem associated with temporal difference learning (TD) (Sutton 1988). 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) 1995
8

---

Published as a conference paper at ICLR 2025
Antos et al.
2008 Bertsekas (2009) showed that minimizing PBE is equivalent to solving smooth
and strongly monotone VI problem of the form ( where F2)) = E(z - TT(2)) (Bertsekas) 2009)
Tr I" R is the linear Bellman policy evaluation operator defined over all states (s'
in given MDP and defined as (=) = f + 7 2, where In= is the associated expected reward vector each state and P* is the state to state probability transition matrix given by the MDP and т. is the diagonal matrix with entries corresponding to the stationary distribution & E Iº of states according л. The constraint Z in this case is the set of all representable value functions. With respect to 0, solving the VI associated with minimizing PBE is equivalent to finding the fixed point:
(vo(s") (r=( PB [uo. (s))ss))) )
0, E arg min BE 0.) = E
(1I)
==1
where ug is the predicted value vector given parameters 0. See Appendix D for more details.
5.2.1 LINEAR APPROXIMATION
Parameter error [|0 - O2perll
107
For our linear RL experiments, we consider a slow-mixing 100-state Markov chain from Bertsekas
30-1
(2099 and Yu & Bertsekas (2009). Using linear model. g 40 with Rd & Raxd and d < n. Bertsekas (2009) proposed several methods leverage the hidden structure in F. Sim- ilar to Sakos et al. (2024), the proposed methods are presented via preconditioning schemes that ap- proximate projected gradient step in the space of representable value functions Z. [Bertsekas] (2009) suggests performing the deterministic and stochastic PHGD-like updates:
10-1
10
10-
Sun-GD, inner m1
GD, luner -d
Sun-GiD Inner =10
Outer loop iterations
The average approximation error be- tween GD the surrogate (14 Sur--GD) and up- date (13) over 10,000 runs in slow mixing 100- state Markov chain from [Brttskaas] (2009) and Yu
Figure 3:
B,+1 = 0 (4 - F(z)),
(12) & Bertsekas (2009) Example 3). Surr-GD is ob- served converge to the exact update (13) with
0,+1 1 - (C,0- ft).
(13) faster convergence for more inner steps.
The deterministic update is expensive, requiring the full feature matrix Φ. Hence, Bertsekas (2009) constructs online sequence of estimators [1e,,,,, (CeHee, and {A: from trajectory and suggests the stochastic update (3) Although this method applies more generally, in the context of
solving II update (13) equivalent least-squares policy evaluation (Bertsekas & loffe 1996).
Equivalently, update 12) can be seen as one step of the generalized Gauss-Newton method (Ortega & RReeinboldt 2000) on the surrogate (0) 1/2| hb Tx (bb.))l 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 be a contraction (Bertsekas) 2012).
Similar to the deterministic update, we show that the stochastic version can be shown to be the min- imizer of a surrogate loss (f). whose minimizer is the exact update (13). The stochastic surrogate & and its gradient, derived in Proposition D.1 are
1 (.()) - 2 00 - - (2))
-0) D. 0z).
(14)
where E and T. correspond to the natural estimators using the empirical distribution (see Appendix for more details). Instead of minimizing the loss exactly it can be approximated with GD, thus intractable. Figure demonstrates the
avoiding the matrix inversion D which can make
13
effectiveness of approximating update (13) via GD the surrogate & 14
5.2.2 NON-LINEAR PROJECTED BELLMAN ERROR
For the non-linear setting, approximate the value function of fixed reference policy with a two- layer neural network in two Mujoco environments, Ant and Half Cheetah (Todorov et al. 2012). These environments characterized by continuous state and action spaces, where the agent must

---

Published as a conference paper at ICLR 2025
Thresholded Sum a'-0.5, Inner=50
Sum- CD with double sampling. g. Inner550
Sum-iD, Inte=10
Sun-0D, Inter 000
Sun-GD with doutle sampling, inrer=10
Sun-CD with double sampli inner=1000
Sun-dD, inter-50
TDO (SursDD, inner=
Prediction Ertr
Outorioop Based Comparison (4r
Wallcbokk Time Based Compartson (Ant
30
08
Outeffoop Iteradins
Walldbok Time (seconc3)
Outarfoop Sased Compar ison (Half (hestahwel)
Walldock Based Compatison [Half Cheelahrof)
Valuw Prdetionn
Prodiction
16' Outarfoop Iteradios
Walldoock Time (secondi))
Figure 4: Comparison of average performance of TD(O) and surrogale methods 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.
control high-dimensional, physics-based simulations to achieve locomotion tasks. The reference policy derived by training a policy network with the soft-actor-critic algorithm (Haarnoja et al. 2018). For each environment, we consider two different surrogate-based methods with TD()) as a special case. Similar to the linear case, we aim to find the fixed point (II), and consider the surrogate (f) = 1/2l/09 - ( However, due to the large state spaces we must instead consider miniziming the stochastic surrogate &g (9) from Section 3.2 Notice that l consists of two main parts: an inner product term that is linear in Ug = g(f), and a squared error term ||00 Up uo,11² 1|² Our two surrogate methods use different estimates for the linear and error term.
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. (2023) for scalar minimization, and introduces bias due to approximating the squared error term across all states with states seen in the batch. With this approximation we perform either a fixed number of steps (inner = # steps) or an adaptive number of steps depending on loss ratio (Thresholded Surr-GD). Taking one step recovers a batch version of (D(0), for more details see Algorithms 2
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 the gradient. For more details see Algorithm 3
All methods are evaluated with value prediction error, the squared error for a test sample of 10,000 states visited by fixed reference policy. The values in these test states are approximated by 10 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 meth- ods converge lower prediction error than TD(0), as indicated by the red dashed line.
Although the inner loop in the surrogate methods requires more gradient computations, the compu- tational overhead is marginal when compared to environment interactions, a common bottleneck in RL tasks (Vaswani et al. 202T). We observe that increasing the inner loop size improves data effi- ciency at the 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 in- equality problems with hidden monotone structure. We have presented a novel a-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 meth- ods 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(O) that are more data and run-time efficient in the deep reinforcement learning setting.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
We thank Nicolas Le Roux, David Kanaa, losif Sakos, Andrew Patterson, Khurram Javed, and Arushi Jain, for helpful discussions and feedback. This work was supported by Borealis Al through the Borealis AI Global Fellowship Award.
REFERENCES
Abbas Abdolmaleki, Jost Tobias Springenberg, Yuval Tassa, Remi Munos, Nicolas Heess, and Mar- tin Riedmiller. Maximum a posteriori policy optimisation. In International Conference on Learn- ing Representations, 2018.
Ahmad Ajalloeian and Sebastian U Stich. On the convergence of sgd with biased gradients. arXiv preprint arXiv:2008.0000 00051, 2020.
András Antos, Csaba Szepesvári, and Rémi Munos. Learning near-optimal policies with bellman- residual minimization based fitted policy iteration and single sample path. Machine Learning, 11:89-129, 2008
Francis Bach. Breaking the curse of dimensionality with convex neural networks. Journal of Machine Learning Research, 18(19):1-53, 2017. URL http::/ttt/mmtt// http:////mm...rrr/pppessss/s////
14-546. html
Leemon Baird. Residual algorithms: Reinforcement learning with function approximation. In Machine learning proceedingy 1995, pp. 30-37. Elsevier, 1995.
Peter Bartlett, Yoav Freund, Wee Sun Lee, and Robert Schapire. Boosting the margin: A new explanation for the effectiveness of voting methods. The annals of statistics, 26(5):1651-1688) 1998.
Amir Beck. First-order methods in optimization. SIAM, 2017
Mikhail Belkin, Alexander Rakhlin, and Alexandre B Tsybakov. Does data interpolation contra- dict statistical optimality? In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 1611-1619. PMLR, 2019.
Dimitri Bertsekas. Dynamic programming and optimal control: Volume I, volume 4. Athena scien- tific, 2012.
Dimitri Bertsekas. Projected equations, variational inequalities, and temporal difference methods. Lab. for Information and Decision Systems Report LIDS-P-2880 MIT, 2009.
Dimitri P Bertsekas and Sergey loffe. Temporal differences- policy iteration and applications in neuro-dynamic programming. Lab. for Info. and Decision Systems Report LIDS-P-2349, MIT; Cambridge, MA, 14:8, 1996.
Åke Björck. Numerical methods for least squares problems. SIAM, 1996.
Sébastien Bubeck al. Convex optimization: Algorithms and complexity. Foundations and Trends@ in Machine Learning, 8(3-4):231-33 (5344)2311357,2015 2015.
Jean-Philippe Chancelier and Michel De Lara. Conditional infimum and hidden convexity in opti- mization. arXiv preprint arXiv:2104.05200 10.005266. 2021.
Ching-An Cheng, Jonathan Lee, Ken Goldberg, and Byron Boots. Online learning with continuous variations: Dynamic regret and reductions. In International Conference Artificial Intelligence and Statistics, pp. 2218-22122 2228, PMLR, 2020.
Constantinos Daskalakis, Stratis Skoulakis, and Manolis Zampetakis. The complexity constrained min-max optimization. In Proceedings of the 53rd Anmual ACM SIGACT Symposium Theory of Computing, pp. 1466-1478, 2021.
Dmitriy Drusvyatskiy and Lin Xiao. Stochastic optimization with decision-dependent distributions. Mathematics Operations Research, 48(2):954-99) 2023.

---

Published as a conference paper at ICLR 2025
Francisco Facchinei and Jong-Shi Pang. mentarity problems. Springer, 2003.
Finite-dimensional variational inequalities and comple-
Ilyas Fatkhullin, Niao He, and Yifan Hu. Stochastic optimization under hidden convexity, arXiv preprint arKiv:2401.0010 2023.
Barbara Franci and Sergio Grammatico. Convergence of sequences: A survey. Annual Re-
views in Control, 53:161-186, 2022. ISSN 1367-5788. doi: https://boi.ory/100006fjjji..
2022.01.003 URL https:/ /ww. sci scissciienesss encedi rect wtt.cooo//c..c....c wwt.///cceenc///rttillle/pp
91367578822000031
Gauthier Gidel, David Balduzzi, Wojciech Czarnekki Marta Garnelo, and Yoram Bachrach. A limited-capacity minimax theorem for non-convex games or: How i learned to stop worrying about mixed-nash and love neural nets. In International Conference on Artificial Intelligence and Statistics, pp.
PMLR, 2021.
Charles Guille-Escuret Manuela Girotti, Baptiste Goujaud, and Ioannis Mitliagkas. A study of condition numbers for first-order optimization. Arindam Banerjee and Kenji Fukumizu (eds.), Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, volume 130 of Proceedings of Machine Learning Research, pp. 1261-1269. PMLR, 13-15 Apr 2021. URL https: Ntttps://proceedingg mir. www.eppeess/eee / 30 gui escuret22s html
Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with stochastic actor. In International confer- ence on machine learming, pp. 1861-1870. PMLR, 2018.
Lars Hörmander. The analysis of linear partial differential operators III: Pseudo-differentin oper- ators. Springer Science & Business Media, 2007.
Rie Johnson and Tong Zhang. Guided learning of nonconvex models through successive func- tional gradient optimization. In Hal Daumé IIII and Aarti Singh (eds.), Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learn- ing Research, pp. 4921 4930. PMLR, 13-18 Jul 2020. URL htLL:ttttt////poceeeiiii mir. html
Diederik Kingma. Adam: A method for stochastic optimization. arXiv preprint 11Xiv:1412.6980, 2014.
Jonathan Wilder Lavington, Sharan Vaswani, Reza Babanezhad Harikandeh, Mark Schmidt, and Nicolas Le Roux. Target-based surrogates for stochastic optimization. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett (eds.), Proceedings of the 40th International Conference on Machine Learning. volume 202 of Proceedings of Machine Learning Reseurch, pp. 18614-18651. PMLR, 23-29 Jul 2023. URL html.
https://proceedi ngs m 120
Nicolas Loizou, Hugo Berard, Gauthier Gidel, Ioannis Mitliagkas, and Simon Lacoste-Julien. Stochastic gradient descent-ascent and consensus optimization for smooth games: Convergence analysis under expected co-coercivity. Advances in Neural Information Processing Systems, 34: 19095-19108, 2021.
Stanislaw Lojasiewicz. Une propriété topologique des sous-ensembles analytiques réels, 1963.
Andjela Mladenovic, losif Sakos, Gauthier Gidel, and Georgios Piliouras. Generalized natural gra- dient flows hidden convex-concave games and GANs. In International Conference Learning Representations, 2022. URL httpp:://ppe.rreeeeeee wtw.://www........o.ooooeeoooaoa
net htt/://oommmiiiii
Mehrnaz Mofakhami, Ioannis Mitliagkas, and Gauthier Gidel. Performative prediction with neural networks. In International Conference on Artificial Intelligence and Statistics, pp. 1 11079-11093. PMLR, 2023.
Katta G Murty and Santosh Kabadi. Some np-complete problems in quadratic and nonlinear programming. Technical report, 1985.
12

---

Published as a conference paper at ICLR 2025
Arkadij Semenović Nemirovskij and David Borisovich Yudin. Problem complexity and method efficiency in optimization. 1983.
Jorge Nocedal and Stephen J Wright. Numerical optimization. Springer, 1999.
James M Ortega and Werner C Rheinboldt. Iterative solution of nonlinear equations in several variables. SIAM, 2000.
Juan Perdomo, Tijana Zmic, Celestine Mendler-Dünner, and Moritz Hardt. Performative prediction. In International Conference on Machine Learning, pp. 7599-7609, PMLR, 2020.
Lerrel Pinto, James Davidson, Rahul Sukthankar, and Abhinav Gupta. Robust adversarial reinforce-
ment learning. In International conference on machine learning, pp. 2817-2826. PMLR, 2017.
Boris T Polyak. Gradient methods for solving equations and inequalities. USSR Computational Mathematics and Mathematical Physics, 4(6):17-32, 1964.
R.T. Rockafellar. Convex Analysis. Princeton Landmarks in Mathematics and Physics. Prince- ton University Press, 1997. ISBN 9780691015866. URL fttpp::/booos..ooo wwwgle.ooooggcooooooooo
books?iddwj4Fa44 V7QC
Iosif Sakos, EmaaanuuilVVsileioos
Vasileios Vlatakis GaanuiiiGGaragkouiii. Panayotis Mertikopoulos, and Georgios Piliouras. Exploiting hidden structures in non-convex games for convergence to nash equilibrium. Advances in Neural Information Processing Systems, 36, 2024.
John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In International conference on machine learning, pp. 1889-1897. PMLR, 2015.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347, 2017.
Mikhail V Solodov and Benar F Svaiter. A hybrid approximate extragradient-proxina point algo- rithm using the enlargement a maximal monotone operator. Set- Valued Analysis, 7(4):323-345, 1999.
Richard S Sutton. Learning to predict by the methods of temporal differences. Machine learning, 3:9 44, 1988.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Emanuel Todorov, Tom Erez, and Yuval Tassa. Mujoco: A physics engine for model-based control. In 2012 IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 5026-5033. IEEE, 2012. doi: 10.1 10.100//ROS.22122636111
Sharan Vaswani, Olivier Bachem, Simone Totaro, Robert Müller, Shivam Garg, Matthieu Geist, Marlos C Machado, Pablo Samuel Castro, and Nicolas Le Roux. general class of surrogate functions for stable and efficient reinforcement learning. arXiv preprint arXiv:2108.0588 2021.
Lampros Flokas, and Georgios Piliouras. Solving min-max optimization with hidden structure via gradient descent ascent. Advances in Neural Information Processing Systems, 14:2373-2386.. 2021.
Hamnanouil-Vasieeion VaatakisGGkarakkooii
Yong Xia. A survey of hidden convex optimization. Journal of the Operations Research Society of China, 8(1):1-28, 2020.
Huizhen Yu and Dimitri P. Bertsekas. Convergence results for some temporal difference methods based least squares. IEEE Transactions on Automatic Control, 54()):151--1531 2009. ISSN 0018-9286. doi: 10. (09/TAC.2009.022
2029.2000097. Funding Information: Manuscript received July 17, 2006; revised August 15, 2007 and August 22, 2008. Current version published July 09, 2009. This work was supported by National Science Foundation (NSF) Grant ECS-0218328. Recommended by Associate Editor Lim.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. International Conference on Learning Rep- resentations, 2017. URL wtI.httpss.... htttps:///pperreeeeeeeee eww net ftatt//frummiimmmm (os
13

---

Published as a conference paper at ICLR 2025
A PROOFS
Remark A.1. If g is continuous, and {g(0) : :0 E { is convex with as its closure, then the
least-squares surrogate loss (0) 211g(0) 2 + (2==)l admits unique point 27 2 such that
e = x + (=)))
and for any A
マ [ls(0) =/ s <e(0) - -i
where e = innfoRs' (0).
Proof. Let [(z) = 111== -() We have that f(=) (0) for all 0 Rd. Now consider the set 2 = cl(g(() 8 E R since it is closed and convex, we have that f has a unique minimum z because it is --strongly
1 (2 be the surrogate loss with respect to the predictions
convex. Furthermore, we have
- f()) 11))== f(z)).
Now since =7 E Z and 2 is the closure of (a(0) 0 E Rd,, there exists a sequence of parameters (OE) such that {= g(0)))eeN + 2 Therefore have that,
f(z;) lim f(z)) lim (0,) 2 G 2 f(2)). (-00
t0000
Where we have used the continuity of f and g. The last inequality follows because {g(0) 0 R4) C Z. Therefore E = [(+]) and the result follows.
Lemma A.2. I is monotone and z. is in the relative interior of the constraint Z, then
(v(),) - + < n?
2 [F(x)) - F(zx)l1?
Furthermore, under the a-descent condition (Definition 2. we have
|| =1'l - am/ ((() F(=))ll-
Proof. If 2, is solution then we have
(F(2z), 2.) - 0, Vz E Z.
If 2, is in the relative interior then for any E Z there exists À > such that z'= 6'=01- (1-1)2 Aea Z (Rockafellar [997) 6.4]. Therefore by optimality we have
0 (F(2.), '' 2-.) = (F(z), (1 A) + Az. - 2a) = (1 A)(F(2,), - -2,) S 0.
Where the last inequality follows from À > 1. A Altogether we have
(F(z.), 2 2.) = 0, V2 E Z.
Moreover, as consequence we have that for any two points z' E 2 (F(z.), 2²) (F(z.), 2x) (F(z.) ) 2n 2²) 0. Letting z7 be the exact projected gradient step and ((.)) the current iterate we have
(0,),) - Er = | (11m (2 - 2 + +
=n(((e))) 2x 27) ; =1 21l1
=n((((z)) - F(z.); zi) + ((F(2.)) z1)
- 1| 2
2
-F(((=))) - F(Z.), 2 - =)) 2 | - zx 1|
122 < _ (P((.)) F(2.)11
14

---

Published as a conference paper at ICLR 2025
Where the last two inequalities follow by: 2, being within the relative interior, and the inequality
(u, u) I [1lll 2p
| for any p > O.
By Remark A.1 and the a-decent condition,
2 2+1 zi1? s ((0++1) s a ( a² -1 F(z.))?
Proposition A.3. Let f R + R be L-smooth. For some g. Rd + R" define the surrogate loss
(0) 1 (l) ze [V=)2) where 2t g(0)). Then the a-descent condition (Deftnition
guarantees
f(2(+1) S f(z)) L(1 - aa²)(e
E7). -
If f is bounded below then {a - 27 JEE - 0. where 27 = IT( 1 V((=))
Proof. Let = -
- ((441)-f(z))
s (2)), 2411 - 21) + 1 2e11
2
L
Li - 2n 21+1 - -zz) +
|| - 12
2
T,
-11 - -zel1 + (21 - 21, 21+1 - Ex) + 2 [111 =2113)
L || - 2+11|3 - - 2012²)
2
= L (0(+)))) - ec(0,))
The second to last equality follows from expanding _11 - =zel2 = =1112411 - 2c + 2 - =2 Using the a-descent condition we have
(0++1)) - (e(O.) S ())()))(()))) ET),
yielding the first result. f is bounded below by some constant then we have:
T
4) 5 f(1) L(1 - -3((1()))))) f(z)) S f(21) Σ
Therefore the series Den (e(),) f converges with (0())) lt 0. By Remark A.1 have f1 z 1|2 < (((0.) f implying the result 2₁ - 0.
Let Assumption 3.1 hold and let {a, = g(0:))(eN be the iterates produced by Algo- rithm 7 a and n, are picked such that p== 1 27/(H - aL) + (1+ a²)m² L22 < then, z converge linearly the solution 2, the following linear rate:
Theorem 3.2
|| - 11 < p² |||| 12.
(15)
2(a-oL) Particularly, if < and 1) < ([402]12 then p < 1 and a S #t. and 1 = 2u
then p S 1
f
612
Proof. First note that by definition of Algorithm I the iterates 2, = g(0r) satisfy the a-descent property (Definition 2.1. therefore Lemma A.2 holds. Recall that 2; the exact projection update, is
contraction if 7 since
|| - =2 S n2ll 22
(16)
15

---

Published as a conference paper at ICLR 2025
where x² 11 2nμ + 2 Facchinei & Pang 2003
Theorem 12.1.2). For the remainder, assume
that 1j < 2u so that E [0. 1). Denoting Fr F(z)) and F. = F(z.), we have I
||=0-1 - 2 =
1 - 2. Z++1 =
2 - 2.11² 2(2++1 2/: 27 - 2.) + | 2 1|
I 2 2x 11 2 - =2illlz; 2.11 + ||++11 27
(eauchy-cchwar))
< || 2. 11 20m Fr F=ll|== 2.1 a
F.
(Lemma A.2
< || 2 212 + 20m 2=11 +a²12 - - 1+
(Smoothness of F and 1)
S x² Et - 2. + 20m =. 11 a²1 1 -- =2.1l
(Eq. 16
= 2| 2u 12 (1 2n + 2an + (1 + a² |m L²).
If < then
||--1 2x 11 1| 2x 2=1 11-27(m
+(1 + a2));(22 (p- (1-2)(u-at)+
Taking 7 < 2(p-aL) would guarantee a contraction. (1+a2)L2
a S R and taking 2I
2y 5L
we have:
0S4/D054/2 S
1
2nju + 20m + (1+ (1+a 12?
mp +
1
2 I?
17
4
2p
122
1
1
5L2
5L2
5L2
Proposition A.S. Take 8,41 to be approximate minima of (0). Suppose T = II o (Id FnF) is a contraction, if (0c+1) f - 0 then the induced sequence (z: g(,))ee converges, 2t - 2. where is the unique solution (I(2, F).
Proof. Let 24+1 be the approximation error between 2++1 and 2 the minimum of the surrogate l, (exact projected gradient step).
1 ||
zx
? ززا 2, + etl1
1
1
=2
112 2 + (z) - 2,, a)) + |leal?
2
030 1
2.11 ?1l=7 2=12 |cell1 + 1 |lcal
1
||
2p
xE(0.1)
x(1 p)
|| 1212 + (1+ (l.(0 ET).
1
$
Where we use the fact that | 12
|
1 (.(00)))) et from Remark A. Take any
P such that x(1 + p) < 1 then apply Lemma 3.9 Franci & Grammatico (0222).
Proposition 3.3
There exists L-smooth and p-strongly monotone F, and sequence of iterates {athe verifying the alpha descent condition with a < 1 such that zt diverges for any n,
Proof. Let consider the simple min max example with loss
min max 1 2 ry y.²
1
2
This problem be written VIP where z (x,, y) and the operator F is linear given by the matrix
1 1
=
16

---

Published as a conference paper at ICLR 2025
It is well-known that F is both smooth and strongly monotone with 2++1 24 (zs) being contraction for small enough 7) (Facchinei & Pang 2003). Now we consider a biased direction given by matrix P. that is 2++1 2, Pzz, then using the fact that & 0 the a-descent on the surrogate corresponds to the following bound
|| - + 1/== (n S a/11//211-
Despite being 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/concaviy of the loss. Our counterex- ample simply adds a bit of rotation that ensures a < but yet is detrimental to the convergence. Mathematically, we take P (Id =FQ)nF where Q is the rotation matrix
Q
With this construction we are guaranteed that or <
since
11 - P)zel = [|QQFEzll = Fz
where the last equality is due the the fact that Q an orthogonal matrix and therefore does not change the Euclidean norm of vector.
Now taking a = 1/v2 gives
P
Id
Y/2
22
7
1
v2
v2
17
0
n
0.
2
We have that E++1 = 24 Pz.
1 Ze has an a 1/v2 but yet diverges for any 17 > 0 since
the Eigenvalues of the linear system À = in therefore the spectral radius strictly greater than one. Note that these dynamics are equivalent to gradient descent ascent on the bilinear loss f(z u) =
zy, zy, which is known diverge for any stepsize.
Theorem 3.6 Let Z = RR, and Assumption (34) hold. If Fe(x) is L-smooth and nj 2(14c)T. where
2(1 + a²) then any trajectory {0: )eeN satisfying the o-expected descent condition guar-
antees:
B 2 - 2. 112] s SE [ - 2= (1 nn + a²) + (1
Proof. For convenience let (2+) Fr. Let 2 2, F and pt 2 - 2 Eo,,, denote the expectation over 2++1 = g(f++1) given 21, and & The expected a-descent condition in the unconstrained case is equivalent to
Ee
|| - 2 + P S 1
By concavity of the square root and the expected a-descent condition we have E and
[XX] S
V
[| - 24 + fn
= Eosty VIlee11 +
(17)
1 v IE
||z011 - n
(18)
$ am Fell-
(19)
17

---

Published as a conference paper at ICLR 2025
We also have the following bound
E0,+1 [112411 - z=|l]] Eot+1 || - 24 + nF. - 17E:11
(20)
s 10,+1
2/|2e41 - 2 + f +
(21)
s 2(1 + a )²)))'||F:1]
(22)
Next we expand and bound the distance 2112111 - 2011?.
1
1
2 ||
2=11²
2 11 Pt- - 11
2
11
(pe, 2$ - 2.) + |lpel|
2
2
2 - 2, 11a
(f 22 x.) + (nE - Pt: 2t - 2.) + 2 ||p:1
2
1
1
S
2 2. 2| 7( 21 2.) + |l pe 11 2011 + 2 31pp 11
2
1
1
2 2.11 - Fi, 2t z.) || 2 F.lll 2. +
2 || -zell2
2
Taking an expectation over 1 given 2e, and &. we have
1
19
2.11 + 2(1 + a a²))?²
Bi
1 22+11
2x
2 || zz -nnn 24 2.) + nal maIl Fell|
||Eb
m 2t 2.)) nall P |11 -- z. + en²
|| z.
|
2
|| - z. T 2t - 2.) + _
a²
1| - 1. + 17 + e) |A
where in the inequality we used
19 22 and in the second inequality c 2 2(1 + a²). Taking an
expectation given information up to time and using the expected co-coercivity assumption gives,
a²
72
E,
2 [++1
=.
2t 2. 1| (F 2.) +
||
2.
E, [1:11P]]
2
2
5.4
1
a²
2t 2, 112
() 21 22)
|| 21
1p- + L) 2 2.) + 17 + c)o²
2
a²
2 ||
2z 112
17 (1 17(1 + L) (Fi, 21 - 2,) +
1 - 2, 1 12 + c)o²
2
v(+t))
1
à²
|| 2, 1| nn (1 711 + c)L) || 2, 1
1 2 + r² (1 + c)o²
2
2
If we take 7 < 2[I+cL then we have the following recursion
F+41 z. |p] -11 - -2.1 (1 mu + a²) + 12 + c)o2
E2
Taking an expectation over 2, gives the result.
B NON-LINEAR LEAST-SQUARES
Lemma B.1. Let f()) = } 10)) where r Rd - RR, r(0) (r:(0), ... T.) (.)
Suppose
T0) is B-smooth and Dr(?) has singular values that globally upper bounded by Fmax 0. If r is bounded, then ff is L-smooth: there exists L > 0 such that [|V ff(e))l < Li 0l
for any 0,0' E Rdd
18

---

Published as a conference paper at ICLR 2025
Proof. Since each r; is B-smooth we have that
[|Dr(0) - Dr((') T Il - sup (Dr(O) Dr(O') yell )olll : E "R",|olle S
max [Vg.(t) - Vo.(6)) - L| 8'1
[VS(0) VS(00) [[Dr()) r(0) - Dr((') r(0'11
[| rr(0) Dr(0) (r(')) + Dr(0) r(()) - (r((0)r((()))
[i) rr(6) Dr(0) Dr(0)Tr(0") "r(0'] [ - Dr(0")
max [r(0] - r(0')l + [|Dr(0) - Dr(O) -1((01111a11((()))) 112111(00)|
1 max 0 1 + --111- - 0
Where the last inequality follows from r being mmax Lipschitz since (r(0)-r((')]] < |Dr
8'Il by the mean value inequality (Hörmander, 2007 and by the fact that |Dr(() max Since r is bounded it follows that there exists [|]( 3 C' for all 0.
Definition B.2 (Polykk 1964);
Eojasiewicz (1963)) ).
function R + satisfies the PL.
condition if there exists 0 such that for all x E R
[V 2 2p([(x)) f*),
(23)
where f" = inf geR= [(x).
Assume f satisfies the p-PL condition, and let Jmin be a lower bound on the singular values of Dg(0) Then, have J g min -I.
Proposition 4.1
Proof. We have that
f -(0)]l2 [Dg V 2- (2))))
2 oiin Vf(=)]1
(min((((2)) - inf inf(([( f(=))
min u (J(z) min ((=')
''EZ
a ((f(((() inf f(a(e))))
#'
Proposition B.4. gf Rd - Rd g(0) (0), ; In (0)) is differentiable where is B- smooth and Dy( has globally lower and upper bounded singular values, then (g(0) 0 E Rd) is unbounded.
Proof. We prove by contradiction. Suppose {g(0) : 0 E Rdd is bounded and denote Z as its closure which is also bounded. Then there exists v E R & Z. Consider the function f(() 7 (0) v Taking r(0) = g(0) v, we have Dr = Dg. and r; are still 3-smooth, therefore by Lemma is L-smooth. Since f is continuous and Z is compact, its minimum is attained, and thus there exists
2, E such that
2 1|2. v/12 inf f()).
#aRd
Moreover, there exists sequence (0r) such that g(O:) - z. since E is closed. By the smooth- ness of f it also follows that
V f()0)1
- f(0.)
inf f(0).
2L
6E
19

---

Published as a conference paper at ICLR 2025
Time for 10k Updates (s)
1.0
0.0
0.6
PHGD
GNG)
DGAr75)
(M(1)
LM110)
GDA
Sum-EDG)
Sum
Sum GDL100)
Figure 5: Time in seconds for performing 10,000 iterations of each method. The number in paren- thesis correspond to number of inner steps taken. As special case we have PHGD and GDA are equivalent to GN(1) and Surr-GD(1) respectively.
PH0DD)p0.J)
SGGNaanx-773-1004.. -0001)
GDAlm=
PH0DD)e11)
Hesjo j
Outer loop iteraiion
Figure 6: Average convergence for various surrogate methods from Section ii the hidden matching pennies game. The average computed over 1,000 trajectories each with randomly sampled parameters aj and 0g.
Since singular values of DT) are lower-bounded, there exists amin 0 such that [ Tell 2 @min||ul] Therefore we have
[V((1)11
0 lim f(0.) inf f(0) 2 lim DER4
2L
[Dg)(0,) (g((O)
-)ll
2 (lg(O:) v112.
lim
lim
2L
2L
which implies that z. = lim, ((,)) = and that v is indeed within 2 a contradiction!
20

---

Published as a conference paper at ICLR 2025
PHGD6)00.)
MMiimer-S.--011-00000
Sun Sur-GDXinnere GDXimncr=10,p0.
GDA()=0.1)
Sun--iDiimer-100. 100.
10-1
-P
10
0
2000
4081
6001
XD0
1000
Outer loop iterations
Figure 7: Average convergence for various surrogate methods from Section in the hidden rock- paper-scissors game. The average was computed over 1,000 trajectories each with randomly sam- pled parameters A} and 0g.
C MIN MAX EXPERIMENTS
C.I HIDDEN MATCHING PENNIES
In the hidden matching pennies game each player has the paramcterization h²(0) = sigmoid(a} CE)U(a) The parameters for each player are:
a = 0.5, and a = for player 1,
2 = 0.7, and a² = for player 2.
The parameters a1, o² were chosen approximately replicate the trajectory of PHGD presented in [akoos et al. 2024 Figure 4). The initial parameters O₁ were selected to be the same as those selected by Sakos
2024), 0, (0). 03) (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. On randomly sampled from two independent Gaussians with standard deviation of 4. Similarly, each az was randomly sampled from a uniform random variable with support [-1,
C.2 HIDDEN POCK-PAPER-SS PAPER-SCISSORS
Each player i's mixed strategy in the hidden rock socc-ppper-seisoors game is parameterized by the func- tion h²()@) softmax A CELU(A))"), with fi E RR. The min-max objective is f(2 22) (z A=²) 0.2 || 1| where = (z (=",²² 2²) and is the equilibrium of vock-paper-scissors (sam- ple rock, paper, and scissors with equal probability) (Sakos et al. 2024). Figure we observe average convergence across 100 random initializations of 02 E R and matrixes A for various sur- rogate based methods. 01 was sampled from 5 5-dimensional isotropic Gaussian while each element of A3, was sampled from uniform random variable with support 11.
D POLICY EVALUATION AND PROJECTED BELLMAN ERROR
In this section we provide some backeround on minimizing projected Bellman error (PBE) and the stochastic methods proposed by Bertsekas 2009). For given MDP with states (s² (st..... s"),
and policy иं we denote the expected reward 7= E R", discount factor y E (0, 1), and state to state probability transition matrix P. Raxn The associated linear Bellman operator is (z) Tx + yPa and is contraction Bertsekas (2012). The value vector V e R is the unique fixed point of T,, with ith component o' equals to the discounted return starting from state
21

---

Published as a conference paper at ICLR 2025
s', E, ( (21, Di= (s))ss)) s where we use (s) to mean r4 such that s and the expectation is over possible trajectories ($1: ..).
Under function approximation it may not be possible find fixed point of T and find the true value function. Instead we can consider the projected fixed point,
2x (T=((r
(24)
Where the projection is on to the set of realizable value functions Z {eg 0 R.. We use the notation to in place of g(0) to be consistent with the RL literature, the prediction for state s is (a(s*) (0)' E is the diagonal matrix with entries corresponding to the stationary distribution E ,..... (T) of Ps.
As pointed out by Bertsekas (2009), finding the fixed point 24 is equivalent to solving a VI of the form with constraint 2 and operator
F(z) = [(: - (z)).
(25)
Additionally, |ertsekas (2009) 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 2, the corresponds to finding parameters 0, such that
0, arg min BE(0,0.) - Σ (vo(s)) - (ra(s')- -/Bypp (6)1==)))
(26)
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, ming BF 0) and PBE. The fixed points of these objectives need not coincide even with linear function approxi- mation Sutton & Barto 2018).
Using the function BE and the stationary condition 266 we can define the following natural gap function
B B = BE 0) inf BE((',
(27)
Notice that B Egg
(f) 2 0 for all 0 and is zero and only if a fixed point of (26).
Since II= o Tn is known to be contraction (Bertsekas) 2012) but is expensive to compute exactly, we can devise a surrogate loss that approximates The operator IIg T' equivalent the scaled projected gradient method 2++1 surrogate loss
I1 - E- FF()), where 2 = Uo., and is minimum of the
1
(x(
2 1100 (un. - - FF=o))))))) 1
(28)
2 l00a Ta (V..)
(29)
Note that if = = Id than this is the same surrogate loss 44 with 1.
D.1 THE LINEAR CASE
In this section we assume that predicted values are linear, g0) = +0, with some feature matrix
(st)
E gnxd
T (s*)
In this case we have that the operator F is also linear in
F(z) F(Φ0)
E(00 70.00 - ==)==((
7P=0)0 E
22

---

Published as a conference paper at ICLR 2025
Since linear, there exists preconditioning scheme that generate sequence of parameters {6e) hen such that {*++ = 10 = [I= (2))) } and therefore is guaranteed to converge linearly. This preconditioning scheme is simply the minimizer of the weighted least-squares surrogate loss (()) = 1/2| (0:))
0 = 01 ( =Φ) - F(2)).
there is no unique minimizer then the pseudo-invers (Φ T E can used. To approximate the iteration Bertsekas (2009) suggests using estimators that depend only the history states (81,82, 82, S,, 8t+1/ 1) and rewards (ri,..., rr) to approximate the conditioning matrix & E and gradient Φ T F(z)). The following estimators are proposed:
D. = + ((s:)o
G = -
- -((s++1))
A + o(s:)r:
the chain fully mixed then the sampled states are drawn according to making the above estimators unbiased:
① T = Σ ((( = =E [D.]
Φ F(()) = Σ ('o(s)) (Pa)) - (r E [,, - nr
Where (Pa)s,o' is the transition probability to state s' when in state 8. Therefore the iteration
0 (C.) At),
eventually converges to exact deterministic iteration. Interestingly, the stochastic version can be shown to be the minimmum of the surrogate
E.(0) 11000 (
Where (=) = F with E, r, and P. being estimated with the empirical distribution. is visited in trajectory of length t as
More precisely, denoting the number of times that ns)), and the number of times is visited after a as n(s, then the empirical distribution over states is Ç (a(*))/,.... "n.......)))))))) n/t)))/E) and is the diagonal matrix with diagonal ğ. Similarly, the transition matrix is estimated by (Pa) = n(s, s')n(() if n(s) > O, and arbitrary otherwise. For convenience, we write {(st)=(3
Proposition D.I. The gradient of the surrogate loss (0) = 1 - (z))13 is
vū(00== - (,00) D -0).
If D, is invertible then its mininum is
0+1 =0= - -x)-
23

---

Published as a conference paper at ICLR 2025
Proof. By definition of E, we have that Dj = _ E, ((s))((s))) = =T Similarly, we have that C₂ = + ((s))(((s)) ro(5++1)))
= @ = - 7, Ei=1 ((5:)0(5:+1)) Where
1
1 Σ
7 2=1
((s))((((+11
n(s, (0())((())
(30)
1 Σ ((x)) Σ n(8,8')(b('))
(31)
1 Σ n(s)((s)) Σ
n(s,8')
n(s) ((8')
(32)
i
1 Σ n(8)((s))
_ (Pa)a
(33)
Σ {())(()) ((P)).
(34)
② EP,
(35)
Therefore C. = + T - -7, Similarly, A= = 1 Σi= Φ($,)r = - T
Now consider the weighted least squares loss
(() 60 (80/))1
The gradient of & is
(0) + T T- (b0,)) 2 TE(00 - -P, 10, F+)
(36)
Φ E(0 40, + 40, 7P, - -ix)
(37)
Φ E(00 20,) 4 E(40, Pp, 10,- - -rt)
(38)
(, 0,) + C, - ft
(39)
Setting the gradient to zero gives the minimum of &
D.2 THE NONLINEAR CASE
In this section, we detail the surrogate algorithms used for the nonlinear setting, as outlined in Algorithms 2 and 4 As complement Section 5.2, compare the convergence properties of TD(O) 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 no environment interaction.
and
In our deep learnin//nonlinaar setting, the state space is too large to verify if we have solved the VI 25 by the gu (2)) 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,, Tt, 1)+1) from a fixed reference policy Using these observations we construct an empirical estimate of BB 26
11
BF 6') = n
Σ (vo(s)) (r+ - your (8++1)))
(40)
We can then define the following fixed point problem: find 0, such that
E arg min BF. 0.).
(41)
Given this new empirical approximation of PBE we can define gap analogous 27
BE gapp((()) (8) (E 0) inf (E(6',
(42)
#'
24

---

Published as a conference paper at ICLR 2025
Threshelded Sur-GD, inner-50
Sur-GD, inner-50
Surt-GD,
(Sur=GD, inne=1]
SursGD, nnerm10
Gradient Based Comparison (Ant-v4]
Wallelock Time Based Comparison (Ant-v4)
10
Ballman Cap
1.4
12
28
30
Gradient Computations
(seconds)
Gradient Based Comparison (Half Cheetal-44)
Wallclock Time Based Comparison (Half Cheetah-v4)
Bellman Gap
1.44
Dellman
Gradient Computations
Wallelack (seconds)
Figure 8: Comparison of Bellman gap during training TD(O) and surrogate methods in the offline full-batch setting nonlinear function approximation Ant (top) and HalfCheetah (bottom) environments, measured by gradient computations (left) and wallclock time (right). The average Bellman gap (42) 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.
Threshelded Inner-50
GD, inner=50
GO,
GD, nner=1]
Sun-GD, hrar=10
Gradient Based Comparison (Ant-v4)
Wallclock Time Based Comparison (Ant-v4)
Value Prediction Eror
38
Computations
Gradient Based Camparison (Half Cheetah-v4)
Wallclock Time Based Comparison (Half Cheatah-v4)
Value Prediction Errer
Prediction
Computations
Figure 9: Comparison of average performance TD(O) and surrogate methods in minimizing the value predic- tion error the offline full-batch setting with nonlinear function approximation (bottom) environments, measured by gradient computations (left) and wallclock time (right). The average value prediction eror across 20 runs along with 95% confidence intervals are computed from fixed test set. The red dashed line represents the lowest value prediction erro achieved by any of the algorithms.
(top) and HalfCheetah
25

---

Published as a conference paper at ICLR 2025
campling
aratient Baxed Compation (Aai-ar))
Wellsookk Time Based Companson (Anirol)
Value Valle Prediction Ennor
value Prediction
IP Gradient Baxed Compatkon Qralf Cheelabvv))
Welkriock Based Comparson Cheetabell)
Value Prodiction Eiee
Value Prodiction Emtrr
Outerroop Iterations
Waltbbok Time Isecondsi
Figure 10: Comparison of average performance of surrogate methods in minimizing the value prediction eroor for RL tasks with a 16-layer MLP Ant measured by outer loop itcrations (left) and wallclock time (right). The average value prediction enror across runs along with 95% confidence intervals are computed from fixed test set. The red dashed line represents the lowest value prediction error achieved by any of the algorithms.
In practice we approximate the infimum in BE by 500 steps of AdamW, with a learning rate of 1 x 10-4 and exponential annealing at a decay rate of y = 0.995. the offline setting we consider deterministic algorithms like in the min-max experiments of Section [.1] and therefore we do not consider the double sampling algorithm (Algorithm B but only full-batch versions of Algorithm P and Algorithm 4 We compare different algorithms with B Exgup (42) giving a measure of how much the fixed point condition 411 is violated. Given enough data this fixed point is proxy for the fixed point (26).
Since environment interaction is required during training, 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 larger role.
As shown in Figure 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 Figure g we also evaluate the value prediction error on test set to further assess the performance of the algorithms in the full batch and deterministic setting. In all cases, at least one variant the surrogate method converges faster than TD(0), both in terms of gradient computations and wall-clock time. This demonstrates that, with appropriate choice of inner loop steps and alpha threshold, the surrogate method not only outperforms TD(0) terms of stability but also in computational efficiency.
D.2.1 LARGER NETWORK
In Figure 10 we report the average performance of surrogate methods using 16 layer MLP. We observe similar runtimes and performance the layer MI.P used in Section 4
26

---

Published as a conference paper at ICLR 2025
Algorithm 2: Surrogate Method with Inner Loop
Input:
Reference policy n, initial value function parameters On. length of trajectories N. discount factor learning rate 7) number of inner steps M, number of outer loop iterations T, stop gradient function s.(()
for f tto do
Collect a batch of trajectories {(s;, ai, ri, +() from
for each (8; T2x s!) in the batch do
| Compute TD target: = + g (s())
Initialize inner loop 0: 0g 0g
for m = to MM 1 do
for each (s,, Fú, s() in the batch do
Compute TD error: s!.m) = V oftm) (8;) yi
Compute mean squared error: N Σ/ 1 (0
Update inner loop 0: 0!m+11) m n Eim1 mm Vo (i (s:)
Update outer loop 0: 0t+1 = M.
Algorithm 3: Surrogate Method with Double Sampling
Input: Reference policy π, initial value function parameters 0o. length of trajectories N, buffer size K, discount factor 7, learning rate 7,, number of inner steps M, number of outer loop iterations T, stop gradient function sq(.)
Collect K batches of trajectories {ss, a, rs. > from æ to construct buffer for [ = to 7 do
Collect a batch of trajectories {(s;, a,, r;, N from
for each (s;, Fá s{) in the batch do
Compute TD target: = Ti + 7sg Vo, (s())
Compute TD error: F(Vo, (8:) sg( Vo, (s:)) Vi
Initialize inner loop 0: 0000 O
for to M 1 do
Sample mod K-th batch {(sj. ag Ty. 1 from the buffer
for each (s;, Tú, st) in the new batch do
Compute linearization term 1 (O(")) = (Vo, (8:)), V yam (8,) - sg(V (s,)))
for each (8j, Tj 8)) in the buffer batch do
Compute regularization term 12 l2(
V mm) (8j) - sg(Vo, (8))(1
Construct the surrogate loss function L(O(m)) + (1(() + (2((())))
Update inner loop 0!!)) by minimizing the surrogate loss:
( m²) 17 V)L(()
Update outer loop 0: or+1 AM)
27

---

Published as a conference paper at ICLR 2025
Algorithm 4: Thresholded Surrogate Method
Input:
Reference policy n, initial value function parameters Og. length of trajectories N. discount factor learning rate 7/. number of inner steps M, number of outer loop iterations T, stop gradient function sg((), a² E (0, 1)
for f tt do
Collect a batch of trajectories {(s;, ai ri, +()] from
for each (8; F2x s!) in the batch do
| Compute TD target: = r; + 7gg (Vo,
Initialize inner loop 0: 050) 0t
Compute initial surrogate loss: ((())) = N E/ || Vo, (5:) - -3.12
while ((((m) (1,(6.) 2 a² and m I M do for each (8i, rá, 84) in the batch do
Compute TD error: 8!!²) o (8:) y/
Compute mean squared error: 1 >i (6(m))
N ii=1
Update inner loop 0: 0lm++1) x- l(m) 1/ Σm= 0: m.
Vo VoVom
Update m m m +-1
Update outer loop 8: 8c+1 = 0.
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. 2020). In performative prediction more generally opti- mization under decision dieeendenddisrrbuutioon distributions (Drusvyatskiy & Xiao 2023), the model predictions
g(0) influence the targets y. With moving targets it is of interest 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 g(0) IR". Where each prediction is z' (0)
given by the n-dimensional vector, h(x,, 0). for some feature vector and fixed model architecture h. Given an error function f(2, v), quantifying error between predictions R2" and targets y R", the performatively stable models satisfy
0_ E arg min Ey D(- [e(g(0). y)]
(43)
The prediction dependent shift in targets is represented by the distribution D(-) being function of the model predictions (f). Note that we have used the formulation of performative prediction with respect model predictions (Mofakhami et al.) (023) instead of parameters.
The problem of minimizng projected Bellman error is special case of (43) with {(2, y) = 1|2 v1l
and (2=) is the distribution with full weight on T (z).
The problem of finding a performatively stable point can more generally be expressed as the follow- ing decision-dependent optimization problem:
0_ E arg fog
(44)
Or equivalently a constrained optimization problem with constraint 2 = cl(g(0): : 0 Rd):
0, E arg minfg(e.) (g(()) z, E arg minf2, (z).
0
zE2
If Z is closed convex and (2) is convex and differentiable with respect 2, then the above constrainted formulation is equivalent to the fixed point problem:
2, II o T(z)) I[ (z.)),
(45)
where we denote the gradient of (2) with respect to & as simply (z. As mentioned in Section D Bertsekas (209) showed that solving (45) is equivalent to solving strongly monotone
28

---

Published as a conference paper at ICLR 2025
and smooth either 7 or IIoT is contraction. Therefore, under these contraction conditions (45)
a hidden strongly monotone and smooth VI problem of the form ( Thankfully, (Drusvyatskiy
& Xiao 2023 Cheng et al. 2020) showed that II T is contraction if fz) is μ strongly convex with respect to 2 and 2' is --pisschitz with respect to z' and if 8/v < 1. Therefore, under standard performative prediction assumptions such those found in [rusvyyaskii & Xiao (2023), the performatively stable point (43) is equivalent to solving a hidden strongly monotone and smooth VI problem where our surrogate loss approach (Algorithm (I) applies and converges to the stable point under Theorems
3.2 A.5).
29


Reviews:
[{"review_id": "XZyKLauZsI", "reviewer": "Reviewer_LPnR", "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.\n\nExperimentally, 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.", "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?\n- 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?\n\nStyle:\n- Fig 1: It is hard to tell the methods apart, maybe use different line styles.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- The extension of iterative surrogate optimization from the scalar to the variational inequality case is a significant contribution.\n- Paper offers a rigorous theoretical analysis.\n- Strong performance of the method compared to the TD0 baseline.\n- Well-written and relatively easy to follow.", "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "0onKAcFRpM", "reviewer": "Reviewer_eBkP", "summary": "In this paper, the authors introduce a surrogate-loss-based framework for optimization of variational inequality (VI) systems, such as min-max. \n\nThis 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. \n\nExperimentally, 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!\n\nTo 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!", "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)?\n\n2. 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?\n\n3. 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!\n\n3. 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?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 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). \n\nThe 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 :)", "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. \n\nTo 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.\n\nI 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!). \n\nTo 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. \n\nTo 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!", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "5V4Dxm9HqY", "reviewer": "Reviewer_L5s9", "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.", "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?\n\n(2) The condition in the while loop of Algorithm 1 can not be verified. How could we let alpha be the user-defined parameter?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 4, "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.", "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "jQd0O9fSvu", "reviewer": "Reviewer_HyYK", "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.", "questions": "Questions:\n1. 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.\n\nComments:\n- 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.\n- 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\".\n- The related work paragraph in the introduction should probably be a subsection or its name should be removed or changed.\n- 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.\n\nReferences:\n\nSakos, Iosif, et al. \"Exploiting hidden structures in non-convex games for convergence to Nash equilibrium.\" Advances in Neural Information Processing Systems 36 (2024).", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 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.\n2. 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.", "weaknesses": "1. Certain parts lack clarity. Condition 2 in Theorem 3.2 seems unnecessary and needs refinement. (See question and comments).\n2. 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)