pwc-archive/papers-with-abstracts huggingface dataset:
Train Big, Then Compress: Rethinking Model Size for Efficient Training and Inference of Transformers
Authors: Zhuohan Li, Eric Wallace, Sheng Shen, Kevin Lin, Kurt Keutzer, Dan Klein, Joseph Gonzalez
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: Machine Translation, Quantization, Translation

Since hardware resources are limited, the objective of training deep learning models is typically to maximize accuracy subject to the time and memory constraints of training and inference. We study the impact of model size in this setting, focusing on Transformer models for NLP tasks that are limited by compute: self-supervised pretraining and high-resource machine translation. We first show that even though smaller Transformer models execute faster per iteration, wider and deeper models converge in significantly fewer steps. Moreover, this acceleration in convergence typically outpaces the additional computational overhead of using larger models. Therefore, the most compute-efficient training strategy is to counterintuitively train extremely large models but stop after a small number of iterations. This leads to an apparent trade-off between the training efficiency of large Transformer models and the inference efficiency of small Transformer models. However, we show that large models are more robust to compression techniques such as quantization and pruning than small models. Consequently, one can get the best of both worlds: heavily compressed, large models achieve higher accuracy than lightly compressed, small models.
XTREME: A Massively Multilingual Multi-task Benchmark for Evaluating Cross-lingual Generalisation
Authors: Junjie Hu, Sebastian Ruder, Aditya Siddhant, Graham Neubig, Orhan Firat, Melvin Johnson
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: Cross-Lingual Transfer, Retrieval, Sentence, Sentence Retrieval, Zero-Shot Cross-Lingual Transfer

Much recent progress in applications of machine learning models to NLP has been driven by benchmarks that evaluate models across a wide variety of tasks. However, these broad-coverage benchmarks have been mostly limited to English, and despite an increasing interest in multilingual models, a benchmark that enables the comprehensive evaluation of such methods on a diverse range of languages and tasks is still missing. To this end, we introduce the Cross-lingual TRansfer Evaluation of Multilingual Encoders (XTREME) benchmark, a multi-task benchmark for evaluating the cross-lingual generalization capabilities of multilingual representations across 40 languages and 9 tasks. We demonstrate that while models tested on English reach human performance on many tasks, there is still a sizable gap in the performance of cross-lingually transferred models, particularly on syntactic and sentence retrieval tasks. There is also a wide spread of results across languages. We will release the benchmark to encourage research on cross-lingual learning methods that transfer linguistic knowledge across a diverse and representative set of languages and tasks.
A Swiss Army Knife for Minimax Optimal Transport
Authors: Sofien Dhouib, Ievgen Redko, Tanguy Kerdoncuff, Rémi Emonet, Marc Sebban
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1

The Optimal transport (OT) problem and its associated Wasserstein distance have recently become a topic of great interest in the machine learning community. However, the underlying optimization problem is known to have two major restrictions: (i) it largely depends on the choice of the cost function and (ii) its sample complexity scales exponentially with the dimension. In this paper, we propose a general formulation of a minimax OT problem that can tackle these restrictions by jointly optimizing the cost matrix and the transport plan, allowing us to define a robust distance between distributions. We propose to use a cutting-set method to solve this general problem and show its links and advantages compared to other existing minimax OT approaches. Additionally, we use this method to define a notion of stability allowing us to select the most robust cost matrix. Finally, we provide an experimental study highlighting the efficiency of our approach.
Expectation Maximization with Bias-Corrected Calibration is Hard-To-Beat at Label Shift Adaptation
Authors: Amr Mohamed Alexandari, Anshul Kundaje, Avanti Shrikumar
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: Medical Diagnosis

Label shift refers to the phenomenon where the prior class probability p(y) changes between the training and test distributions, while the conditional probability p(x|y) stays fixed. Label shift arises in settings like medical diagnosis, where a classifier trained to predict disease given symptoms must be adapted to scenarios where the baseline prevalence of the disease is different. Given estimates of p(y|x) from a predictive model, Saerens et al. proposed an efficient EM algorithm to correct for label shift that does not require model retraining. A limiting assumption of this algorithm is that p(y|x) is calibrated, which is not true of modern neural networks. Recently, Black Box Shift Learning (BBSL) and Regularized Learning under Label Shifts (RLLS) have emerged as state-of-the-art techniques to cope with label shift when a classifier does not output calibrated probabilities. However, both BBSL and RLLS require model retraining with importance weights, which poses challenges in practice, and neither has been benchmarked against EM. We show that by combining EM with a type of calibration we call bias-corrected calibration, we outperform both BBSL and RLLS across diverse datasets and distribution shifts. We further show that the EM objective is concave and bounded, and introduce a theoretically principled strategy for estimating source-domain priors that improves robustness to poor calibration. This work demonstrates that EM with appropriate calibration is a formidable and efficient baseline that future work in label shift adaptation should be compared with.

Colab notebooks reproducing experiments are available at (anonymized link): https://github.com/blindauth/labelshiftexperiments
Kernel Methods for Cooperative Multi-Agent Learning with Delays
Authors: Abhimanyu Dubey, Alex `Sandy' Pentland
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: Clustering, Decision Making

Cooperative multi-agent decision making involves a group of agents collectively solving individual learning problems, while communicating over a (sparse) network with delays. In this paper, we consider the kernelised contextual bandit problem, where the reward obtained by an agent is an arbitrary linear function of the contexts' images in the related reproducing kernel Hilbert space (RKHS), and a group of agents must cooperate to collectively solve their unique decision problems. We propose Coop-KernelUCB that provides near-optimal bounds on the per-agent regret in this setting, and is both computationally and communicatively efficient. For special cases of the cooperative problem, we also provide variants of Coop-KernelUCB that provides optimal per-agent regret. In addition, our algorithm generalizes several existing results in the multi-agent bandit setting. Finally, on a series of both synthetic and real-world multi-agent network benchmarks, our algorithm significantly outperforms existing clustering or consensus-based algorithms, even in the linear setting.
Optimal Non-parametric Learning in Repeated Contextual Auctions with Strategic Buyer
Authors: Alexey Drutsa
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1

We study learning algorithms that optimize revenue in repeated contextual posted-price auctions where a seller interacts with a single strategic buyer that seeks to maximize his cumulative discounted surplus.
The buyer's valuation of a good is a fixed private function of a $d$-dimensional context (feature) vector that describes the good being sold.
In contrast to existing studies on repeated contextual auctions with strategic buyer, in our work, the seller is not assumed to know the parametric model that underlies this valuation function.
We introduce a novel non-parametric learning algorithm that is horizon-independent and has tight strategic regret upper bound of $\Theta(T^{d/(d+1)})$.
We also non-trivially generalize several value-localization techniques of non-contextual repeated auctions  to make them effective in  the considered contextual non-parametric learning of the buyer valuation function.
Optimization and Analysis of the pAp@k Metric for Recommender Systems
Authors: Gaurush Hiranandani, Warut Vijitbenjaronk, Sanmi Koyejo, Prateek Jain
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: Recommendation Systems

Modern recommendation and notification systems must be robust to data imbalance, limitations on the number of recommendations/notifications, and heterogeneous engagement profiles across users. The pAp@k metric, which combines the partial-AUC and the precision@k metrics, was recently proposed to evaluate such recommendation systems and has been used in real-world deployments. Conceptually, pAp@k measures the probability of correctly ranking a top-ranked positive instance over top-ranked negative instances. Due to the combinatorial aspect surfaced by top-ranked points, little is known about the characteristics and optimization methods of pAp@k. In this paper, we analyze the learning-theoretic properties of pAp@k and propose novel surrogates that are consistent under certain data regularity conditions. We then provide gradient descent based algorithms to optimize the surrogates directly. Our analysis and experimental evaluation suggest that pAp@k indeed exhibits a certain dual behavior with respect to partial-AUC and precision@k. Moreover, the proposed methods outperform all the baselines in various applications. Taken together, our results motivate the use of pAp@k for large-scale recommender systems.
Smaller, more accurate regression forests using tree alternating optimization
Authors: Arman Zharmagambetov, Miguel Carreira-Perpinan
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: Ensemble Learning, regression

Regression forests (ensembles of regression trees) have long been recognized as the leading off-the-shelf method for regression, where the task is to predict a continuous scalar or vector output. The main approaches are based on bagging, where individual trees are trained independently on bootstrap samples of the data; or on boosting, where individual trees are trained sequentially on the whole data but with adaptively weighted instances. However, both approaches rely on a greedy top-down procedure such as CART to learn an axis-aligned tree, where each decision node tests for a single feature. We instead use the recently proposed Tree Alternating Optimization (TAO) algorithm. This is able to learn an oblique tree, where each decision node tests for a linear combination of features, and which has much higher accuracy than axis-aligned trees. We show that using TAO with the bagging approach produces much better forests than random forests, Adaboost or gradient boosting in every dataset we have tried across a wide range of input and output dimensionality and sample size. The resulting forest has significantly lower test regression error while using shallower trees with fewer parameters and lower inference time overall. This result has an immense practical impact and advocates for the power of optimization in ensemble learning.
A distributional view on multi objective policy optimization
Authors: Abbas Abdolmaleki, Sandy Huang, Leonard Hasenclever, Michael Neunert, Martina Zambelli, Murilo Martins, Francis Song, Nicolas Heess, Raia Hadsell, Martin Riedmiller
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: Multi-Objective Reinforcement Learning, Reinforcement Learning (RL)

Many real-world problems require trading off multiple competing objectives. However, these objectives are often in different units with different scales, which can make it challenging for practitioners to express numerical preferences over objectives in their native units. In this paper we propose a novel algorithm for multi-objective reinforcement learning that enables setting desired preferences for objectives in a scale-invariant way. We propose to learn a target local policy for each objective, and we use supervised learning to fit a parametric policy to a combination of these distributions. We demonstrate the effectiveness of our approach on challenging high-dimensional real and simulated robotics tasks, and show that setting different preferences in our framework allows us to trace out the space of nondominated solutions.
Bayesian Sparsification of Deep C-valued Networks
Authors: Ivan Nazarov, Evgeny Burnaev
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: Music Transcription

With continual miniaturization ever more applications of deep learning can be found in embedded systems, where it is common to encounter data with natural representation in the complex domain. To this end we extend Sparse Variational Dropout to complex-valued neural networks and verify the proposed Bayesian technique by conducting a large numerical study of the performance-compression trade-off of C-valued networks on two tasks: image recognition on MNIST-like and CIFAR10 datasets and music transcription on MusicNet. We replicate the state-of-the-art result by Trabelsi et al. (2018) on MusicNet with a complex-valued network compressed by 50-100x at a small performance penalty.
Constructive universal distribution generation through deep ReLU networks
Authors: Dmytro Perekrestenko, Stephan Müller, Helmut Bölcskei
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1

We present an explicit deep network construction that transforms uniformly distributed one-dimensional noise into an arbitrarily close approximation of any two-dimensional target distribution of finite differential entropy and Lipschitz-continuous pdf. The key ingredient of our design is a generalization of the  "space-filling'' property of sawtooth functions introduced in (Bailey & Telgarsky, 2018). We elicit the importance of depth 
in our construction in driving the Wasserstein distance between the target distribution and its approximation realized by the proposed neural network to zero. Finally, we outline how our construction can be extended to output distributions of arbitrary dimension.
IPBoost – Non-Convex Boosting via Integer Programming
Authors: Sebastian Pokutta, Marc Pfetsch
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: BIG-bench Machine Learning

Recently non-convex optimization approaches for solving machine learning problems have gained significant attention. In this paper we explore non-convex boosting in classification by means of integer programming and demonstrate real-world practicability of the approach while circumvent- ing shortcomings of convex boosting approaches. We report results that are comparable to or better than the current state-of-the-art.
Learning disconnected manifolds: a no GAN's land
Authors: Ugo Tanielian, Thibaut Issenhuth, Elvis Dohmatob, Jeremie Mary
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1

Typical architectures of Generative Adversarial Networks make use of a unimodal latent/input distribution transformed by a continuous generator. Consequently, the modeled distribution always has connected support which is cumbersome when learning a disconnected set of manifolds. We formalize this problem by establishing a "no free lunch" theorem for the disconnected manifold learning stating an upper-bound on the precision of the targeted distribution. This is done by building on the necessary existence of a low-quality region where the generator continuously samples data between two disconnected modes.  Finally, we derive a rejection sampling method based on the norm of generator’s Jacobian and show its efficiency on several generators including BigGAN.
Restarted Bayesian Online Change-point Detector achieves Optimal Detection Delay
Authors: REDA ALAMI, Odalric-Ambrym Maillard, Raphaël Féraud
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: Change Point Detection, Learning Theory

In this paper, we consider the problem of sequential change-point detection where both the change-points and the distributions before and after the change are assumed to be unknown. For this key problem in statistical and sequential learning theory,  we derive a variant of the Bayesian Online Change Point Detector proposed by \cite{adams2007bayesian} which is easier to analyze than the original version while keeping its powerful message-passing algorithm. 
	We provide a non-asymptotic analysis of the false-alarm rate and the detection delay that matches the existing lower-bound. We further provide the first explicit high-probability control of the detection delay for such approach. Experiments on synthetic and real-world data show that this proposal compares favorably with the state-of-art change-point detection strategy, namely the Improved Generalized Likelihood Ratio (Improved GLR) while outperforming the original Bayesian Online Change Point Detection strategy.
Adaptive Sampling for Estimating Probability Distributions
Authors: Shubhanshu Shekhar, Tara Javidi, Mohammad Ghavamzadeh
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1

We consider the problem of allocating a fixed budget of samples to a finite set of discrete distributions to learn them uniformly well (minimizing the maximum error) in terms of four common distance measures: $\ell_2^2$, $\ell_1$, $f$-divergence, and separation distance. To present a unified treatment of these distances, we first propose a general \emph{optimistic tracking algorithm} and analyze its sample allocation performance w.r.t.~an oracle. We then instantiate this algorithm for the four distance measures and derive bounds on their regret. We also show that the allocation performance of the proposed algorithm cannot, in general, be improved, by deriving lower-bounds on the expected deviation from the oracle allocation for any adaptive scheme. We verify our theoretical findings through some experiments. Finally, we show that the techniques developed in the paper can be easily extended to learn some classes of continuous distributions as well as to the related setting of minimizing the average error (in terms of the four distances) in learning a set of distributions.
Equivariant Flows: exact likelihood generative learning for symmetric densities.
Authors: Jonas Köhler, Leon Klein, Frank Noe
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1

Normalizing flows  are  exact-likelihood  generative  neural  networks  which  approximately transform  samples from a simple prior distribution to samples of the probability distribution of interest.  
Recent work showed that such generative models can be utilized in statistical mechanics to sample equilibrium states of many-body systems in physics and chemistry. 
To scale and generalize these results, it is essential that the natural symmetries in the probability density – in physics defined by the invariances of the target potential – are built into the flow.  
We provide a theoretical sufficient criterium showing that the distribution generated by \textit{equivariant} normalizing flows is invariant with respect to these symmetries by design. 
Furthermore, we propose building blocks for flows preserving symmetries which are usually found in physical/chemical many-body particle systems.
Using benchmark systems motivated from molecular physics, we demonstrate that those symmetry preserving flows can provide better generalization capabilities and sampling efficiency.
Non-Stationary Bandits with Intermediate Observations
Authors: Claire Vernade, András György, Timothy Mann
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: Recommendation Systems

Online recommender systems often face long delays in receiving feedback, especially when optimizing for some long-term metrics. While mitigating the effects of delays in learning is well-understood in stationary environments, the problem becomes much more challenging when the environment changes. In fact, if the timescale of the change is comparable to the delay, it is impossible to learn about the environment, since the available observations are already obsolete.
However, the arising issues can be addressed if intermediate signals are available without delay, such that given those signals, the long-term behavior of the system is stationary. To model this situation, we 
introduce the problem of stochastic, non-stationary, delayed bandits with intermediate observations. We develop a computationally efficient algorithm based on $\UCRL$, and prove sublinear regret guarantees for its performance. Experimental results demonstrate that our method is able to learn in non-stationary delayed environments where existing methods fail.
Online Convex Optimization in the Random Order Model
Authors: Dan Garber, Gal Korcia, Kfir Levy
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: model, regression

Online Convex Optimization (OCO) is a powerful framework for sequential prediction, portraying the natural uncertainty inherent in data-streams as though the data were generated by an almost limitless adversary. However, this view, which is often too pessimistic for real-world data, comes with a price. The complexity of solving many important online tasks in this adversarial framework becomes much worse than that of their offline counterparts.

In this work we consider a natural random-order version of the OCO model, in which the adversary can choose the set of loss functions, but does not get to choose the order in which they are supplied to the learner; Instead, they are observed in uniformly random order. While such a model is clearly not suitable for temporal data, which inherently depends on time, it is very much plausible in distributed settings, in which data is generated by multiple independent sources, or streamed without particular order.

Focusing on two important families of online tasks, one which generalizes online linear and logistic regression, and the other being online PCA, we show that under standard well-conditioned-data assumptions (that are often being made in the corresponding offline settings), standard online gradient descent (OGD) methods become much more efficient in the random-order model. In particular, for the first group of tasks which includes linear regression, we show that OGD guarantees polylogarithmic regret (while the only method to achieve comparable regret in the fully-adversarial setting is the Online-Newton Step method which requires quadratic memory and at least quadratic runtime). This result holds even without assuming the convexity of individual loss functions. In the case of online k-PCA, we show that OGD minimizes regret using only a rank-k SVD on each iteration and requires only linear memory (instead of nearly quadratic memory and/or potentially high-rank SVDs required by algorithms for the fully-adversarial setting).
Quantile Causal Discovery
Authors: Natasa Tagasovska, Thibault Vatter, Valérie Chavez-Demoulin
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: Causal Discovery, Causal Inference, quantile regression, regression

Causal inference using observational data is challenging, especially in the bivariate case.
Through the minimum description length principle, we link the postulate of independence between the generating mechanisms of the cause and of the effect given the cause to quantile regression.
Based on this theory, we develop Quantile Causal Discovery (QCD), a new method to uncover causal relationships.
Because it uses multiple quantile levels instead of the conditional mean only, QCD is adaptive not only to additive, but also to multiplicative or even location-scale generating mechanisms.
To illustrate the empirical effectiveness of our approach, we perform an extensive empirical comparison on both synthetic and real datasets.
This study shows that QCD is robust across different implementations of the method (i.e., the quantile regression algorithm), computationally efficient, and compares favorably to state-of-the-art methods.