Publications

Provable Guarantees for General Two-sided Sequential Matching Markets
Alfredo Torrico
Margarida Carvalho
Andrea Lodi
Two-sided markets have become increasingly more important during the last years, mostly because of their numerous applications in housing, l… (see more)abor and dating. Consumer-supplier matching platforms pose several technical challenges, specially due to the trade-off between recommending suitable suppliers to consumers and avoiding collisions among consumers' preferences. In this work, we study a general version of the two-sided sequential matching model introduced by Ashlagi et al. (2019). The setting is the following: we (the platform) offer a menu of suppliers to each consumer. Then, every consumer selects, simultaneously and independently, to match with a supplier or to remain unmatched. Suppliers observe the subset of consumers that selected them, and choose either to match a consumer or leave the system. Finally, a match takes place if both the consumer and the supplier sequentially select each other. Each agent's behavior is probabilistic and determined by a regular discrete choice model. Our objective is to choose an assortment family that maximizes the expected cardinality of the matching. Given the computational complexity of the problem, we show several provable guarantees for the general model, which in particular, significantly improve the approximation factors previously obtained.
2020-06-07
arXiv.org (preprint)
dblp.uni-trier.de
Dark control: The default mode network as a reinforcement learning agent
Elvis Dohmatob
Guillaume Dumas
Danilo Bzdok
The default mode network (DMN) is believed to subserve the baseline mental activity in humans. Its higher energy consumption compared to oth… (see more)er brain networks and its intimate coupling with conscious awareness are both pointing to an unknown overarching function. Many research streams speak in favor of an evolutionarily adaptive role in envisioning experience to anticipate the future. In the present work, we propose a process model that tries to explain how the DMN may implement continuous evaluation and prediction of the environment to guide behavior. The main purpose of DMN activity, we argue, may be described by Markov decision processes that optimize action policies via value estimates through vicarious trial and error. Our formal perspective on DMN function naturally accommodates as special cases previous interpretations based on (a) predictive coding, (b) semantic associations, and (c) a sentinel role. Moreover, this process model for the neural optimization of complex behavior in the DMN offers parsimonious explanations for recent experimental findings in animals and humans.
2020-06-04
Human Brain Mapping (unknown)
doi.org
Prioritization of patients access to outpatient augmentative and alternative communication services in Quebec: a decision tool
S. A. Rahimi
Julien Dery
Marie-Eve Lamontagne
Afshin Jamshidi
Emilie Lacroix
Angel Ruiz
Daoud Ait-Kadi
François Routhier
2020-06-04
Disability and Rehabilitation: Assistive Technology (published)
doi.org
Precision public health: Dream or reality?
Maureen Dobbins
David L Buckeridge
2020-06-03
Canada communicable disease report = Releve des maladies transmissibles au Canada (published)
doi.org
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
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
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
Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics (published)
doi.org
proceedings.mlr.press
The Neurobiology of Social Distance
Danilo Bzdok
Robin I. M. Dunbar
2020-06-02
Trends in Cognitive Sciences (published)
doi.org
A Tight and Unified Analysis of Gradient-Based Methods for a Whole Spectrum of Differentiable Games
Waïss Azizian
Ioannis Mitliagkas
Simon Lacoste-Julien
Gauthier Gidel
We consider differentiable games where the goal is to find a Nash equilibrium. The machine learning community has recently started using var… (see more)iants of the gradient method (GD). Prime examples are extragradient (EG), the optimistic gradient method (OG) and consensus optimization (CO), which enjoy linear convergence in cases like bilinear games, where the standard GD fails. The full benefits of theses relatively new methods are not known as there is no unified analysis for both strongly monotone and bilinear games. We provide new analyses of the EG's local and global convergence properties and use is to get a tighter global convergence rate for OG and CO. Our analysis covers the whole range of settings between bilinear and strongly monotone games. It reveals that these methods converge via different mechanisms at these extremes; in between, it exploits the most favorable mechanism for the given problem. We then prove that EG achieves the optimal rate for a wide class of algorithms with any number of extrapolations. Our tight analysis of EG's convergence rate in games shows that, unlike in convex minimization, EG may be much faster than GD.
2020-06-02
International Conference on Artificial Intelligence and Statistics (unknown)
doi.org
proceedings.mlr.press