Publications (43)
Falsifiable implies Learnable
David Balduzzi
The paper demonstrates that falsifiability is fundamental to learning. We prove the following theorem for statistical learning and sequential prediction: If a theory is falsifiable…
Smooth markets: A basic mechanism for organizing gradient-based learners
David Balduzzi, Wojciech M Czarnecki, Thomas W Anthony +5
With the success of modern machine learning, it is becoming increasingly important to understand and control how learning algorithms interact. Unfortunately, negative results from…
Correlated random features for fast semi-supervised learning
Brian McWilliams, David Balduzzi, Joachim M. Buhmann
This paper presents Correlated Nystrom Views (XNV), a fast semi-supervised algorithm for regression and classification. The algorithm draws on two main ideas. First, it generates t…
Cortical prediction markets
David Balduzzi
We investigate cortical learning from the perspective of mechanism design. First, we show that discretizing standard models of neurons and synaptic plasticity leads to rational age…
Strongly-Typed Agents are Guaranteed to Interact Safely
David Balduzzi
As artificial agents proliferate, it is becoming increasingly important to ensure that their interactions with one another are well-behaved. In this paper, we formalize a common-se…
Neural Taylor Approximations: Convergence and Exploration in Rectifier Networks
David Balduzzi, Brian McWilliams, Tony Butler-Yeoman
Modern convolutional networks, incorporating rectifiers and max-pooling, are neither smooth nor convex; standard guarantees therefore do not apply. Nevertheless, methods from conve…
Deep Online Convex Optimization with Gated Games
David Balduzzi
Methods from convex optimization are widely used as building blocks for deep learning algorithms. However, the reasons for their empirical success are unclear, since modern convolu…
Domain Generalization for Object Recognition with Multi-task Autoencoders
Muhammad Ghifary, W. Bastiaan Kleijn, Mengjie Zhang +1
The problem of domain generalization is to take knowledge acquired from a number of related domains where training data is available, and to then successfully apply it to previousl…
Semantics, Representations and Grammars for Deep Learning
David Balduzzi
Deep learning is currently the subject of intensive study. However, fundamental concepts such as representations are not formally defined -- researchers "know them when they see th…
From Poincaré Recurrence to Convergence in Imperfect Information Games: Finding Equilibrium via Regularization
Julien Perolat, Remi Munos, Jean-Baptiste Lespiau +10
In this paper we investigate the Follow the Regularized Leader dynamics in sequential imperfect information games (IIG). We generalize existing results of Poincaré recurrence from…
Open-ended Learning in Symmetric Zero-sum Games
David Balduzzi, Marta Garnelo, Yoram Bachrach +4
Zero-sum games such as chess and poker are, abstractly, functions that evaluate pairs of agents, for example labeling them `winner' and `loser'. If the game is approximately transi…
Kickback cuts Backprop's red-tape: Biologically plausible credit assignment in neural networks
David Balduzzi, Hastagiri Vanchinathan, Joachim Buhmann
Error backpropagation is an extremely effective algorithm for assigning credit in artificial neural networks. However, weight updates under Backprop depend on lengthy recursive com…
Stable Opponent Shaping in Differentiable Games
Alistair Letcher, Jakob Foerster, David Balduzzi +2
A growing number of learning methods are actually differentiable games whose players optimise multiple, interdependent objectives in parallel -- from GANs and intrinsic curiosity t…
Domain Generalization via Invariant Feature Representation
Krikamol Muandet, David Balduzzi, Bernhard Schölkopf
This paper investigates domain generalization: How to take knowledge acquired from an arbitrary number of related domains and apply it to previously unseen domains? We propose Doma…
Randomized co-training: from cortical neurons to machine learning and back again
David Balduzzi
Despite its size and complexity, the human cortex exhibits striking anatomical regularities, suggesting there may simple meta-algorithms underlying cortical learning and computatio…
Towards a learning-theoretic analysis of spike-timing dependent plasticity
David Balduzzi, Michel Besserve
This paper suggests a learning-theoretic perspective on how synaptic plasticity benefits global brain functioning. We introduce a model, the selectron, that (i) arises as the fast…
Pick Your Battles: Interaction Graphs as Population-Level Objectives for Strategic Diversity
Marta Garnelo, Wojciech Marian Czarnecki, Siqi Liu +5
Strategic diversity is often essential in games: in multi-player games, for example, evaluating a player against a diverse set of strategies will yield a more accurate estimate of…
On the information-theoretic structure of distributed measurements
David Balduzzi
The internal structure of a measuring device, which depends on what its components are and how they are organized, determines how it categorizes its inputs. This paper presents a g…
A Nonparametric Conjugate Prior Distribution for the Maximizing Argument of a Noisy Function
Pedro A. Ortega, Jordi Grau-Moya, Tim Genewein +2
We propose a novel Bayesian approach to solve stochastic optimization problems that involve finding extrema of noisy, nonlinear functions. Previous work has focused on representing…
Deep Reconstruction-Classification Networks for Unsupervised Domain Adaptation
Muhammad Ghifary, W. Bastiaan Kleijn, Mengjie Zhang +2
In this paper, we propose a novel unsupervised domain adaptation algorithm based on deep learning for visual object recognition. Specifically, we design a new model called Deep Rec…
Differentiable Game Mechanics
Alistair Letcher, David Balduzzi, Sebastien Racaniere +4
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…
Deep Online Convex Optimization by Putting Forecaster to Sleep
David Balduzzi
Methods from convex optimization such as accelerated gradient descent are widely used as building blocks for deep learning algorithms. However, the reasons for their empirical succ…
Falsification and future performance
David Balduzzi
We information-theoretically reformulate two measures of capacity from statistical learning theory: empirical VC-entropy and empirical Rademacher complexity. We show these capacity…
The Mechanics of n-Player Differentiable Games
David Balduzzi, Sebastien Racaniere, James Martens +3
The cornerstone underpinning deep learning is the guarantee that gradient descent on an objective converges to local minima. Unfortunately, this guarantee fails in settings, such a…
Strongly-Typed Recurrent Neural Networks
David Balduzzi, Muhammad Ghifary
Recurrent neural networks are increasing popular models for sequential learning. Unfortunately, although the most effective RNN architectures are perhaps excessively complicated, e…
Quantifying causal influences
Dominik Janzing, David Balduzzi, Moritz Grosse-Wentrup +1
Many methods for causal inference generate directed acyclic graphs (DAGs) that formalize causal relations between variables. Given the joint distribution on all these variables…
Information, learning and falsification
David Balduzzi
There are (at least) three approaches to quantifying information. The first, algorithmic information or Kolmogorov complexity, takes events as strings and, given a universal Turing…
Donagi-Markman cubic for Hitchin systems
David Balduzzi
The Donagi-Markman cubic is the differential of the period map for algebraic completely integrable systems. Here we prove a formula for the cubic in the case of Hitchin's system fo…
Detecting emergent processes in cellular automata with excess information
David Balduzzi
Many natural processes occur over characteristic spatial and temporal scales. This paper presents tools for (i) flexibly and scalably coarse-graining cellular automata and (ii) ide…
Poisson geometry of parabolic bundles on Elliptic curves
David Balduzzi
The moduli space of -bundles on an elliptic curve with additional flag structure admits a Poisson structure. The bivector can be defined using double loop group, loop group and…
Compliance-Aware Bandits
Nicolás Della Penna, Mark D. Reid, David Balduzzi
Motivated by clinical trials, we study bandits with observable non-compliance. At each step, the learner chooses an arm, after, instead of observing only the reward, it also observ…
Real World Games Look Like Spinning Tops
Wojciech Marian Czarnecki, Gauthier Gidel, Brendan Tracey +4
This paper investigates the geometrical properties of real world games (e.g. Tic-Tac-Toe, Go, StarCraft II). We hypothesise that their geometrical structure resemble a spinning top…
Scatter Component Analysis: A Unified Framework for Domain Adaptation and Domain Generalization
Muhammad Ghifary, David Balduzzi, W. Bastiaan Kleijn +1
This paper addresses classification tasks on a particular target domain in which labeled training data are only available from source domains different from (but related to) the ta…
Metabolic cost as an organizing principle for cooperative learning
David Balduzzi, Pedro A Ortega, Michel Besserve
This paper investigates how neurons can use metabolic cost to facilitate learning at a population level. Although decision-making by individual neurons has been extensively studied…
Uncovering the Temporal Dynamics of Diffusion Networks
Manuel Gomez Rodriguez, David Balduzzi, Bernhard Schölkopf
Time plays an essential role in the diffusion of information, influence and disease over networks. In many cases we only observe when a node copies information, makes a decision or…
Learning to Resolve Alliance Dilemmas in Many-Player Zero-Sum Games
Edward Hughes, Thomas W. Anthony, Tom Eccles +3
Zero-sum games have long guided artificial intelligence research, since they possess both a rich strategy space of best-responses and a clear evaluation metric. What's more, compet…
A Limited-Capacity Minimax Theorem for Non-Convex Games or: How I Learned to Stop Worrying about Mixed-Nash and Love Neural Nets
Gauthier Gidel, David Balduzzi, Wojciech Marian Czarnecki +2
Adversarial training, a special case of multi-objective optimization, is an increasingly prevalent machine learning technique: some of its most notable applications include GAN-bas…
D3C: Reducing the Price of Anarchy in Multi-Agent Learning
Ian Gemp, Kevin R. McKee, Richard Everett +4
In multiagent systems, the complex interaction of fixed incentives can lead agents to outcomes that are poor (inefficient) not only for the group, but also for each individual. Pri…
LOGAN: Latent Optimisation for Generative Adversarial Networks
Yan Wu, Jeff Donahue, David Balduzzi +2
Training generative adversarial networks requires balancing of delicate adversarial dynamics. Even with careful tuning, training may diverge or end up in a bad equilibrium with dro…
The Shattered Gradients Problem: If resnets are the answer, then what is the question?
David Balduzzi, Marcus Frean, Lennox Leary +3
A long-standing obstacle to progress in deep learning is the problem of vanishing and exploding gradients. Although, the problem has largely been overcome via carefully constructed…
Compatible Value Gradients for Reinforcement Learning of Continuous Deep Policies
David Balduzzi, Muhammad Ghifary
This paper proposes GProp, a deep reinforcement learning algorithm for continuous policies with compatible function approximation. The algorithm is based on two innovations. Firstl…
Regulating the information in spikes: a useful bias
David Balduzzi
The bias/variance tradeoff is fundamental to learning: increasing a model's complexity can improve its fit on training data, but potentially worsens performance on future samples.…
Re-evaluating Evaluation
David Balduzzi, Karl Tuyls, Julien Perolat +1
Progress in machine learning is measured by careful evaluation on problems of outstanding common interest. However, the proliferation of benchmark suites and environments, adversar…