pwc-archive/papers-with-abstracts huggingface dataset:
Normalization Helps Training of Quantized LSTM
Authors: Lu Hou, Jinhua Zhu, James Kwok, Fei Gao, Tao Qin, Tie-Yan Liu
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12
Tasks: Quantization

The long-short-term memory (LSTM), though powerful, is memory and computa\x02tion expensive. To alleviate this problem, one approach is to compress its weights by quantization. However, existing quantization methods usually have inferior performance when used on LSTMs. In this paper, we first show theoretically that training a quantized LSTM is difficult because quantization makes the exploding gradient problem more severe, particularly when the LSTM weight matrices are large. We then show that the popularly used weight/layer/batch normalization schemes can help stabilize the gradient magnitude in training quantized LSTMs. Empirical results show that the normalized quantized LSTMs achieve significantly better results than their unnormalized counterparts. Their performance is also comparable with the full-precision LSTM, while being much smaller in size.
Explicit Planning for Efficient Exploration in Reinforcement Learning
Authors: Liangpeng Zhang, Ke Tang, Xin Yao
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12
Tasks: Efficient Exploration, reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

Efficient exploration is crucial to achieving good performance in reinforcement learning. Existing systematic exploration strategies (R-MAX, MBIE, UCRL, etc.), despite being promising theoretically, are essentially greedy strategies that follow some predefined heuristics. When the heuristics do not match the dynamics of Markov decision processes (MDPs) well, an excessive amount of time can be wasted in travelling through already-explored states, lowering the overall efficiency. We argue that explicit planning for exploration can help alleviate such a problem, and propose a Value Iteration for Exploration Cost (VIEC) algorithm which computes the optimal exploration scheme by solving an augmented MDP. We then present a detailed analysis of the exploration behaviour of some popular strategies, showing how these strategies can fail and spend O(n^2 md) or O(n^2 m + nmd) steps to collect sufficient data in some tower-shaped MDPs, while the optimal exploration scheme, which can be obtained by VIEC, only needs O(nmd), where n, m are the numbers of states and actions and d is the data demand. The analysis not only points out the weakness of existing heuristic-based strategies, but also suggests a remarkable potential in explicit planning for exploration.
Nonlinear scaling of resource allocation in sensory bottlenecks
Authors: Laura Rose Edmondson, Alejandro Jimenez Rodriguez, Hannes P. Saal
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12

In many sensory systems, information transmission is constrained by a bottleneck,
where the number of output neurons is vastly smaller than the number of input
neurons. Efficient coding theory predicts that in these scenarios the brain should
allocate its limited resources by removing redundant information. Previous work
has typically assumed that receptors are uniformly distributed across the sensory
sheet, when in reality these vary in density, often by an order of magnitude. How,
then, should the brain efficiently allocate output neurons when the density of input
neurons is nonuniform? Here, we show analytically and numerically that resource
allocation scales nonlinearly in efficient coding models that maximize information
transfer, when inputs arise from separate regions with different receptor densities.
Importantly, the proportion of output neurons allocated to a given input region
changes depending on the width of the bottleneck, and thus cannot be predicted
from input density or region size alone. Narrow bottlenecks favor magnification of
high density input regions, while wider bottlenecks often cause contraction. Our
results demonstrate that both expansion and contraction of sensory input regions
can arise in efficient coding models and that the final allocation crucially depends
on the neural resources made available.
PerspectiveNet: A Scene-consistent Image Generator for New View Synthesis in Real Indoor Environments
Authors: Ben Graham, David Novotny, Jeremy Reizenstein
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12

Given a set of a reference RGBD views of an indoor environment, and a new viewpoint, our goal is to predict the view from that location. Prior work on new-view generation has predominantly focused on significantly constrained scenarios, typically involving artificially rendered views of isolated CAD models. Here we tackle a much more challenging version of the problem. We devise an approach that exploits known geometric properties of the scene (per-frame camera extrinsics and depth) in order to warp reference views into the new ones. The defects in the generated views are handled by a novel RGBD inpainting network, PerspectiveNet, that is fine-tuned for a given scene in order to obtain images that are geometrically consistent with all the views in the scene camera system. Experiments conducted on the ScanNet and SceneNet datasets reveal performance superior to strong baselines.
Self-Routing Capsule Networks
Authors: Taeyoung Hahn, Myeongjang Pyeon, Gunhee Kim
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12
Tasks: Clustering, Mixture-of-Experts

Capsule networks have recently gained a great deal of interest as a new architecture of neural networks that can be more robust to input perturbations than similar-sized CNNs. Capsule networks have two major distinctions from the conventional CNNs: (i) each layer consists of a set of capsules that specialize in disjoint regions of the feature space and (ii) the routing-by-agreement coordinates connections between adjacent capsule layers. Although the routing-by-agreement is capable of filtering out noisy predictions of capsules by dynamically adjusting their influences, its unsupervised clustering nature causes two weaknesses: (i) high computational complexity and (ii) cluster assumption that may not hold in presence of heavy input noise. In this work, we propose a novel and surprisingly simple routing strategy called self-routing where each capsule is routed independently by its subordinate routing network. Therefore, the agreement between capsules is not required anymore but both poses and activations of upper-level capsules are obtained in a way similar to Mixture-of-Experts. Our experiments on CIFAR-10, SVHN and SmallNORB show that the self-routing performs more robustly against white-box adversarial attacks and affine transformations, requiring less computation.
The Parameterized Complexity of Cascading Portfolio Scheduling
Authors: Eduard Eiben, Robert Ganian, Iyad Kanj, Stefan Szeider
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12
Tasks: Relation, Scheduling

Cascading portfolio scheduling is a static algorithm selection strategy which uses a sample of test instances to compute an optimal ordering (a cascading schedule) of a portfolio of available algorithms.  The algorithms are then applied to each future instance according to this cascading schedule, until some algorithm in the schedule succeeds. Cascading algorithm scheduling has proven to be effective in several applications, including QBF solving and the generation of ImageNet classification models.

It is known that the computation of an optimal cascading schedule in
the offline phase is NP-hard. In this paper we study the parameterized complexity of this problem and establish its fixed-parameter tractability by utilizing structural properties of the success relation between algorithms and test instances.

Our findings are significant as they reveal that in spite of the intractability of the problem in its general form, one can indeed exploit sparseness or density of the success relation to obtain non-trivial runtime guarantees for finding an optimal cascading schedule.
Maximum Expected Hitting Cost of a Markov Decision Process and Informativeness of Rewards
Authors: Falcon Dai, Matthew Walter
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12
Tasks: Informativeness

We propose a new complexity measure for Markov decision processes (MDPs), the maximum expected hitting cost (MEHC). This measure tightens the closely related notion of diameter [JOA10] by accounting for the reward structure.
We show that this parameter replaces diameter in the upper bound on the optimal value span of an extended MDP, thus refining the associated upper bounds on the regret of several UCRL2-like algorithms.
Furthermore, we show that potential-based reward shaping [NHR99] can induce equivalent reward functions with varying informativeness, as measured by MEHC.
By analyzing the change in the maximum expected hitting cost, this work presents a formal understanding of the effect of potential-based reward shaping on regret (and sample complexity) in the undiscounted average reward setting.
We further establish that shaping can reduce or increase MEHC by at most a factor of two in a large class of MDPs with finite MEHC and unsaturated optimal average rewards.
Bipartite expander Hopfield networks as self-decoding high-capacity error correcting codes
Authors: Rishidev Chaudhuri, Ila Fiete
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12
Tasks: Decoder

Neural network models of memory and error correction famously include the Hopfield network, which can directly store---and error-correct through its dynamics---arbitrary N-bit patterns, but only for ~N such patterns. On the other end of the spectrum, Shannon's coding theory established that it is possible to represent exponentially many states (~e^N) using N symbols in such a way that an optimal decoder could correct all noise upto a threshold. We prove that it is possible to construct an associative content-addressable network that combines the properties of strong error correcting codes and Hopfield networks: it simultaneously possesses exponentially many stable states, these states are robust enough, with large enough basins of attraction that they can be correctly recovered despite errors in a finite fraction of all nodes, and the errors are intrinsically corrected by the network’s own dynamics. The network is a two-layer Boltzmann machine with simple neural dynamics, low dynamic-range (binary) pairwise synaptic connections, and sparse expander graph connectivity. Thus, quasi-random sparse structures---characteristic of important error-correcting codes---may provide for high-performance computation in artificial neural networks and the brain.
A Unifying Framework for Spectrum-Preserving Graph Sparsification and Coarsening
Authors: Gecia Bravo Hermsdorff, Lee Gunderson
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12
Tasks: Graph Similarity

How might one ``reduce'' a graph? 
That is, generate a smaller graph that preserves the global structure at the expense of discarding local details?  
There has been extensive work on both graph sparsification (removing edges) and graph coarsening (merging nodes, often by edge contraction); however, these operations are currently treated separately.  
Interestingly, for a planar graph, edge deletion corresponds to edge contraction in its planar dual (and more generally, for a graphical matroid and its dual).  
Moreover, with respect to the dynamics induced by the graph Laplacian (e.g., diffusion), deletion and contraction are physical manifestations of two reciprocal limits: edge weights of $0$ and $\infty$, respectively.  
In this work, we provide a unifying framework that captures both of these operations, allowing one to simultaneously sparsify and coarsen a graph while preserving its large-scale structure.  
The limit of infinite edge weight is rarely considered, as many classical notions of graph similarity diverge.  However, its algebraic, geometric, and physical interpretations are reflected in the Laplacian pseudoinverse $\mat{L}^\dagger$, which remains finite in this limit.  
Motivated by this insight, we provide a probabilistic algorithm that reduces graphs while preserving $\mat{L}^\dagger$, using an unbiased procedure that minimizes its variance. 
We compare our algorithm with several existing sparsification and coarsening algorithms using real-world datasets, and demonstrate that it more accurately preserves the large-scale structure.
On two ways to use determinantal point processes for Monte Carlo integration
Authors: Guillaume Gautier, Rémi Bardenet, Michal Valko
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12
Tasks: Numerical Integration, Point Processes

When approximating an integral by a weighted sum of function evaluations, determinantal point processes (DPPs) provide a way to enforce repulsion between the evaluation points.
This negative dependence is encoded by a kernel.
Fifteen years before the discovery of DPPs, Ermakov & Zolotukhin (EZ, 1960) had the intuition of sampling a DPP and solving a linear system to compute an unbiased Monte Carlo estimator of the integral.
In the absence of DPP machinery to derive an efficient sampler and analyze their estimator, the idea of Monte Carlo integration with DPPs was stored in the cellar of numerical integration. 
Recently, Bardenet & Hardy (BH, 2019) came up with a more natural estimator with a fast central limit theorem (CLT).
In this paper, we first take the EZ estimator out of the cellar, and analyze it using modern arguments.
Second, we provide an efficient implementation to sample exactly a particular multidimensional DPP called multivariate Jacobi ensemble.
The latter satisfies the assumptions of the aforementioned CLT. 
Third, our new implementation lets us investigate the behavior of the two unbiased Monte Carlo estimators in yet unexplored regimes.
We demonstrate experimentally good properties when the kernel is adapted to basis of functions in which the integrand is sparse or has fast-decaying coefficients.
If such a basis and the level of sparsity are known (e.g., we integrate a linear combination of kernel eigenfunctions), the EZ estimator can be the right choice, but otherwise it can display an erratic behavior.
Max-value Entropy Search for Multi-Objective Bayesian Optimization
Authors: Syrine Belakaria, Aryan Deshwal, Janardhan Rao Doppa
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12
Tasks: Bayesian Optimisation, Bayesian Optimization, Multiobjective Optimization

We consider the problem of multi-objective (MO) blackbox optimization using expensive function evaluations, where the goal is to approximate the true Pareto-set of solutions by minimizing the number of function evaluations. For example, in hardware design optimization, we need to find the designs that trade-off performance, energy, and area overhead using expensive simulations. We propose a novel approach referred to as Max-value Entropy Search for Multi-objective Optimization (MESMO) to solve this problem. MESMO employs an output-space entropy based acquisition function to efficiently select the sequence of inputs for evaluation for quickly uncovering high-quality solutions.
 We also provide theoretical analysis to characterize the efficacy of MESMO. Our experiments on several synthetic and real-world benchmark problems show that MESMO consistently outperforms state-of-the-art algorithms.
SMILe: Scalable Meta Inverse Reinforcement Learning through Context-Conditional Policies
Authors: Seyed Kamyar Seyed Ghasemipour, Shixiang (Shane) Gu, Richard Zemel
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12
Tasks: continuous-control, Continuous Control, Decision Making, Few-Shot Learning, Imitation Learning, reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL), Sequential Decision Making

Imitation Learning (IL) has been successfully applied to complex sequential decision-making problems where standard Reinforcement Learning (RL) algorithms fail. A number of recent methods extend IL to few-shot learning scenarios, where a meta-trained policy learns to quickly master new tasks using limited demonstrations. However, although Inverse Reinforcement Learning (IRL) often outperforms Behavioral Cloning (BC) in terms of imitation quality, most of these approaches build on BC due to its simple optimization objective. In this work, we propose SMILe, a scalable framework for Meta Inverse Reinforcement Learning (Meta-IRL) based on maximum entropy IRL, which can learn high-quality policies from few demonstrations. We examine the efficacy of our method on a variety of high-dimensional simulated continuous control tasks and observe that SMILe significantly outperforms Meta-BC. Furthermore, we observe that SMILe performs comparably or outperforms Meta-DAgger, while being applicable in the state-only setting and not requiring online experts. To our knowledge, our approach is the first efficient method for Meta-IRL that scales to the function approximator setting. For datasets and reproducing results please refer to https://github.com/KamyarGh/rl_swiss/blob/master/reproducing/smile_paper.md .
Solving Interpretable Kernel Dimensionality Reduction
Authors: Chieh Wu, Jared Miller, Yale Chang, Mario Sznaier, Jennifer Dy
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12
Tasks: Clustering, Dimensionality Reduction

Kernel dimensionality reduction (KDR) algorithms find a low dimensional representation of the original data by optimizing kernel dependency measures that are capable of capturing nonlinear relationships. The standard strategy is to first map the data into a high dimensional feature space using kernels prior to a projection onto a low dimensional space. While KDR methods can be easily solved by keeping the most dominant eigenvectors of the kernel matrix, its features are no longer easy to interpret.  Alternatively, Interpretable KDR (IKDR) is different in that it projects onto a subspace \textit{before} the kernel feature mapping, therefore, the projection matrix can indicate how the original features linearly combine to form the new features. Unfortunately, the IKDR objective requires a non-convex manifold optimization that is difficult to solve and can no longer be solved by eigendecomposition. Recently, an efficient iterative spectral (eigendecomposition) method (ISM) has been proposed for this objective in the context of alternative clustering. However, ISM only provides theoretical guarantees for the Gaussian kernel. This greatly constrains ISM's usage since any kernel method using ISM is now limited to a single kernel. This work extends the theoretical guarantees of ISM to an entire family of kernels, thereby empowering ISM to solve any kernel method of the same objective. In identifying this family, we prove that each kernel within the family has a surrogate $\Phi$ matrix and the optimal projection is formed by its most dominant eigenvectors. With this extension, we establish how a wide range of IKDR applications across different learning paradigms can be solved by ISM. To support reproducible results, the source code is made publicly available on  \url{https://github.com/ANONYMIZED}.
Post training 4-bit quantization of convolutional networks for rapid-deployment
Authors: Ron Banner, Yury Nahshan, Daniel Soudry
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12
Tasks: Quantization

Convolutional neural networks require significant memory bandwidth and storage for intermediate computations, apart from substantial computing resources. Neural network quantization has significant benefits in reducing the amount of intermediate results, but it often requires the full datasets and time-consuming fine tuning to recover the accuracy lost after quantization. This paper introduces the first practical 4-bit post training quantization approach: it does not involve training the quantized model (fine-tuning), nor it requires the availability of the full dataset. We target the quantization of both activations and weights and suggest three complementary methods for minimizing quantization error at the tensor level, two of whom obtain a closed-form analytical solution. Combining these methods, our approach achieves accuracy that is just a few percents less the state-of-the-art baseline across a wide range of convolutional models. The source code to replicate all experiments is available on GitHub: \url{https://github.com/submission2019/cnn-quantization}.
Learning Local Search Heuristics for Boolean Satisfiability
Authors: Emre Yolcu, Barnabas Poczos
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12
Tasks: Deep Reinforcement Learning, Graph Neural Network, reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL), Variable Selection

We present an approach to learn SAT solver heuristics from scratch through deep reinforcement learning with a curriculum. In particular, we incorporate a graph neural network in a stochastic local search algorithm to act as the variable selection heuristic. We consider Boolean satisfiability problems from different classes and learn specialized heuristics for each class. Although we do not aim to compete with the state-of-the-art SAT solvers in run time, we demonstrate that the learned heuristics allow us to find satisfying assignments in fewer steps compared to a generic heuristic, and we provide analysis of our results through experiments.
Provably Efficient Q-learning with Function Approximation via Distribution Shift Error Checking Oracle
Authors: Simon S. Du, Yuping Luo, Ruosong Wang, Hanrui Zhang
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12
Tasks: Q-Learning, reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

Q-learning with function approximation is one of the most popular methods in reinforcement learning. Though the idea of using function approximation was proposed at least 60 years ago, even in the simplest setup, i.e, approximating Q-functions with linear functions, it is still an open problem how to design a provably efficient algorithm that learns a near-optimal policy. The key challenges are how to efficiently explore the state space and how to decide when to stop exploring in conjunction with the function approximation scheme.

The current paper presents a provably efficient algorithm for Q-learning with linear function approximation. Under certain regularity assumptions, our algorithm, Difference Maximization Q-learning, combined with linear function approximation, returns a near-optimal policy using polynomial number of trajectories. Our algorithm introduces a new notion, the Distribution Shift Error Checking (DSEC) oracle. This oracle tests whether there exists a function in the function class that predicts well on a distribution $\mathcal{D}_1$, but predicts poorly on another distribution $\mathcal{D}_2$, where $\mathcal{D}_1$ and $\mathcal{D}_2$ are distributions over states induced by two different exploration policies. For the linear function class, this oracle is equivalent to solving a top eigenvalue problem. We believe our algorithmic insights, especially the DSEC oracle, are also useful in designing and analyzing reinforcement learning algorithms with general function approximation.