publications

2024

1. preprint

   Polymatrix Competitive Gradient Descent

   J. Ma,  A. Letcher, F. Schäfer, Y. Shi, A. Anandkumar

   preprint

   Abs arXiv

   Many economic games and machine learning approaches can be cast as competitive optimization problems where multiple agents are minimizing their respective objective function, which depends on all agents’ actions. While gradient descent is a reliable basic workhorse for single-agent optimization, it often leads to oscillation in competitive optimization. In this work we propose polymatrix competitive gradient descent (PCGD) as a method for solving general sum competitive optimization involving arbitrary numbers of agents. The updates of our method are obtained as the Nash equilibria of a local polymatrix approximation with a quadratic regularization, and can be computed efficiently by solving a linear system of equations. We prove local convergence of PCGD to stable fixed points for n-player general-sum games, and show that it does not require adapting the step size to the strength of the player-interactions. We use PCGD to optimize policies in multi-agent reinforcement learning and demonstrate its advantages in Snake, Markov soccer and an electricity market game. Agents trained by PCGD outperform agents trained with simultaneous gradient descent, symplectic gradient adjustment, and extragradient in Snake and Markov soccer games and on the electricity market game, PCGD trains faster than both simultaneous gradient descent and the extragradient method.

2. preprint

   How Do Pauli Gates Propagate?

   A. Letcher

   Abs

   Among the primary building blocks of quantum circuits are the Pauli gates (X, Y, Z) and their controlled counterparts (usually CX or CZ). The latter are commonly stacked together to form entanglement layers in a linear / reverse-linear / pairwise / full or circular fashion, as implemented in the quantum computing library, Qiskit. This short article addresses the simple question of how Pauli gates ‘propagate’ across any number m of such layers. While this question is easily resolved for a single layer (m = 1), we prove explicit commutation relations for arbitrary m ∈ N using elementary combinatorics.

3. QJ

   Tight and Efficient Gradient Bounds for Parameterized Quantum Circuits

   A. Letcher, S. Woerner, C. Zoufal

   Quantum Journal

   Abs arXiv HTML

   The training of a parameterized model largely depends on the landscape of the underlying loss function. In particular, vanishing gradients are a central bottleneck in the scalability of variational quantum algorithms (VQAs), and are known to arise in various ways. However, a caveat of most existing gradient bound results is the requirement of t-design circuit assumptions that are typically not satisfied in practice. In this work, we loosen these assumptions altogether and derive tight upper and lower bounds on loss and gradient concentration for a large class of parameterized quantum circuits and arbitrary observables, which are significantly stronger than prior work. Moreover, we show that these bounds, as well as the variance of the loss itself, can be estimated efficiently and classically-providing practical tools to study the loss landscapes of VQA models, including verifying whether or not a circuit/observable induces barren plateaus. In particular, our results can readily be leveraged to rule out barren plateaus for a realistic class of ansätze and mixed observables, namely, observables containing a non-vanishing local term. This insight has direct implications for hybrid Quantum Generative Adversarial Networks (qGANs). We prove that designing the discriminator appropriately leads to 1-local weights that stay constant in the number of qubits, regardless of discriminator depth. This implies that qGANs with appropriately chosen generators do not suffer from barren plateaus even at scale-making them a promising candidate for applications in generative quantum machine learning. We demonstrate this result by training a qGAN to learn a 2D mixture of Gaussian distributions with up to 16 qubits, and provide numerical evidence that global contributions to the gradient, while initially exponentially small, may kick in substantially over the course of training.

2023

1. ICML

   Adversarial Cheap Talk

   C. Lu, T. Willi,  A. Letcher, J. Foerster

   International Conference on Machine Learning

   Abs arXiv HTML

   Adversarial attacks in reinforcement learning (RL) often assume highly-privileged access to the learning agent’s parameters, environment or data. Instead, this paper proposes a novel adversarial setting called a Cheap Talk MDP in which an Adversary has a minimal range of influence over the Victim. Parameterised as a deterministic policy that only conditions on the current state, an Adversary can merely append information to a Victim’s observation. To motivate the minimum-viability, we prove that in this setting the Adversary cannot occlude the ground truth, influence the underlying dynamics of the environment, introduce non-stationarity, add stochasticity, see the Victim’s actions, or access their parameters. Additionally, we present a novel meta-learning algorithm to train the Adversary, called adversarial cheap talk (ACT). Using ACT, we demonstrate that the resulting Adversary still manages to influence the Victim’s training and test performance despite these restrictive assumptions. Affecting train-time performance reveals a new attack vector and provides insight into the success and failure modes of existing RL algorithms. More specifically, we show that an ACT Adversary is capable of harming performance by interfering with the learner’s function approximation and helping the Victim’s performance by appending useful features. Finally, we demonstrate that an ACT Adversary can append information during train-time to directly and arbitrarily control the Victim at test-time in a zero-shot manner.

2022

1. NIPS

   Discovered Policy Optimisation

   C. Lu, J. Kuba,  A. Letcher, L. Metz, C. Schroeder Witt, J. Foerster

   Advances in Neural Information Processing Systems

   Abs arXiv HTML

   Tremendous progress has been made in reinforcement learning (RL) over the past decade. Most of these advancements came through the continual development of new algorithms, which were designed using a combination of mathematical derivations, intuitions, and experimentation. Such an approach of creating algorithms manually is limited by human understanding and ingenuity. In contrast, meta-learning provides a toolkit for automatic machine learning method optimisation, potentially addressing this flaw. However, black-box approaches which attempt to discover RL algorithms with minimal prior structure have thus far not outperformed existing hand-crafted algorithms. Mirror Learning, which includes RL algorithms, such as PPO, offers a potential middle-ground starting point: while every method in this framework comes with theoretical guarantees, components that differentiate them are subject to design. In this paper we explore the Mirror Learning space by meta-learning a "drift" function. We refer to the immediate result as Learnt Policy Optimisation (LPO). By analysing LPO we gain original insights into policy optimisation which we use to formulate a novel, closed-form RL algorithm, Discovered Policy Optimisation (DPO). Our experiments in Brax environments confirm state-of-the-art performance of LPO and DPO, as well as their transfer to unseen settings.

2. ICML

   COLA: Consistent Learning with Opponent-Learning Awareness

   T. Willi, J. Treutlein,  A. Letcher, J. Foerster

   International Conference on Machine Learning

   Abs arXiv HTML

   Learning in general-sum games can be unstable and often leads to socially undesirable, Pareto-dominated outcomes. To mitigate this, Learning with Opponent-Learning Awareness (LOLA) introduced opponent shaping to this setting, by accounting for the agent’s influence on the anticipated learning steps of other agents. However, the original LOLA formulation (and follow-up work) is inconsistent because LOLA models other agents as naive learners rather than LOLA agents. In previous work, this inconsistency was suggested as a cause of LOLA’s failure to preserve stable fixed points (SFPs). First, we formalize consistency and show that higher-order LOLA (HOLA) solves LOLA’s inconsistency problem if it converges. Second, we correct a claim made in the literature, by proving that, contrary to Schäfer and Anandkumar (2019), Competitive Gradient Descent (CGD) does not recover HOLA as a series expansion. Hence, CGD also does not solve the consistency problem. Third, we propose a new method called Consistent LOLA (COLA), which learns update functions that are consistent under mutual opponent shaping. It requires no more than second-order derivatives and learns consistent update functions even when HOLA fails to converge. However, we also prove that even consistent update functions do not preserve SFPs, contradicting the hypothesis that this shortcoming is caused by LOLA’s inconsistency. Finally, in an empirical evaluation on a set of general-sum games, we find that COLA finds prosocial solutions and that it converges under a wider range of learning rates than HOLA and LOLA. We support the latter finding with a theoretical result for a simple game.

2021

1. ICLR

   On the Impossibility of Global Convergence in Multi-Loss Optimization

   A. Letcher

   International Conference on Learning Representations

   Abs arXiv HTML Code

   Under mild regularity conditions, gradient-based methods converge globally to a critical point in the single-loss setting. This is known to break down for vanilla gradient descent when moving to multi-loss optimization, but can we hope to build some algorithm with global guarantees? We negatively resolve this open problem by proving that any reasonable algorithm will exhibit limit cycles or diverge to infinite losses in some differentiable game, even in two-player games with zero-sum interactions. A reasonable algorithm is simply one which avoids strict maxima, an exceedingly weak assumption since converging to maxima would be the opposite of minimization. This impossibility theorem holds even if we impose existence of a strict minimum and no other critical points. The proof is constructive, enabling us to display explicit limit cycles for existing gradient-based methods. Nonetheless, it remains an open question whether cycles arise in high-dimensional games of interest to ML practitioners, such as GANs or multi-agent RL.

2020

1. NIPS

   Ridge Rider: Finding Diverse Solutions by Following Eigenvectors of the Hessian

   J. Parker-Holder, L. Metz, C. Resnick, H. Hu, A. Lerer,  A. Letcher, A. Peysakhovich, A. Pacchiano, J. Foerster

   Advances in Neural Information Processing Systems

   Abs arXiv HTML Blog

   Over the last decade, a single algorithm has changed many facets of our lives - Stochastic Gradient Descent (SGD). In the era of ever decreasing loss functions, SGD and its various offspring have become the go-to optimization tool in machine learning and are a key component of the success of deep neural networks (DNNs). While SGD is guaranteed to converge to a local optimum (under loose assumptions), in some cases it may matter which local optimum is found, and this is often context-dependent. Examples frequently arise in machine learning, from shape-versus-texture-features to ensemble methods and zero-shot coordination. In these settings, there are desired solutions which SGD on ’standard’ loss functions will not find, since it instead converges to the ’easy’ solutions. In this paper, we present a different approach. Rather than following the gradient, which corresponds to a locally greedy direction, we instead follow the eigenvectors of the Hessian, which we call "ridges". By iteratively following and branching amongst the ridges, we effectively span the loss surface to find qualitatively different solutions. We show both theoretically and experimentally that our method, called Ridge Rider (RR), offers a promising direction for a variety of challenging problems.

2019

1. JMLR

   Differentiable Game Mechanics

   A. Letcher, D. Balduzzi, S. Racanière, J. Martens, J. Foerster, K. Tuyls, T. Graepel

   Journal of Machine Learning Research

   Abs arXiv HTML Code

   Deep learning is built on the foundational guarantee that gradient descent on an objective function converges to local minima. Unfortunately, this guarantee fails in settings, such as generative adversarial nets, that exhibit multiple interacting losses. The behavior of gradient-based methods in games is not well understood – and is becoming increasingly important as adversarial and multi-objective architectures proliferate. In this paper, we develop new tools to understand and control the dynamics in n-player differentiable games. The key result is to decompose the game Jacobian into two components. The first, symmetric component, is related to potential games, which reduce to gradient descent on an implicit function. The second, antisymmetric component, relates to Hamiltonian games, a new class of games that obey a conservation law akin to conservation laws in classical mechanical systems. The decomposition motivates Symplectic Gradient Adjustment (SGA), a new algorithm for finding stable fixed points in differentiable games. Basic experiments show SGA is competitive with recently proposed algorithms for finding stable fixed points in GANs – while at the same time being applicable to, and having guarantees in, much more general cases.

2. ICLR

   Stable Opponent Shaping in Differentiable Games

   A. Letcher, J. Foerster, D. Balduzzi, T. Rocktäschel, S. Whiteson

   International Conference on Learning Representations

   Abs arXiv HTML Code

   A growing number of learning methods are actually games which optimise multiple, interdependent objectives in parallel – from GANs and intrinsic curiosity to multi-agent RL. Opponent shaping is a powerful approach to improve learning dynamics in such games, accounting for the fact that the ’environment’ includes agents adapting to one another’s updates. Learning with Opponent-Learning Awareness (LOLA) is a recent algorithm which exploits this dynamic response and encourages cooperation in settings like the Iterated Prisoner’s Dilemma. Although experimentally successful, we show that LOLA can exhibit ’arrogant’ behaviour directly at odds with convergence. In fact, remarkably few algorithms have theoretical guarantees applying across all differentiable games. In this paper we present Stable Opponent Shaping (SOS), a new method that interpolates between LOLA and a stable variant named LookAhead. We prove that LookAhead locally converges and avoids strict saddles in all differentiable games, the strongest results in the field so far. SOS inherits these desirable guarantees, while also shaping the learning of opponents and consistently either matching or outperforming LOLA experimentally.

2018

1. ICASSP

   Automatic Conflict Detection in Police Body-Worn Audio

   A. Letcher, J. Trišović, C. Cademartori, X. Chen, J. Xu

   IEEE International Conference on Acoustics, Speech and Signal Processing

   Abs arXiv HTML

   Automatic conflict detection has grown in relevance with the advent of body-worn technology, but existing metrics such as turn-taking and overlap are poor indicators of conflict in police-public interactions. Moreover, standard techniques to compute them fall short when applied to such diversified and noisy contexts. We develop a pipeline catered to this task combining adaptive noise removal, non-speech filtering and new measures of conflict based on the repetition and intensity of phrases in speech. We demonstrate the effectiveness of our approach on body-worn audio data collected by the Los Angeles Police Department.

theses

1. MSc

   Stability and Exploitation in Differentiable Games, 2018

   Abs PDF

   While machine learning has traditionally focused on optimising single loss functions, a growing number of algorithms deal with multiple interacting goals, from GANs to multi-agent RL. Naively transposing gradient descent has been shown to fail, while state-of-the-art proposals are tailored to specific applications (e.g. two-player zero-sum games) or lack strong theoretical guarantees. We provide a unified approach to this problem and prove local convergence of Consensus Optimisation, Symplectic Gradient Adjustment and lookahead in all differentiable games. Learning with Opponent-Learning Awareness (LOLA) takes a different approach by shaping and exploiting opponent learning, reaching better equilibria and outperforming previous methods. On the flip side, we construct the first example where this backlashes in self-play, producing arrogant behaviour and poor losses. We address and solve this catch-22 with a new algorithm named Stable Opponent Shaping (SOS), inheriting strong convergence guarantees from lookahead and shaping capacity from LOLA. We obtain convergence of LOLA to equilibria in two-player zero-sum and n-player cooperative games as a corollary.

2. BSc

   Algebraic Features of Multiple Zeta Values, 2017

   Abs PDF

   This report aims to present multiple zeta values, a topic which has witnessed a rich mathematical revival and profound breakthroughs in recent years, yet remains cloaked with long-standing conjectures. It is aimed at the undergraduate/first-year postgraduate reader, but we hope that it will be relevant to anyone with curiosity for the subject. The first three chapters introduce the algebraic structure of multiple zeta values in a detailed, rigorous and approachable way. Chapter 4 investigates interpolation (as recently introduced by Yamamoto) and presents a few independent results on the topic. The final chapter gives a glimpse of a more sophisticated approach involving the theory of motives, which has borne powerful results in recent years.