summaries: 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.

summaries: 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).   The 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.  The optimal solutions of the game are characterized by the local NE.  Motivated 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.

summaries: 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.

summaries: 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.

abstractText: 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 local Nash equilibria, 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 half of training iterations. Our optimizers are easy to implement, free of additional parameters, and can be plugged into any domain-adversarial framework.

authors:
David Acuna
Guojun Zhang
Marc T. Law
Sanja

title: Fidler. f -domain adversarial learning: Theory and algorithms

venue: In Proceedings of the 38th International Conference on Machine Learning,

authors:
Waïss Azizian
Ioannis Mitliagkas
Simon Lacoste-Julien
Gauthier Gidel

title: A tight and unified analysis of gradient-based methods for a whole spectrum of differentiable games

venue: In Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics,

authors:
David Barrett
Benoit Dherin

title: Implicit gradient regularization

venue: In International Conference on Learning Representations,

authors:
Tamer Başar
Geert Jan Olsder

title: Dynamic Noncooperative Game Theory, 2nd Edition

venue: Society for Industrial and Applied Mathematics,

authors:
Shai Ben-David
John Blitzer
Koby Crammer
Fernando Pereira

title: Analysis of representations for domain adaptation

authors:
Shai Ben-David
John Blitzer
Koby Crammer
Alex Kulesza
Fernando Pereira
Jennifer Wortman Vaughan

title: A theory of learning from different domains

venue: Machine learning,

authors:
Shai Ben-David
Tyler Lu
Teresa Luu
Dávid Pál

title: Impossibility theorems for domain adaptation

venue: In Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics,

authors:
Hugo Berard
Gauthier Gidel
Amjad Almahairi
Pascal Vincent
Simon Lacoste-Julien

title: A closer look at the optimization landscapes of generative adversarial networks

authors:
John Blitzer
Ryan McDonald
Fernando Pereira

title: Domain adaptation with structural correspondence learning

venue: In Proceedings of the 2006 conference on empirical methods in natural language processing,

authors:
James Bradbury
Roy Frostig
Peter Hawkins
Matthew James Johnson
Chris Leary
Dougal Maclaurin
George Necula
Adam Paszke
Jake VanderPlas
Skye Wanderman-Milne
Qiao Zhang

title: JAX: composable transformations of Python+NumPy programs, 2018

venue: URL http://github.com/google/jax

title: A history of runge-kutta methods

venue: Applied numerical mathematics,

authors:
Woong-Gi Chang
Tackgeun You
Seonguk Seo
Suha Kwak
Bohyung Han

title: Domain-specific batch normalization for unsupervised domain adaptation

venue: In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition,

authors:
Ricky T.Q. Chen
Yulia Rubanova
Jesse Bettencourt
David K Duvenaud

title: Neural ordinary differential equations

venue: In Advances in Neural Information Processing Systems,

authors:
Nicolas Courty
Rémi Flamary
Amaury Habrard
Alain Rakotomamonjy

title: Joint distribution optimal transportation for domain adaptation

authors:
Sofien Dhouib
Ievgen Redko
Carole Lartizien

title: Margin-aware adversarial domain adaptation with optimal transport

venue: Proceedings of the 37th International Conference on Machine Learning,

authors:
Yaroslav Ganin
Victor Lempitsky

title: Unsupervised domain adaptation by backpropagation

authors:
Yaroslav Ganin
Evgeniya Ustinova
Hana Ajakan
Pascal Germain
Hugo Larochelle
François Laviolette
Mario Marchand
Victor Lempitsky

title: Domain-adversarial training of neural networks

venue: The Journal of Machine Learning Research,

authors:
Ian Gemp
Sridhar Mahadevan

title: Global convergence to the equilibrium of gans using variational inequalities

venue: arXiv preprint arXiv:1808.01531,

authors:
Gauthier Gidel
Hugo Berard
Gaëtan Vignoud
Pascal Vincent
Simon Lacoste-Julien

title: A variational inequality perspective on generative adversarial networks

venue: In ICLR,

authors:
Gauthier Gidel
Reyhane Askari Hemmat
Mohammad Pezeshki
Rémi Le Priol
Gabriel Huang
Simon LacosteJulien
Ioannis Mitliagkas

title: Negative momentum for improved game dynamics

venue: In The 22nd International Conference on Artificial Intelligence and Statistics,

authors:
Ian Goodfellow
Jean Pouget-Abadie
Mehdi Mirza
Bing Xu
David Warde-Farley
Sherjil Ozair
Aaron Courville
Yoshua Bengio

title: Generative adversarial nets

authors:
Ernst Hairer
Marlis Hochbruck
Arieh Iserles
Christian Lubich

title: Geometric numerical integration

venue: Oberwolfach Reports,

authors:
Kaiming He
Xiangyu Zhang
Shaoqing Ren
Jian Sun

title: Deep residual learning for image recognition

venue: In Proceedings of the IEEE conference on computer vision and pattern recognition,

authors:
Judy Hoffman
Eric Tzeng
Taesung Park
Jun-Yan Zhu
Phillip Isola
Kate Saenko
Alexei Efros
Trevor Darrell

title: Cycada: Cycle-consistent adversarial domain adaptation

authors:
Yu-Guan Hsieh
Franck Iutzeler
Jérôme Malick
Panayotis Mertikopoulos

title: Explore aggressively, update conservatively: Stochastic extragradient methods with variable stepsize scaling

authors:
Xiang Jiang
Qicheng Lao
Stan Matwin
Mohammad Havaei

title: Implicit class-conditioned domain alignment for unsupervised domain adaptation

authors:
Chi Jin
Praneeth Netrapalli
Michael Jordan

title: What is local optimality in nonconvex-nonconcave minimax optimization

venue: In International Conference on Machine Learning,

authors:
Diederik P Kingma
Jimmy Ba

title: Adam: A method for stochastic optimization

venue: arXiv preprint arXiv:1412.6980,

title: The extragradient method for finding saddle points and other problems

authors:
Yann LeCun
Léon Bottou
Yoshua Bengio
Patrick Haffner

title: Gradient-based learning applied to document recognition

venue: Proceedings of the IEEE,

authors:
Jason D. Lee
Max Simchowitz
Michael I. Jordan
Benjamin Recht

title: Gradient descent only converges to minimizers

venue: In 29th Annual Conference on Learning Theory,

authors:
Alistair Letcher
David Balduzzi
Sébastien Racanière
James Martens
Jakob Foerster
Karl Tuyls
Thore Graepel

title: Differentiable game mechanics

venue: Journal of Machine Learning Research,

authors:
Liam Li
Kevin Jamieson
Afshin Rostamizadeh
Ekaterina Gonina
Moritz Hardt
Ben Recht
Ameet Talwalkar

title: Massively parallel hyperparameter tuning

authors:
Richard Liaw
Eric Liang
Robert Nishihara
Philipp Moritz
Joseph E Gonzalez
Ion Stoica

title: Tune: A research platform for distributed model selection and training

venue: arXiv preprint arXiv:1807.05118,

authors:
Mingsheng Long
Zhangjie Cao
Jianmin Wang
Michael I Jordan

title: Conditional adversarial domain adaptation

authors:
Jonathan Lorraine
David Acuna
Paul Vicol
David Duvenaud

title: Complex momentum for optimization in games, 2021a

authors:
Jonathan Lorraine
Paul Vicol
Jack Parker-Holder
Tal Kachman
Luke Metz
Jakob Foerster

title: Lyapunov exponents for diversity in differentiable games

venue: arXiv preprint arXiv:2112.14570,

title: An o (sr)-resolution ode framework for discrete-time optimization algorithms and applications to convex-concave saddle-point problems

venue: arXiv preprint arXiv:2001.08826,

authors:
Yishay Mansour
Mehryar Mohri
Afshin Rostamizadeh

title: Domain adaptation: Learning bounds and algorithms

venue: In Proceedings of The 22nd Annual Conference on Learning Theory (COLT

authors:
Eric Mazumdar
Lillian J Ratliff
S Shankar Sastry

title: On gradient-based learning in continuous games

venue: SIAM Journal on Mathematics of Data Science,

authors:
Eric V Mazumdar
Michael I Jordan
S Shankar Sastry

title: On finding local nash equilibria (and only local nash equilibria) in zero-sum games

authors:
Panayotis Mertikopoulos
Bruno Lecouat
Houssam Zenati
Chuan-Sheng Foo
Vijay Chandrasekhar
Georgios Piliouras

title: Optimistic mirror descent in saddle-point problems: Going the extra(-gradient) mile

authors:
Lars Mescheder
Sebastian Nowozin
Andreas Geiger

title: The numerics of gans

venue: Advances in neural information processing systems,

authors:
Xingchao Peng
Ben Usman
Neela Kaushik
Judy Hoffman
Dequan Wang
Kate Saenko

title: Visda: The visual domain adaptation challenge

venue: arXiv preprint arXiv:1710.06924,

authors:
Chongli Qin
Yan Wu
Jost Tobias Springenberg
Andy Brock
Jeff Donahue
Timothy Lillicrap
Pushmeet Kohli

title: Training generative adversarial networks by solving ordinary differential equations

authors:
Lillian J Ratliff
Samuel A Burden
S Shankar Sastry

title: On the characterization of local nash equilibria in continuous games

venue: IEEE Transactions on Automatic Control,

authors:
Kuniaki Saito
Kohei Watanabe
Yoshitaka Ushiku
Tatsuya Harada

title: Maximum classifier discrepancy for unsupervised domain adaptation

venue: In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition,

authors:
Damien Scieur
Vincent Roulet
Francis Bach
Alexandre d'Aspremont

title: Integration methods and optimization algorithms

authors:
Ozan Sener
Hyun Oh Song
Ashutosh Saxena
Silvio Savarese

title: Learning transferrable representations for unsupervised domain adaptation

venue: Advances in Neural Information Processing Systems,

authors:
Bin Shi
Simon S Du
Michael I Jordan
Weijie J Su

title: Understanding the acceleration phenomenon via high-resolution differential equations

venue: arXiv preprint arXiv:1810.08907,

authors:
Rui Shu
Hung Bui
Hirokazu Narui
Stefano Ermon

title: A dirt-t approach to unsupervised domain adaptation

authors:
Yu Sun
Eric Tzeng
Trevor Darrell
Alexei A Efros

title: Unsupervised domain adaptation through selfsupervision

venue: arXiv preprint arXiv:1909.11825,

authors:
Ilya Sutskever
James Martens
George Dahl
Geoffrey Hinton

title: On the importance of initialization and momentum in deep learning

authors:
Laurens Van der Maaten
Geoffrey Hinton

title: Visualizing data using t-sne

venue: Journal of machine learning research,

authors:
Guojun Zhang
Yaoliang Yu

title: Convergence of gradient-based methods on bilinear games

authors:
Jingzhao Zhang
Aryan Mokhtari
Suvrit Sra
Ali Jadbabaie

title: Direct runge-kutta discretization achieves acceleration

venue: arXiv preprint arXiv:1805.00521,

authors:
Yuchen Zhang
Tianle Liu
Mingsheng Long
Michael Jordan

title: Bridging theory and algorithm for domain adaptation

venue: In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning,

venue: D EXPERIMENTAL SETUP ADDITIONAL DETAILS Our algorithm

venue: CO Only

title: We follow the splits and evaluation protocol from Courty et al

heading: 1 INTRODUCTION

text:
Unsupervised domain adaptation (UDA) deals with the lack of labeled data in a 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-art algorithms tackle UDA by learning domaininvariant representations in an adversarial fashion (Shu et al., 2018; Long et al., 2018; Saito et al., 2018; Hoffman et al., 2018; Zhang et al., 2019; Acuna et al., 2021). Their goal is to fool an auxiliary classifier that operates in a representation space and aims to classify whether the datapoint belongs to either the source or the target domain. This idea, called Domain-Adversarial Learning (DAL), was introduced by Ganin et al. (2016) and can be more formally understood as 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; Sun et al., 2019; Chang et al., 2019). One major cause of instability is the adversarial nature of the learning algorithm which results from the introduction of the Gradient Reversal Layer (GRL, Ganin et al., 2016) (Figure 1). 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 a 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 Başar & Olsder (1998); Letcher et al. (2019); Mazumdar et al. (2020) and draw inspiration from the existing two-player zero-sum game interpretations of Generative Adversarial Networks (GANs)
(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 1), which we coin as the Domain-Adversarial Game. We also propose to interpret and characterize optimal solutions in DAL as 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. Alternatively, we could also use other popular gradient based optimizers proposed in the context of differentiable games (e.g. Korpelevich, 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 domain-adversarial game (§ 4). The main result of § 4.2 (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 § 4.3, Appendix B.2 and Appendix E, 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. § 4.3 and § 6 show 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.
2 PRELIMINARIES <latexit sha1_base64="XcLU0OQlzQn4TD3DERhz5ZsAZ/U=">AAAB8nicbVBNS8NAFHypX7V+VT16WSyCp5KIoseiF48VbC2moWy223bpJht2X4QS+jO8eFDEq7/Gm//GTZuDtg4sDDPvsfMmTKQw6LrfTmlldW19o7xZ2dre2d2r7h+0jUo14y2mpNKdkBouRcxbKFDyTqI5jULJH8LxTe4/PHFthIrvcZLwIKLDWAwEo2glvxtRHDEqs8dpr1pz6+4MZJl4BalBgWav+tXtK5ZGPEYmqTG+5yYYZFSjYJJPK93U8ISyMR1y39KYRtwE2SzylJxYpU8GStsXI5mpvzcyGhkziUI7mUc0i14u/uf5KQ6ugkzESYo8ZvOPBqkkqEh+P+kLzRnKiSWUaWGzEjaimjK0LVVsCd7iycukfVb3Luru3XmtcV3UUYYjOIZT8OASGnALTWgBAwXP8ApvDjovzrvzMR8tOcXOIfyB8/kDl52RdA==</latexit>Z
<latexit sha1_base64="3xtdy5laA/WQWHLvq4EtMaredYI=">AAAB7XicbVBNS8NAEJ34WetX1aOXxSJ4Kokoeix68VjBfkAbyma7adZuNmF3IpTQ/+DFgyJe/T/e/Ddu2xy09cHA470ZZuYFqRQGXffbWVldW9/YLG2Vt3d29/YrB4ctk2Sa8SZLZKI7ATVcCsWbKFDyTqo5jQPJ28Hoduq3n7g2IlEPOE65H9OhEqFgFK3U6kUUSdSvVN2aOwNZJl5BqlCg0a989QYJy2KukElqTNdzU/RzqlEwySflXmZ4StmIDnnXUkVjbvx8du2EnFplQMJE21JIZurviZzGxozjwHbGFCOz6E3F/7xuhuG1nwuVZsgVmy8KM0kwIdPXyUBozlCOLaFMC3srYRHVlKENqGxD8BZfXiat85p3WXPvL6r1myKOEhzDCZyBB1dQhztoQBMYPMIzvMKbkzgvzrvzMW9dcYqZI/gD5/MHKgqO2w==</latexit> ĥ
<latexit sha1_base64="4ZzWvs7xxQO9ik+Ene1mXfvAGHA=">AAAB73icbVDLSgNBEOyNrxhfUY9eBoPoKeyKosegF48RzAOSJcxOZrNDZmfXmV4hLPkJLx4U8ervePNvnDwOmljQUFR1090VpFIYdN1vp7Cyura+UdwsbW3v7O6V9w+aJsk04w2WyES3A2q4FIo3UKDk7VRzGgeSt4Lh7cRvPXFtRKIecJRyP6YDJULBKFqp3Y0okoic9soVt+pOQZaJNycVmKPeK391+wnLYq6QSWpMx3NT9HOqUTDJx6VuZnhK2ZAOeMdSRWNu/Hx675icWKVPwkTbUkim6u+JnMbGjOLAdsYUI7PoTcT/vE6G4bWfC5VmyBWbLQozSTAhk+dJX2jOUI4soUwLeythEdWUoY2oZEPwFl9eJs3zqndZde8vKrWbeRxFOIJjOAMPrqAGd1CHBjCQ8Ayv8OY8Oi/Ou/Mxay0485lD+APn8wfj5o82</latexit> ĥ0
<latexit sha1_base64="2G0f8RUU8YWS9zeN9PTsk8ECOOY=">AAAB8HicbVDLSgMxFL1TX7W+qi7dBIvgqsyIosuiG5dV7EPaoWQymTY0yQxJRihDv8KNC0Xc+jnu/BvT6Sy09UDgcM655N4TJJxp47rfTmlldW19o7xZ2dre2d2r7h+0dZwqQlsk5rHqBlhTziRtGWY47SaKYhFw2gnGNzO/80SVZrF8MJOE+gIPJYsYwcZKj/eDPrfhEA+qNbfu5kDLxCtIDQo0B9WvfhiTVFBpCMda9zw3MX6GlWGE02mln2qaYDLGQ9qzVGJBtZ/lC0/RiVVCFMXKPmlQrv6eyLDQeiICmxTYjPSiNxP/83qpia78jMkkNVSS+UdRypGJ0ex6FDJFieETSzBRzO6KyAgrTIztqGJL8BZPXibts7p3UXfvzmuN66KOMhzBMZyCB5fQgFtoQgsICHiGV3hzlPPivDsf82jJKWYO4Q+czx+ZdZBG</latexit> R (GRL) <latexit sha1_base64="1Out49/IGg3BAWnSOWbUFY4P5mo=">AAAB+HicdVDLSgMxFM3UV62Pjrp0EyyCG8tMHdu6K7pxWcE+oFPKnTRtQzOZIckItfRL3LhQxK2f4s6/MdNWUNEDgcM553JvThBzprTjfFiZldW19Y3sZm5re2c3b+/tN1WUSEIbJOKRbAegKGeCNjTTnLZjSSEMOG0F46vUb91RqVgkbvUkpt0QhoINGAFtpJ6dP/W5SfcB+wICDj274BQvquWSV8ZO0XEqbslNSaninXnYNUqKAlqi3rPf/X5EkpAKTTgo1XGdWHenIDUjnM5yfqJoDGQMQ9oxVEBIVXc6P3yGj43Sx4NImic0nqvfJ6YQKjUJA5MMQY/Uby8V//I6iR5Uu1Mm4kRTQRaLBgnHOsJpC7jPJCWaTwwBIpm5FZMRSCDadJUzJXz9FP9PmqWie150brxC7XJZRxYdoiN0glxUQTV0jeqogQhK0AN6Qs/WvfVovVivi2jGWs4coB+w3j4BX0GS6w==</latexit> r
<latexit sha1_base64="4e7VN7IWD/ZM+123qYV7uoLuXJs=">AAAB7XicbVDLSgNBEOz1GeMr6tHLYBA8hV1R9Bj04jGCeUCyhN7JbDJmdmaZmRVCyD948aCIV//Hm3/jJNmDJhY0FFXddHdFqeDG+v63t7K6tr6xWdgqbu/s7u2XDg4bRmWasjpVQulWhIYJLlndcitYK9UMk0iwZjS8nfrNJ6YNV/LBjlIWJtiXPOYUrZMaHYmRwG6p7Ff8GcgyCXJShhy1bumr01M0S5i0VKAx7cBPbThGbTkVbFLsZIalSIfYZ21HJSbMhOPZtRNy6pQeiZV2JS2Zqb8nxpgYM0oi15mgHZhFbyr+57UzG1+HYy7TzDJJ54viTBCryPR10uOaUStGjiDV3N1K6AA1UusCKroQgsWXl0njvBJcVvz7i3L1Jo+jAMdwAmcQwBVU4Q5qUAcKj/AMr/DmKe/Fe/c+5q0rXj5zBH/gff4AgK6PFA==</latexit>r
<latexit sha1_base64="4e7VN7IWD/ZM+123qYV7uoLuXJs=">AAAB7XicbVDLSgNBEOz1GeMr6tHLYBA8hV1R9Bj04jGCeUCyhN7JbDJmdmaZmRVCyD948aCIV//Hm3/jJNmDJhY0FFXddHdFqeDG+v63t7K6tr6xWdgqbu/s7u2XDg4bRmWasjpVQulWhIYJLlndcitYK9UMk0iwZjS8nfrNJ6YNV/LBjlIWJtiXPOYUrZMaHYmRwG6p7Ff8GcgyCXJShhy1bumr01M0S5i0VKAx7cBPbThGbTkVbFLsZIalSIfYZ21HJSbMhOPZtRNy6pQeiZV2JS2Zqb8nxpgYM0oi15mgHZhFbyr+57UzG1+HYy7TzDJJ54viTBCryPR10uOaUStGjiDV3N1K6AA1UusCKroQgsWXl0njvBJcVvz7i3L1Jo+jAMdwAmcQwBVU4Q5qUAcKj/AMr/DmKe/Fe/c+5q0rXj5zBH/gff4AgK6PFA==</latexit>r
<latexit sha1_base64="qmqxvw54qUUoUaz9MnxwYmJpOwM=">AAAB6HicbVBNS8NAEJ3Ur1q/qh69LBbBU0lE0WPRi8cW7Ae0oWy2k3btZhN2N0IJ/QVePCji1Z/kzX/jts1BWx8MPN6bYWZekAiujet+O4W19Y3NreJ2aWd3b/+gfHjU0nGqGDZZLGLVCahGwSU2DTcCO4lCGgUC28H4bua3n1BpHssHM0nQj+hQ8pAzaqzUGPbLFbfqzkFWiZeTCuSo98tfvUHM0gilYYJq3fXcxPgZVYYzgdNSL9WYUDamQ+xaKmmE2s/mh07JmVUGJIyVLWnIXP09kdFI60kU2M6ImpFe9mbif143NeGNn3GZpAYlWywKU0FMTGZfkwFXyIyYWEKZ4vZWwkZUUWZsNiUbgrf88ippXVS9q6rbuKzUbvM4inACp3AOHlxDDe6hDk1ggPAMr/DmPDovzrvzsWgtOPnMMfyB8/kDzceM7w==</latexit>g
Figure 1: We study domainadversarial training from a game perspective. In DAL (Ganin et al. (2016)), three networks interact with each other: the feature extractor (g), the domain classifier (ĥ′) and the classifier (ĥ). During backpropagation, the GRL flips the sign of the gradient with respect to g.
We focus on the UDA scenario and follow the formulation from Acuna et al. (2021). This makes our analysis general and applicable to most state-of-the-art DAL algorithms (e.g., 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 xsi are sampled i.i.d. from a (source) distribution Ps and the target inputs xti are sampled i.i.d. from a (target) distribution Pt, both over X . We have Y = {0, 1} for binary classification, and Y = {1, ..., k} in the multiclass case. The risk of a hypothesis h : X → Y w.r.t. the labeling function f , using a loss function ` : Y×Y → R+ under distribution D is defined as: R`D(h, f) := ED[`(h(x), f(x))]. For simplicity, we define R`S(h) := R ` Ps (h, fs) and R`T (h) := R ` Pt
(h, ft). The hypothesis class of h is denoted byH.
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 λ∗: Theorem 1. (Acuna et al. (2021)) Let us note ` : Y × Y → [0, 1], λ∗ := minh∈HR`S(h) +R`T (h), and Dφh,H(Ps||Pt) := suph′∈H |Ex∼Ps [`(h(x), h′(x))]− Ex∼Pt [φ∗(`(h(x), h′(x)))|. We have:
R`T (h) ≤ R`S(h) + Dφh,H(Ps||Pt) + λ∗. (1)
The function φ : R+ → R defines a particular f -divergence and φ∗ is its (Fenchel) conjugate. As is typical in UDA, we assume that the hypothesis class is complex enough and both fs and ft are similar in such a way that the non-estimable term (λ∗) is negligible and can be ignored.
Domain-Adversarial Training (see Figure 1) aims to find a 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 = ĥ ◦ g with g : X → Z , and ĥ : Z → Y . Another function class Ĥ is then defined to formulate H := {ĥ ◦ g : ĥ ∈ Ĥ, g ∈ G}. The algorithm tries to find the function g ∈ G such that ĥ ◦ g minimizes the risk of the source domain (i.e. the first term in Theorem 1), and its composition with ĥ and ĥ′ minimizes the divergence of the two distributions (i.e. the second term in Theorem 1).
Algorithmically, the computation of the divergence function in Theorem 1 is estimated by a so-called domain classifier ĥ′ ∈ Ĥ whose role is to detect whether the datapoint g(xi) ∈ Z belongs to the source or to the target domain. When there does not exist a function ĥ′ ∈ Ĥ that can properly distinguish between g(xsi ) and g(x t i), g is said to be invariant to the domains.
Learning is performed using GD and the GRL (denoted by Rλ) on the following objective:
min ĥ∈Ĥ,g∈G,ĥ′∈Ĥ
Ex∼ps [`(ĥ ◦ g, y)]− αds,t(ĥ, ĥ′, Rλ(g)), (2)
where ds,t(ĥ, ĥ′, g) := Ex∼ps [ˆ̀(ĥ′ ◦ g, ĥ ◦ g)]− Ex∼pt [(φ∗ ◦ ˆ̀)(ĥ′ ◦ g, ĥ ◦ g)]. Mathematically, the GRL Rλ is treated as a “pseudo-function” defined by two (incompatible) equations describing its forward and back-propagation behavior (Ganin & Lempitsky, 2015; Ganin et al., 2016). Specifically,
Rλ(x) := x and dRλ(x)/dx := −λ, (3) where λ and α are hyper-parameters that control the tradeoff between achieving small source error and learning an invariant representation. The surrogate loss ` : Y × Y → R (e.g., cross-entropy) is used to minimize the empirical risk in the source domain. The choice of function ˆ̀ : Y × Y → R and of conjugate φ∗ of the f -divergence defines the particular algorithm (Ganin et al., 2016; Saito et al., 2018; Zhang et al., 2019; Acuna et al., 2021). From eq. 2, 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.

heading: 3 A GAME PERSPECTIVE ON DAL

text: We now interpret DAL from a game-theoretical perspective. In § 3.1, we rewrite the DAL objective as a three-player game. In this view, each of the feature extractor and two classifiers is a player. This allows us to define optimality in 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 § 4.

heading: 3.1 DOMAIN-ADVERSARIAL GAME

text:
We now rewrite and analyze the DAL problem in eq. 2 as a three-player game. Let Ĥ, Ĥ′ and G be classes of neural network functions and define ω1 ⊆ Ω1 and ω3 ⊆ Ω3 as a vector composed of the parameters of the classifier and domain classifier networks ĥ ∈ Ĥ and ĥ′ ∈ Ĥ, respectively. Similarly, let ω2 ⊆ Ω2 be the parameters of the feature extractor network g ∈ G. Their joint domain is denoted by Ω = Ω1 × Ω2 × Ω3 and the joint parameter set is ω = (ω1, ω2, ω3). Let each neural network be a 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 Ji : Ω→ 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-Adversarial Game as the three-player game G(I,Ωi, Ji) where I := {1, 2, 3}, dim(Ω) = ∑3 i=1 dim(Ωi) = d, Ωi ⊆ Rdi and:
J1(ω1, ω−1) := `(ω1, ω2) + αds,t(ω)
J2(ω2, ω−2) := `(ω1, ω2) + αλds,t(ω) J3(ω3, ω−3) := − αds,t(ω), (4)
We use the shorthand `(ω1, ω2) for Ex,y∼ps [`(ω1 ◦ ω2(x), y)], and ωi’s refer to the feature extractor g and the classifiers (ĥ and ĥ′). Similar notation follows for ds,t. Here, we assume that each Ji is smooth in each of its arguments ωi ∈ Ωi. 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 Rλ in ds,t 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 ω∗ ∈ Ω is said to be a Nash Equilibrium of the Domain-Adversarial Game if ∀i ∈ {1, 2, 3},∀ωi ∈ Ωi, we have: Ji(ω∗i , ω∗−i) ≤ Ji(ωi, ω∗−i). 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
is unrealistic using gradient-based methods (Letcher et al., 2019). Thus, we focus on local NE which relaxes the NE to a local neighborhood B(w∗, δ) := {||w − w∗|| < δ} 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 own strategy set. In other words, the player J1 cannot change the parameters ω2, ω3. It only has access to ω1 ∈ Ω1. While the motivation of the three-player game follows naturally from the original formulation of DAL where three networks interact with each other (see Figure 1), the optimization problem (2) could also be interpreted as the minimax objective of a two-player zero-sum game. Thus, a natural question arises: can we interpret the domain-adversarial game as a two player zero-sum game? This can be done for example by defining ω∗12 := (ω ∗ 1 , ω ∗ 2), and considering the cost of the two players (ω12, ω3) as J12 = J and J3 = −J where J(ω12, ω3) := Eps [`(ω1, ω2)] + ds,t(ω). In general, however, the solution of the two-player game (ω∗12, ω ∗ 3) is not equal to the NE solution of the three-player game (ω∗1 , ω ∗ 2 , ω ∗ 3). This is because the team optimal solution ω ∗ 12 6= (ω∗1 , ω∗2) in general. We illustrate this in the following counterexample (see Başar & Olsder (1998) for more details): Example 1. Let the function J(ω) := 12 ( ω21 + 4ω1ω2 + ω 2 2 − ω23 ) . (a) Suppose the three-player game ω = (ω1, ω2, ω3) with J1 = J2 = J and J3 = −J . Each Ji is strictly convex in ωi. The NE solution of the game ω∗ = (0, 0, 0) is unique. (b) Suppose the two-player game ω = (ω12, ω3) with J12 = J and J3 = −J . The solution ω∗ from (a) is not a NE solution. To see this, let ω̂ := (−1, 1, 0). We have that J12(ω̂) = −1 < J12(ω∗) = 0. This contradicts Definition 1. One can verify that there is no NE in this two-player scenario.

heading: 3.2 CHARACTERIZATION OF THE DOMAIN-ADVERSARIAL GAME

text:
We now introduce the game’s vector field (also called pseudo-gradient) and the pseudo-gradient’s Jacobian. We also provide a characterization of local NE based on them (see § 3). These are the core concepts used in our analysis (§ 4). We first define the game’s vector field v(w), and its Jacobian H(ω) (also called the game Hessian (Letcher et al., 2019)):
v(ω) := (∇ω1J1,∇ω2J2,∇ω3J3) ∈ Rd, H(ω) := ∇v(ω) ∈ Rd×d (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(ω) 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(ω) is asymmetric. This is in contrast with the Hessian in supervised learning. Before proceeding with a characterization of local NE in terms of v(w) and H(ω), we first define sufficient and necessary conditions for local NEs: Proposition 1. (Necessary condition). Suppose each Ji is twice continuously differentiable in each ωi, any local NE ω∗ satisfies: i)∇ωiJi(ω∗) = 0 and ii) ∀i ∈ {1, 2, 3},∇2ωi,ωiJi(ω∗) 0. Proposition 2. (Sufficient condition). Suppose each Ji is twice continuously differentiable in each ωi. ω∗i is a local NE if i) ∇ωiJi(ω∗) = 0 and ii) ∀i,∇2ωi,ωiJi(ω∗) 0.
The necessary and sufficient conditions from Propositions 1 and 2 are reminiscent of conditions for local optimality in continuous optimization (Nocedal & Wright, 2006). Similar conditions were also proposed in Ratliff 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(ω): Proposition 3. (Strict Local NE) w is a strict local NE if v(w) = 0 and H(ω) +H(ω)> 0. The sufficient condition implies that the NE is structurally stable (Ratliff et al., 2016). Structural stability is important as it implies that slightly biased estimators of the gradient (e.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., ω∗ for which Proposition 3 is satisfied).

heading: 4 LEARNING ALGORITHMS

text:
We defined optimality as the local NE and provided sufficient conditions in terms of the pseudogradient and its Jacobian. In this section, we assume the existence of the strict local NE (Prop. 3)
in the neighborhood of the current point (e.g., initialization), and analyze the continuous gradient dynamics of the Domain-Adversarial Game (eq. 4 and eq. 5). We show that given the sufficient conditions from Prop. 3, asymptotic convergence to a local NE is guaranteed through an application of Hurwitz condition (Khalil, 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. 1). 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, 2021). 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.
Our algorithmic analysis is based on the continuous gradient-play dynamics and the derivation of the modified or high-resolution ODE of popular integrators (e.g., GD/Euler Method and Runge-Kutta). 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, 2021). 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 (2020). As in Shi et al. (2018); Lu (2020); Barrett & Dherin (2021), our derivation of the high resolution ODEs is in the full-batch 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 our results are 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. (2020); Zhang & Yu (2020). In our problem, the game is neither bilinear nor necessarily strongly monotone. See proofs in appendices.

heading: 4.1 CONTINUOUS GRADIENT DYNAMICS

text:
Given v(ω) the continuous gradient dynamics can be written as:
ω̇(t) = −v(ω). (6) For later reasons and to distinguish between eq. 6 and the gradient flow, we will refer to these as the gradient-play dynamics as in Başar & Olsder (1998); Mazumdar et al. (2020). These dynamics are well studied and understood when the game is either a potential or a purely adversarial game (see definitions in appendices). While eq. 2 may look like a single objective, the introduction of the GRL (Rλ), makes a 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: Proposition 4. The domain-adversarial game is neither a potential nor necessarily a purely adversarial 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.1) to derive sufficient conditions for which the continuous dynamics of the gradient play would converge. Lemma 1. (Hurwitz condition) Let ∇v(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 ∇v(w∗) (i.e. in the spectrum Sp(∇v(w∗))) 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 ω∗. Therefore, Lemma 1 provides sufficient conditions for the asymptotic convergence of the gradientplay 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 § 6).

heading: 4.2 ANALYSIS OF GD WITH THE GRL

text:
We showed above that given the existence of a 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 an explicit solution of the ODE. Thus, we rely on integration algorithms to approximate the solution. One simple approach is to use the Euler method:
w+ = w − ηv(w). (7)
This is commonly known as GD. The equivalence between v(w) (game’s vector field) and the gradient of Equation (2) (original DAL formulation) follows from the use of the GRL (Rλ). We remind the reader that the GRL is a “pseudo-function” defined by two (incompatible) equations describing its forward and back-propagation behavior, i.e., a flip in the gradient’s sign for the backward pass (see Figure 1, Section 2 and Ganin et al. (2016)). Equation (7) 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 et al., 2006) and applying Hurwitz condition on the high-resolution ODE. Theorem 2. The high resolution ODE of GD with the GRL up to O(η) is:
ẇ = −v(w)−η2∇v(w)v(w) (8) Moreover, this is asymptotically stable (see Appendix A.1) at a stationary point w∗ (Proposition 3) iff for all eigenvalue written as λ = a+ ib ∈ Sp(−∇v(w∗)), we have 0 > η(a2 − b2)/2 > a. A striking difference between Equation (6) and Equation (8) is made clear (additional term marked in red). This additional term is a 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∇v(ω∗) 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 η. The following corollary formalizes this: Corollary 1. The high resolution ODE of GD with GRL in Equation (8) is asymptotically stable only if the learning rate η is in the interval: 0 < η < −2ab2−a2 , for all λ = a+ ib ∈ Sp(−∇v(w∗)) with large imaginary part (i.e., such that |a| < |b|). To have good convergence properties, the imaginary part of the eigenvalues of −∇v(w∗) must be small enough. Therefore, if some eigenvalue λ = a+ ib satisfies a < 0 and b2 a2 −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 `(w1, w2) = w21 + 2w1w2 + w22 , λ = 1 and ds,t(w2, w3) = w 2 2 + 99w2w3 − w23 . Then ẇ = −v(w) becomes: ẇ = Aw = (−2 −2 0 −2 −4 −99 0 99 −2 ) . The
eigenvalues of A are −2 and −3± 2i √ 2449. From Corollary 1, η should be 0 < η < 6.2× 10−3.

heading: 4.3 HIGHER ORDER ODE SOLVERS

text:
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 O(η). To obtain a better approximation, we consider Runge-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+ = w − η2 (v(w) + v(w − ηv(w))). (9) 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 hyper-parameters. More importantly, such discrete dynamics approximate the continuous ODE of Equation (6) to a higher precision. In Appendix C, 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.
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 E.5 for more details and wall-clock comparison). Moreover, if not initialized in the neighborhood of a local NE, high-order solvers and gradient-based methods might also converge to a 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, 2020; Azizian et al., 2020) to DAL. Classic examples are the Extra-Gradient (EG) method (Korpelevich, 1976) and Consensus Optimization (CO) (Mescheder et al., 2017). In Appendix B.2 we analyze the continuous dynamics of the EG method, and show that
we cannot take the learning rate of EG to be large either. Thus, we obtain a similar conclusion as Corollary 1. Then, in practice for DAL, stability for EG comes at the price of slow convergence due to the use of small learning rates. We experimentally show this in Figure 3. With respect to CO, we show in Appendix C that this algorithm can be interpreted in the limit as an approximation of the RK2 solver. In practice, if its additional hyper-parameter (γ) is tuned thoroughly, CO may approximate the 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 e.g., Gidel et al. (2019a); Hsieh et al. (2020); Lorraine et al. (2021a;b). Some of them are modifications of the EG method that we compared to e.g. Extra-Adam (Gidel et al., 2019a) 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 a 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.

heading: 5 RELATED WORK

text:
To the best of our knowledge, DAL has not been previously analyzed from a 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. Ratliff 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 domain-adversarial 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. Scieur et al. (2017) showed that accelerated optimization methods can be interpreted as integration schemes of the gradient flow equation. Zhang et al. (2018) showed that the use of high order RK integrators can achieve acceleration in convex functions. In the context of two-players game (i.e GANs), Gemp & Mahadevan (2018) consider using a second-order ODE integrator. More recently, Qin et al. (2020) proposed to combine RK solvers with regularization on the generators’ gradient norm. Chen et al. (2018) interpreted the residual connection in modern networks as the Euler’s integration of 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-player game interpretation of the domain-adaptation 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 to the popularity of Generative Adversarial Networks (GANs) (Goodfellow et al., 2014). For example, several algorithms have been proposed and analyzed (Mescheder et al., 2017; Mertikopoulos et al., 2019; Gidel et al., 2019a;b; Zhang & Yu, 2020; Hsieh et al., 2020), in both deterministic and stochastic scenarios. In our problem, we have a general three-player games resulting of a novel game interpretation of the domain-adversarial problem. It is worth noting that while Gidel 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.

heading: 6 EXPERIMENTAL RESULTS

text:
We conduct an extensive experimental analysis. We compare with default optimizers used in domainadversarial 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-adversarial framework of Ganin et al.
(2016) (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 (e.g., f -DAL (Acuna et al., 2021) combined with Implicit Alignment (Jiang et al., 2020)).

heading: 6.1 EXPERIMENTAL ANALYSIS ON DIGITS

text:
Implementation Details. Our first experimental analysis is based on the digits benchmark with models trained from scratch (i.e., with random initialization). This benchmark constitutes of two digits datasets MNIST (CC BY-SA 3.0) and USPS (LeCun et al., 1998; Long et al., 2018) with two transfer tasks (M → U and U →M). We adopt the splits and evaluation protocol 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 additional hyper-parameters of Adam. Hyperparameters such as learning rate, learning schedule and adaptation coefficient (λ) are determined for all optimizers by running a dense grid search and selecting the best hyper-parameters on the transfer task M→U. 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→M). We use the same seed and identically initialize the network weights for all optimizers. This analysis is conducted on Jax (Bradbury et al., 2018) (see Appendix D).
Comparison vs optimizers used in DAL. Figure 2 (top) illustrates the training dynamics for the loss in the target domain and the performance transfer. As expected, our optimizer converges faster and achieves noticeable performance gains. A core idea of DAL is to learn domain-invariant representations, thus we plot in Figure 2 (bottom) t-SNE (Van der Maaten & Hinton, 2008) visualizations of the last layer features of the network. We show this over a sequence of epochs for GD with GRL vs RK2. A different color is used for the source and target datasets. In the comparison vs Adam, we emphasize that Adam computes adaptive learning rates which our method does not. That said, Figure 2 shows 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 theoretical 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.
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 dynamics of the EG, we notice that the EG method is not able to train with learning rates bigger than 0.006, as a 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 Method (RK2). More details on this in supplementary.
Robustness to hyper-parameters. Figure 4 shows transfer performance of our method for different choices of hyper-parameters while highlighting (green line) the best score of the best performing GD hyperparameters on the same dataset. Our method is robust to a wide variety of hyperparameters.
0.1 0.3 0.4
92
94
96 LR
const poly
LR Schedule
RK2 RK4
Method
0.1 0.5 1.0
adapt
92 94 96
92
94
96 Transfer Acc.
Figure 4: Robustness to hyperparameters. We compare the transfer performance 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.
0 8000 16000 24000 # of Iterations
65.0
67.5
70.0
72.5
Tr an
sf er
P er
fo rm
an ce
Grad. Descent (Nesterov) Ours (RK2)
Figure 6: Transfer Performance on Visda (DANN). 0 6000 12000 18000 24000 # of Iteration(s)
1.25
1.50
1.75
2.00
2.25
Ta rg
et T
as k
Lo ss
Grad. Descent LR:0.3 Nesterov Momentun LR:0.1
Figure 7: Stability anal. on Digits. Most aggressive step size before divergence. Adam diverges for η > 0.001.
6.2 COMPARISON IN COMPLEX ADAPTATION TASKS Method Sim→Real GD-NM 71.7 ± 0.7
Ours(RK2) 73.8 ± 0.3
Table 1: Accuracy (DANN) on Visda 2017 with ResNet-50.
We evaluate the performance of our algorithm with Resnet-50 (He et al., 2016) on more challenging adaptation benchmarks. Specifically, this analysis is conducted on Visda-2017 benchmark (Peng et al., 2017). This is a simulation-to-real dataset with two different domains: (S) synthetic renderings of 3D models and (R) real images. For this experiment, we use PyTorch (Paszke et al., 2019), our evaluation protocol follows 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 et al., 2018; Zhang et al., 2019; Jiang et al., 2020; Acuna et al., 2021). For ours, we keep the hyper-parameters, but increase the learning rate (0.2), and the batch size to 128. In this task, our approach corresponds to the improved Euler’s method (RK2). Table 1 shows the comparison. Figure 6 compares the training dynamics of our method vs GD-NM. In Figure 5, 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 applicability of our method to SoTA DAL frameworks. Specifically, we let the DA method being f -DAL Pearson as in Acuna et al. (2021) with Implicit Alignment Jiang et al. (2020). We use the tuned parameters and optimizer from Acuna et al. (2021); Jiang et al.
(2020) as the baseline. In our case, we only increase the learning rate (0.2). Table 2 shows 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., 2006). We show noticeable gains by replacing the GD with either RK2 or RK4. Results and details can be found in Appendix E.1.

heading: 7 CONCLUSIONS

text:
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 on our analysis, we 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 to noticeable improvements in terms of the transfer performance and the number of training iterations. We showed that these ODE solvers can be used as a 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.

heading: SUPPLEMENTARY MATERIAL

heading: CONTENTS

heading: 1 Introduction 1

heading: 2 Preliminaries 2

heading: 3 A Game Perspective on DAL 3

text:
3.1 Domain-Adversarial Game . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
3.2 Characterization of the Domain-Adversarial Game . . . . . . . . . . . . . . . . . . . . . . . 4

heading: 4 Learning Algorithms 4

text:
4.1 Continuous Gradient Dynamics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
4.2 Analysis of GD with the GRL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
4.3 Higher order ODE Solvers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

heading: 5 Related Work 7

heading: 6 Experimental Results 7

text:
6.1 Experimental Analysis on Digits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
6.2 Comparison in complex adaptation tasks . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

heading: 7 Conclusions 9

heading: A Concepts in Game Theory 15

text:
A.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
A.2 Games Characterizations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
A.3 Case of Study in DANN. Original Formulation from Ganin et al. (2016) . . . . . . . . . . . . 15

heading: B Derivation of high-resolution ODEs 17

text:
B.1 High-resolution ODE of second-order Runge–Kutta method . . . . . . . . . . . . . . . . . . 17
B.2 Continuous dynamics of Extra-Gradient (EG) . . . . . . . . . . . . . . . . . . . . . . . . . . 17
B.3 High-resolution ODE of classic fourth-order Runge–Kutta method (RK4) . . . . . . . . . . . 18

heading: C Proofs and additional theoretical results 20

text:
C.1 Proposed Learning Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
C.2 CO approximates RK2 (Heun’s Method) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

heading: D Experimental Setup Additional Details 22

heading: E Additional Experiments 23

text:
E.1 Natural Language Processing Tasks. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
E.2 Sensitivity to Sampling Noise . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
E.3 Additional Comparison vs Game Optimization Algorithms . . . . . . . . . . . . . . . . . . . 24
E.4 CO vs Gradient Descent and Extra-Gradient Algorithms . . . . . . . . . . . . . . . . . . . . 24
E.5 Wall-Clock Comparison . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

heading: F PyTorch PseudoCode of RK2 Solver 25

heading: A CONCEPTS IN GAME THEORY

heading: A.1 DEFINITIONS

text:
Definition 2. (Local Nash Equilibrium) : A point (w∗i , w∗−i) ∈ Ω is said to be a local Nash Equilibrium of the domain-adversarial game if there exists some δ > 0 such that:
∀i ∈ {1, 2, 3}, Ji(w∗i , w∗−i) ≤ Ji(wi, w∗−i), s.t. ||ωi − ω∗i ||2 < δ (10)
Intuitively, this is restricting the concept of NE to a local neighborhood B(x∗, δ) := {||x− x∗||2 < δ} with δ > 0.
A more practical characterization of the NE can be given in terms of the Best Response Map of each player which we now define.
Definition 3. (Best Response Map (BR)) The best response map BRi : Ω−i ⇒ Ωi of player i is defined as:
BRi(ω−i) := arg min ωi∈Ωi Ji(ωi, ω−i), (11)
here the symbol ⇒ emphasizes that the best response map is generally a set map and not a singleton, thus it is not a function in general. In other words, there may be a subset of element in Ωi for which Ji(., ω−i) is a minimum.
The notion of NE can be defined in terms of the generalized BR : Ω ⇒ Ω map. This can be thought as an stacked vector where the i-th element of BR is BRi(ω−i). Proposition 5. A pointw∗i ∈ Ω is said to be a NE of the game if it is a fixed point of the generalized BR : Ω ⇒ Ω map. That is,
ω∗ ∈ BR(ω∗) =⇒ ∀i ∈ {1, 2, 3}, ω∗i ∈ BRi(ω∗−i) (12)
Proof. This follows from the definitions of BR map and NE.
Definition 4. (Asymptotically Stable) A point ω is said to be a locally asymptotically stable point of the continuous dynamics ω̇ = f(ω) if Re(λ) < 0 for all λ ∈ Sp(∇f(ω)), where Sp(∇f(ω)) is the spectrum of ∇f(ω).
Definition 4 is also known as the Hurwitz condition Khalil (2002).
Definition 5. A stationary point x of a C2 function φ : Rn → R is said to be a strict saddle point if:
• λmin(∇2xxφ(x∗)) < 0 and,
• λ(∇2xxφ(x∗)) > 0, for any other λ ∈ sp(∇2xxφ(x∗))

heading: A.2 GAMES CHARACTERIZATIONS

text:
Potential Games. Potential Games were introduced in Monderer & Shapley (1996) and can be defined as a type of game for which there exists an implicit potential function φ : Ω → R such that ∇φ(ω) = v(ω). Consequently, a necessary and sufficient condition for the game to be potential is the Jacobian of the vector field ∇v(ω) being symmetric (see 3.3 in Mazumdar et al. (2020) and Monderer & Shapley (1996)).
Purely Adversarial Games. This particular type of game refers to the other extreme in which H(ω) is a non-symmetric matrix with purely imaginary eigenvalues. If the game Hessian is skew-symmetric these have also been called Hamiltonian Games Letcher et al. (2019).

heading: A.3 CASE OF STUDY IN DANN. ORIGINAL FORMULATION FROM GANIN ET AL. (2016)

text:
As mentioned in the main text (Section 2), our analysis is compatible with both the original and more recent formulation of domain-adversarial training such as Zhang et al. (2019); Acuna et al. (2021). In this section, we specifically derive additional results for DANN Ganin et al. (2016).
In order to obtain the original formulation of DANN, let us define ˆ̀(_, b) = log(σ(b)) and φ∗(t) = − log(1−et) in Equation (2). This corresponds to the Jensen-Shannon divergence (JS) (up to a constant shift that does not affect optimization). We can then rewrite ds,t as:
ds,t = Ex∼ps log σ ◦ ĥ ′ ◦ g(x) + Ex∼pt log(1− σ ◦ ĥ ′ ◦ g(x)) (13)
where σ(x) := 1 1+e−x . To simplify the notation, we writeH := σ ◦ H.
We can now re-define the pseudo-gradient v(w) of the game as the gradient of each player loss with respect to its parameters. Letting α = 1, we get from Equation (4).
v(ω) := (∇ω1`,∇ω2(`+ λds,t),−∇ω3ds,t) ∈ R d. (14)
The following propositions characterize local NE in terms of the pseudo-gradient v(w) and its Jacobian H(ω). Proposition 6. (Local NE) Suppose v(w) = 0 and(
∇2ω1` ∇ 2 ω1,ω2`
∇2ω1,ω2` ∇ 2 ω2(`+ λds,t)
) 0, ∇2ω3ds,t ≺ 0, (15)
then w is an isolated local NE.
The proof is simple and follows from Propositions 1 and 2, the definition of the vector field v(ω) and the condition H +H> 0.
Cooperation with Competition. By examining the matrix H(ω), one can see that, in our scenario, the game is neither a potential game nor a purely adversarial game. However, we can write the vector field in the following form:
v(w) = ∇ω1`∇ω2` 0  ︸ ︷︷ ︸ ∇φ(ω) +  0λ∇ω2dst −∇ω3dst  ︸ ︷︷ ︸ v̂(ω)
(16)
where the first part corresponds to the gradient of the potential function φ(ω) = `(ω1, ω2). The second part, on the other hand, corresponds to a function v̂(w) whose Jacobian is a non-symmetric matrix. Analyzing them separately leads to either a potential or an adversarial game respectively. We define this particular type of game as cooperation (i.e., in the potential term) with competition (i.e., the adversarial term).
It is worth noting that, while the spectrum of the game Hessian for the 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 a GAN using the non-saturating loss proposed by Goodfellow et al. (2014) (e.g. λ = 1). In other words, the second term can be written as the pseudo-gradient of the two player zero-sum game minω2 maxω3 dst. Building on this key observation and the work of Mescheder et al. (2017); Berard et al. (2020) (Figure 4), where it was experimentally shown that the eigenvalues 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 1 to further motivate the use of higher-order ODE solvers instead of GD with the GRL. Example 3. Consider the three-player game Equation (16) where `(w1, w2) = w21 + 2w1w2 +w22 , λ = 1 and ds,t(w2, w3) = w 2 2 + 99w2w3 − w23 . The gradient play dynamics ẇ = −v(w) becomes:
ẇ = Aw =  −2 −2 0−2 −4 −99 0 99 −2 w. The eigenvalues of A are −2 and −3± 2i √ 2449. From Corollary 1, η should be 0 < η < 6.2 · 10−3.
Is the three-player game formulation desired? In domain adaptation, optimization is a means to an end. The final goal is to minimize the upper bound from Theorem 1 to ensure better performance in the target domain. One might then wonder whether interpreting optimality in terms of NE is desirable. In our context, NE means finding the optimal g∗, ĥ∗ and ĥ
′∗ of the cost functions defined in Equation (4). This in turns leads to minimizing the upper bound in Theorem 1.
Remark on sequential games: Recently, Jin et al. (2020) 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-adversarial learning, updates are usually performed in a simultaneous manner using the GRL. Thus, we focus here on the general case where the order of the players is not known.

heading: B DERIVATION OF HIGH-RESOLUTION ODES

text:
Lemma 2. The high resolution ODE of resulting of the GD algorithm with the GRL is:
ẇ = −v(w)− η 2 ∇v(w)v(w) +O(η2), (17)
Proof. This follows from Corollary 1 of Lu (2020).

heading: B.1 HIGH-RESOLUTION ODE OF SECOND-ORDER RUNGE–KUTTA METHOD

text:
The high-resolution ODE was discussed in Shi et al. (2018); Lu (2020). For discrete algorithms with the following update:
w+ = w + f(η, w), (18)
we can think of the trajectory as a discretization of the continuous dynamics w : [0,+∞) → Rd, and in Equation (18), we have w = w(t), w+ = w(t+ η). Here, with slight abuse of notation we also use w for the continuous function of dynamics.
We derive high-resolution ODE of the second-order Runge–Kutta method:
wk+1/2 = wk − η
2α v(wk), wk+1 = wk − η((1− α)v(wk) + αv(wk+1/2)),
where 0 < α ≤ 1 and α is a constant. If α = 1/2, we obtain Heun’s method; if α = 1, we obtain the midpoint method; if α = 2/3, we obtain the Ralston’s method. Combining the two equations, we have:
wk+1 − wk η = −(1− α)v(wk)− αv(wk − η 2α v(wk)). (19)
Using the Taylor expansion:
v(wk − η
2α v(wk)) = v(wk)−
η
2α ∇v(wk)>v(wk) +O(η2)
Plugging it back into Equation (19) and using the Taylor expansion wk+1 = wk + ηẇ + η2ẅ/2, we have:
ẇ + 1 2 ηẅ = −v(w) + 1 2 ∇v(w)>v(w) +O(η2). (20)
Now we make the assumption that we have the high-resolution ODE that:
ẇ = f0(w) + ηf1(w) +O(η 2). (21)
Taking the derivative over t we have:
ẅ = ∇f0(w)f0(w) +O(η). (22) Combining Equation (20), Equation (21) and Equation (22), we obtain that:
f0(w) = −v(w), f1(w) = 0, (23) i.e., the high resolution ODE of second-order Runge–Kutta method is:
ẇ = −v(w) +O(η2). (24)

heading: B.2 CONTINUOUS DYNAMICS OF EXTRA-GRADIENT (EG)

text:
The continuous dynamics of Gradient Descent Ascent (GDA), Extra-Gradient (EG) and Heun’s method can be summarized as follows: ẇ = v(w) + α∇v(w)v(w) For GDA, we have α = −η/2; for EG, we have α = η/2 (Lu, 2020); for Heun’s method, ẇ = v(w) +O(η2). The Jacobian of the dynamics at the stationary point is∇v(w) + α∇v(w)2. Take λ = a+ ib ∈ Sp(∇v(w)). The eigenvalue of the Jacobian of the dynamics is:
α(a+ ib)2 + a+ ib = a+ α(a2 − b2) + i(b+ 2ab)α. (25) We want the real part to be negative, i.e.:
a+ α(a2 − b2) < 0, (26) and thus:
a(1 + αa) < αb2. (27)
for EG, α = η/2 and the dynamics diverges if a(1+(η/2)a) ≥ ηb2/2. When η is large, and η(a2−b2)/2 ≥ −a then it diverges. However, the high-resolution ODE of second-order Runge–Kutta methods only requires a < 0.

heading: B.3 HIGH-RESOLUTION ODE OF CLASSIC FOURTH-ORDER RUNGE–KUTTA METHOD (RK4)

text:
In this subsection, we derive the high-resolution ODE of the classic fourth-order Runge–Kutta method. We prove the following result: Theorem 3. The high-resolution ODE of the classic fourth-order Runge–Kutta method (RK4):
w+ = w − η 6 (v(w) + 2v2(w) + 2v3(w) + v4(w)), (28)
where
v2(w) = v(w − η
2 v(w)), v3(w) = v(w −
η 2 v2(w)), v4(w) = v(w − ηv3(w)), (29)
is
ẇ = −v(w) +O(η4). (30)
Proof. We use the following Taylor expansion:
v(w + δ) = v(w) = ∇v(w)δ + 1 2 ∇2v(w)(δ, δ) + 1 6 ∇3v(w)(δ, δ, δ) +O(‖δ4‖), (31)
where ∇2v(w) : Rd × Rd → Rd is a symmetric bilinear form, and ∇3v(w) : Rd × Rd × Rd → Rd is a symmetric trilinear form. With the formula we have:
v4(w) = v(w)− η∇v(w)v3(w) + η2
2 ∇2v(w)(v3(w), v3(w))−
η3
6 ∇3v(w)(v3(w), v3(w), v3(w)) +O(η4),
(32)
v3(w) = v(w)− η
2 ∇v(w)v2(w) +
η2
8 ∇2v(w)(v2(w), v2(w))−
η3 48 ∇3v(w)(v2(w), v2(w), v2(w)) +O(η4),
(33)
v2(w) = v(w)− η 2 ∇v(w)v(w) + η
2
8 ∇2v(w)(v(w), v(w))− η
3
48 ∇3v(w)(v(w), v(w), v(w)) +O(η4).
(34)
Putting them together we have:
v4(w) + 2v3(w) + 2v2(w) + v(w) = 6v(w)− η∇v(w)(v3(w) + v2(w) + v(w))
+ η2
2
( ∇2v(w)(v3(w), v3(w)) + 1
2 ∇2v(w)(v2(w), v2(w)) +
1 2 ∇2v(w)(v(w), v(w))
) +
− η 3
4 ∇3v(w)(v(w), v(w), v(w)) +O(η4), (35)
v3(w) + v2(w) + v(w) = 3v(w)− η
2 ∇v(w)(v2(w) + v(w)) +
η2
4 ∇2v(w)(v(w), v(w)) +O(η3),
(36)
v2(w) + v(w) = 2v(w)− η
2 ∇v(w)v(w) +O(η2). (37)
Bringing Equation (37) into Equation (36), we obtain:
v3(w) + v2(w) + v(w) = 3v(w)− η∇v(w)v(w) + η2 4 ∇2v(w)(v(w), v(w)) + η 2 4 (∇v(w))2v(w) +O(η3). (38)
Putting Equation (38) and Equation (37) together, we have:
−η∇v(w)(v3(w) + v2(w) + v(w)) = −3η∇v(w)v(w) + η2(∇v(w))2v(w)
− η 3 4 ∇v(w)∇2v(w)(v(w), v(w))− η 3 4 (∇v(w))3v(w) +O(η4).
(39)
Moreover, we have
∇2v(w)(v2(w), v2(w)) = ∇2v(w)(v − η 2 ∇v(w)v(w), v − η 2 ∇v(w)v(w)) +O(η2)
= ∇2v(w)(v(w), v(w))− η∇2v(w)(∇v(w)v(w), v(w)) +O(η2), (40)
and similarly
∇2v(w)(v3(w), v3(w)) = ∇2v(w)(v(w), v(w))− η∇2v(w)(∇v(w)v(w), v(w)) +O(η2). (41)
Bringing Equation (39) and Equation (40) into Equation (35) results in
v4(w) + 2v3(w) + 2v2(w) + v(w) = 6v(w)− 3η∇v(w)v(w) + η2((∇v(w))2v(w) +∇2v(w)(v(w), v(w))
− η 3
4 ((∇v(w))3v(w) + 3∇2v(w)(∇v(w)v(w), v(w))
+∇v(w)∇2v(w)(v(w), v(w)) +∇3v(w)(v(w), v(w), v(w))) +O(η4). (42)
Let us now derive the high-resolution ODE. From Equation (28), we have:
w+ − w η = −1 6 (v4(w) + 2v3(w) + 2v2(w) + v(w)). (43)
Let us assume that w+ = w(t+ η) and w = w(t). Expanding the left we have:
ẇ + η
2 ẅ +
η2
6
... w +
η3
24
.... w. (44)
Let us assume that the high-resolution ODE up to O(η4) has the form:
ẇ = f0(w) + ηf1(w) + η 2f2(w) + η 3f3(w) +O(η 4). (45)
Taking derivatives on both sides, we have:
ẅ = (∇f0(w) + η∇f1(w) + η2∇f2(w) + η3∇f3(w))ẇ +O(η4) = ∇f0(w)f0(w) + η(∇f1(w)f0(w) +∇f1(w)f0(w)) + η2(∇f1(w)f1(w) +∇f0(w)f2(w) +∇f2(w)f0(w)) +O(η3). (46)
Comparing the order O(1) on both sides of Equation (43) we have:
f0(w) = −v(w), f1(w) + 1
2 ∇f0(w)f0(w) =
1 2 ∇v(w)v(w), (47)
which gives f0(w) = −v(w) and f1(w) = 0. Bringing it back to Equation (46) we obtain:
ẅ = ∇v(w)v(w) +O(η2). (48)
We take the derivatives on both sides of Equation (48) to get: ... w = ∇(∇v(w)v(w))ẇ +O(η2)
= −∇(∇v(w)v(w))v(w) +O(η2). (49)
Let us now compute∇(∇v(w)v(w))v(w). We note that∇(∇v(w)v(w)) is a linear form and
∇v(w + δ)v(w + δ) = (∇v(w) +∇2v(w)δ + o(‖δ‖))(v(w) +∇v(w)δ + o(‖δ‖)) = ∇v(w)v(w) +∇2v(w)(δ, v(w)) +∇2v(w)δ + o(‖δ‖). (50)
Therefore, we have ... w = −∇(∇v(w)v(w))v(w) = −∇2v(w)(v(w), v(w))−∇2v(w)v(w) +O(η2). (51)
With Equation (51) we can compare O(η2) on both sides on Equation (43) and obtain
f2(w) = 0. (52)
Finally, we take the derivative of Equation (51). Since
∇2v(w + δ)(v(w + δ), v(w + δ)) = (∇2v(w) +∇3v(w)δ)(v(w) +∇v(w)δ, v(w) +∇v(w)δ) = ∇2v(w)(v(w), v(w)) +∇3v(w)(δ, v(w), v(w)) + 2∇2v(w)(v(w),∇v(w)δ) + o(‖δ‖), (53)
we have:
∇(∇2v(w)(v(w), v(w)))v(w) = ∇3v(w)(v(w), v(w), v(w)) + 2∇2v(w)(v(w),∇v(w)v(w)). (54)
Similarly, since
(∇v(w + δ))(∇v(w + δ))v(w + δ) = (∇v(w) +∇2v(w)δ)(∇v(w) +∇2v(w)δ)(v(w) +∇v(w)δ) = (∇v(w))2v(w) +∇2v(w)(δ,∇v(w)v(w)) +∇v(w)∇2v(w)(δ, v(w)) +∇v(w))3δ + (‖δ‖) (55)
∇(∇v(w))2v(w)(v(w)) = ∇2v(w)(v(w),∇v(w)v(w)) +∇v(w)∇2v(w)(v(w), v(w)) +∇v(w)3v(w). (56)
Combining Equation (51), Equation (54) and Equation (56) gives: .... w = ∇...wẇ = ∇v(w)3v(w) +∇3v(w)(v(w), v(w), v(w)) + 3∇2v(w)(v(w),∇v(w)v(w))
+∇v(w)∇2v(w)(v(w), v(w)). (57)
Combining Equation (45), Equation (46), Equation (51) and Equation (57) and comparing the O(η3) term of Equation (43), we obtain
f3(w) = 0. (58)
Therefore, the high-resolution ODE is:
ẇ = −v(w) +O(η4). (59)

heading: C PROOFS AND ADDITIONAL THEORETICAL RESULTS

text:
Several proofs in this section are based on the derivations of the high resolution ODEs that were proven in Appendix B.
Theorem 4. Suppose φ : Rn → R and φ is C2. Suppose also any stationary point x∗ of φ s.t.∇φ(x∗) = 0 is either:
1. a strict local minimum, i.e.∇2xxφ(x∗) 0;
2. a strict saddle. (Definition 5)
Then, the gradient flow is attracted towards a local minimum of φ.
Proof. ẋ = −∇φ(x) (60)
Define g(x) := −∇φ(x).
a) Let us first show that strict saddles are non-asymptotically stable fixed points. Thus, gradient descent is not attracted to them.
g(x) ≈ −∇2xxφ(x)(x− x∗) since∇φ(x∗) = 0 (61) g(z) ≈ −Λ(z − z∗) where z := UTx (62)
This implies g(z)i ≈ λmin(∇2xxφ(x∗))(z − z∗)i > 0. Thus, we just showed that strict saddles are nonasymptotically 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)− φ(x∗) to be a Lyapunov function. We have x∗ is asymptotically stable if:
∇V (x)T g(x) < 0 ∀x 6= x∗ (63)
From which the result follows. (e.g∇V (x)T g(x) = −||g(x)||22).
Similar results with a different proof can be derived from Lee et al. (2016).
Theorem 2. The high resolution ODE of GD with the GRL up to O(η) is:
ẇ = −v(w)−η 2 ∇v(w)v(w) (64)
Moreover, this is asymptotically stable (see Appendix A.1) at a stationary point w∗ (Proposition 3) iff for all eigenvalue written as λ = a+ ib ∈ Sp(−∇v(w∗)), we have 0 > η(a2 − b2)/2 > a.
Proof. This theorem can be obtained by computing the Jacobian of the ODE dynamics and using the Hurwitz condition Lemma 1. Specifically, we have the Jacobian of the dynamics at the stationary point is:
−∇v(ω∗)− η 2 ∇v(ω∗)2 (65)
Take λ = a+ ib ∈ Sp(−∇v(ω∗)), we must have:
<[a+ ib− η 2 (−a− ib)2] < 0,where < stands for the real part. (66)
then,
a− η 2 (a2 − b2) < 0 (67)
as desired.
Corollary 1. For the high resolution ODE of GD with GRL (i.e., Equation (64)) to be asymptotically stable, the learning rate η should be upper bounded by:
0 < η < −2a b2 − a2 , (68)
for all λ = a+ ib ∈ Sp(−∇v(w∗)) with large imaginary part (i.e. such that |a| < |b|).
Proof. With |a| < |b| where b is the imaginary part of λ ∈ C, an algebraic manipulation of Theorem 2. i.e. η(b2 − a2) < −2a leads to the desired result.
Theorem 3. The high resolution ODE of any RK2 method up to O(η), ẇ = −v(w), is asymptotically stable if for all eigenvalues λ = a+ ib ∈ Sp(−∇v(w∗)), we have a < 0.
Proof. This theorem can be obtained by computing the Jacobian of the ODE dynamics (see Appendix B for the derivation) and using the Hurwitz condition Lemma 1. For details, see the proof of Theorem 2.
Unlike the high resolution ODE of GD with GRL in Corollary 1, up to O(η), there is no upper bound constraint on the learning rate. Therefore, at the cost of an additional extra-gradient computation, we are allowed to take a more aggressive step. We observe in practice that this leads to both faster convergence and better transfer performance.
Lemma 3. Suppose the game G(I,Ωi, Ji) is a potential game with potential function φ. Suppose the minimizers of φ are either a local minimum or a strict saddle (see Definition 5). The gradient play dynamics converges to a local Nash Equilibrium.
Proof. A potential game can be analyzed in terms of the implicit function φ(w) since∇φ(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 6.
Proposition 4. The domain-adversarial game is neither a potential nor necessarily a purely adversarial game. Moreover, its gradient dynamics are not equivalent to the gradient flow.
Proof. From appendix A.2, a sufficient and necessary condition for a game to be potential is ∇v(ω) being symmetric. Computing ∇v(ω) using Equation (4) leads to ∇v(ω) being asymmetric, from which the first part of the result follows. Another way to see this, it is to notice a there is no potential function φ satisfying ∇φ(ω) = v(ω) (because of the flip in the sign in ds,t). Since the game is not a potential game then the vector field is not equal to the gradient flow (see also for more details Mazumdar et al. (2020). ) To see the game is not necessarily a purely adversarial game, it suffices to show an example for which this does not happen. See Appendix A.3 and example therein.

heading: C.1 PROPOSED LEARNING ALGORITHM

text:
Algorithm 1 Pseudo-Code of the Proposed Learning Algorithm Input: source data Ds, target data Dt, player losses Ji, network weights {ωi}3i=1, learning rate η for t = 1 to T − 1 do xs, ys ∼ Ds, xt ∼ Dt v = [gradient(xs, xt, ys, Ji) for i in 1..3 ]. ω = Gradient Descent(v, w, η) ω = Runge-KuttaSolver(v, w, η, steps=1)
end for

heading: C.2 CO APPROXIMATES RK2 (HEUN’S METHOD)

text:
We have the update rule of CO Mescheder et al. (2017):
ω+ = ω − [ηv(ω) + γ 1 2 ∇||v(ω)||22] (69)
where 1 2 ∇||v(ω)||22 = ∇v(w)>v(w)
From RK2 (Heun‘s Method), we have:
w+ = w − η 2 (v(w) + v(w − ηv(w))). (70)
= w − η 2 (2v(w)− η∇v(w)v(w) +O(η2)) (71)
If −∇v(w) = ∇v(w)> =⇒ ∇v(w) skew-symmetric, we can see that Equation (71) approximates the CO optimization method from Mescheder et al. (2017). This assumption is however not necessarily true in our case which may explain why RK2 was better in experiments. Experimentally, for CO, the best transfer performance was obtained for γ = 0.0001. We also observed that CO is very sensitive to the choice of γ.

heading: D EXPERIMENTAL SETUP ADDITIONAL DETAILS

text:
Our algorithm is implemented in Jax Bradbury et al. (2018) (Digits, NLP benchmark) and PyTorch (Visual Task). Experiments are conducted on a NVIDIA Titan V and V100 GPU Cards.
The digits benchmark constitutes of two digits datasets MNIST and USPS LeCun et al. (1998); Long et al. (2018) with two transfer tasks (M→ U and U→M). We adopt the splits and evaluation protocol from Long et al. (2018) 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 use LeNet LeCun et al. (1998) as the backbone architecture, dropout (0.5), fix the batch size to 32, the number of 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-parameters of Adam.
Grid Search Details for Comparison vs Standard Optimizers. For the learning rate, learning schedule and adaptation coefficient (λ), we 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, 0.4.
• learning scheduler: none, polynomial.
• adaptation coefficient (λ): 0.1, 0.5, 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 a HyperBandScheduler Li et al. (2018). The same hyper-parameters are used for the other task (i.e U→M). The best criteria correspond to the transfer accuracy (as it 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 γ 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.03, 0.1, 0.3, 0.4.
• learning scheduler: none, polynomial.
• Adaptation coefficient (λ): 0.1, 0.5, 1.
• CO Only. Additional (γ): 10, 1.0, 0.1, 0.01, 0.001, 0.001, 0.0001
We show the best results of this grid search in Table 6. 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.1) and on top of the public available implementations of Long et al. (2018); Zhang et al. (2019); Junguang 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 Long et al. (2018); Zhang et al. (2019). For our method, we keep the exact same hyper-parameters of GD with NM, but
increase the learning rate. We do not experiment with RK4 since the performance was similar to RK2 in the other benchmarks (see Tables 3 and 4), and it is more computationally expensive.
Experiment on Visda 2017 with SoTA algorithms. For the comparison using SoTA algorithms, we use the well-tuned hyper-parameters from Jiang et al. (2020) and set the discrepancy measure to be f -DAL Pearson as in Acuna et al. (2021) since this empirically was shown to be better than both JS and γ-JS/MDD. We use Implicit Alignment Jiang et al. (2020) as this method also allows to account for the dissimilarity between the labels marginals. We did not run grid search here as it would be very computationally expensive. In 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 al. (2006) that contains online reviews of products collected on the Amazon website. We follow the splits and evaluation protocol from Courty et al. (2017); Dhouib et al. (2020) and choose 4 of its subsets corresponding to different product categories, namely: books (B), dvd (D), electronics (E) and kitchen (K). As in Courty et al. (2017); Dhouib et al. (2020), from where we took the baseline result, the network architecture is a two layer MLP with sigmoid function. In our case, hyper-parameters are kept the same but the learning rate is increased by a factor of 10.
Implementation on different frameworks. We use both Jax and Pytorch in our paper for simplicity. Since the proposed method only requires changing some lines of code, it can be 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 analysis 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 a grid-search significantly increases the computational demand so we did not do this. That said, we report avg and std for our main experiments using the best parameters found on the grid-search.

heading: E ADDITIONAL EXPERIMENTS

heading: E.1 NATURAL LANGUAGE PROCESSING TASKS.

text: We also evaluate our approach on natural language processing tasks. We use the Amazon product reviews dataset (Blitzer et al., 2006). We follow the splits and evaluation protocol from Courty et al. (2017); Dhouib et al. (2020) and choose 4 of its subsets corresponding to different product categories, namely: books (B), dvd (D), electronics (E) and kitchen (K). In our case, hyper-parameters are the same provided by authors but the learning rate is increased by a factor of 10. Table 4 shows noticeable gains by replacing the optimizer with either RK2 or RK4.

heading: E.2 SENSITIVITY TO SAMPLING NOISE

heading: E.3 ADDITIONAL COMPARISON VS GAME OPTIMIZATION ALGORITHMS

text:
In Table 5, we show the sensitivity of our method to sampling Noise controlled by the mini-batch size. Specifically, we show results for 64, 128, 160 ( with 160 being the bigger size we could fit in 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-search for the comparison vs game optimization algorithms. For each optimizer, these results correspond to their best (in terms of transfer performance) determined from the gridsearch explained in Appendix E. We also add GD for comparison. Our method notably outperforms the baselines.

heading: E.4 CO VS GRADIENT DESCENT AND EXTRA-GRADIENT ALGORITHMS

text:
In Table 6 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, we provide some intuition about why this may be the case in practice and conduct an additional experimental on this direction.
In the analysis presented in Section 4, we show that a better discretization implies better convergence to a local optimality (assuming ω∗ exists, and that it is a strict local NE). Specifically, under those assumptions, we show that in both GD and EG methods we should put an upper bound to their learning rate (see Section 4 and appendix B.2). In Appendix C.2, on the other hand, we show CO can be interpreted in the limit as an approximation of the RK2 solver. Based on 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, we compare the performance before and after removing the best performing γ from the grid search. We can see for values others than the best γ, CO does not outperform GD-NM either.

heading: E.5 WALL-CLOCK COMPARISON

text: In Table 8, we show experimental results of a wall-clock comparison between RK2 and GD-NM. Specifically, we compute the average over 100 runs on a NVIDIA GPU: TITAN V, CudaVersion 10.1 and PyTorch version: 1.5.1. As we can see, the average increase in time is less than 2x slower in wall-clock time.This is in 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.

heading: F PYTORCH PSEUDOCODE OF RK2 SOLVER

text:
Below, we show how to implement the RK2 solver in PyTorch by simply modifying the existing implementation of SGD.
# Based on https://github.com/pytorch/pytorch/blob/release/1.5/torch/optim/sgd.py class RK2(torch.optim.optimizer): # ...... def update_step(self,fwd_bwd_fn):
""" fwd_bwd_fn: fn that computes y=model(x); loss(y,yhat).backward() example: # training loop x, yhat=sample_from_dataloader() optimizer.zero_grad()
def fwd_bwd_fn(): y=model(x) loss=compute_loss(y,yhat) loss.backward() return loss,y
fwd_bwd_fn() optimizer.update(fwd_bwd_fn)
""" # We want to compute the update equation: # w - n/2* v(w) - n/2 * v(w-n*v(w)) temp_step = {} with torch.no_grad():
for jj_, group in enumerate(self.param_groups): #ignore weight-decay for simplicity.
for ii_, p in enumerate(group['params']): if p.grad is None:
continue d_p = p.grad # v(w)
# first part of the step. # w - n/2*v(w) p1 = p.data.clone().detach() p1.add_(d_p, alpha=-0.5 * group['lr'])
#storing for later used. temp_step[f"{jj_}_{ii_}"] = p1
# Computing now w-n*v(w) for the second part of the step p.add_(d_p, alpha=-1.0 * group['lr'])
# set to none p.grad = None # self.zero_grad()
# extra step evaluation. # this function does model forward,compute loss and loss backward. loss, _ = fwd_bwd_fn() # gradients are now v(w-n*v(w))
with torch.no_grad():
for jj_, group in enumerate(self.param_groups): for ii_, p in enumerate(group['params']):
if p.grad is None: continue d_p = p.grad # v(w-n*v(w))
# unpacking the first part of the step. p1 = temp_step[f"{jj_}_{ii_}"]
# updating p with the stored value from before. # this is equivalent to p = p1 = w-n/2 * v(w) (but sligthly faster) p.zero_() p.add_(p1)
#w= w - n/2*v(w) - n/2 * v(w-n*v(w)) p.add_(d_p, alpha=-0.5 * group['lr'])

title: DOMAIN ADVERSARIAL TRAINING A GAME PERSPECTIVE