Publications

Accelerating Smooth Games by Manipulating Spectral Shapes
Waïss Azizian
Damien Scieur
Ioannis Mitliagkas
Simon Lacoste-Julien
Gauthier Gidel
We use matrix iteration theory to characterize acceleration in smooth games. We define the spectral shape of a family of games as the set co… (see more)ntaining all eigenvalues of the Jacobians of standard gradient dynamics in the family. Shapes restricted to the real line represent well-understood classes of problems, like minimization. Shapes spanning the complex plane capture the added numerical challenges in solving smooth games. In this framework, we describe gradient-based methods, such as extragradient, as transformations on the spectral shape. Using this perspective, we propose an optimal algorithm for bilinear games. For smooth and strongly monotone operators, we identify a continuum between convex minimization, where acceleration is possible using Polyak's momentum, and the worst case where gradient descent is optimal. Finally, going beyond first-order methods, we propose an accelerated version of consensus optimization.
2020-06-02
Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics (published)
doi.org
proceedings.mlr.press
Coping With Simulators That Don't Always Return
Andrew Warrington
Saeid Naderiparizi
Frank N. Wood
2020-06-02
Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics (published)
proceedings.mlr.press
proceedings.mlr.press
Deep Active Learning: Unified and Principled Method for Query and Training
Changjian Shui
Fan Zhou
Christian Gagné
Boyu Wang
2020-06-02
Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics (published)
proceedings.mlr.press
proceedings.mlr.press
A Distributional Analysis of Sampling-Based Reinforcement Learning Algorithms
Philip Amortila
Doina Precup
Prakash Panangaden
Bellemare Marc-Emmanuel
We present a distributional approach to theoretical analyses of reinforcement learning algorithms for constant step-sizes. We demonstrate it… (see more)s effectiveness by presenting simple and unified proofs of convergence for a variety of commonly-used methods. We show that value-based methods such as TD(
2020-06-02
Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics (published)
doi.org
proceedings.mlr.press
Efficient Planning under Partial Observability with Unnormalized Q Functions and Spectral Learning
Tianyu Li
Bogdan Mazoure
Doina Precup
Guillaume Rabusseau
2020-06-02
Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics (published)
doi.org
proceedings.mlr.press
Expressiveness and Learning of Hidden Quantum Markov Models
Sandesh M. Adhikary
Siddarth Srinivasan
Geoff Gordon
Byron Boots
Extending classical probabilistic reasoning using the quantum mechanical view of probability has been of recent interest, particularly in th… (see more)e development of hidden quantum Markov models (HQMMs) to model stochastic processes. However, there has been little progress in characterizing the expressiveness of such models and learning them from data. We tackle these problems by showing that HQMMs are a special subclass of the general class of observable operator models (OOMs) that do not suffer from the \emph{negative probability problem} by design. We also provide a feasible retraction-based learning algorithm for HQMMs using constrained gradient descent on the Stiefel manifold of model parameters. We demonstrate that this approach is faster and scales to larger models than previous learning algorithms.
2020-06-02
Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics (published)
proceedings.mlr.press
proceedings.mlr.press
Fast and Furious Convergence: Stochastic Second Order Methods under Interpolation
Si Yi Meng
Sharan Vaswani
Issam Hadj Laradji
Mark Schmidt
Simon Lacoste-Julien
We consider stochastic second-order methods for minimizing smooth and strongly-convex functions under an interpolation condition satisfied b… (see more)y over-parameterized models. Under this condition, we show that the regularized subsampled Newton method (R-SSN) achieves global linear convergence with an adaptive step-size and a constant batch-size. By growing the batch size for both the subsampled gradient and Hessian, we show that R-SSN can converge at a quadratic rate in a local neighbourhood of the solution. We also show that R-SSN attains local linear convergence for the family of self-concordant functions. Furthermore, we analyze stochastic BFGS algorithms in the interpolation setting and prove their global linear convergence. We empirically evaluate stochastic L-BFGS and a "Hessian-free" implementation of R-SSN for binary classification on synthetic, linearly-separable datasets and real datasets under a kernel mapping. Our experimental results demonstrate the fast convergence of these methods, both in terms of the number of iterations and wall-clock time.
2020-06-02
Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics (published)
proceedings.mlr.press
proceedings.mlr.press
GAIT: A Geometric Approach to Information Theory
Jose Gallego-Posada
Ankit Vani
Max Schwarzer
Simon Lacoste-Julien
We advocate the use of a notion of entropy that reflects the relative abundances of the symbols in an alphabet, as well as the similarities … (see more)between them. This concept was originally introduced in theoretical ecology to study the diversity of ecosystems. Based on this notion of entropy, we introduce geometry-aware counterparts for several concepts and theorems in information theory. Notably, our proposed divergence exhibits performance on par with state-of-the-art methods based on the Wasserstein distance, but enjoys a closed-form expression that can be computed efficiently. We demonstrate the versatility of our method via experiments on a broad range of domains: training generative models, computing image barycenters, approximating empirical measures and counting modes.
2020-06-02
Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics (published)
proceedings.mlr.press
proceedings.mlr.press
Old Dog Learns New Tricks: Randomized UCB for Bandit Problems
Sharan Vaswani
Abbas Mehrabian
Audrey Durand
Branislav Kveton
2020-06-02
Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics (published)
proceedings.mlr.press
proceedings.mlr.press
A principled approach for generating adversarial images under non-smooth dissimilarity metrics
Aram-Alexandre Pooladian
Chris Finlay
Tim Hoheisel
Adam Oberman
2020-06-02
Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics (published)
proceedings.mlr.press
proceedings.mlr.press
A Reduction from Reinforcement Learning to No-Regret Online Learning
Ching-An Cheng
Remi Tachet des Combes
Byron Boots
Geoff Gordon
We present a reduction from reinforcement learning (RL) to no-regret online learning based on the saddle-point formulation of RL, by which "… (see more)any" online algorithm with sublinear regret can generate policies with provable performance guarantees. This new perspective decouples the RL problem into two parts: regret minimization and function approximation. The first part admits a standard online-learning analysis, and the second part can be quantified independently of the learning algorithm. Therefore, the proposed reduction can be used as a tool to systematically design new RL algorithms. We demonstrate this idea by devising a simple RL algorithm based on mirror descent and the generative-model oracle. For any
2020-06-02
Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics (published)
proceedings.mlr.press
proceedings.mlr.press
Stochastic Neural Network with Kronecker Flow
Chin-wei Huang
Ahmed Touati
Pascal Vincent
Gintare Karolina Dziugaite
Alexandre Lacoste
Aaron Courville
Recent advances in variational inference enable the modelling of highly structured joint distributions, but are limited in their capacity to… (see more) scale to the high-dimensional setting of stochastic neural networks. This limitation motivates a need for scalable parameterizations of the noise generation process, in a manner that adequately captures the dependencies among the various parameters. In this work, we address this need and present the Kronecker Flow, a generalization of the Kronecker product to invertible mappings designed for stochastic neural networks. We apply our method to variational Bayesian neural networks on predictive tasks, PAC-Bayes generalization bound estimation, and approximate Thompson sampling in contextual bandits. In all setups, our methods prove to be competitive with existing methods and better than the baselines.
2020-06-02
Artificial Intelligence and Statistics (published)
doi.org
proceedings.mlr.press