Domain Adversarial Training: A Game Perspective
Authors: David Acuna
Marc T Law
Guojun Zhang
Sanja Fidler
Venue: ICLR 2022 Poster (2022)
Keywords: Domain Adversarial Training
Domain Adaptation
Neural Networks Optimization
Game Theory

Abstract: The dominant line of work in domain adaptation has focused on learning invariant representations using domain-adversarial training. In this paper, we interpret this approach from a game theoretical perspective. Defining optimal solutions in domain-adversarial training as a local Nash equilibrium, we show that gradient descent in domain-adversarial training can violate the asymptotic convergence guarantees of the optimizer, oftentimes hindering the transfer performance. Our analysis leads us to replace gradient descent with high-order ODE solvers (i.e., Runge–Kutta), for which we derive asymptotic convergence guarantees. This family of optimizers is significantly more stable and allows more aggressive learning rates, leading to high performance gains when used as a drop-in replacement over standard optimizers. Our experiments show that in conjunction with state-of-the-art domain-adversarial methods, we achieve up to 3.5% improvement with less than of half training iterations. Our optimizers are easy to implement, free of additional parameters, and can be plugged into any domain-adversarial framework.

Published as a conference paper at ICLR 2022
DOMAIN ADVERSARIAL TRAINING A GAME PERSPECTIVE
David Acuna 123 Mare T. Law?, Guojun Zhang Sanja Fidler
University of Toronto ?NVIDIA Vector Institute *University of Waterloo
ABSTRACT
The dominant line of work in domain adaptation has focused on learning invariant representations using domain-adversarial training. In this paper, we interpret this approach from a game theoretical perspective. Defining optimal solutions in laversaaa training as local Nash equilibria, we show that gradient descent in comain-adversarinn training can violate the asymptotic convergence guarantees of the optimizer, oftentimes hindering the transfer performance. Our analysis leads us to replace gradient descent with high-order ODE solvers (i.e., Runge-Kuttee for which we derive asymptotic convergence guarantees. This family of optimizers is significantly more stable and allows more aggressive learning rates, leading to high performance gains when used as a drop-in replacement over standard optimizers. Our experiments show that in conjunction with ofte-of-thheart methods, we achieve up to 3.5% improvement with less than half of training iterations. Our optimizers are easy to implement, free of additional parameters, and can be plugged into any Nomain-adversant framework.
Nomain-adversarte
INTRODUCTION
Unsupervised domain adaptation (UDA) deals with the lack of labeled data in target domain by transferring knowledge from a labeled source domain (i.e., a related dataset with different distribution where abundant labeled data already exists). The paramount importance of this paradigm has led to remarkable advances in the field in terms of both theory and algorithms (Ben-David et al. 2007] 2010a b. Mansour et al. 2009). Several state-of-the-ar algorithms tackle UDA by learning domain- invariant representations in adversarial fashion (Shu et al. [208 Long et al., 2018 Saito et al.)
2018 Hoffman et al., 2018 8 Zhang et al. 2019: Acuna et al. 2021). Their goal is to fool an auxiliary classifier that operates in representation space and aims to classify whether the datapoint belongs to either the source or the target domain. This idea, called
Aonaai-AAvvesariia Learning (DAL), was introduced by Ganin et (016)) and can be more formally understood minimizing the discrepancy between source and target domain in a representation space (Acuna et al.) 2021).
Despite DAL being a dominant approach for UDA, alternative solutions have been sought as DAL is noticeably unstable and difficult to train in practice (Sener et al. 2016 [unn et al., 2019 Chang et al.) 2019). One major cause of instability the adversarial nature of the learning algorithm which results from the introduction of the Gradient Reversal Layer (GRL,, Ganin et al. 2016) (Figure D GRL flips the sign of the gradient during the backward pass, which has profound implications on the training dynamics and asymptotic behavior of the learning algorithm. Indeed, GRL transforms gradient descent into competitive gradient- based algorithm which may converge to periodic orbits and other non-trivial limiting behavior that arise for instance in chaotic systems (Mazumdar et al., 2020). Surprisingly, little attention has been paid to this fact, and specifically to the adversarial component and interaction among the three different networks in the algorithm. In particular, three fundamental questions have not been answered from an algorithmic point of view, 1) What is optimality in DAL? 2) What makes DAL difficult to train and 3) How can we mitigate this problem?
In this work, we aim to answer these questions by interpreting the DAL framework through the lens of game theory. Specifically, we use tools developed by the game theoretical community in Bayar & Olsder (1998); Letchhe et al. (2019); Mazumdar et al. (2020) and draw inspiration from the existing two-player zero-sum game interpretations of Generative Adversarial Networks (GANs)

---

Published as a conference paper at ICLR 2022
(Goodfellow et al. 2014). We emphasize that in DAL, however, we have three rather than two networks interacting with each other, with partial cooperation and competition. We propose a natural three-player game interpretation for DAL, which is not necessarily equivalent to two-player zero-sum game interpretations (see Example T. which we coin as the Domain-Adversarin Game We also propose interpret and characterize optimal solutions in DAL local Nash Equilibria (see Section 3). This characterization introduces a proper mathematical definition of algorithmic optimality for DAL. It also provides sufficient conditions for optimality that drives the algorithmic analysis.
With our proposed game perspective in mind, a simple optimization solution would be to use the Gradient Descent (GD) algorithm, which is the de facto solution but known to be unstable. Alternativly,, we could also use other popular gradient based optimizers proposed in the context of differentiable games (e.g. [Korpeeevich] 1976. Mescheder et al. 2017). However, we notice that these do not outperform GD in practice (see $ $(6). To understand why, we analyze the asymptotic behavior of gradient- based algorithms in the proposed (Theorem 2 shows that GD with GRL (i.e., the existing solution for DAL) violates the asymptotic convergence guarantees to local NE unless an upper bound is placed on the learning rate, which may explain its training instability and sensitivity to optimizer parameters. In $ Appendix B.22 and Appendix we also provide a similar analysis for the popular game optimization algorithms mentioned above. We emphasize however that while some of our results may be of independent interest for learning in general games, our focus is DAL $ $14.3)am and (hos both theoretically and experimentally that the limitations mentioned above disappear if standard optimizers are replaced with ODE solvers of at least second order. These are straightforward to implement as drop-in replacements to existing optimizers. They also lead to more stable algorithms, allow for more aggressive learning rates and provide notable performance gains.
comain--dvvesarre
game ($ 4). The main result of $ 4.2
2 PRELIMINARIES
V
We focus on the UDA scenario and follow the formulation from Acuua et al. 2021). This makes our analysis general and applicable most state-of of- the-art DAL algorithms (e.g../Ganill Ganin et al. (2016); Saito et al. (2018); Zhang et al. (2019)). We assume that the learner has access to a source dataset (S) with labeled examples and a target dataset (T) with unlabeled examples, where the source inputs ag are sampled i.idd from a (source) distribution P3 and the target inputs x are sampled i.idd. from a (target) distribution P. both over X. We have y = {0, 1} for binary classification, and y [1,..., k.} in the multiclass case. The risk of hypothesis h X + y w.r.t. the labeling function f. using a loss function é: V y + RR, under dis- tribution D is defined as: R2 (h, f) == ED ED ((((x), [(x)]] For sim- plicity, we define RC's (h) == R2p, (h, fs) and (h) == R2p, Jt).
z
M
AV
Rx [U
Figure 1: We study domain- adversarial training from game perspective. In DAL (Ganin et al. (216)), three networks in- teract with each other: the fea- ture extractor (g), the domain classifier (h') and the classifier (h). During backpropagation, the f the sign of the gra-
The hypothesis class of h is denoted by H.
dient with respect to
UDA aims to minimize the risk in the target domain while only having access to labeled data in the source domain. This risk is upper bounded in terms of the risk of the source domain, the discrepancy between the two distributions and the joint hypothesis error X*:
Theorem 1. (Acuna et al. (002)) ) Let us note é: y x y - [0, 1), X = minneR R/((h) + R²),,, E E
and D
h (P. == supw EH E. (,-p,((((()))) [((M(z), (x))) -
We have:
R+(M) < (M) + Di, (P.1 + X
The function Φ R4 + R defines a particular f-divergence and 6' is its (Fenchel) conjugate. As is typical in UDA, we assume that the hypothesis class complex enough and both fa and Sa are similar in such a way that the non-estimable term (X*) is negligible and can be ignored.
Domain-A A Adversarial Training (see Figure I aims to find hypothesis h H that jointly minimizes the first two terms of Theorem 1 To this end, the hypothesis h is interpreted as the composition of
h ho o g with X + Z, and h: Z + y. Another function class 7. is then defined to formulate H. := {h ooggg g: h E H. G). The algorithm tries to find the function E G such that o minimizes the risk of the source domain (i.e. the first term in Theorem D. and its composition with h and / minimizes the divergence of the two distributions (i.e. the second term in Theorem 1
2

---

Published as a conference paper at ICLR 2022
Algorithmically, the computation of the divergence function in Theorem is estimated by so-called domain classifier '' E H whose role is detect whether the datapoint g(mi) E 2 belongs to the source or to the target domain. When there does not exist function h' H. that can properly distinguish between g(x²) and g(z)), g is said to be invariant to the domains.
Learning is performed using GI and the GRI. (denoted by Rx) on the following objective:
min heH.
Ee=p,l(h g, w)] odd,, (h, K Rx(g));
where dr. (h, R', == R. l6th's og og h) E 1(0* o () o g, h o g)]. Mathematically, the GRL RA is treated as a "pseudo- "pseudo-function" defined by two (incompatible) equations describing its forward and back- pooopprppggttion behavior (Ganin & Lempitsky 2015 Ganin et al. 2016). Specifically,
(x)x) z and dRx
-X,
where À and a are hyper-parametert that control the tradeoff between achieving small source error and learning an invariant representation. The surrogate loss é y x y R (e.g., cross-entropy) is used minimize the empirical risk in the source domain. The choice of function ê y R and of conjugate o² of the f f-divergence defines the particular algorithm (Ganin et al. 2016 Saito al. 2018 Zhang et al., [019 Acuna et al.) (202T). From eq. X
we can notice that GRL introduces an adversarial scheme. We next interpret eq. 2 as a three-player game where the players are h h' and g. and study its continuous gradient dynamics.
A GAME PERSPECTIVE ON DAL
We now interpret DAL from game- theeetthcreeicall perspective. In $ $3.1, we rewrite the DAL objective as a three-playee game. In this view, each of the feature extractor and two classifiers is player. This allows us to define optimality terms of local Nash Equilibrium (see Def. 2 in Appendices). In 3.2
we introduce the vector field, the game Hessian and the tools that allow us to characterize local NE for the players. This characterization leads to our analysis of the continuous dynamics in $
3.1 DOMAIN-ADVERSARIAL GAME
We now rewrite and analyze the DAL problem in eq. 2 as three-player game. Let H. Hi' and G be classes of neural network functions and define w1 C Si and w/ C 2g as a vector composed of the parameters of the classifier and domain classifier networks h E H and h H. respectively. Similarly, let W2 S 22 be the parameters of the feature extractor network
G. Their joint domain denoted by . Q1 x S22 X G2 and the joint parameter set is w (W1, w2, W3). Let each neural network be player and its parameter choice to be its individual strategy (here continuous). The goal of each player is then to selfishly minimize its own cost function J, + R. We use the subscript -i to refer to all parameters/players but i. With the notation introduced, we can now formally define the Domain-Adversarii Game as the three-player game G(I, L4, J.) where == (1.
dim = Σi= di,()).) = d, Ω C RRd, and:
J1 (Wi, w-1) = E(w1, w2) + ade,e(w)
Jz w-) == ((w1, w2) + adds, Ju (5 w-)) == - add,, (w))
(4)
We use the shorthand f(w1, W2) for Engyr [l(ws o wr (z), v)], and w; 's refer to the feature extractor g and the classifiers (h and h²). Similar notation follows for ds,t. Here, we assume that each Jj is smooth in each of its arguments W; E 22
The gradient field of Equation 2 and the game's vector field (see $ 3.2) are equivalent, making the original interpretation of DAL and our three-player formulation equivalent. However, it is worth noting that our intepretation does not explicitly require the use of R2 in d,, in Equation (4). We can write optimality conditions of the above problem through the concept of Nash Equilibrium:
Definition 1. (Nash Equilibrium (NE)) A point w* E Ω said be Nash Equilibrium of the Domain-Adversane Adversarial Game vi E (1,2,3), Vw: E Q2 we have: J,(wf, )) S Ja(a,,
In our scenario, the losses are not convex/concave. NE then does not necessarily exist and, in general, finding NE is analogous to, but much harder than, finding global minima in neural networks which
3

---

Published as a conference paper at ICLR 2022
is unrealistic using gradient- gradient-based methods (Letcher et al. relaxes the NE to a local neighborhood ( .6) := [1 w=
2019). Thus, focus local NE which
< 53 with >> 0 (see Definition 2)
Intuitively, a NE means that no player has the incentive to change its own strategy (here parameters of the neural network) because it will not generate any additional pay off (here it will not minimize its cost function). We emphasize that each player only has access to its words, the player J cannot change the parameters W2, 4/. It only has access to W E Ω2-
strategy set. In other
While the motivation of the three- prayer game follows naturally from the original formulation of DAL where three networks interact with each other (see Figure D.. the optimization problem 2 could also be interpreted as the minimax objective of two-player zero-sum game. Thus, natural question arises: can we interpret the done for example by defining wiz == (wi w and considering the cost of the two players (w12, wa) as J12 = J and Js = J where J [w12, Ws) := [ [f(w1,ww) + dd.((w). In general, however, the solution of the two-player game (w wg) is not equal to the NE solution of the three-player game (wi, w2, w¹). This is because the team optimal solution w12 + ( ) in general. We illustrate this in the following counterexample (see Başar & Olsder 1998) for more details):
game as two player zero-sum game? This can be
Example 1. Let the function J(w) == (wf + 4w1w2 + w -w²)
(a) Suppose the three-player game w = (Wi, W2, wa) with J1 = J2 J and J3 = J. Each Ja is strictly convex in wi. The NE solution of the game w" (0, 0) unique.
(b) Suppose the two-player game w (w12, with J12 J and J3 J. The solution w" from
(a) is not a NE solution. To see this, let is == (-1, 1, 0). We have that (w) = -1 < J12 "z("") ) =
This contradicts Definition [
One can verify that there is no NE in this two-player scenario.
3.2 CHARACTERIZATION OF THE DOMAIN-ADVERS.OO
GAME
We now introduce the game's 's vector field (also called -gadddeer) and the aseudo-gradiend Jacobian. We also provide a characterization of local NE based on them (see $ $ These are the core concepts used in our analysis (8 (8))). We first define the game's 's vector field v(w), and its Jacobian
(ww) (also called the game Hessian (Letcher et al. 2019)):
(5) Note that the vector field v(w) and the three-player formulation naturally capture the behavior introduced by the GRL in the original formulation. Specifically, v((w) is identical to the gradient with respect to the parameters of the original DAL objective with GRL (Equation (2). Therefore, in both cases the behavior of GD is identical. Assuming the same initial conditions. they will reach the same solution. This shows the equivalence between our perspective and the original DAL formulation. We emphasize that by equivalence, we mean the same dynamics, and the same intermediate and final solutions. Another fact worth emphasizing is that H (w) is asymmetric. This is in contrast with the Hessian in supervised learning. Before proceeding with a characterization of local NE in terms of ((w) and H(w), we first define sufficient and necessary conditions for local NEs:
v(w) = JV, V.. V., E Rd, H(w) == Ve(w) E Rdxd
Proposition 1. (Necessary condition). Suppose each J; is twice continuously differentiable in each wi, any local NE w* satisfies: i) V. = 0 and ii) Vi E {1, 3). V2 Ji Z 0.
Proposition 2. (Sufficient condition). Suppose each Jg is twice continuously differentiable in each wi. W is local NE if (w"") 0 and ii) Vi, V2 Wer "(("") > 0.
The necessary and sufficient conditions from Propositions T and are reminiscent of conditions for local optimality in continuous optimization (Nocedal & Wright, 2006). Similar conditions were also proposed in Ratlif et al. (2016) where the sufficient condition defines the differential Nash equilibrium. We can now characterize a local NE in terms of v(w) and H (w):
Proposition 3. (Strict Local NE) w is a strict local NE if v(w) = 0 and H (w) + H(w) > 0.
The sufficient condition implies that the NE is structurally stable (Ratliff et al. 2016). Structural stability is important as it implics that slightly biased estimators of the gradient (c.g.. due to sampling noise) will not have vastly different behaviors in neighborhoods of equilibria (Mazumdar et al. 2020).
In the following, we focus on the strict local NE (i.e., wt for which Proposition 3 satistied).
4 LEARNING ALGORITTM
We defined optimality as the local NE and provided sufficient conditions in terms of the pscudo- gradient and its Jacobian. In this section, we assume the existence of the strict local NE (Prop. 3
4

---

Published as a conference paper at ICLR 2022
in the neighborhood of the current point (e.g., initialization), and analyze the continuous gradient dynamics of the Adverssiaaa Game (eq. 4 and eq. (5). We show that given the sufficient local NE is guaranteed through an application of Hurwitz condition (Kallil 2002). Most importantly, we show that using GD with the GRL could violate those guarantees unless its learning rate is upper bounded (see Thm. 2 an Cor. [ This is in sharp contrast with known results from supervised learning where the implicit regularization introduced by GD has been shown to be desirable (Barrett & Dherin 202T). We also analyze the use of higher-order ODE solvers for DAL and show that the above restrictions are not required if GD is replaced with them. Finally, we compare our resulting optimizers with recently algorithms in the context of games.
conditions from Prop. B asymptotic convergence
Our algorithmic analysis based on the continuous gradient-play dynamics and the derivation of the modified or high-resolution ODE of popular integrators (e.g.. GD//uler Method and Lunge-Kuutal This type of analysis is also known in the numerical integration community as backward error analysis (Hairer et al. 2006) and has recently been used to understand the implicit regularization effect of GD in supervised learning (Barrett & Dherin 202T). High resolution ODEs have also been used in Shi et al. (2018) to understand the acceleration effect of optimization algorithms, and more recently in Lu (2220). As in Shh et al. (2018) : Lu (2020); |Barrett & Dherin (202I), our derivation of the high resolution ODEs is in the batc- setting. The derivation of the stochastic dynamics of stochastic discrete time algorithms is significantly more complicated and is beyond the scope of this work.
We experimentally demonstrate that results also valid when there is stochasticity due to sampling noise in the mini-batch. We emphasize that our analysis does not put any constraint or structure on the players' cost functions as opposed to Azizian et al. al.] (2020); Zhang Yu (2020). In our problem, the game is neither bilinear nor necessarily strongly monotone. See proots in appendices.
4.1 CONTINUOUS GRADIENT DYNAMICS
Given v(w) the continuous gradient dynamics can be written as:
(6) For later reasons and to distinguish between eq. and the gradient flow, we will refer to these as the gradient-play dynamics as in Başar & Olsder [1998); Mazumdar et al. (2020). These dynamics are well studied and understood when the game is either a potential or purely adversarial game (see definitions in appendices). While eq. 2 may look like a single objective, the introduction of the GRL (Rx), makes fundamental difference between our case and the dynamics that are analyzed in the single-objective gradient- based learning and optimization literature. We summarize this below:
(() -w(w).
Proposition 4. The domain-adwes adversarial game is neither a potential nor necessarily a purely adver- sarial game. Moreover, its gradient dynamics are not equivalent to the gradient flow.
Fortunately, we can directly apply the Hurwitz condition (Khalil) 2002) (also known as the condition for asymptotic stability, see Appendix (A.I] to derive sufficient conditions for which the continuous dynamics of the gradient play would converge.
Lemma 1. (Hurwitz condition) Let Vv(w*) be the Jacobian of the vector field at a stationary point w² where v(w") = 0. If the real part of every eigenvalue À of Ve(w") (i.e. in the spectrum (o(Vew"))) is positive then the continuous gradient dynamics are asymptotically stable.
In this work, we assume the algorithms are initialized in a neighborhood of a strict local NE w". Therefore, Lemma provides sufficient conditions for the asymptotic convergence of the gradient- play dynamics to a local NE. In practice this assumption may not hold, and it is computationally hard to verify. Despite this, our experiments show noticeable performance gains in several tasks, benchmarks and network architectures (see $ ())
4.2 ANALYSIS OF GD WITH THE GRL
We showed above that given the existence of strict local NE, the gradient-play dynamics are attracted to the strict local NE. A natural question then arises: If under this assumption local asymptotic convergence is guaranteed, what could make DAL notoriously hard to train and unstable? In practice, we do not have access to explicit solution of the ODE. Thus, we rely on integration algorithms to approximate the solution. One simple approach is to use the Euler method:
+
r)o(w).
5

---

Published as a conference paper at ICLR 2022
This is commonly known GD. The equivalence between v(w) (game's vector field) and the gradient of Equation 22) (original DAL formulation) follows from the use of the GRL (Rx). We remind the reader that the GRL is a esseddofunnction defined by two (incompatible) equations describing its forward and back-propagation behavior, i.e., a flip in the gradient's 's sign for the hackward pass (see Figure [ Section and et al. (20T6)) Equation ( is then the default algorithm used in DAL.. Now, to provide an answer to the motivating question of this section, we propose to analyze the high-resolution ODE of this numerical integrator (i.e., Euler) and in turn its asymptotic behavior. This is similar to deriving the modified continuous dynamics for which the integrator produces the exact solution (Hairer al. al.) (2006) and applying Hurwitz condition on the high-resolution ODE.
Theorem 2. The high resolution ODE of GD with the GRL up to (()) is:
ن = =- 2 (Vo(w))())
(8)
Moreover, this is asymptotically stable (see Appendix A. 7 at stationary point w² (Proposition
3
fif
for all eigenvalue written as x = a + ib E 5p( V (w ). we have 0 >> 71(2² - 1/ a.
striking difference between Equation (6) and Equation (8) is made clear (additional term marked in red). This additional term is result of the discretization of the gradient-play dynamics using Euler's method (i.e. GD) and leads to a different Jacobian of the dynamics. This term was recently shown to be beneficial for standard supervised learning (Barrett & Dherin 2021). where Vu(w") is symmetric and thus only has real eigenvalues. In our scenario, this term is undesirable. In fact, this additional term puts an upper bound on the learning rate r). The following corollary formalizes this:
Corollary 1. The high resolution ODE of GD with GRL in Equation (8) is asymptorically stable only with
if the learning rate v is in the interval: 0 < 1] < v--a" for all X - a a +b E
-2n
large imaginary part (i.e., such that |a] < [b|).
To have good convergence properties, the imaginary part of the eigenvalues of -ee (w") must be small enough. Therefore, if some eigenvalue À = a + ib satisfies < 0 and 6² > a² >>>>>>>>>>> -2a the learning rates should be chosen to be very small. This is verified in Section 6 and in Example 2
Example 2. Consider the three-player game where f(w1, w2) = w + 2w I w2 + w X
1 and
(w,, w3)= = w2 + 99w2 - w3z. Then i -u(w) becomes: úi Aw (_) -1 -99 The
-2
99 -2
eigenvalues of A are 2 and -3 + 2i 2449. From Corollary 1 1) should be 0 < < 6.2 x 10-3
4.3 HIGHER ORDER ODE SOLVERS
The limitation described above exists because GD with the GRL can be understood as a discretization of the gradient-play dynamics using Euler's Method. Thus, it only approximates the continuous dynamics up to (n)) To obtain a better approximation, we consider Runge-Kure Kutta (RK) methods of order two and beyond (Butcher, 1996). For example, take the improved Euler's method (a particular RK method of second order) that can be written as:
w+ = [v((w) v(w -
((w-))((w)). me(w))).
Comparing Equation (9) (i.e., update rule of RK2) with Equation 7 (i.e., update rule of GD), one can see that the RK2 method is straightforward to implement in standard deep learning frameworks. Moreover, it does not introduce additional dynamics approximate the continuous ODE of Equation (6) a higher precision. In Appendix [ we provide asymptotic guarantees for the high resolution ODE of general RK methods their generalized expression and the algorithm pseudo-code. See also PyTorch pseudo-code in Appendix E
paprr-paraettrs... More importantly, such discrete
Limitation. A disadvantage of using high-order solvers is that they require additional extra steps. Specifically. one extra step in the case of RK2 (computation of the additional second term in Equation (9)) In our implementation, however, this was less than 2x slower in wall-clock time (see Appendix F..5 for more details and wall-clock comparison). Moreover, not initialized in the neighborhood of a local NE, high-order solvers and gradient- based methods might also converge to non-NE as described in Mazumdar et al. (2019) although this is likely a rare case.
Comparison vs other game optimization algorithms. DAL has not been previously interpreted from a game perspective. Our interpretation allows us to bring recently proposed algorithms to the context of differentiable games (Zhang& & Yu 2200 Azizian et al. 2020) to DAL. Classic examples the Eextra-Gradien (EG) method (Korpelevich] 1976) and Consensus Optimization (CO) (Mescheder al. 2017). In Appendix B.2 we analyze the continuous dynamics of the EG method, and show that

---

Published as a conference paper at ICLR 2022
cannot take the learning rate of EG to be large either. Thus, obtain a similar conclusion as Corollary [ Then, in practice for DAL, stability for EG comes at the price of slow convergence due to the use of small learning rates. We experimenaally show this in Figure With respect to CO, show in Appendix ththt this algorithm can be interpreted in the limit as an approximation of the RK2 solver. In practice, if its additional hyper-paramett continuous dynamics better than GD and EG. We believe this may be the reason why CO slightly outperforms GD and EG (see Appendix E.4 In all cases, RK solvers outperform GD, EG and CO. This is in line with our theoretical analysis since they better approximate the continuous dynamics (Hairer et al.) 2006). It is worth noting that many other optimizers have recently been proposed in the context of games -.g.Gl et al. (2019a); Hsieh et al. (2020): Lorraine et al. (202 la b). Some of them are modifications of the EG method that we compared to e.g. Extra-Adam (Gidel et al. 2019a)
(7) is tuned thoroughly, CO may approximate the
or double step-size EG (Hsieh et al.
2020). More practical modifications in terms of adaptive step size could also be applied on top of RK solvers as done in Qin et al. (2020). A comparison of all existing game optimizers in DAL, and better theoretical understanding of such modification on RK solvers are beyond the scope of this work. However, we believe it is an interesting and unexplored research direction that our game perspective on DAL enables.
RELATED WORK
To the best of our knowledge, DAL has not been previously analyzed from game perspective. Moreover, the stability of the optimizer and the implications of introducing the GRL. has not been analyzed either. Here, we compare our results with the general literature.
Gradient-Based Learning in Games. |Ratiff et al. (2016) proposed a characterization of local Nash Equilibrium providing sufficient and necessary conditions for its existence. Mazumdar et al. (2020) proposed a general framework to analyze the limiting behavior of the gradient-play algorithms in games using tools from dynamical systems. Our work builds on top of this characterization but specializes them to the aaveessrraaa problem. We propose a more stable learning algorithm that better approximates the gradient-play dynamics. Our resulting algorithm does not introduce explicit adjustments or modify the learning dynamics, nor does it require the computation of the several Hessian vector products or new hyperparameters. This is in contrast with general algorithms previously analyzed in the context of differentiable games (Azizian et al. 2020 Letcher et al. 2019).
Integration Methods and ML. et al. (2117) showed that accelerated optimization methods can be interpreted as integration schemes of the gradient flow equation. Zhhng et al. (2018) showed that the use of high order RK integrators can achieve acceleration convex functions. In the context of two-playen game (i.e GANs), Gemp & Mahadevan (2018) consider using second-orde ODE integrator. More recently, Qin et al. (2020) proposed to combine RK solvers with regularization on the generators' gradient norm. [Chen et al. (008)) interpreted the residual connection in modern networks as the Euler's integration a continuous systems. In our case, we notice that the combination of GD with the GRL can be interpreted as the Euler's discretization of the continuous gradient play dynamics, which could prevent asymptotic convergence guarantees. We then study the discretization step of popular ODE solvers and provide simple guarantees for stability. Moreover, our analysis is based on a novel three- playeeplyerrge game interpretation of the addattatonttt problem. This is also different from a single potential function or two-player games (i.e. GANs).
Two-Player Zero-Sum Games have recently received significant attention in the machine learning literature due the popularity of Generative Adversarial Networks (GANs) (Goodfellow al. 2014). For example, several algorithms have been proposed and analyzed (Mescheder et al. 2017] Mertikopoulos et al. 2019, Gidel et al., 2019a Zhang & Yu 2020: Hsich al.] (200)) in both deterministic and stochastic scenarios. In our problem, we have general three-player games resulting of novel game interpretation of the coomain-adversaee et al. (2019a) focused on GANs, their convergence theory and methods for stochastic variational inequalities could also be applied to three- players games and thus DAL using our perspective.
problem. It is worth noting that while Gidel
EXPERIMENTAL RESULTS
We conduct extensive experimental analysis. We compare with default optimizers used in domain- adversarial training such as GD, GD with Nesterov Momentum (GD-NM) (as in Sutskever et al. (2013)) and Adam (Kingma & Ba 2014). We also compare against recently proposed optimizers in the context of differentiable games such as EG (Korpelevich) 1976) and CO (Mescheder et al. 2017). We focus our experimental analysis on the original domain-adverrarial framework of Ganin et al.
7

---

Published as a conference paper at ICLR 2022
(DANN). However, in section 6.2 we also show the versatility and efficacy of our approach improving the performance of recently proposed SoTA DAL framework (c.g., f-DAL (Acuna et al. combined with Implicit Alignment (Jiang et al. 2020b).
(016)
2021
6.1 EXPERIMENTAL ANALYSIS ON DIGITS
Implementation Details. Our first experimen- tal analysis is based on the digits benchmark with models trained from scratch (i.e., with ran- dom initialization). This benchmark constitutes of two digits datasets MNIST (CC BY-SA 3.0) and USPS (LeCun al., 1998 Long et al., 2018) with two transfer tasks (M- + U and U M). We adopt the splits and evaluation pro-
Cred Descont
21
0.000
Adoen
2nd.. Dascet Namamum
0.30
Sural Oueipenc
0:25
.Crosleett Descon
tocol from Long et al. (2018) and follow their standard implementation details.
For GD-NM, we use the default momentum value (0.9). We follow the same approach for the of Adam. Hyper- parameters such as learning rate, learning sched- ule and adaptation coefficient (A) are determined for all optimizers by running a dense grid search and selecting the best hyper-parameters on the transfer task M- As usual in UDA, the best criteria are determined based on best transfer accuracy. The same parameters are then used for the other task (i.e., U-+).. We use the same seed and identically initialize the network weights for all optimizers. This analysis is conducted on Jax (Bradbury et al.
.Dus (RKC)
additional
Figure 2: Our method vs popular optimizers on the Digits Benchmark. (Top-Left) Loss in target domain. (Top-Right) Transfer performance. (Bottom) (-SNE Visualization of the last layer representations during training. Our method converges faster, has better per- formance and produces more aligned features faster.
2018) (see Appendix D].
Comparison vs optimizers used in DAL. Figure 2 (top) illus- trates the training dynamics for the loss in the target domain and the performance transfer. As expected, our optimizer con- verges faster and achieves noticeable performance gains. A core idea of DAL is to learn Nomain--nvariann representations.
Transfer Performance
&
80
Extra Gradient Consensus Opt (urs(RK2)
22
thus we plot in Figure 2 (bottom) 1-SNE (Van der Maaten & Hinton 2008 visualizations of the last layer features of the network. We show this over sequence of epochs for GD with
Our5(RK4)
16
24
Epachs
GRL vs RK2. A difffernt color is used for the source and target datasets. In the comparison vs Adam, emphasize that Adam computes adaptive learning rates which our method does not. That said, Ssoure that our two methods RK2 and RK4 outperform all baselines in terms of both convergence and transfer performance. In Figure 7 we show how unstable these standard optimizers are when more aggressive step sizes are used. This is in line with our thcoretical analysis. Experimentally, it can be seen that in DAL, GD is more stable than GD-NM and Adam, with the latter being the most unstable. This sheds lights on why well tuned GD-NM is often preferred over Adam in DAL.
Figure 3: Comparison among op- timization algorithms (M-U) with DANN.
Comparison vs game optimization algorithms. We now compare RK solvers vs other recently proposed game optimization algorithms. Specifically, we compare vs the EG method (Korpelevich) 1976) and CO (Mescheder et al. 2017). In every case, we perform a dense grid under the same budget for all the optimizer and report the best selection (see Appendix E for details). In line with our theoretical analysis of the continuous dynamies of the FG, we notice that the EG method is not able to train with learning rates bigger than 0,006, result it performs signficantly worse than any other optimizer (including simple GD). Also inline with our theoretical analysis, CO performs better than EG and all other popular gradient algorithms used in DAL.. This is because CO can be seen as an approximation of Heun's 's Method (RK2). More details on this in supplementary.
Robustness to dyper-parameters Figure 4 shows transfer performance of our method for different choices of hyperparameters on the same dataset. Our method is robust to wide variety of hyperparameters.
while highlighting (green line) the best score of the best performing GD
8

---

Published as a conference paper at ICLR 2022
UR
Schedude
Method
Aaaue
Trersfer Acc.
16
74
72
66
380
3.1
RN2
0.5
Crackent Discent
Figure 4: Robusiness to kyperparameters. We compare the transfer perfor- mance of our method for different hyperarameters in the task M-> U in the Digits benchmark. Green line shows the best score for the best performing hyperparameters of GD. Blue star corresponds to the best solution. Our method performs well for a wide variety of hyperparameters.
Figure 5: Sensitiviry to Sam- pling Noise. Different amounts of sampling noise controlled by the batch size (64, 128, 160) (Visda).
Method
Adam
GD
90.0 1: 0.4
M-UU
96.8
93.4 1: 0.7
U -M
91.7
Avg
Tandter
70.0
72.5
225
2.00
1.75
Nesterov Mo memtin
Gradi Descent LR:0.3
GD-NM
91.8
94.4 + 04
93.1
67.5
Grad Descent (hesseor))
150
(ur))K44)
(Rx)(K2)
95.0 1 1.4
95.14:0.1
97.3
97.3 a: 0.2
4
0.1
96.1
96.3
65.0
Durs (BK22)
1.25
5000
18600 24000
12030 18300 24030
of Rteraions
treeationts)
Table 3: Accuracy (%) on Digits (DANN).
Figure 6: Transfer Perfor-
Figure 7: Stability anal. on Digits. Most aggressive step size before diver- gence. Adam diverges for > 0.001.
mance on Visda (DANN).
6.2 COMPARISON IN COMPLEX ADAPTATION TASKS We evaluate the performance of our algorithm with Resnet-50 (He
Method
Sim->Rea
jet al. 2016) on more challenging adaptation benchmarks. Specif- ically, this analysis is conducted on Visda-2017 benchmark (Peng)
GD-NM
71.7 + 0.7
jt al. 2017). This a simulation-to-real dataset with two different domains: (S) synthetic renderings of 3D models and (R) real im-
Ours(RK2)
73.8 + 0.3
ages. For this experiment, we use PyTorch (Paskke et al. 2019). our
Table Accuracy (DANN) on Visda 2017 with ResNet-50.
evaluation protocol follows Bolloos/Zhang Zhang et al. (2019) and uses ResNet-50 as the backbone network. For the optimizer parameters, we tune thoroughly GD-NM, which is the optimizer used in this setting (Long 2018 Zhang et al. 2019 Jiang et al. 2020 Acuna et al., (021). ). For ours, we keep the hyper-parameters, but increase the learning rate (0.2), and the batch size to 128. In this task, approach corresponds the improved Euler's method (RK2). Table | shows the comparison. Figure 6 compares the training dynamics of our method vs GD-NM. In Figure [ we evaluate the sensitivity of our method (in terms of transfer performance) to sampling noise as controlled by the batch size.
Improving SOTA DAL frameworks. We use this complex visual adaptation task to showcase the ap- plicability of our method to SoTA DAL frameworks. Specifically, we let the DA method being f-DAL Pearson as in Accua et al. (202I) with Implicit Align- ment[jiang et al. (2020). We use the tuned parameters and optimizer from Acuna et al. 2: Jiang et al.)
Method
Sim->Real
f-DAL GD-NM f-DAL RK2 (Ours)
72.9 (29.5K iter)
76.4 (10.5K iter)
Table 2:
Comparison using SoTA DA adversarial frameworks with ResNet-50 on Visda.
(2020) as the baseline. In case, only increase the learning rate (0.2). Table shoows that our method achieves peak results (+3.5% in 10.5K iterations (vs 29.5K iterations for GD-NM).
Natural Language Processing Tasks. We also evaluate our approach on natural language processing tasks on the Amazon product reviews dataset (Blitzer et al. (006). We show noticeable gains by replacing the GD with either RK2 or RK4. Results and details can be found in Appendix E.
7 CONCLUSIONS
We analyzed DAL from a game-theoretical perspective where optimality is defined as local NE. From this view, we showed that standard optimizers in DAL. can violate the asymptotic guarantees of the gradient-play dynamics, requiring careful tuning and small learning rates. Based our analysis, proposed to replace existing optimizers with higher-order ODE solvers. We showed both theoretically and experimentally that these are more stable and allow for higher learning rates, leading noticeable improvements in terms of the transfer performance and the number of training iterations. We showed that these ODE solvers can be used as drop-in replacement and outperformed strong baselines.
Acknowledgements. We would like to thank James Lucas, Jonathan Lorraine, Tianshi Cao, Rafid Mahmood, Mark Brophy and the anonymous reviewers for feedback on earlier versions of this work.

---

Published as a conference paper at ICLR 2022
REFERENCES
David Acuna, Guojun Zhang, Mare T. Law, and Sanja Fidler. f-domain adversarial learning: Theory and algorithms. In Proceedings of the 38th International Conference on Machine Learning, volume 139, pp. 66-75. PMLR, 2021.
Waïss Azizian, Toannis Mitliagkas, Simon Lacoste-Julicn, and Gauthier Gidel, A tight and unified analysis of gradient- methods for a whole spectrum differentiable games. In Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learning Research, pp. 2863-2873. PMLR, 26-28 Aug 2020.
David Barrett and Benoit Dherin. Implicit gradient regularization. In International Conference on Learning Representations, 2021. htt.htttpss//oppeeeviess.ss http:pppwww......eeeeeeeoorr.rm.
Tamer Başar and Geert Olsder. Dynamic Noncooperativee Game Theory, 2nd Edition. Society for Industrial and Applied Mathematics, 1998, doi: 10. (0.1137779781111199111 URL httpt::/t///uuut siam. org/
boi/abs
Shai Ben-David, John Blitzer, Koby Crammer, and Fernando Pereira. Analysis of representations for domain adaptation. In Advances in neural information processing syxtems, pp. 137-144, 2007.
Shai Rev-David, John Blitzer, Koby Crammer, Alex Kulesza, Fernando Pereira, and Jennifer Wortman Vaugham. A thcory of learning from different domains. Machine learning, 79(1-2):151-175 2010a.
Shai Ben- Devid, Tyler Lu, Teresa Luu, and Dávid Pál. Impossibility theorems for domain adaptation. In Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, pp. 129-136. 2010b.
Hugo Berard, Gauthier Gidel, Amjad Almahairi, Pascal Vincent, and Simon Lacoste-Julien. A closer look the optimization landscapes of generative adversarial networks. In International Conference on Learning Representations, 2020. URL (tt.t:tttt///t http:://pppeeeeeieeeom URttttp:://oeeerrriei... http://wwwww..eeetoroooeeeeeeeee LI-
John Blitzer, Ryan McDonald, and Fernando Pereira. Domain adaptation with structural correspondence lcarning. In Proceedings of the 2006 conference on empirical methods in natural language processing, pp. 120-128, 2006.
James Bradbury, Roy Frostig, Peter Hawkins, Matthew James Johnson, Chris Leary, Dougal Maclauria. George Necula, Adam Paszke, Jake VanderPlas, Skye Wanderman-Minn Milne, and Qiao Zhang. JAX: composable transformations of Python+NumPy programs, 2018. URL Utthttp::
com/ google/jar
John Charles Butcher. history of runge-kutte methods. Applied numerical mathematics, 20(3):447-260 1996.
Woong-Gi Gi Chang. Tackgeun You, Sconguk Sco, Suha Kwak, and Bohyung Han. Domain batch normalization for unsupervised domain adaptation. In Proceedings of the IEEE/CV Conference on Computer Vision and Pattern Recognition, pp. 7354-7362, 2019.
Ricky T. Q Chen, Yulia Rubanova, Jesse Bettencourt, and David K Duvenaud. Neural ordinary differential cquations. In Advances Neural Information Processing Systems, volume 31, 2018.
Nicolas Courty, Rémi Flamary, Amaury Habrard, and Alain Rakotomamoniy. Joint distribution optimal transportation for domain adaptation. In Advances in Neural Information Processing Systems, volume 30, 2017.
Sofien Dhouib, levgen Redko, and Carole Lartizien, Margin-aware adversarial domain adaptation with optimal transport. In Hal Daumé III and Aarti Singh (eds.), Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 2514-2524, PMLR, 13-18 Jul 2020. URL
mlr. wwwpspreepeeeppp v11 ht1119//hhhiib20.. htm.
Yaroslav Ganin and Victor Lempitsky. Unsupervised domain adaptation by backpropagation. In International conference on machine learning, pp. 1180-1189, PMLR, 2015.
Yaroslav Ganin, Evgeniya Ustinova, Hana Ajakan, Pascal Germain, Hugo Larochelle, François Laviolette, Mario Marchand, and Victor Lempitsky. Domain-adveree adversarial training of neural networks, The Journal of Machine Learning Research,
(00:20996220000 2016.
Ian Gemp and Sridhar Mahadevan. Global convergence to the equilibrium of gans using variational inequalities. arXiv preprint arXiv:/888.00 01531, 2018
Gauthier Gidel, Hugo Berard, Gaëtan Vignoud, Pascal Vincent, and Simon Lacoste-Julien. A variational incquality perspective on generative adversarial networks. In ICLR, 2019a.
10

---

Published as a conference paper at ICLR 2022
Gauthier Gidel, Reyhane Askari Hemmat, Mohammad Pezeshki, Rémi Le Priol, Gabriel Huang. Simon Lacoste- Julien, and loannis Mitliagkas. Negative momentum for improved game dynamics. In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 1802-1811. PMLR, 2019b.
lan Goodfellow, Jean Pouget-Abades Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In Advances in neural information processing systems, pp. 2672-2680, 2014.
Ernst Hairer, Marlis Hochbruck, Arieh Iserles, and Christian Lubich. Geometric numerical integration. Ober- wolfach Reports, 3(1):005 882, 2006.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp- 770-778, 2016.
Judy Hoffman, Eric Tzeng, Tacsung Park, Jun- Man Zhu, Phillip Isola, Kate Saenko, Alexci Efros, and Trevor Darrell. Cycada: Cycle-consistent adversarial domain adaptation. In International conference on machine learning, pp. 1989-1998. PMLR, 2018.
Yu-Guan Hsieh, Franck lutzeler, Jérôme Malick, and Panayotis Mertikopoulos. Explore aggressively. update conservatively: Stochastic extragradient methods with variable stepsize scaling, In Advances in Neurul Information Processing Systems, volume 33, pp. 16223-16234, 2020.
Xiang Jiang. Qicheng Lao, Stan Matwin, and Mohammad Havaci. Implicit class consiconddt domain alignment for unsupervised domain adaptation. In Hal Daumé III and Aarti Singh (eds.). Proceedings of 37th Interna tional Conference on Machine Learning, volume 4827. PMLR, 13-18 Jul 2020. URL http::/::///o///
Proceedings of Machine Learning Research, pp. 4816- htm
ngs. ml
Chi Jin, Praneeth Netrapalli, and Michael Jordan. What is local optimality in nomconvex-nonconnee.... minimax optimization? In International Conference Machine Learning, pp. 4880-4889. PMLR, 2020.
Mingsheng Long Junguang Jiang, Bo Fu. Transfer-leamingg library. 2020.
h https://githur com/ hhuml/
TEansfer-Jearning--ia
Hassan K Khalil. Nonlinear systems. Prentice-Hal 2002.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv: 1412.6980, 2014.
GM Korpelevich. The extragradient method for finding saddle points and other problems. Matecon, 12:747-756. 1976.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-basse learning applied to document recognition. Proceedings of the IEEE, 86(11):2278 2324, 1998.
Jason D. Loc, Max Simchowitz, Michael I. Jordan, and Benjamin Recht. Gradient descent only converges to minimizers. In 29th Annual Conference on Learning Theory, volume 49, pp. 1246-1257. PMLR, 2016.
Alistair Letcher, David Balduzzi, Sébastien Racanière, James Martens, Jakob Foerster, Karl Tuyls, and Thore Graepel. Differentiable game mechanics, Journal of Machine Learning Research, 20(84):1-40, 2019. URL http::/ /mir.. wwtp:/ap...ee..... wttppeers/////190000 html
Liam Li. Kevin Jamieson, Afshin Rostamizadeh, Ekaterina Gonina, Moritz Hardt, Ben Recht, and Ameet Talwalkar. Massively parallel hyperparameter tuning. 2018
Richard Liaw, Fric Liang, Robert Nishihara, Philipp Moritz, Joseph E Gonzalez, and Ion Stoica. Tune: research platform distributed model selection and training. arXiv preprint 1807.051/8 2018.
Mingsheng Long, Zhangjie Cao, Jianmin Wang, and Michael Jordan. Conditional adversarial domain adaptation. In Advances in Neural Information Processing Systems, pp. 1640-1650, 2018.
Jonathan Lorraine, David Acuna, Paul Vicol, and David Duvenaud. Complex momentum for optimization in games, 2021a.
Jonathan Lorraine, Paul Vicol, Jack Parker-Holder, Tal Kachman, Luke Metz, and Jakob Focrster. Lyapunov exponents for diversity in differentiable games. arXiv preprint 122.5 2021b.
Haihao Lui. An resoluton ode framework for discrete-time optimization algorithms and applications to convex-coneave saddle-point problems. arXiv preprint arXiv:2001.08826, 2020.
11

---

Published as a conference paper at ICLR 2022
Yishay Mansour, Mehryar Mohri, and Afshin Rostamizadeh. Domain adaptation: Learning bounds and algorithms. Proceedings of The 22nd Annual Conference on Learning Theory (COLT 2009), Montréal, Canada, 2009. URL http: CS nyu, edu/ http://ohhlllpppscce//// ipt madap.pp.
Eric Mazumdar, Lillian Ratliff, and Shankar Sastry. On gradient- hased learning continuous games. SIAM Journal on Mathematics of Data Science, 2(1):103-131, 2020.
Eric V Mazumdar, Michael Jordan, and Shankar Sastry. On finding local nash equilibria (and only local nash equilibria) in zero-sum games. arXiv preprint 1901vv:901.00000 2019.
Panayotis Mertikopoulos, Bruno Lecouat, Houssam Zenati, Chuan-Sheng Foo, Vijay Chandrasekhar, and Georgios Piliouras, Optimistic mirror descent in saddle-point problems: Going the extral graddent) mile. In International Conference Learning Representations, 2019. URL /pteesev// net/
forum2id=Rkg81[CRK.
Lars Mescheder, Sebastian Nowozin, and Andreas Geiger. The numeries of gans. Advances in neural information processing systems, 30: 1825-1835, 2017.
Dov Monderer and Lloyd Shapley. Potential games. Games and economic behavior, 14(1):124-143, 1996.
Jorge Nocedal and Stephen Wright. Numerical optimization. Springer Science Business Media, 2006.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killcen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf. Edward Yang. Zachary De- Vito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang. Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performance deep learning library. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' Alché Buc, E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Sys- tems 32, pp. 8024 8035, Curran Associates, Inc., 2019. URL 9015 wel--ppytrchh--hheeeeee an- an- www.mptattiieee.mmmmm..mm style http:://aa.aaiaooooooooooaoaaoaa
odf
Xingchao Peng, Ben Usman, Neela Kaushik, Judy Hoffman, Dequan Wang, and Kate Saenko. Visda: The visual domain adaptation challenge. arXiv preprini urXi::171000692. 2017.
Chongli Qin. Yan Wu, Jost Tobias Springenberg, Andy Brock, Jeff Donahue, Timothy Lillicrap, and Pushmeet Kohli, Training generative adversarial networks by solving ordinary differential equations. In Advances in Neural Information Processing Systems, volume 33, pp. 5599-5609, 2020.
Lillian Ratifff Samuel A Burden, and Shankar Sastry. On the characterization of local nash equilibria in continuous games. IEEE Transactions on Automatic Control, 61):23330 2016.
Kuniaki Saito, Kohei Watanabe, Yoshitaka Ushiku, and Tatsuya Harada. Maximum classifier discrepancy for unsupervised domain adaptation. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 3723-3732, 2018.
Damien Scicur, Vincent Roulet, Francis Bach, and Alexandre d' d'Aspremont. Integration methods and optimization algorithms. In Advances in Newral Information Processing Systems, volume 30, 2017.
Ozan Scner, Hyun Oh Song, Ashutosh Saxena, and Silvio Savarese. Learning transferrable repre- sentations for unsupervised domain adaptation. In D. Lee, M. Sugiyama. U. Luxburg. I. Guyon, and R. Garnett (eds.). Advances in Neural Information Processing Systems, volume 29. Cur- ran Associates, Inc., 2016. URL [a::ps://ppst /ps=ps::/proceedings. newrips. http:///.....eeeeeeee//////////a ///1//////////p
Bin Shi, Simon Du, Michael Jordan, and Weijie Su. Understanding the acceleration phenomenon via high-resolution differential equations. arXiv preprint 1rX.v./810.08907,, 2018.
Rui Shu, Hung Bui, Hirokazu Narui, and Stefano Ermon. dirt-t approach to unsupervised domain adaptation. In International Conference on Learning Representations, 2018.
Yu Sun, Eric Tzeng, Trevor Darrell, and Alexei A Efros. Unsupervised domain adaptation through self- supervision. arXiv preprint arXiv: 1825, 2019.
Ilya Suiskever, James Martens, George Dahl, and Geoffrey Hinton. On the importance of initialization and momentum in deep learning. In International conference on machine learning, pp. 1-39-1147. PMLR, 2013.
Laurens Van der Maaten and Geoffrey Hinton. Visualizing data using t-sne. Journal of machine learning research, 9(1 1), 2008
12

---

Published as a conference paper at ICLR 2022
Guojun Zhang and Yaoliang Yu. Convergence of gradient-based methods bilinear games. In International Conference on Learning Representations, 2020.
Jingzhao Zhang, Aryan Mokhtari, Suvrit Sra, and Ali Jadbabaie. Direct runge-kutta discretization achieves acceleration. arXiv preprint arXiv:1805.00521, 2018.
Yuchen Zhang, Tianle Liu, Mingsheng Long, and Michael Jordan. Bridging theory and algorithm for domain adaptation. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 7404 7413. Long Beach, California, USA, 09 15 Jun 2019. PMLR. URL http: http:://pprocccanngg.oo mir press/ v97 / wwwzzaangg Saaaanngg 9tmm
13

---

Published as a conference paper at ICLR 2022
SUPPLEMENTARY MATERIAL
CONTENTS
Introduction
1
Preliminaries
Game Perspective on DAL
3.1
Dovvain-Adversarial Game
3.2
Characterization of the Domain-Adversaria Game
4
4
Learning Algorithms
Continuous Gradient Dynamics
Analysis with the GRT
Higher order ODE Solvers
5
Related Work
7
6
Experimental Results
7
Experimental Analysis on Digits
Comparison complex adaptation tasks
7
Conclusions
A
Concepts in Game Theory
15
Detinition
15
Games Characterizations
15
A.3 Case of Study DANN, Original Formulation from Ganin et al. (2016)
15
B Derivation of high-resolution ODES
17
B.1
High-resolution ODE of second-order Runge- Kutta method
17
Continuous dynamics of Extra-Gradient (EG)
17
High-resolution ODE classic fourth-order Runge Kulla method (RK4)
18
Proofs and additional theoretical results
20
Proposed Learning Algorithm
21
approximates RK2 (Heun's Method)
22
Experimental Setup Additional Details
22
Additional Experiments
23
E.
Natural Language Processing Tasks,
23
Sensitivity to Sampling Noise
23
Additional Comparison Game Optimization Algorithms
24
CO Gradient Descent and Extra-Gradient Algorithms
24
14

---

Published as a conference paper at ICLR 2022
E.5 Wall-Clock Comparison
24
Py Torch PseudoCode of RK2 Solver
25
A
CONCEPTS IN GAME THEORY
A.1 DEFINITIONS
Definition (Local Nash Equilibrium): point (w],w"; said local Nash Equilibriun of the domain adversarial game if there exists some > 0 such that:
Vi E (1,2,3), J:(wt, w 2) Je(ws, wid) s.t. |ws wi ||2 <
(10)
Intuitively, this is restricting the concept of NE to local neighborhood B(x",6) 6) : {1|= x2122 < 63 with
8 > 0.
practical characterization of the NE can be given in of the Best Response Map of each player which we now define.
Definition 3. (Best Response Map (BR)) The best response map BR; Q2 = O of player i is defined as:
BR; (R:(w=)) == arg min Jwwr,
(11)
wie
here the symbol = emphasizes best response map generally set map and not a singleton, thus is not function in general. In other words, there may be subset of element in Q for which (.,,w=)) is minimum.
The notion of NE be defined in terms of the generalized BR Ω = Ω map. This can be thought stacked vector where i-th element of BR is (w-(w.
Proposition 5. A point w E Q2 is said to be NE of the game if is a.fixed point of the generulized BR Ω = 22 map. That is.
w" E BR(w'))
= V (1,2,3), w E (BR((w"))
(12)
Proof. This follows from the definitions of BR map and NE.
Definition 4. (Asymptotically Stable) A point w is said to be a locally asymptotically stable point of the continuous dynamics do = f(w) if Re(A) < for all X E Sp(V fw)),, where Sp(V is the spectrum of (((.).
Definition Fis also known as the Hurwitz condition Khali] (002
Definition A stationary point a of C² function & R + said to be a strict saddle point if:
Amin( Amin(Vaz (zz"("") < 0 and,
A(V2.bl2 0, for any other X E sp sp( Vizd(="))
A.2 GAMES CHARACTERIZATIONSS
Potential Games. Potential Games were introduced in Monderer & Shapley (199) and be defined as
a type of game for which there exists an implicit potenrial function Φ 52 - such that Vel(w) = v(w). Consequently, a necessary and sufficient condition for the game to be potential is the Jacobian of the vector field Vv(w) being symmetric (see 3.3 in Mazumdar al. (2020) and Monderer & Shapley (1996)).
Purely Adversarial Games. This particular type of game refers the other extreme in which ((w) is non-symmetric matrix with purely imaginary cigenvalues. the game Hessian skew-symmetric these have also been called Hamiltonian Games Letcher et al. (2019).
A.3 CASE OF STUDY IN DANN. ORIGINAL FORMULATION FROM GANIN ET AL. 2016
As mentioned in the main text (Section 2 our analysis is compatible with both the original and more recent formulation of adweiinadversarral training such as Zhang et al. (2019) Acuna et al. 2021. In this section, specifically derive additional results for DANN Gamin al. 2016).
15

---

Published as a conference paper at ICLR 2022
In order to obtain the original formulation of DANN, let define ((_,)) b) = lo)(((b)) and o'd (() log(1-c')
Equation (2). This corresponds to the affect optimization). We can then rewrite ds, as:
divergence (JS) (up to constant shift that does
d,, = Exr log o h' g(x)) + Brwn log(1 - o h' s(x))
(13)
where (I:) Ite To simplify the notation, write H. o H.
We can now re-define the pscudo- pscudo-gradient v(w) of the game as the gradient of cach player loss with respect to its parameters. Letting we get from Equation
v()) = (v C, V (6 + Ada.s), - Vugda.e) R
(14)
The following propositions characterize local NE in terms of the pseudo-gradiens v(w) and its Jacobian H (w).
Proposition (Local NE) Suppose v(w) = and
Vin
V Wu (E )doee) O, Vag ~0,
V4 Wi
(15)
then is isolated local NE.
The proof is simple and follows from Propositions condition H + H1 > 0.
1 and 2 the definition of the vector field e(w) and the
that, in our scenario, the game is neither potential game nor purely adversarial game. However, write the vector field in the following form:
Cooperation with Competition. By examining the matrix (w),
Vui
m(w)= =
Vuze
+
AV dua
(16)
V
dhat
Vd(w)
((w)
where the first part corresponds to the gradient of the potential function ((w) = ((wr,(())) The second part, on the other hand, corresponds to function ((w) whose Jacobian is non-symmetric matrix. Analyzing them separately leads either potential an adversarial game respectively. We define this particular type of game cooperation (i.c., in the potential term) with competition (i.c., the adversarial term).
is worth noting that, while the spectrum of the game Hessian for first term has only real eigenvalues, the second term can have complex eigenvalues with a large imaginary component, Indeed, it can be shown that this second term approximates the one obtained for GAN using the non-saturating loss proposed by Goodfellow al. (2014) (e.g. À 1). In other words, the second term be written the geeudo-gradien of the two player zero-sum game min max.., dac- Building on this key observation and the work Mescheder et (017)): Berard et al. (2220) (Figure 4), where was experimentally shown that the eigenvalucs of the game Hessian for GANs have indeed a large imaginary component around stationary points, we can assume that the spectrum of the game Hessian in our case also have eigenvalues with a large imaginary component around the stationary points. This observation can also be used with Corollary ODE solvers instead of GD with GRL.
I to further motivate the of higher-order
Example 3. Consider the three-player game Equation (6 where f(wi, wi 2w1 w2 + w2. À = 1 and da, du,( wa) w + 99w2wy wz. The gradient play dynamics ub ((w) becomes:
2
2
= Aw
2
4
-99
w.
0
99
-2
The eigenvalues of A are 22 and -3 + 2 2149. From Corollary
should be < < 10
Is the three-player game formulation desired? In domain adaptation. optimization is means to an end. The final goal minimize the upper bound from Theorem to ensure better performance the target domain. One might then wonder whether interpreting optimality terms of NE is desirable. our context, NE means finding the optimal 9²' h- and f.' of the cost functions defined in Equation 44 This in turns leads minimizing the upper bound in Theorem
Remark on sequential games: Recently, Jin et al. (2000) introduced a notion of local min-max optimality for two-player's game exploiting the sequential nature of some problems in adversarial ML (i.e GANs). In domain-adversann learning, updates are usually performed in simultaneous manner using the GRL. Thus, focus here the general case where the order of the players not known.
16

---

Published as a conference paper at ICLR 2022
B DERIVATION OF HIGH-RESOLUTION ODES
Lemma 2. The high resolution ODE of resulting of the GD algorithum with the GRL is:
v v(w)
7 Vu(w))(() O(1²),
(17)
Proof.
This follows from Corollary of 20220
B. HIGH- RESOLUTION ODE OF SECOND ORDER RUNGE- KUTTA METHOD
The high-resolution resolution ODE was discussed in Shi et al. (2018) Lu (020)). For discrete algorithms with the following update:
w w + [1) w)
(18)
we can think of the trajectory as discretization of the continuous dynamics w : [0, +00) + R2, and in Equation (18), we have w(t), w wn(t + n)). Here, with slight abuse of notation we also use w for the continuous function of dynamies.
We derive high-resolution ODE of the second-order Runge Kutta method:
7 (((k), We+1 = we ( a))((ws)) 00(
Wk4-1/2 = Wkg 2a
where 0 a and is constant. If 1/2, we obtain Heun's 's method; a 1, obtain the midpoint method; a = 2/3, we obtain the Ralston's method. Combining two equations, we have:
Wi+1 Wk
-(1 a)o(wu) av(wx 7 v(wx)).
(19)
"
2a
Using the Taylor expansion:
v(we-
77 u ((wx) v(wx) ve(wu) ((w)) + O(1)²)
2a
20x
Plugging it back into Equation
19 and using the Taylor expansion wh+1 wk + mnb + 1////2 we have:
2 mp0
(ww) vv(w))<(w)) v(w) O(7²).
+ 1
(20)
Now we make assumption that we have the high-resolution ODE that:
fu(w) (w) + O(n").
(21)
Taking the derivative over f we have:
fo(w)fo( w) (
(22)
Combining Equation 20 Equation
and Equation 22 we obtain that:
fo(w) -ww), 3 fi (w) 0,
(23)
ie.. the high resolution ODE of second-ordes Runge Kutta method is:
i = -v(w) + 0(1²).
(24)
B.2 CONTINUOUS DYNAMICS EXTRA-GRADIEN (EG)
The continuous dynamics of Gradient Descent Ascent (GDA), Extra Gradient (EG) and Heun's 's method can be summarized as follows:
v v(w) + a o (n(w)u
For GDA, have -1/ for EG, we have 7/2 Lu 2020 for Heun's 's method, úi = v(w) O11)².
The Jacobian of the dynamics at the stationary point is V Ve(w)² Take À + ib Sp(Ve(w)) The eigenvalue of the Jacobian of the dynamics
a(a ab)²
ib a(a² b²) + i(b 2ab)a.
(25)
We want the real part to be negative, i.c.:
a + aaa2 - -b²) < 0,
(26)
and thus:
a(1 + oa) < ab².
(27)
for FG, and the dynamics diverges if (11+ (n/2)a) 2 n/2/ /2. When 1j large, and nnd nnana then it diverges. However, the high-resolution ODE of sccond-order Runge-Kutta methods only requires
17

---

Published as a conference paper at ICLR 2022
B.3 NIGH-RESOLUTION ODE OF CLASSIC FOURTH- RUNGE KUTTA METHOD (RK4)
this subsection, we derive the high-resolution ODE of the classic fourth-order Runge Kutta method. prove following result: Theorem 3. The high-resolution ODE of the classic fourth-order Runge-Kuutn Kutta method (RK4):
w o (o(w) + +02((w) + 2ug 2uz(w) + =s(w)),
(28)
where
(2(w) = v(w
? ((w)), vz(w)= c(w ? v2(2)) ca(w) = o(w - -nju(w))) 2
(29)
2
is
E = vww) + O())).
(30)
Proof.
We the following Taylor expansion:
v(w + 6) = v(w) = Vu(w)ō + V
(31)
where V²n(w) Rd x Rd + h is symmetric bilinear form, and V [(w) symmetric trilinear form. With the formula we have:
R Rd
x
Rd is
(ww) = v(w) [V(())us()) + v ((wx((s(w) v
va(w)) + 0(1"),
6
(32)
vs(w) v(w) Ve(w)va(w) v2 vw)
( O(7²),
48
(33)
02(w) www) "I Ve(w)((w) 8
v'v(w)(((w), ((w))
48
(34)
Putting them together we have:
Va (w) + 2w>(w) + 202(w) -otte +
- v2 vlu(w)((ss(w 1 v'e(w)(vs(w) + (
7
2
n²
v (()
O(n²),
(35)
4
uy (w) + v2(w) + v(w) ww - (vw
+ v(w)) + z v (()))(((w))vu())) + +
(36)
v2(w) + v(w) 2v(w) Vv(())((w)++ + O(7")
(37)
Bringing Equation 33) Equation 36 we obtain:
es(w) + (w v(w) 3u(w) - 1/ VeV(())( + o (ww" u(w)) + (V((w)))o(w) + + (38)
Putting Equation 38 and Equation 37
together, we have:
(e + (w)) + v(w)) = 3,/Ve(w)(()) + (VV
(((w)))((()))()))oooo n ((o(w))'((u)++00 +
(39)
Moreover, have
V =()) - Vo(w))(ww) - Vo(w)((w)) 0
(F O(()),
(40)
and similarly
((()))(((w)) (wo.eeell.ooooooooooo0oo00000000 O(n)) (41)
18

---

Published as a conference paper at ICLR 2022
Bringing Equation (39 and Equation 40 into Equation
35
results in
(u(w) + (w)(w) + (w)) + v(w)) = - 3r o1
4
+ Vo(w)VV'((u)(v(u)) + V e(w))) + O(n").
(42)
Let us now derive the high resoluesotttion ODE, From Equation
we have:
w w
(wa(w) + 20% (w)(w) + (w2(w) + v(w)).
(43)
Let us assume that w = (t( + 7) and w w(t). Expanding the left we have:
2 1 + S 17
24 W.
(44)
Let us assume that the high-resolution ODE up to O1)²*) has the form:
à fo(w) + nfw + 17" fu(w) + fs(w)
(45)
Taking derivatives both sides, have:
+ + ((T O(1)) = (V((w) +
+ -/tp:///w000.///////.o--------//
+ (((
O(7²).
(46)
Comparing the order O(1) on both sides Equation 43 we have:
fo(w)= v(w), (w) + Vl(w))((w)) = Vo(w)o(w))
(47)
which gives fo(w) = v(w) and fi (w) Bringing back to Equation (46 we obtain:
Ø Vu(w)o(w) + O(n").
(48)
We take the derivatives on both sides of Equation 48 to get:
((Vo(u)((w)) +
(TT Let us now compute ((Ve()))(())))((()) We note that V(Ve(w)u(w)) is linear form and
(49)
Ve(w 00o( = (Ve(w) < Vll &olu)) o(111)))
= Vv(w)u(w))
(50)
Therefore, we have
(51)
With Equation
51 we compare O(1²²) on both sides Equation
43 and obtain
fa(w)
(52)
Finally, we take the derivative of Equation 51) Since
Vev(1 + 5)(w + 6), v(w0 + 6))
= (
+ 2V'((w))(ww) Vo(w)o)
+
(53)
we have:
((V")( )())))))))))))))))))))))))))))) (w))) 2
oV)((w)((())) vo()))()) (54)
Similarly, since
(Ve( +0))ow
= (Ve(w) HA
= =(w Vo Vo(w)o()))
+ (
(55)
19

---

Published as a conference paper at ICLR 2022
((Vo(a)))((w>(((()) (v(()) Vo(w)v(w)) Vo((u)V' Vu(w))((w). (56)
Combining Equation 51
Equation 54 and Equation
56 gives:
W Vinb Ve(w) + (())(((()) v()), (3 Ve(w)((w))
((()))) v(w)).
(57)
Combining Equation 45
Equation (46)
Equation 51 and Equation 57 and comparing the ((1))) term of
Equation 43).
we obtain
fa(w) = O.
(58)
Therefore, the high-resolution ODE is:
w = -
(59)
L
C PROOFS AND ADDITIONAL THEORETICAL RESULTS
Several proofs in this section are based on the derivations of the high resolution ODEs that were proven in
Appendix B
Theorem 4. Suppose & R + R and & is C², Suppose also any stationary point x² of o s.t. Vo(x*) = 0
either:
strict local minimum, i.e. 22 (2x"
2. strict saddle. (Definition 5
Then, the gradient flow is attracted towards a local minimum of Φ
Proof.
i -vb(<)
(60)
Define g(r) = VV
Let us first show that strict saddles are non-asymptotically stable fixed points. Thus, gradient descent is not attracted to them.
((x) ~ (2n0(x)( - x²)
since Vo(x") = where = == U
(61)
g(2) A(2-2²))
(62)
This implies g(=); R Amin (V= () - 2²); > Thus, we just showed that strict saddles are non- asymptotically stable, as desired.
Let us now show that all the local minima are asymptotically stable, and gradient descent is then attracted to them.
b) Define V(x) = ((x) o(x") be Lyapunov function. We have xf is asymptotically stable if:
VV(x) *
(63)
From which the result follows. (c.g (V g(x) -11((=1113)
Similar results with different proof be derived from Lee al. 2016).
Theorem The high resolution ODE of GD with the GRL up to O(n) is:
-o(w) (V(())((w)
(64)
Moreover, this is asymptotically stable (see AppendixxA.I at stationary point w" (Proposition eigenvalue written as X + ib E (o(-Vu(w"") )). we have O > 11aa 62)/2 > a.
3 iff for all
Proof. This theorem can obtained by computing the Jacobian condition Lemma[] Specifically, we have the Jacobian of the dynamics at the stationary point is:
ODE dynamics using Hurwitz
-V(w=" ? vu(w")²
(65)
20

---

Published as a conference paper at ICLR 2022
Take A a Sp( ([-[v(ww")) }), must have:
Rlu + ib 2 (-a ib)²] < O, where P2 stands for the real part.
(66)
then,
(a b²) <
(67)
desired.
Corollary 1. For the high resolution ODE of GD with GRL (i... Equation 64 to be asymptotically stable, the learning rate n should be upper bounded by:
2a 0 <<1 < 8 a²²
(68)
for all x ib Sp(- (Vv(w))))) with large imaginary part (i.e. such that [a] < [b/].
Proef. With |al < [6] where b is the imaginary part of A E C, algebraic manipulation of Theorem ie. 11(b² at) 2a leads the desired result.
Theorem 3. The high resolution ODE of any RK2 method up to O ab = -o(w), is asymptotically stuble if for all eigenvalues x =
Sp( -u(["")())))) }), we have a < O.
Proof. This theorem can be obtained by computing the Jacobian the ODE dynamics (see Appendix B the derivation) and using the Hurwitz condition Lemma]] [ For details, see the proof of Theorem
Unlike the high resolution ODE of GD with GRL in Corollary D up to O(r)). there is no upper bound constraint on the learning rate. Therefore, the cost additional extra gradient computation, we are allowed take a more aggressive step. We observe in practice that this leads to both faster convergence and better transfer performance.
extra-gradient
Lemma Suppose the game G(I, S4 J.) is potential game with potential function functionn & Suppose minimizers of & are either local minimum or strict saddle (see Definition Sy. The gradient play dynamics converges to local Nash Equilibrium.
Proof. A potential game can analyzed in terms of the implicit function ((w) since Vo(w) v(w). From Theorem 4 we know the gradient flow in Φ(w) converges to a point w" that is a local minimum. Thus, this follows from Proposition
D
Proposition domain domain- adversarial game neither a potential nor necessarily purely adversarial game. Moreover, its gradient dynamics are not equivalent to the gradient flow.
sufficient and necessary condition for game to be potential is Vr(w:) being symmetric. Computing Vi(w) using Equation [4) leads Vv(w) being asymmetric, from which the first part of the result follows. Another way to see this, it to notice a there is no potential function e satisfying Vo(w) = v(w) (because of the flip in the sign in de, Since the game is not potential game then the vector
Prouf. From appendix A.2
field is not equal to the gradient flow (see also for more details Mazumdar et al. (2020). ) To see the game
not necessarily purely adversarial game, it suffices show example for which this does not happen.
See Appendix A.3 and example therein.
C.I PROPOSED LEARNING ALGORITHM
Algorithm Pseudo-Code of the Proposed Learning Algorithm
Input: source data D., target data D,, player losses J,, network weights fwi k=1 learning rate n for t = to 7 do
Fx, 3/4 D.. D:
F. [gradient(I.. Ft, Ve, Js) for i in 1..3 ]. W Gradient Descent(v, w0, 1))
W Singe-KutaSolver((e w, steps=1)
end for
21

---

Published as a conference paper at ICLR 2022
C.2 CO APPROXIMATES RK2 (HEUN'S METHOD)
We have the update rule of CO Mescheder 2017):
w- [no(w) (
(69)
where V | 1 = Ve(w)) v(w)
From RK2 (Heun's s Method), we have:
w= + w
11 (v(w)) + r(w ((w-nu(w)))
(70)
2
" 2 (20(w) - (/V(())(()) 0(1)))
= w
(71)
If V'-ve(w) = Ve(w)
Ve(w) skew symmetrie. we can see that Equation 71 approximates the CO
optimization method from Mescheder al. (2017) This assumption is however not necessarily true in our case which may explain why RK2 was better experiments. Experimentally, for CO, the best transfer performance was obtained for y = 0.0001. We also observed that CO is very sensitive to the choice of 7.-
D EXPERIMENTAL SETUP ADDITIONAL DETAILS
Our algorithm is implemented in Jax Bradbury et al. (2018) (Digits, NLP benchmark) and PyTorch (Visual Task). Experiments conducted NVIDIA Titan V and VI00 GPU Cards.
The digits benchmark constitutes of two digits datasets MNIST and USPS LeCun al. [9988] Long et (2088) with two transfer tasks (M + and
M). We adopt the splits and evaluation protocol from Long
el al. (018)) which uses 60,000 and 7,291 training images and the standard test set of 10,000 and 2,007 Test images for MNIST and USPS, respectively. We follow the standard implementation details of Long et al. 2018 for this benchmark. Therefore, we LeNet(LeCun et al. (1998) the backbone architecture, dropout (0.5), fix the batch size to 32, the number iterations per epoch to 937 and use weight decay (0.005). For GD-NM. we use the default momentum value (0.9). We follow the same approach for the additional hyper- apper-paraettess of Adam.
Grid Search Details for Comparison Standard Optimizers. For the learning rate, learning schedule and adaptation coefficient (A), run the following grid search and select the best hyper-parameters for each optimizer.
learning rate: 0.0001, 0.001, 0.01, 0.03, 0.1, 0.3,
learning scheduler: none, polynomial.
adaptation coefficient (A): 0.1,
The grid is run using Ray Tune Liaw et al. 2018) and on the transfer task M->U. To avoid expending resources in bad runs we use HyperBandScheduun Li al. (201). The same hyper-parameters are used for the other task (i.e - M). The best criteria correspond to the transfer accuracy is typically done in UDA).
Grid Search Details for Comparison vs Game Optimization Algorithms. Similar to the previous experiment, for the comparison vs game optimization algorithms, we run the following grid search in order to select their best parameters for the comparison. In the case of CO, we additionally add 7 extra-hypermeter to the grid as we experimentally found this optimizer to be sensitive to this parameter.
learning rate: 0.0001, 0.001, 0.006, 0.01, 0.1.0.11... 0.3, 0.4.
learning scheduler: none, polynomial.
Adaptation coefficient (A): 0.1, 0.., 1.
CO Only. Additional (7): 10, 1.0, 0.1, 1,1,0.000 0.01, 0.001, 0.001, 0.0001
We show the best results of this grid search in Table For EG, we observe training diverges for learning rates greater than 0.006.
Experiment on Visda 2017. For the visual tasks our implementation is built on PyTorch(1.5.) and on top of the public available implementations LonL et al. (2018): Zhang et al, (2019); JJunuaan Jiang (2020). We did not run grid search here as it would be very computationally expensive. For the optimizer parameters, we tune thoroughly GD with Nesterov Momentum following the recommendation and implementation from I Long al. 2018): Zhang al. 2019). For our method, we keep the exact same haper-parameters of GD with NM, but
22

---

Published as a conference paper at ICLR 2022
increase the learning rate. We do not experiment with RK4 since the performance similar RK2 in the other benchmarks (see Tables and it more computationally expensive.
Experiment on Visda 2017 with SoTA algorithms. For the comparison using SoTA algorithms, we use the well-tuned hyper-parameterss from Jiang el al. (2020) and set the discrepancy measure to be f-DAL Pearson in Acuna et al. [222T) since this empirically was shown to be better than both JS and 7-JS//DD, We use Implicit Alignment Diang et al. (2020) as this method also allows account for the dissimilarity between the labels marginals. We did not run grid search here as it would very computationally expensive. our case, we only increase the learning rate to 0.2.
Experiment on Natural Language. In this experiment, we use the Amazon product reviews dataset Blitzer et (2006) that contains online reviews of products collected on the Amazon website. We follow the splits and evaluation protocol from Courty
2017): Dhouib al. (2020) and choose 4 of its subsets corresponding different product categories, namely: books (B), dvd (D), electronies (E) and kitchen (K). As in Courtyy et al. (017))(Dhouib Dhouib et al. (2000), from where we took the baseline result, the network architecture a two layer
MLP with sigmoid function. In our case. pppammprreeterss are kept the same but the learning rate is increased by factor of 10.
Implementation different frameworks. We use both Jax and Pytorch in our paper for simplicity. Since the proposed method only requires changing some lines of code, can easily implemented in different frameworks. Prototyping in Jax small scale experiments such as the one in the Digits datasets is very easy. We then use PyTorch in order to integrate our optimizers with large-scale SoTA UDA methods (their codebase was implemented in PyTorch). This shows the versatility and simplicity of implementation of high-order ODE solvers. We did not see any issue while working with either Jax or Pytorch. Our choice of framework was simply based on modifying existing source code to evaluate our optimizer.
Remark on error bars. For experimental amalysis involving a grid-search, we use the same seed and identically initialize the networks. That is, we give every optimizer the same fair opportunity to win as reported above. Note that reporting avg and std from grid-search significantly increases the computational demand did not this. That said, we report avg and std our main experiments using the best parameters found on the grid-search.
E ADDITIONAL EXPERIMENTS
E. NATURAL LANGUAGE PROCESSING TASKS.
We also evaluate our approach on natural language processing tasks. We use the Amazon product reviews dataset (Bliteer et al. 2006). We follow the splits and evaluation protocol from coouCyy al. (207)): Dhouib et al. (2020) choose of its subsets corresponding to different product categories, namely: books (B), dvd (D), electronies (E) and kitchen (K). our case, hyper-parameiert are the same provided by authors the learning rate is
increased by factor of 10. Table shows noticeable gains by replacing the optimizer with either RK2 or RK4.
B-D
B E. B-
D-BB
D -E
D-
E.
E-+
E.
K
-
K .D
K - E Avg
DANN DDouwi et al. 2020
80.6
74.7
76.7
74.7
73.8
76.5
71.8
72.6
85
71.8
73
84.7
76.3
with RK2 with RK4
82.3
74.3
75.7
80.2
79.2
79.6
72.3
74.2
86.5
72.6
73.6
86.2
78.1
81.6
75.0
78.1
79.4
78.3
80.0
74.1
74.6
86.7
73,5
74.6
86.0
78.5
Table 4: Accuracy (%) on the Amazon Reviews Sentiment Analysis Dataset (NLP)
E.2 SENSITIVITY TO SAMPLING NOISE
Table 5: Sensitivity to Sampling Noise controlled by the batch size in the Visda Dataset. Resnet-50
Batch Size
Avg
Std
GD
64
67.82
0.29
128
67.50
0.11
160
67.42
0.24
64
73.20
0.36
Ours(RK2)
128
73.81
0.26
160
74.18
0.15
23

---

Published as a conference paper at ICLR 2022
Table 6: Comparison vs Game Optimization Algorithms (best result from the grid search)
Algorithm
M U
GD GD-NM
90.0
93.2
EG Korpelevich 1976)
86.7
CO Mescheder et al. (017))
93.8
Ours (RK2)
95.3
Ours(RK4)
95.9
E.3 ADDITIONAL COMPARISON VS GAME OPTIMIZATION ALGORITHMS
Table we show the sensitivity our method sampling Noise controlled by the mini-batch size. Specifi- cally, we show results for 64, 128, 160 with 160 being bigger size we could GPU memory). We also add results for GD. We observed that our method performs slightly better when the batch size was bigger.
Table 6 shows the results of the grid-scarch for the comparison vs game optimization algorithms. For each optimizer, these results correspond their best (in terms of transfer performance) determined from the grid- search explained Appendix baselines.
also add GD comparison. Our method notably outperforms
E.4 CO VS GRADIENT DESCENT AND EXTRA-GRADIES ALGORITIMMS
In Table oowe we can observe that RK solvers outperform the baselines. Interestingly, we can also observe that CO outperforms both EG and GD-NM. In this section, provide intuition about why this may be the case in practice and conduct additional experimental on this direction.
the analysis presented in Section 4 we show that a better discretization implies better convergence to local optimality (assuming w' exists, and that it is a strict local NE). Specifically, under those assumptions, we show that in both GD and EG methods
should put upper bound to their learning rate (see Section and appendix B22 In Appendix C22) on the other hand, we show CO be interpreted in the limit approximation the RK2 solver. Based this, we believe in practice CO may approximate the continuous dynamics better than GD and EG. Particularly, if we have an additional hyperparameter (+) to tune thoroughly. We believe this might also be the reason of why we found CO to be very sensitive to the parameter. In Table 7 compare the performance before and after removing the best performing y from the grid search. We can see for values others than the best y, CO does not outperform GD-NM either.
Table 7: Performance of CO others. CO(y =le-3) corresponds to the best result after removing le-4 from the grid search.
Method
M +U
GD
90.0 GD-NM
93.2
CO (7 le-4)
93.8
CO (7 le-3)
91.6
RK2
95.3
E.5 WALL-CLOCK COMPARISON
Table 8: Average Time Per Iteration Comparison WWall-Clock Comparison)
Algorithm
Avg time per iteration
GD-NM
0.26 + 0.003
Ours(RK2)
0.49 + 0.008
24

---

Published as a conference paper at ICLR 2022
show experimental results of wall-clock comparison between RK2 and GD-NM. Specifically, we compute the average over 100 on a NVIDIA GPU: TITAN CudaVersion 10.1 and Py PoTorc version: 1.5.1. As we can see, the average increase time is less than 2x slower in wall-clock time. This is line with the claims made in our submission. We additionally emphasize that this time can be improved with more efficient implementations (e-g. Cuda). Moreover, many more efficient high-order ODE solvers exist and could be used in the future. Our work also inspires future research in this direction.
In Table
F PYTORCH PSEUDOCODE OF RK2 SOLVER
Below, show how implement the RK2 solver in PyTorch by simply modifying the existing implementation SGD.
class (torch. http://www.cccccccc/////////aaaa
Based https://github
def update_step (self,
( fnd_
fwo_bwd fn: that computes y=model (x) loss (y, yhat) .backward
example:
training 1oop
X, yhat=sample_ wwwpssaaapeeeeeeeeeeeeeee from datadaadatedeeeeeeooeoeeeeeeeeee ()
petimizer.zero_gzzee
def Fwd [id_bwd_ff ()
y-model (x)
joss=compute lospppute_____sss_eeeeeeosssssss loss yhat)
loss. loss.backward()
return loss,y
fnd_bwd__f(( optimizer update (fwd_bwd__t) ***
We want to compute the update equation:
- -n2x v (w) n/2 x v (w-nxv(w))
temp_step = 1)
with torch.no_grad.
for ji_, group enumerate (self. (self. param groups) Rignore weight-decay for simplicity.
for ii_, p in enumerate (group I'params' 11) if p.grad is None: continue d p.grad # (w)
first part of the step.
n/2xv(w)
pl b.data.ccenee detach
pl. _i_add_[__pp) alpha--0.5 group['Ir']
#storing for later used. temp_step E"
pl
Computing now w-n+v(w) for the second part of the step p add (d_e, alpha--1.0 group['Ir'])
set to none
p.grad = None # self,
# extra step evaluation.
f this function does model forward, compute loss and loss backward. loss, bwd () # gradients are now v (K-R+v(w))
with terch Berch.no_gradul
25

---

Published as a conference paper at ICLR 2022
for ji_, group in enumerate (self. param groups)
for ii_, P enumerate (group pparams 1]); if p.grad is None:
continue
d_p p.grad # v(N-nAv(v))
umpacking the first part of the step.
pl = (cmp__steplF((11__111111.
updating p with the stored value from before.
this is equivalent to p pl w-n/2 v V (but sligthly faster) p. p.zero_()
p.add_(p1)
fv= n/2xv n/2 v(w-nxv(w)
p. p.ddd_ alpha=-0.5 group [ouupl11. ('1r'))
26


Reviews:
[{"review_id": "y-64Ix8UXw", "reviewer": "Reviewer_1YN1", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "Strengths:\n\n* Well written and understandable\n* Theoretical sound in both problem description and solution\n* Analyzing domain adaptation learning from a game perspective and analyzing the stability of the optimizer with the gradient reversal layer model is novel \n* Relevant related work is considered and compared\n* The experimental part is sufficient and supports the theoretical claims\n\nWeaknesses:\n* The theoretical analysis is limited to full batch training while in practice as well in the experiments mini-batches are used. However, the authors mentioned it in the paper.\n* As with gradient-based methods, this method could also converge to a non-Nash equilibrium as outlined in [1], however this is likely a rare case and not unique to this proposal\n\n[1] Mazumdar et al. On Finding Local Nash Equilibria (and Only Local Nash Equilibria) in Zero-Sum Games. https://arxiv.org/abs/1901.00838\n", "summary_of_the_paper": "This manuscript considers the adversarial domain adaptation training problem, specifically the gradient reversal method, from the perspective of game theory. The authors show that gradient-based optimizers without an upper bound on the learning rate violate asymptotic convergence guarantees to local NEs. The authors further show that these constraints can be lifted by higher order ODE solvers. In the experimental part, the authors evaluate their method i.e. Runge-Kutta ODE solvers of order 2 and 4 with different general and also game optimized gradient-based optimizers on a MNIST/USPS digits dataset. Furthermore, they show hyperparameter robustness of their method and finally, the method is tested on more complex image and NLP datasets and compared to current SOTA methods. Overall better results are achieved.\n", "summary_of_the_review": "The proposed method is theoretical founded and the experimental part supports the claims and the analysis is novel. I vote for accept, good paper.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "sqaHTzr6LUH", "reviewer": "Reviewer_tiyE", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "(I am not a specialist in domain adversarial learning. Therefore I am not entirely sure about the novelty and impact of the work in this field).\n\nThe paper is very well written. The introduction of both fields of domain adversarial learning (sec 2) and game theory (sec 3) is done properly, with an adequate study of the related work. Moreover, the authors did a good job convincing about the complexity of the three-players game setting.\n\nFrom this perspective, using known tools from game theory / variationally inequalities / numerical analysis for ODE discretization, the authors show necessary and sufficient conditions for the existence of local Nash equilibrium (prop. 1 and 2), showed that a modified dynamic of the gradient flow (equation (8) ) ensure global convergence of the Euler discretization, and developed an algorithm (RK-2, generalization of extra-gradient, equation (9)).\n\nFinally, they discussed several approaches with solid numerical experiments on various problems.\n\nIn terms of novelty, there are no \"new\" theoretical results, properly speaking. The novelty here is the derivation of the domain adversarial learning into a game, which is not straightforward but simplifies its analysis. Thanks to this new perspective, I believe this could open new doors and research direction in this field. For this reason, and because the paper is particularly well written, I recommend the paper to be accepted.\n\n\n*** Post rebuttal\n\nI have read the authors' answer and decided to keep my score. ", "summary_of_the_paper": "The authors exhibit a strong link between game theory and domain-adversarial training. They show the optimal point in the latter is a Nash equilibrium of a three players game. From this perspective, the authors show that standard approaches, like gradient descent, cannot work in this setting as the method is known to be divergent in such a case. Instead, they propose to use Runge-Kutta methods (for example) to discretize the ODE, which gives insights for novel algorithms with better convergence guarantees.", "summary_of_the_review": "The authors presented a link between game theory and domain-adversarial training. In similar topic, such as GAN, such link opened new research perspectives and impacted positively the area. I believe this could be also the case here.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "sFAIHPWNAAs", "reviewer": "Reviewer_uzT5", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "1. The authors claim that \"The gradient field of Equation (2) and the game's vector field (see Section 3.2) are equivalent, making\nthe original interpretation of DAL and our three-player formulation equivalent.\" Why does field equivalence induce formulation equivalence? What is the exact definition of \"equivalence\" here?\n\n2. The layout of the paper needs to be improved. For example, Example  2 should be an independent paragraph in the paper but not a \"window\" embedded in the other section. Some figures and tables have the same issue. \n", "summary_of_the_paper": "This paper analyzes adversarial domain learning (DAL) from a game-theoretical perspective, where the optimal condition is defined as obtaining the local Nash equilibrium. From this view, the authors show that the standard optimization method in DAL can violate the asymptotic guarantees of the gradient-play dynamics, thus requiring careful tuning and small learning rates. Based on these analyses, this paper proposed to replace the existing optimization method with higher-order ordinary differential equation solvers. Both theoretical and experimental results show that the latter ODE method is more stable and allows for higher learning rates, leading to noticeable improvements in transfer performance and the number of training iterations. ", "summary_of_the_review": "This paper is well-written and easy to follow. The theoretical contribution is solid, and the experimental studies show the superiority of the proposed method on the domain transfer task. As a consequence, I think the quality of this paper is marginally above the acceptance threshold. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "7GqHin6bLum", "reviewer": "Reviewer_LuBk", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "Strengths :\nThe game-theoretical formulation is natural for this important problem.\n\nThe experiments seem to support the asymptotic convergence guarantees of the optimizer.\n\nThe empirical results look somewhat significant.\n\nThe practical significance of this work reveals that using high-order solvers instead of Gradient Descent (GD) in this setting leads to better results.\n\nWeakness:\nThe technical novelty is only marginally novel and quite straightforward.\n\n\n", "summary_of_the_paper": "The setting in the paper is the classic unsupervised domain adaptation problem, where we are given a labeled sample from a source distribution and an unlabeled sample from a target distribution. The goal is to minimize the risk on the target distribution. Theoretical results led to a breakthrough in practice - the Domain Adversarial Learning architecture (Ganin et al., 2016). \n\nThe paper suggests looking at the paper from a game theory perspective. This is natural, as the objective is to minimize the loss on the source distribution while maximizing the distinction between the distributions. \nThe optimal solutions of the game are characterized by the local NE.\n\nMotivated by the results from game theory, the authors suggest replacing Gradient Descent (due to its limitation in this optimization problem) with other optimizers - ODE (ordinary differential equation) solvers.", "summary_of_the_review": "My vote is -  marginally above the acceptance threshold due to the aforementioned reasons.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: Summary (from reviewer uzT5): This paper analyzes adversarial domain learning (DAL) from a game-theoretical perspective, where the optimal condition is defined as obtaining the local Nash equilibrium. From this view, the authors show that the standard optimization method in DAL can violate the asymptotic guarantees of the gradient-play dynamics, thus requiring careful tuning and small learning rates. Based on these analyses, this paper proposed to replace the existing optimization method with higher-order ordinary differential equation solvers. Both theoretical and experimental results show that the latter ODE method is more stable and allows for higher learning rates, leading to noticeable improvements in transfer performance and the number of training iterations.

All reviewers appreciated the contributions of this paper and recommended acceptance. While the methods themselves are not novel, the game perspective applied to this problem appears to be and the use of higher-order solves yield interesting theoretical and empirical improvements.

== Additional comments ==

1) For the comparison vs. game optimization algorithms (Figure 3), it would be nice to normalize the x-axis so that one "epoch" yields comparable computational cost among the different methods (as RK4 and RK2 is much more expensive than EG or GD per mini-batch). Given that EG had such bad performance there, it would not change the conclusions; but the current scaling is still quite misleading. Same comments for Figure 2.

2) Note that modern approaches for stochastic extragradient recommend to use different step-sizes for the extrapolation step and the update step (see e.g. Hsieh et al. NeurIPS 2020 "Explore Aggressively, Update Conservatively: Stochastic Extragradient Methods with Variable Stepsize Scaling") I suspect that much bigger step-sizes could be used in this case while maintaining convergence, and this version should be added to Figure 3.

3) In "Related Work | Two-Player Zero-Sum Games" -> note that Gidel et al. 2019a provided all their convergence theory and methods for stochastic variational inequalities and thus it also applies to three-player games, unlike seems to be implied by this paragraph. In particular, all the algorithms they investigated (Extra-Adam amongst others) could also be applied to DAL. While I can see that the specifics of the objective in DAL might be different than for GAN optimization, it would be worthwhile to acknowledge these alternative approaches more clearly, and I encourage the DAL community to investigate their performance more exhaustively for DAL than what was done in this paper.
Decision: Accept (Poster)