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. 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. 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.  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.name: David Acuna
authors.name: Marc T. Law
authors.name: Guojun Zhang
authors.name: Sanja Fidler
references.authors: David Acuna Guojun Zhang Marc T. Law Sanja
references.title: Fidler. f -domain adversarial learning: Theory and algorithms
references.venue: In Proceedings of the 38th International Conference on Machine Learning,
references.authors: Waïss Azizian Ioannis Mitliagkas Simon Lacoste-Julien Gauthier Gidel
references.title: A tight and unified analysis of gradient-based methods for a whole spectrum of differentiable games
references.venue: In Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics,
references.authors: David Barrett Benoit Dherin
references.title: Implicit gradient regularization
references.venue: In International Conference on Learning Representations,
references.authors: Tamer Başar Geert Jan Olsder
references.title: Dynamic Noncooperative Game Theory, 2nd Edition
references.venue: Society for Industrial and Applied Mathematics,
references.authors: Shai Ben-David John Blitzer Koby Crammer Fernando Pereira
references.title: Analysis of representations for domain adaptation
references.venue: In Advances in neural information processing systems,
references.authors: Shai Ben-David John Blitzer Koby Crammer Alex Kulesza Fernando Pereira Jennifer Wortman Vaughan
references.title: A theory of learning from different domains
references.venue: Machine learning,
references.authors: Shai Ben-David Tyler Lu Teresa Luu Dávid Pál
references.title: Impossibility theorems for domain adaptation
references.venue: In Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics,
references.authors: Hugo Berard Gauthier Gidel Amjad Almahairi Pascal Vincent Simon Lacoste-Julien
references.title: A closer look at the optimization landscapes of generative adversarial networks
references.venue: In International Conference on Learning Representations,
references.authors: John Blitzer Ryan McDonald Fernando Pereira
references.title: Domain adaptation with structural correspondence learning
references.venue: In Proceedings of the 2006 conference on empirical methods in natural language processing,
references.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
references.title: JAX: composable transformations of Python+NumPy programs, 2018
references.venue: URL http://github.com/google/jax
references.authors: John Charles Butcher
references.title: A history of runge-kutta methods
references.venue: Applied numerical mathematics,
references.authors: Woong-Gi Chang Tackgeun You Seonguk Seo Suha Kwak Bohyung Han
references.title: Domain-specific batch normalization for unsupervised domain adaptation
references.venue: In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition,
references.authors: Ricky T.Q. Chen Yulia Rubanova Jesse Bettencourt David K Duvenaud
references.title: Neural ordinary differential equations
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Nicolas Courty Rémi Flamary Amaury Habrard Alain Rakotomamonjy
references.title: Joint distribution optimal transportation for domain adaptation
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Sofien Dhouib Ievgen Redko Carole Lartizien
references.title: Margin-aware adversarial domain adaptation with optimal transport
references.venue: Proceedings of the 37th International Conference on Machine Learning,
references.authors: Yaroslav Ganin Victor Lempitsky
references.title: Unsupervised domain adaptation by backpropagation
references.venue: In International conference on machine learning,
references.authors: Yaroslav Ganin Evgeniya Ustinova Hana Ajakan Pascal Germain Hugo Larochelle François Laviolette Mario Marchand Victor Lempitsky
references.title: Domain-adversarial training of neural networks
references.venue: The Journal of Machine Learning Research,
references.authors: Ian Gemp Sridhar Mahadevan
references.title: Global convergence to the equilibrium of gans using variational inequalities
references.venue: arXiv preprint arXiv:1808.01531,
references.authors: Gauthier Gidel Hugo Berard Gaëtan Vignoud Pascal Vincent Simon Lacoste-Julien
references.title: A variational inequality perspective on generative adversarial networks
references.venue: In ICLR,
references.authors: Gauthier Gidel Reyhane Askari Hemmat Mohammad Pezeshki Rémi Le Priol Gabriel Huang Simon LacosteJulien Ioannis Mitliagkas
references.title: Negative momentum for improved game dynamics
references.venue: In The 22nd International Conference on Artificial Intelligence and Statistics,
references.authors: Ian Goodfellow Jean Pouget-Abadie Mehdi Mirza Bing Xu David Warde-Farley Sherjil Ozair Aaron Courville Yoshua Bengio
references.title: Generative adversarial nets
references.venue: In Advances in neural information processing systems,
references.authors: Ernst Hairer Marlis Hochbruck Arieh Iserles Christian Lubich
references.title: Geometric numerical integration
references.venue: Oberwolfach Reports,
references.authors: Kaiming He Xiangyu Zhang Shaoqing Ren Jian Sun
references.title: Deep residual learning for image recognition
references.venue: In Proceedings of the IEEE conference on computer vision and pattern recognition,
references.authors: Judy Hoffman Eric Tzeng Taesung Park Jun-Yan Zhu Phillip Isola Kate Saenko Alexei Efros Trevor Darrell
references.title: Cycada: Cycle-consistent adversarial domain adaptation
references.venue: In International conference on machine learning,
references.authors: Yu-Guan Hsieh Franck Iutzeler Jérôme Malick Panayotis Mertikopoulos
references.title: Explore aggressively, update conservatively: Stochastic extragradient methods with variable stepsize scaling
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Xiang Jiang Qicheng Lao Stan Matwin Mohammad Havaei
references.title: Implicit class-conditioned domain alignment for unsupervised domain adaptation
references.venue: Proceedings of the 37th International Conference on Machine Learning,
references.authors: Chi Jin Praneeth Netrapalli Michael Jordan
references.title: What is local optimality in nonconvex-nonconcave minimax optimization
references.venue: In International Conference on Machine Learning,
references.authors: Diederik P Kingma Jimmy Ba
references.title: Adam: A method for stochastic optimization
references.venue: arXiv preprint arXiv:1412.6980,
references.authors: GM Korpelevich
references.title: The extragradient method for finding saddle points and other problems
references.venue: Matecon, 12:747–756,
references.authors: Yann LeCun Léon Bottou Yoshua Bengio Patrick Haffner
references.title: Gradient-based learning applied to document recognition
references.venue: Proceedings of the IEEE,
references.authors: Jason D. Lee Max Simchowitz Michael I. Jordan Benjamin Recht
references.title: Gradient descent only converges to minimizers
references.venue: In 29th Annual Conference on Learning Theory,
references.authors: Alistair Letcher David Balduzzi Sébastien Racanière James Martens Jakob Foerster Karl Tuyls Thore Graepel
references.title: Differentiable game mechanics
references.venue: Journal of Machine Learning Research,
references.authors: Liam Li Kevin Jamieson Afshin Rostamizadeh Ekaterina Gonina Moritz Hardt Ben Recht Ameet Talwalkar
references.title: Massively parallel hyperparameter tuning
references.authors: Richard Liaw Eric Liang Robert Nishihara Philipp Moritz Joseph E Gonzalez Ion Stoica
references.title: Tune: A research platform for distributed model selection and training
references.venue: arXiv preprint arXiv:1807.05118,
references.authors: Mingsheng Long Zhangjie Cao Jianmin Wang Michael I Jordan
references.title: Conditional adversarial domain adaptation
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Jonathan Lorraine David Acuna Paul Vicol David Duvenaud
references.title: Complex momentum for optimization in games, 2021a
references.authors: Jonathan Lorraine Paul Vicol Jack Parker-Holder Tal Kachman Luke Metz Jakob Foerster
references.title: Lyapunov exponents for diversity in differentiable games
references.venue: arXiv preprint arXiv:2112.14570,
references.authors: Haihao Lu
references.title: An o (sr)-resolution ode framework for discrete-time optimization algorithms and applications to convex-concave saddle-point problems
references.venue: arXiv preprint arXiv:2001.08826,
references.authors: Yishay Mansour Mehryar Mohri Afshin Rostamizadeh
references.title: Domain adaptation: Learning bounds and algorithms
references.venue: In Proceedings of The 22nd Annual Conference on Learning Theory (COLT
references.authors: Eric Mazumdar Lillian J Ratliff S Shankar Sastry
references.title: On gradient-based learning in continuous games
references.venue: SIAM Journal on Mathematics of Data Science,
references.authors: Eric V Mazumdar Michael I Jordan S Shankar Sastry
references.title: On finding local nash equilibria (and only local nash equilibria) in zero-sum games
references.authors: Panayotis Mertikopoulos Bruno Lecouat Houssam Zenati Chuan-Sheng Foo Vijay Chandrasekhar Georgios Piliouras
references.title: Optimistic mirror descent in saddle-point problems: Going the extra(-gradient) mile
references.venue: In International Conference on Learning Representations,
references.authors: Lars Mescheder Sebastian Nowozin Andreas Geiger
references.title: The numerics of gans
references.venue: Advances in neural information processing systems,
references.authors: Xingchao Peng Ben Usman Neela Kaushik Judy Hoffman Dequan Wang Kate Saenko
references.title: Visda: The visual domain adaptation challenge
references.venue: arXiv preprint arXiv:1710.06924,
references.authors: Chongli Qin Yan Wu Jost Tobias Springenberg Andy Brock Jeff Donahue Timothy Lillicrap Pushmeet Kohli
references.title: Training generative adversarial networks by solving ordinary differential equations
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Lillian J Ratliff Samuel A Burden S Shankar Sastry
references.title: On the characterization of local nash equilibria in continuous games
references.venue: IEEE Transactions on Automatic Control,
references.authors: Kuniaki Saito Kohei Watanabe Yoshitaka Ushiku Tatsuya Harada
references.title: Maximum classifier discrepancy for unsupervised domain adaptation
references.venue: In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition,
references.authors: Damien Scieur Vincent Roulet Francis Bach Alexandre d'Aspremont
references.title: Integration methods and optimization algorithms
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Ozan Sener Hyun Oh Song Ashutosh Saxena Silvio Savarese
references.title: Learning transferrable representations for unsupervised domain adaptation
references.venue: Advances in Neural Information Processing Systems,
references.authors: Bin Shi Simon S Du Michael I Jordan Weijie J Su
references.title: Understanding the acceleration phenomenon via high-resolution differential equations
references.venue: arXiv preprint arXiv:1810.08907,
references.authors: Rui Shu Hung Bui Hirokazu Narui Stefano Ermon
references.title: A dirt-t approach to unsupervised domain adaptation
references.venue: In International Conference on Learning Representations,
references.authors: Yu Sun Eric Tzeng Trevor Darrell Alexei A Efros
references.title: Unsupervised domain adaptation through selfsupervision
references.venue: arXiv preprint arXiv:1909.11825,
references.authors: Ilya Sutskever James Martens George Dahl Geoffrey Hinton
references.title: On the importance of initialization and momentum in deep learning
references.venue: In International conference on machine learning,
references.authors: Laurens Van der Maaten Geoffrey Hinton
references.title: Visualizing data using t-sne
references.venue: Journal of machine learning research,
references.authors: Guojun Zhang Yaoliang Yu
references.title: Convergence of gradient-based methods on bilinear games
references.venue: In International Conference on Learning Representations,
references.authors: Jingzhao Zhang Aryan Mokhtari Suvrit Sra Ali Jadbabaie
references.title: Direct runge-kutta discretization achieves acceleration
references.venue: arXiv preprint arXiv:1805.00521,
references.authors: Yuchen Zhang Tianle Liu Mingsheng Long Michael Jordan
references.title: Bridging theory and algorithm for domain adaptation
references.venue: In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning,
references.authors: Berard
references.title: 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
references.authors: Jin
references.title: 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
references.authors: Mazumdar
references.title: 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
references.authors: Jax Bradbury
references.title: 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
references.venue: D EXPERIMENTAL SETUP ADDITIONAL DETAILS Our algorithm
references.authors: Ray Tune Liaw
references.title: 2018) and on the transfer task M→U. To avoid expending resources in bad runs we use a HyperBandScheduler
references.authors: Zhang
references.title: 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
references.venue: CO Only
references.authors: Zhang
references.title: 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
references.authors: Acuna
references.title: 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
references.authors: Dhouib
references.title: We follow the splits and evaluation protocol from Courty et al
sections.heading: 1 INTRODUCTION
sections.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.
sections.heading: 3 A GAME PERSPECTIVE ON DAL
sections.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.
sections.heading: 3.1 DOMAIN-ADVERSARIAL GAME
sections.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.
sections.heading: 3.2 CHARACTERIZATION OF THE DOMAIN-ADVERSARIAL GAME
sections.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).
sections.heading: 4 LEARNING ALGORITHMS
sections.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.
sections.heading: 4.1 CONTINUOUS GRADIENT DYNAMICS
sections.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).
sections.heading: 4.2 ANALYSIS OF GD WITH THE GRL
sections.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.
sections.heading: 4.3 HIGHER ORDER ODE SOLVERS
sections.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.
sections.heading: 5 RELATED WORK
sections.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.
sections.heading: 6 EXPERIMENTAL RESULTS
sections.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)).
sections.heading: 6.1 EXPERIMENTAL ANALYSIS ON DIGITS
sections.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.
sections.heading: 7 CONCLUSIONS
sections.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.
sections.heading: SUPPLEMENTARY MATERIAL
sections.heading: CONTENTS
sections.heading: 1 Introduction 1
sections.heading: 2 Preliminaries 2
sections.heading: 3 A Game Perspective on DAL 3
sections.text: 3.1 Domain-Adversarial Game . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
  3.2 Characterization of the Domain-Adversarial Game . . . . . . . . . . . . . . . . . . . . . . . 4
sections.heading: 4 Learning Algorithms 4
sections.text: 4.1 Continuous Gradient Dynamics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
  4.2 Analysis of GD with the GRL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
  4.3 Higher order ODE Solvers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
sections.heading: 5 Related Work 7
sections.heading: 6 Experimental Results 7
sections.text: 6.1 Experimental Analysis on Digits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
  6.2 Comparison in complex adaptation tasks . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
sections.heading: 7 Conclusions 9
sections.heading: A Concepts in Game Theory 15
sections.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
sections.heading: B Derivation of high-resolution ODEs 17
sections.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
sections.heading: C Proofs and additional theoretical results 20
sections.text: C.1 Proposed Learning Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
  C.2 CO approximates RK2 (Heun’s Method) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
sections.heading: D Experimental Setup Additional Details 22
sections.heading: E Additional Experiments 23
sections.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
sections.heading: F PyTorch PseudoCode of RK2 Solver 25
sections.heading: A CONCEPTS IN GAME THEORY
sections.heading: A.1 DEFINITIONS
sections.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∗))
sections.heading: A.2 GAMES CHARACTERIZATIONS
sections.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).
sections.heading: A.3 CASE OF STUDY IN DANN. ORIGINAL FORMULATION FROM GANIN ET AL. (2016)
sections.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.
sections.heading: B DERIVATION OF HIGH-RESOLUTION ODES
sections.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).
sections.heading: B.1 HIGH-RESOLUTION ODE OF SECOND-ORDER RUNGE–KUTTA METHOD
sections.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)
sections.heading: B.2 CONTINUOUS DYNAMICS OF EXTRA-GRADIENT (EG)
sections.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.
sections.heading: B.3 HIGH-RESOLUTION ODE OF CLASSIC FOURTH-ORDER RUNGE–KUTTA METHOD (RK4)
sections.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)
sections.heading: C PROOFS AND ADDITIONAL THEORETICAL RESULTS
sections.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.
sections.heading: C.1 PROPOSED LEARNING ALGORITHM
sections.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
sections.heading: C.2 CO APPROXIMATES RK2 (HEUN’S METHOD)
sections.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 γ.
sections.heading: D EXPERIMENTAL SETUP ADDITIONAL DETAILS
sections.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.
sections.heading: E ADDITIONAL EXPERIMENTS
sections.heading: E.1 NATURAL LANGUAGE PROCESSING TASKS.
sections.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.
sections.heading: E.2 SENSITIVITY TO SAMPLING NOISE
sections.heading: E.3 ADDITIONAL COMPARISON VS GAME OPTIMIZATION ALGORITHMS
sections.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.
sections.heading: E.4 CO VS GRADIENT DESCENT AND EXTRA-GRADIENT ALGORITHMS
sections.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.
sections.heading: E.5 WALL-CLOCK COMPARISON
sections.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.
sections.heading: F PYTORCH PSEUDOCODE OF RK2 SOLVER
sections.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