pwc-archive/papers-with-abstracts huggingface dataset:
On Semi-parametric Inference for BART
Authors: Veronika Rockova
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: BIG-bench Machine Learning, regression, Uncertainty Quantification, valid

There has been a growing realization of the potential of Bayesian machine learning as a platform that can provide both flexible modeling, accurate predictions as well as coherent uncertainty statements. In particular, Bayesian Additive Regression Trees (BART) have emerged as one of today’s most effective general approaches to predictive modeling under minimal assumptions. Statistical theoretical developments for machine learning have been mostly concerned with approximability or rates of estimation when recovering infinite dimensional objects (curves or densities). Despite the impressive array of available theoretical results, the literature has been largely silent about uncertainty quantification. In this work, we continue the theoretical investigation of BART initiated recently by Rockova and van der Pas (2017). We focus on statistical inference questions. In particular, we study the Bernstein-von Mises (BvM) phenomenon (i.e. asymptotic normality) for smooth linear functionals of the regression surface within the framework of non-parametric regression with fixed covariates. Our semi-parametric BvM results show that, beyond rate-optimal estimation, BART can be also used for valid statistical inference.
Optimizing Multiagent Cooperation via Policy Evolution and Shared Experiences
Authors: Somdeb Majumdar, Shauharda Khadka, Santiago Miret, Stephen Mcaleer, Kagan Tumer
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

Many cooperative multiagent reinforcement learning environments provide agents with a sparse team-based reward, as well as a dense agent-specific reward that incentivizes learning basic skills. Training policies solely on the team-based reward is often difficult due to its sparsity. Also, relying solely on the agent-specific reward is sub-optimal because it usually does not capture the team coordination objective. A common approach is to use reward shaping to construct a proxy reward by combining the individual rewards. However, this requires manual tuning for each environment. We introduce Multiagent Evolutionary Reinforcement Learning (MERL), a split-level training platform that handles the two objectives separately through two optimization processes. An evolutionary algorithm maximizes the sparse team-based objective through neuroevolution on a population of teams. Concurrently, a gradient-based optimizer trains policies to only maximize the dense agent-specific rewards. The gradient-based policies are periodically added to the evolutionary population as a way of information transfer between the two optimization processes. This enables the evolutionary algorithm to use skills learned via the agent-specific rewards toward optimizing the global objective. Results demonstrate that MERL significantly outperforms state-of-the-art methods, such as MADDPG, on a number of difficult coordination benchmarks.
Overparameterization hurts worst-group accuracy with spurious correlations
Authors: Shiori Sagawa, aditi raghunathan, Pang Wei Koh, Percy Liang
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1

Increasing model capacity well beyond the point of zero training error has been observed to improve average test accuracy. However, such overparameterized models have been recently shown to obtain low worst-group accuracy --- i.e., low accuracy on atypical groups of test examples --- when there are spurious correlations that hold for the majority of training examples. We show on two image datasets that in contrast to average accuracy, overparameterization hurts worst-group accuracy in the presence of spurious correlations. We replicate this surprising phenomenon in a synthetic example and identify properties of the data distribution that induce the detrimental effect of overparameterization on worst-group accuracy. Our analysis leads us to show that a counter-intuitive approach of subsampling the majority group yields high worst-group accuracy in the overparameterized regime, whereas upweighting the minority does not. Our results suggest that when it comes to achieving high worst-group accuracy, there is a tension between using overparameterized models vs. using all of the training data.
Rank Aggregation from Pairwise Comparisons in the Presence of Adversarial Corruptions
Authors: Prathamesh Patil, Arpit Agarwal, Shivani Agarwal, Sanjeev Khanna
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: Information Retrieval, Recommendation Systems, Retrieval

Rank aggregation from pairwise preferences has widespread applications in recommendation systems and information retrieval. Given the enormous economic and societal impact of these applications, and the consequent incentives for malicious players to manipulate ranking outcomes in their favor, an important challenge is to make rank aggregation algorithms robust to adversarial manipulations in data. In this paper, we initiate the study of robustness in rank aggregation under the popular Bradley-Terry-Luce (BTL) model for pairwise comparisons. We consider a setting where pairwise comparisons are initially generated according to a BTL model, but a fraction of these comparisons are corrupted by an adversary prior to being reported to us. We consider a strong contamination model, where an adversary having complete knowledge of the initial truthful data and the underlying true BTL parameters, can subsequently corrupt the truthful data by inserting, deleting, or changing data points. The goal is to estimate the true score/weight of each item under the BTL model, even in the presence of these corruptions. We characterize the extent of adversarial corruption under which the true BTL parameters are uniquely identifiable. We also provide a novel pruning algorithm that provably cleans the data of adversarial corruption under reasonable conditions on data generation and corruption. We corroborate our theory with experiments on synthetic data showing that previous algorithms are vulnerable to even small amounts of corruption, whereas our algorithm can clean a reasonably high amount of corruption.
Retrieval Augmented Language Model Pre-Training
Authors: Kelvin Guu, Kenton Lee, Zora Tung, Panupong Pasupat, Ming-Wei Chang
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: Language Modeling, Language Modelling, Masked Language Modeling, model, Open-Domain Question Answering, Question Answering, Retrieval, World Knowledge

Language model pre-training has been shown to capture a surprising amount of world knowledge, crucial for NLP tasks such as question answering. However, this knowledge is stored implicitly in the parameters of a neural network, requiring ever-larger networks to cover more facts. To capture knowledge in a more modular and interpretable way, we augment language model pre-training with a latent knowledge retriever, which allows the model to retrieve and attend over documents from a large corpus such as Wikipedia, used during pre-training, fine-tuning and inference. For the first time, we show how to pre-train such a knowledge retriever in an unsupervised manner, using masked language modeling as the learning signal and backpropagating through a retrieval step that considers millions of documents. We demonstrate the effectiveness of Retrieval-Augmented Language Model pre-training (REALM) by fine-tuning on the challenging task of Open-domain Question Answering (Open-QA). We compare against state-of-the-art models for both explicit and implicit knowledge storage on three popular Open-QA benchmarks, and find that we outperform all previous methods by a significant margin (4-16% absolute accuracy), while also providing qualitative benefits such as interpretability and modularity.
Task-Oriented Active Perception and Planning in Environments with Partially Known Semantics
Authors: Mahsa Ghasemi, Erdem Bulgur, Ufuk Topcu
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1

We consider an agent that is assigned with a temporal logic task in an environment whose semantic representation is only partially known. We represent the semantics of the environment with a set of state properties, called \textit{atomic propositions}. The agent holds a probabilistic belief over the atomic propositions and updates it as new sensory measurements arrive. The goal is to design a policy for the agent that realizes the task with high probability. 
We develop a planning strategy that takes the semantic uncertainties into account and by doing so provides probabilistic guarantees on the task success. Furthermore, as new data arrive, the belief over the atomic propositions evolves and, subsequently, the planning strategy adapts accordingly. We evaluate the proposed method on various finite-horizon tasks in planar navigation settings. The empirical results show that the proposed method provides reliable task performance that also improves as the knowledge about the environment enhances.
Two Simple Ways to Learn Individual Fairness Metric from Data
Authors: Debarghya Mukherjee, Mikhail Yurochkin, Moulinath Banerjee, Yuekai Sun
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: BIG-bench Machine Learning, Fairness, Vocal Bursts Valence Prediction

Individual fairness was proposed to address some of the shortcomings of group fairness. Despite its benefits, it requires a task specific fairness metric that encodes our intuition of what is fair and what is unfair for the ML task at hand. Ambiguity in this metric is the main barrier to wider adoption of individual fairness. In this paper, we present two simple algorithms that learn effective fair metrics from a variety of datasets. We verify empirically that fair training with these metrics leads to improved fairness on three machine learning tasks susceptible to gender and racial biases. We also provide theoretical guarantees on the statistical performance of both approaches.
Variational Imitation Learning with Diverse-quality Demonstrations
Authors: Voot Tangkaratt, Bo Han, Mohammad Emtiyaz Khan, Masashi Sugiyama
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: continuous-control, Continuous Control, Imitation Learning, reinforcement-learning, Reinforcement Learning (RL)

Learning from demonstrations can be challenging when the quality of demonstrations is diverse, and even more so when the quality is unknown and there is no additional information to estimate the quality. We propose a new method for imitation learning in such scenarios. We show that simple quality-estimation approaches might fail due to compounding error, and fix this issue by jointly estimating both the quality and reward using a variational approach. Our method is easy to implement within reinforcement-learning frameworks and also achieves state-of-the-art performance on continuous-control benchmarks.Our work enables scalable and data-efficient imitation learning under more realistic settings than before.
A simpler approach to accelerated optimization: iterative averaging meets optimism
Authors: Pooria Joulani, Anant Raj, András György, Csaba Szepesvari
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1

Recently there have been several attempts to improve the rates of convergence achievable for smooth objectives. In particular, several recent papers have attempted to extend Nesterov's accelerated algorithm to stochastic and variance-reduced optimization. In this paper, we show that there is a simpler approach to obtaining accelerated rates: applying generic, well-known optimistic online learning algorithms and using the online average of their predictions to query the (deterministic or stochastic) first-order optimization oracle at each time step. In particular, we tighten the recent results of Cutkosky (2019) to demonstrate theoretically that online averaging results in a reduced optimization gap, independently of the algorithm involved. Then, we show that a simple tuning of existing generic optimistic online learning algorithms (e.g., Joulani et al [2017]), when combined with the reduced error quantified above, naturally results in optimal accelerated rates. \todoc{what would you consider unnatural? get rid of this word?}
Importantly, the smooth objective may or may not be strongly-convex, and the rates are nevertheless optimal for both stochastic and deterministic first-order oracles. 
We further show that the same ideas transfer to variance-reduced optimization. In each case, the proofs are much simpler than the previous work, such as the new derivations of accelerated algorithms based on a primal-dual view (Wang and Abernethy, 2018) or the ideas based on linear coupling (Allen-Zhu and Orecchia, 2017). Importantly, we also provide algorithms that maintain the ``universality'' property, meaning that the same algorithm achieves the optimal rate for smooth and non-smooth objectives without further prior knowledge, generalizing the results of Kavis et al (2019) and solving a number of their open problems.
Error Estimation for Sketched SVD
Authors: Miles Lopes, N. Benjamin Erichson, Michael Mahoney
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1

In order to compute fast approximations to the singular value decompositions (SVD) of very large matrices, randomized sketching algorithms have become a leading approach. However, a key practical difficulty of sketching an SVD is that the user does not know how far the sketched singular vectors/values are from the exact ones. Indeed, the user may be forced to rely on analytical worst-case error bounds, which do not account for the unique structure of a given problem. As a result, the lack of tools for error estimation often leads to much more computation than is really necessary. To overcome these challenges, this paper develops a fully data-driven bootstrap method that numerically estimates the actual error of sketched singular vectors/values. In particular, this approach allows the user to inspect the quality of a rough initial SVD, and then adaptively predict how much extra work is needed to reach a given error tolerance. Meanwhile, from a computational standpoint, the proposed method incurs only minor cost, because it operates on the (small) output of a sketching algorithm, and it requires no passes over the (large) matrix being factored. Lastly, the proposed method is supported by theoretical guarantees and a very encouraging set of experimental results.
Explainable k-Means and k-Medians Clustering
Authors: Michal Moshkovitz, Sanjoy Dasgupta, Cyrus Rashtchian, Nave Frost
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: Clustering

Clustering is a popular unsupervised learning method for geometric data. Unfortunately, many clustering algorithms use global properties of the data, and there are no simple explanations for cluster assignments. To improve interpretability, we consider using a small threshold tree to partition a dataset into clusters. This leads to cluster assignments that can be explained by very few feature values in a straightforward manner. We study this problem from a theoretical viewpoint, measuring the output quality by the k-means and k-medians objectives. In terms of negative results, we show that popular top-down decision tree algorithms may lead to clusterings with arbitrarily large cost, and we prove that any explainable clustering must incur an \Omega(\log k) approximation compared to the optimal clustering. On the upper bound side, we design efficient algorithms that produce explainable clusters using a tree with k leaves. For two means/medians, we show that a single threshold cut suffices to achieve a constant factor approximation, which is a surprising result that nearly matches our lower bounds. For general k \geq 2, our algorithm is an O(k) approximation to the optimal k-medians and an O(k^2) approximation to the optimal k-means. Prior to our work, no algorithms were known with provable guarantees independent of the dimensionality and input size.
Influence Diagram Bandits
Authors: Tong Yu, Branislav Kveton, Zheng Wen, Ruiyi Zhang, Ole J. Mengshoel
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: Learning-To-Rank, Position

We propose a novel framework for structured bandits, which we call influence diagram bandit. Our framework captures complicated statistical dependencies between actions, latent variables, and observations; and unifies and extends many existing models, such as combinatorial semi-bandits, cascading bandits, and low-rank bandits. We develop novel online learning algorithms that allow us to act efficiently in our models. The key idea is to track a structured posterior distribution of model parameters, either exactly or approximately. To act, we sample model parameters from their posterior and then use the structure of the influence diagram to find the most optimistic actions under the sampled parameters. We experiment with three structured bandit problems: cascading bandits, online learning to rank in the position-based model, and rank-1 bandits. Our algorithms achieve up to about 3 times higher cumulative reward than baselines.
Logarithmic Regret for Online Control with Adversarial Noise
Authors: Dylan Foster, Max Simchowitz
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: LEMMA

We consider the problem of online control in a known linear dynamical system subject to adversarial noise. Existing regret bounds for this setting scale as $\sqrt{T}$ unless strong stochastic assumptions are imposed on the noise. We give the first algorithm with logarithmic regret for arbitrary adversarial noise sequences, provided that the state and control costs are given by fixed quadratic functions. We propose a novel analysis that combines a new variant of the performance difference lemma with techniques from optimal control, allowing us to reduce online control to online prediction with delayed feedback. Unlike prior work, which leverages the so-called online convex optimization with memory framework, our analysis \emph{does not} need to bound movement costs of the iterates, leading to logarithmic regret. Our performance difference lemma-based analysis may be of broader interest beyond linear control.
Online Control of the False Coverage Rate and False Sign Rate
Authors: Asaf Weinstein, Aaditya Ramdas
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: Prediction Intervals

The reproducibility debate has caused a renewed interest in changing how one reports uncertainty, from $p$-value for testing a null hypothesis to a confidence interval (CI) for the corresponding parameter. When CIs for multiple selected parameters are being reported, the analog of the false discovery rate (FDR) is the false coverage rate (FCR), which is the expected ratio of number of reported CIs failing to cover their respective parameters to the total number of reported CIs. 
Here, we consider the general problem of FCR control in the online setting, where there is an infinite sequence of fixed unknown parameters ordered by time. 
While much progress has been made in online testing, a procedure controlling the FDR does not automatically translate to a (nontrivial) procedure that controls the FCR. Therefore, the problem of online FCR control needs to be treated separately. 
We propose a novel solution to the problem which only requires the scientist to be able to construct a marginal CI at any given level. If so desired, our framework also yields online FDR control as a special case, or even online sign-classification procedures that control the false sign rate (FSR). Last, all of our methodology applies equally well to prediction intervals, having particular implications for selective conformal inference.
Optimally Solving Two-Agent Decentralized POMDPs Under One-Sided Information Sharing
Authors: Yuxuan Xie, Jilles Dibangoye, Olivier Buffet
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: Heuristic Search, Vocal Bursts Valence Prediction

Optimally solving decentralized partially observable Markov decision processes under either full or no information sharing received significant attention in recent years. However, little is known about how partial information sharing affects existing theory and algorithms. This paper addresses this question for a team of two agents, with one-sided information sharing---\ie both agents have imperfect information about the state of the world, but only one has access to what the other sees and does. From the perspective of a central planner, we show that the original problem can be reformulated into an equivalent information-state Markov decision process and solved as such. Besides, we prove that the optimal value function exhibits a specific form of uniform continuity. We also present a heuristic search algorithm utilizing this property and providing the first results for this family of problems.
Responsive Safety in Reinforcement Learning
Authors: Adam Stooke, Joshua Achiam, Pieter Abbeel
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL), Safe Reinforcement Learning

CMDPs formalize the problem of safe reinforcement learning by exposing a cost signal alongside the reward and limiting its accumulation.  Lagrangian method are the most commonly used algorithms for the resulting constrained optimization problem.  Yet they are known to oscillate and overshoot cost limits, causing constraint-violating behavior during training.  In this paper, we aim to correct this shortcoming.  We begin by proposing a novel modification to the classic Lagrangian method: we add a ``proportional'' term to the Lagrange multiplier update and show that it induces favorable learning dynamics through damping.  This intuition leads to our introduction of PID control for the Lagrange multiplier in constrained RL, which we cast as a dynamical system.  We conduct extensive experiments in a deep RL setting, in which our methods set a new state of the art by dramatically reducing constraint violations while maintaining high returns.  Moreover, we show significant improvements in robustness to hyperparameters.  Unlike other recent algorithms, ours remains nearly as simple to derive and implement as the baseline Lagrangian method.
SoftSort: A Differantiable Continuous Relaxation of the argsort Operator
Authors: Sebastian Prillo, Julian Eisenschlos
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1

Sorting is an important procedure in computer science. However, the argsort operator - which takes as input a vector and returns its sorting per-mutation - has a discrete image and thus zero gradients almost everywhere. This prohibits end-to-end, gradient-based learning of models that rely on the argsort operator. A natural way to overcome this problem is to replace the argsort operator with a continuous relaxation. Recent work has shown a number of ways to do this. However, the relaxations proposed so far are computationally complex. In this work we propose a simple continuous relaxation for the argsort operator. Unlike previous works, our relaxation is straight-forward: it can be implemented in three lines of code, achieves state-of-the-art performance, is easy to reason about mathematically - substantially simplifying proofs - and is up to six times faster than competing approaches. We open-source the code to reproduce all of the experiments