pwc-archive/papers-with-abstracts huggingface dataset:
Value Function in Frequency Domain and the Characteristic Value Iteration Algorithm
Authors: Amir-Massoud Farahmand
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12
Tasks: Reinforcement Learning

This paper considers the problem of estimating the distribution of returns in reinforcement learning (i.e., distributional RL problem). It presents a new representational framework to maintain the uncertainty of returns and provides mathematical tools to compute it. 
We show that instead of representing a probability distribution function of returns, one can represent their characteristic function instead, the Fourier transform of their distribution. We call the new representation Characteristic Value Function (CVF), which can be interpreted as the frequency domain representation of the probability distribution of returns.
We show that the CVF satisfies a Bellman-like equation, and its corresponding Bellman operator is contraction with respect to certain metrics.
The contraction property allows us to devise an iterative procedure to compute the CVF, which we call Characteristic Value Iteration (CVI). We analyze CVI and its approximate variant and show how approximation errors affect the quality of computed CVF.
Icebreaker: Element-wise Efficient Information Acquisition with a Bayesian Deep Latent Gaussian Model
Authors: Wenbo Gong, Sebastian Tschiatschek, Sebastian Nowozin, Richard E. Turner, José Miguel Hernández-Lobato, Cheng Zhang
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12
Tasks: BIG-bench Machine Learning, Imputation, Recommendation Systems

In this paper, we address the ice-start problem, i.e., the challenge of deploying machine learning models when only a little or no training data is initially available, and acquiring each feature element of data is associated with costs. This setting is representative of the real-world machine learning applications. For instance, in the health care domain, obtaining every single measurement comes with a cost. We propose Icebreaker, a principled framework for elementwise training data acquisition. Icebreaker introduces a full Bayesian Deep Latent Gaussian Model (BELGAM) with a novel inference method, which combines recent advances in amortized inference and stochastic gradient MCMC to enable fast and accurate posterior inference. By utilizing BELGAM’s ability to fully quantify model uncertainty, we also propose two information acquisition functions for imputation and active prediction problems. We demonstrate that BELGAM performs significantly better than previous variational autoencoder (VAE) based models, when the data set size is small, using both machine learning benchmarks and real world recommender systems and health-care applications. Moreover, Icebreaker not only demonstrates improved performance compared to baselines, but it is also capable of achieving better test performance with less training data available.
Offline Contextual Bandits with High Probability Fairness Guarantees
Authors: Blossom Metevier, Stephen Giguere, Sarah Brockman, Ari Kobren, Yuriy Brun, Emma Brunskill, Philip S. Thomas
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12
Tasks: Fairness, Multi-Armed Bandits, Vocal Bursts Intensity Prediction

We present RobinHood, an ofﬂine contextual bandit algorithm designed to satisfy a broad family of fairness constraints. Our algorithm accepts multiple fairness deﬁnitions and allows users to construct their own unique fairness deﬁnitions for the problem at hand. We provide a theoretical analysis of RobinHood, which includes a proof that it will not return an unfair solution with probability greater than a user-speciﬁed threshold. We validate our algorithm on three applications: a tutoring system in which we conduct a user study and consider multiple unique fairness deﬁnitions; a loan approval setting (using the Statlog German credit data set) in which well-known fairness deﬁnitions are applied; and criminal recidivism (using data released by ProPublica). In each setting, our algorithm is able to produce fair policies that achieve performance competitive with other ofﬂine and online contextual bandit algorithms.
Compositional Plan Vectors
Authors: Coline Devin, Daniel Geng, Pieter Abbeel, Trevor Darrell, Sergey Levine
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12
Tasks: Imitation Learning

Autonomous agents situated in real-world environments must be able to master large repertoires of skills.
While a single short skill can be learned quickly, it would be impractical to learn every task independently. Instead, the agent should share knowledge across behaviors such that each task can be learned efficiently, and such that the resulting model can generalize to new tasks, especially ones that are compositions or subsets of tasks seen previously.
A policy conditioned on a goal or demonstration has the potential to share knowledge between tasks if it sees enough diversity of inputs. However, these methods may not generalize to a more complex task at test time. We introduce compositional plan vectors (CPVs) to enable a policy to perform compositions of tasks without additional supervision. CPVs represent trajectories as the sum of the subtasks within them. We show that CPVs can be learned within a one-shot imitation learning framework without any additional supervision or information about task hierarchy, and enable a demonstration-conditioned policy to generalize to tasks that sequence twice as many skills as the tasks seen during training.
 Analogously to embeddings such as word2vec in NLP, CPVs can also support simple arithmetic operations -- for example, we can add the CPVs for two different tasks to command an agent to compose both tasks, without any additional training.
On Human-Aligned Risk Minimization
Authors: Liu Leqi, Adarsh Prasad, Pradeep K. Ravikumar
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12
Tasks: Decision Making, Fairness

The statistical decision theoretic foundations of modern machine learning have largely focused on the minimization of the expectation of some loss function for a given task. However, seminal results in behavioral economics have shown that human decision-making is based on different risk measures than the expectation of any given loss function. In this paper, we pose the following simple question: in contrast to minimizing expected loss, could we minimize a better human-aligned risk measure? While this might not seem natural at first glance, we analyze the properties of such a revised risk measure, and surprisingly show that it might also better align with additional desiderata like fairness that have attracted considerable recent attention. We focus in particular on a class of human-aligned risk measures inspired by cumulative prospect theory. We empirically study these risk measures, and demonstrate their improved performance on desiderata such as fairness, in contrast to the traditional workhorse of expected loss minimization.
Beyond the Single Neuron Convex Barrier for Neural Network Certification
Authors: Gagandeep Singh, Rupanshu Ganvir, Markus Püschel, Martin Vechev
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12

We propose a new parametric framework, called k-ReLU, for computing precise
and scalable convex relaxations used to certify neural networks. The key idea is to
approximate the output of multiple ReLUs in a layer jointly instead of separately.
This joint relaxation captures dependencies between the inputs to different ReLUs
in a layer and thus overcomes the convex barrier imposed by the single neuron
triangle relaxation and its approximations. The framework is parametric in the
number of k ReLUs it considers jointly and can be combined with existing verifiers
in order to improve their precision. Our experimental results show that k-ReLU en-
ables significantly more precise certification than existing state-of-the-art verifiers
while maintaining scalability.
An Algorithm to Learn Polytree Networks with Hidden Nodes
Authors: Firoozeh Sepehr, Donatello Materassi
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12

Ancestral graphs are a prevalent mathematical tool to take into account latent (hidden) variables in a probabilistic graphical model. In ancestral graph representations, the nodes are only the observed (manifest) variables and the notion of m-separation fully characterizes the conditional independence relations among such variables, bypassing the need to explicitly consider latent variables. However, ancestral graph models do not necessarily represent the actual causal structure of the model, and do not contain information about, for example, the precise number and location of the hidden variables. Being able to detect the presence of latent variables while also inferring their precise location within the actual causal structure model is a more challenging task that provides more information about the actual causal relationships among all the model variables, including the latent ones. In this article, we develop an algorithm to exactly recover graphical models of random variables with underlying polytree structures when the latent nodes satisfy specific degree conditions. Therefore, this article proposes an approach for the full identification of hidden variables in a polytree. We also show that the algorithm is complete in the sense that when such degree conditions are not met, there exists another polytree with fewer number of latent nodes satisfying the degree conditions and entailing the same independence relations among the observed variables, making it indistinguishable from the actual polytree.
Efficiently Learning Fourier Sparse Set Functions
Authors: Andisheh Amrollahi, Amir Zandieh, Michael Kapralov, Andreas Krause
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12

Learning set functions is a key challenge arising in many domains, ranging from sketching graphs to black-box optimization with discrete parameters. In this paper we consider the problem of efficiently learning set functions that are defined over a ground set of size $n$ and that are sparse (say $k$-sparse) in the Fourier domain. This is a wide class, that includes graph and hypergraph cut functions, decision trees and more. Our central contribution is the first algorithm that allows learning functions whose Fourier support only contains low degree (say degree $d=o(n)$) polynomials using $O(k d \log n)$ sample complexity and runtime $O( kn \log^2 k \log n \log d)$. This implies that sparse graphs with $k$ edges can, for the first time, be learned from $O(k \log n)$ observations of cut values and in linear time in the number of vertices. 
 Our algorithm can also efficiently learn (sums of) decision trees of small depth.
 The algorithm exploits techniques from the sparse Fourier transform literature and is easily implementable. Lastly, we also develop an efficient robust version of our algorithm and prove $\ell_2/\ell_2$ approximation guarantees without any statistical assumptions on the noise.
Projected Stein Variational Newton: A Fast and Scalable Bayesian Inference Method in High Dimensions
Authors: Peng Chen, Keyi Wu, Joshua Chen, Tom O'Leary-Roseberry, Omar Ghattas
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12
Tasks: Bayesian Inference

We propose a projected Stein variational Newton (pSVN) method for high-dimensional Bayesian inference. To address the curse of dimensionality, we exploit the intrinsic low-dimensional geometric structure of the posterior distribution in the high-dimensional parameter space via its Hessian (of the log posterior) operator and perform a parallel update of the parameter samples projected into a low-dimensional subspace by an SVN method. The subspace is adaptively constructed using the eigenvectors of the averaged Hessian at the current samples. We demonstrate fast convergence of the proposed method, complexity independent of the parameter and sample dimensions, and parallel scalability.
Generalization Error Analysis of Quantized Compressive Learning
Authors: Xiaoyun Li, Ping Li
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12
Tasks: Quantization

Compressive learning is an effective method to deal with very high dimensional datasets by applying learning algorithms in a randomly projected lower dimensional space. In this paper, we consider the learning problem where the projected data is further compressed by scalar quantization, which is called quantized compressive learning. Generalization error bounds are derived for three models: nearest neighbor (NN) classifier, linear classifier and least squares regression. Besides studying finite sample setting, our asymptotic analysis shows that the inner product estimators have deep connection with NN and linear classification problem through the variance of their debiased counterparts. By analyzing the extra error term brought by quantization, our results provide useful implications to the choice of quantizers in applications involving different learning tasks. Empirical study is also conducted to validate our theoretical findings.
Efficient Rematerialization for Deep Networks
Authors: Ravi Kumar, Manish Purohit, Zoya Svitkina, Erik Vee, Joshua Wang
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12

When training complex neural networks, memory usage can be an important bottleneck.  The question of when to rematerialize, i.e., to recompute intermediate values rather than retaining them in memory, becomes critical to achieving the best time and space efficiency.  In this work we consider the rematerialization problem and devise efficient algorithms that use structural characterizations of computation graphs---treewidth and pathwidth---to obtain provably efficient rematerialization schedules. Our experiments demonstrate the performance of these algorithms on many common deep learning models.
Text-Based Interactive Recommendation via Constraint-Augmented Reinforcement Learning
Authors: Ruiyi Zhang, Tong Yu, Yilin Shen, Hongxia Jin, Changyou Chen
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12
Tasks: Interactive Recommendation, Recommendation Systems, reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL), Text Generation

Text-based interactive recommendation provides richer user preferences and has demonstrated advantages over traditional interactive recommender systems. However, recommendations can easily violate preferences of users from their past natural-language feedback, since the recommender needs to explore new items for further improvement. To alleviate this issue, we propose a novel constraint-augmented reinforcement learning (RL) framework to efficiently incorporate user preferences over time. Specifically, we leverage a discriminator to detect recommendations violating user historical preference, which is incorporated into the standard RL objective of maximizing expected cumulative future rewards. Our proposed framework is general and is further extended to the task of constrained text generation. Empirical results show that the proposed method yields consistent improvement relative to standard RL methods.
DeepWave: A Recurrent Neural-Network for Real-Time Acoustic Imaging
Authors: Matthieu Simeoni, Sepand Kashani, Paul Hurley, Martin Vetterli
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12
Tasks: Astronomy, Deblurring

We propose a recurrent neural-network for real-time reconstruction of acoustic camera spherical maps. The network, dubbed DeepWave, is both physically and algorithmically motivated: its recurrent architecture mimics iterative solvers from convex optimisation, and its parsimonious parametrisation is based on the natural structure of acoustic imaging problems.
Each network layer applies successive filtering, biasing and activation steps to its input, which can be interpreted as generalised deblurring and sparsification steps. To comply with the irregular geometry of spherical maps, filtering operations are implemented efficiently by means of graph signal processing techniques.
Unlike commonly-used imaging network architectures, DeepWave is moreover capable of directly processing the complex-valued raw microphone correlations, learning how to optimally back-project these into a spherical map. We propose moreover a smart physically-inspired initialisation scheme that attains much faster training and higher performance than random initialisation.
Our real-data experiments show DeepWave has similar computational speed to the state-of-the-art delay-and-sum imager with vastly superior resolution. While developed primarily for acoustic cameras, DeepWave could easily be adapted to neighbouring  signal processing fields, such as radio astronomy, radar and sonar.
Certifying Geometric Robustness of Neural Networks
Authors: Mislav Balunovic, Maximilian Baader, Gagandeep Singh, Timon Gehr, Martin Vechev
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12

The use of neural networks in safety-critical computer vision systems calls for their
robustness certification against natural geometric transformations (e.g., rotation,
scaling). However, current certification methods target mostly norm-based pixel
perturbations and cannot certify robustness against geometric transformations. In
this work, we propose a new method to compute sound and asymptotically optimal
linear relaxations for any composition of transformations. Our method is based on
a novel combination of sampling and optimization. We implemented the method
in a system called DeepG and demonstrated that it certifies significantly more
complex geometric transformations than existing methods on both defended and
undefended networks while scaling to large architectures.
Input-Output Equivalence of Unitary and Contractive RNNs
Authors: Melikasadat Emami, Mojtaba Sahraee Ardakan, Sundeep Rangan, Alyson K. Fletcher
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12

Unitary recurrent neural networks (URNNs) have been proposed as a method to overcome the vanishing and exploding gradient problem in modeling data with long-term dependencies. A basic question is how restrictive is the unitary constraint on the possible input-output mappings of such a network? This works shows that for any contractive RNN with ReLU activations, there is a URNN with at most twice the number of hidden states and the identical input-output mapping.  Hence, with ReLU activations, URNNs are as expressive as general RNNs.  In contrast, for certain smooth activations, it is shown that the input-output mapping of an RNN cannot be matched with a URNN, even with an arbitrary number of states.  The theoretical results are supported by experiments on modeling of slowly-varying dynamical systems.
Multiple Futures Prediction
Authors: Charlie Tang, Russ R. Salakhutdinov
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12
Tasks: motion prediction, Prediction

Temporal prediction is critical for making intelligent and robust decisions in complex dynamic environments. Motion prediction needs to model the inherently uncertain future which often contains multiple potential outcomes, due to multi-agent interactions and the latent goals of others. Towards these goals, we introduce a probabilistic framework that efficiently learns latent variables to jointly model the multi-step future motions of agents in a scene. Our framework is data-driven and learns semantically meaningful latent variables to represent the multimodal future, without requiring explicit labels. Using a dynamic attention-based state encoder, we learn to encode the past as well as the future interactions among agents, efficiently scaling to any number of agents. Finally, our model can be used for planning via computing a conditional probability density over the trajectories of other agents given a hypothetical rollout of the ego agent. We demonstrate our algorithms by predicting vehicle trajectories of both simulated and real data, demonstrating the state-of-the-art results on several vehicle trajectory datasets.
Neural Taskonomy: Inferring the Similarity of Task-Derived Representations from Brain Activity
Authors: Yu-An Wang, Michael Tarr, Leila Wehbe
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12
Tasks: Edge Detection, Object, Transfer Learning

Convolutional neural networks (CNNs) trained for object classification have been widely used to account for visually-driven neural responses in both human and primate brains. However, because of the generality and complexity of object classification, despite the effectiveness of CNNs in predicting brain activity, it is difficult to draw specific inferences about neural information processing using CNN-derived representations. To address this problem, we used learned representations drawn from 21 computer vision tasks to construct encoding models for predicting brain responses from BOLD5000---a large-scale dataset comprised of fMRI scans collected while observers viewed over 5000 naturalistic scene and object images. Encoding models based on task features predict activity in different regions across the whole brain. Features from 3D tasks such as keypoint/edge detection explain greater variance compared to 2D tasks---a pattern observed across the whole brain. Using results across all 21 task representations, we constructed a ``task graph’’ based on the spatial layout of well-predicted brain areas from each task. A comparison of this brain-derived task structure to the task structure derived from transfer learning accuracy demonstrate that tasks with higher transferability make similar predictions for brain responses from different regions. These results---arising out of state-of-the-art computer vision methods---help reveal the task-specific architecture of the human visual system.
Learning Reward Machines for Partially Observable Reinforcement Learning
Authors: Rodrigo Toro Icarte, Ethan Waldie, Toryn Klassen, Rick Valenzano, Margarita Castro, Sheila McIlraith
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12
Tasks: Partially Observable Reinforcement Learning, Problem Decomposition, reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

Reward Machines (RMs), originally proposed for specifying problems in Reinforcement Learning (RL), provide a structured, automata-based representation of a reward function that allows an agent to decompose problems into subproblems that can be efficiently learned using off-policy learning. Here we show that RMs can be learned from experience, instead of being specified by the user, and that the resulting problem decomposition can be used to effectively solve partially observable RL problems. We pose the task of learning RMs as a discrete optimization problem where the objective is to find an RM that decomposes the problem into a set of subproblems such that the combination of their optimal memoryless policies is an optimal policy for the original problem. We show the effectiveness of this approach on three partially observable domains, where it significantly outperforms A3C, PPO, and ACER, and discuss its advantages, limitations, and broader potential.