mtybilly/Instruct2DS huggingface dataset:
Backpropagation with Callbacks: Foundations for Efficient and Expressive Differentiable Programming
Authors: James Decker, Xilun Wu, Gregory Essertel, Tiark Rompf Fei Wang
Published in: Advances in Neural Information Processing Systems 31  (NeurIPS 2018) (Main Conference Track), 2018

Abstract: Training of deep learning models depends on gradient descent and end-to-end
differentiation. Under the slogan of differentiable programming, there is an
increasing demand for efficient automatic gradient computation for emerging
network architectures that incorporate dynamic control flow, especially in NLP.
In this paper we propose an implementation of backpropagation using functions
with callbacks, where the forward pass is executed as a sequence of function
calls, and the backward pass as a corresponding sequence of function returns.
A key realization is that this technique of chaining callbacks is well known in the
programming languages community as continuation-passing style (CPS). Any
program can be converted to this form using standard techniques, and hence,
any program can be mechanically converted to compute gradients.
Our approach achieves the same flexibility as other reverse-mode automatic
differentiation (AD) techniques, but it can be implemented without any auxiliary
data structures besides the function call stack, and it can easily be combined
with graph construction and native code generation techniques through forms of
multi-stage programming, leading to a highly efficient implementation that
combines the performance benefits of define-then-run software frameworks such
as TensorFlow with the expressiveness of define-by-run frameworks such as PyTorch.
Constrained Cross-Entropy Method for Safe Reinforcement Learning
Authors: Ufuk Topcu Min Wen
Published in: Advances in Neural Information Processing Systems 31  (NeurIPS 2018) (Main Conference Track), 2018

Abstract: We study a safe reinforcement learning problem in which the constraints are defined as the expected cost over finite-length trajectories. We propose a constrained cross-entropy-based method to solve this problem. The method explicitly tracks its performance with respect to constraint satisfaction and thus is well-suited for safety-critical applications. We show that the asymptotic behavior of the proposed algorithm can be almost-surely described by that of an ordinary differential equation. Then we give sufficient conditions on the properties of this differential equation to guarantee the convergence of the proposed algorithm. At last, we show with simulation experiments that the proposed algorithm can effectively learn feasible policies without assumptions on the feasibility of initial policies, even with non-Markovian objective functions and constraint functions.
Graphical model inference: Sequential Monte Carlo meets deterministic approximations
Authors: Jouni Helske, Matti Vihola Fredrik Lindsten
Published in: Advances in Neural Information Processing Systems 31  (NeurIPS 2018) (Main Conference Track), 2018

Abstract: Approximate inference in probabilistic graphical models (PGMs) can be grouped into deterministic methods and Monte-Carlo-based methods. The former can often provide accurate and rapid inferences, but are typically associated with biases that are hard to quantify. The latter enjoy asymptotic consistency, but can suffer from high computational costs. In this paper we present a way of bridging the gap between deterministic and stochastic inference. Specifically, we suggest an efficient sequential Monte Carlo (SMC) algorithm for PGMs which can leverage the output from deterministic inference methods. While generally applicable, we show explicitly how this can be done with loopy belief propagation, expectation propagation, and Laplace approximations. The resulting algorithm can be viewed as a post-correction of the biases associated with these methods and, indeed, numerical results show clear improvements over the baseline deterministic methods as well as over "plain" SMC.
Playing hard exploration games by watching YouTube
Authors: Tobias Pfaff, David Budden, Thomas Paine, Ziyu Wang, Nando de Freitas Yusuf Aytar
Published in: Advances in Neural Information Processing Systems 31  (NeurIPS 2018) (Main Conference Track), 2018

Abstract: Deep reinforcement learning methods traditionally struggle with tasks where environment rewards are particularly sparse. One successful method of guiding exploration in these domains is to imitate trajectories provided by a human demonstrator. However, these demonstrations are typically collected under artificial conditions, i.e. with access to the agent’s exact environment setup and the demonstrator’s action and reward trajectories. Here we propose a method that overcomes these limitations in two stages. First, we learn to map unaligned videos from multiple sources to a common representation using self-supervised objectives constructed over both time and modality (i.e. vision and sound). Second, we embed a single YouTube video in this representation to learn a reward function that encourages an agent to imitate human gameplay. This method of one-shot imitation allows our agent to convincingly exceed human-level performance on the infamously hard exploration games Montezuma’s Revenge, Pitfall! and Private Eye for the first time, even if the agent is not presented with any environment rewards.
Improved Algorithms for Collaborative PAC Learning
Authors: Lydia Zakynthinou Huy Nguyen
Published in: Advances in Neural Information Processing Systems 31  (NeurIPS 2018) (Main Conference Track), 2018

Abstract: We study a recent model of collaborative PAC learning where $k$ players with $k$ different tasks collaborate to learn a single classifier that works for all tasks. Previous work showed that when there is a classifier that has very small error on all tasks, there is a collaborative algorithm that finds a single classifier for all tasks and has $O((\ln (k))^2)$ times the worst-case sample complexity for learning a single task. In this work, we design new algorithms for both the realizable and the non-realizable setting, having sample complexity only $O(\ln (k))$ times the worst-case sample complexity for learning a single task. The sample complexity upper bounds of our algorithms match previous lower bounds and in some range of parameters are even better than previous algorithms that are allowed to output different classifiers for different tasks.
Scaling provable adversarial defenses
Authors: Frank Schmidt, Jan Hendrik Metzen, J. Zico Kolter Eric Wong
Published in: Advances in Neural Information Processing Systems 31  (NeurIPS 2018) (Main Conference Track), 2018

Abstract: Recent work has developed methods for learning deep network classifiers that are \emph{provably} robust to norm-bounded adversarial perturbation; however, these methods are currently only possible for relatively small feedforward networks.  In this paper, in an effort to scale these approaches to substantially larger models, we extend previous work in three main directly.  First, we present a technique for extending these training procedures to much more general networks, with skip connections (such as ResNets) and general nonlinearities; the approach is fully modular, and can be implemented automatically analogously to automatic differentiation. Second, in the specific case of $\ell_\infty$ adversarial perturbations and networks with ReLU nonlinearities, we adopt a nonlinear random projection for training, which scales \emph{linearly} in the number of hidden units (previous approached scaled quadratically).  Third, we show how to further improve robust error through cascade models.  On both MNIST and CIFAR data sets, we train classifiers that improve substantially on the state of the art in provable robust adversarial error bounds: from 5.8% to 3.1% on MNIST  (with $\ell_\infty$ perturbations of $\epsilon=0.1$), and from 80% to 36.4% on CIFAR (with $\ell_\infty$ perturbations of $\epsilon=2/255$).
Understanding Batch Normalization
Authors: Carla P. Gomes, Bart Selman, Kilian Q. Weinberger Nils Bjorck
Published in: Advances in Neural Information Processing Systems 31  (NeurIPS 2018) (Main Conference Track), 2018

Abstract: Batch normalization (BN) is a technique to normalize activations in intermediate layers of deep neural networks. Its tendency to improve accuracy and speed up training have established BN as a favorite technique in deep learning. Yet, despite its enormous success, there remains little consensus on the exact reason and mechanism behind these improvements. In this paper we take a step towards a better understanding of BN, following an empirical approach. We conduct several experiments, and show that BN primarily enables training with larger learning rates, which is the cause for faster convergence and better generalization. For networks without BN we demonstrate how large gradient updates can result in diverging loss and activations growing uncontrollably with network depth, which limits possible learning rates. BN avoids this problem by constantly correcting activations to be zero-mean and of unit standard deviation, which enables larger gradient steps, yields faster convergence and may help bypass sharp local minima. We further show various ways in which gradients and activations of deep unnormalized networks are ill-behaved. We contrast our results against recent findings in random matrix theory, shedding new light on classical initialization schemes and their consequences.
Navigating with Graph Representations for Fast and Scalable Decoding of Neural Language Models
Authors: Wenhan Wang, Xiaodong Liu, Jianfeng Gao, Yuxiong He Minjia Zhang
Published in: Advances in Neural Information Processing Systems 31  (NeurIPS 2018) (Main Conference Track), 2018

Abstract: Neural language models (NLMs) have recently gained a renewed interest by achieving state-of-the-art performance across many natural language processing (NLP) tasks. However, NLMs are very computationally demanding largely due to the computational cost of the decoding process, which consists of a softmax layer over a large vocabulary.We observe that in the decoding of many NLP tasks, only the probabilities of the top-K hypotheses need to be calculated preciously and K is often much smaller than the vocabulary size.
This paper proposes a novel softmax layer approximation algorithm, called Fast Graph Decoder (FGD), which quickly identifies, for a given context, a set of K words that are most likely to occur according to a NLM.  We demonstrate that FGD reduces the decoding time by an order of magnitude while attaining close to the full softmax baseline accuracy on neural machine translation and language modeling tasks. We also prove the theoretical guarantee on the softmax approximation quality.
Learning from discriminative feature feedback
Authors: Akansha Dey, Nicholas Roberts, Sivan Sabato Sanjoy Dasgupta
Published in: Advances in Neural Information Processing Systems 31  (NeurIPS 2018) (Main Conference Track), 2018

Abstract: We consider the problem of learning a multi-class classifier from labels as well as simple explanations that we call "discriminative features". We show that such explanations can be provided whenever the target concept is a decision tree, or more generally belongs to a particular subclass of DNF formulas. We present an efficient online algorithm for learning from such feedback and we give tight bounds on the number of mistakes made during the learning process. These bounds depend only on the size of the target concept and not on the overall number of available features, which could be infinite. We also demonstrate the learning procedure experimentally.
Zeroth-order (Non)-Convex Stochastic Optimization via Conditional Gradient and Gradient Updates
Authors: Saeed Ghadimi Krishnakumar Balasubramanian
Published in: Advances in Neural Information Processing Systems 31  (NeurIPS 2018) (Main Conference Track), 2018

Abstract: In this paper, we propose and analyze zeroth-order stochastic approximation algorithms for nonconvex and convex optimization. Specifically, we propose generalizations of the conditional gradient algorithm achieving rates similar to the standard stochastic gradient algorithm using only zeroth-order information. Furthermore, under a structural sparsity assumption, we first illustrate an implicit regularization phenomenon where the standard stochastic gradient algorithm with zeroth-order information adapts to the sparsity of the problem at hand by just varying the step-size. Next, we propose a truncated stochastic gradient algorithm with zeroth-order information, whose rate of convergence depends only poly-logarithmically on the dimensionality.
Coordinate Descent with Bandit Sampling
Authors: Patrick Thiran, Elisa Celis Farnood Salehi
Published in: Advances in Neural Information Processing Systems 31  (NeurIPS 2018) (Main Conference Track), 2018

Abstract: Coordinate descent methods minimize a cost function by updating a single decision variable (corresponding to one coordinate) at a time. Ideally, we would update the decision variable that yields the largest marginal decrease in the cost function. However, finding this coordinate would require checking all of them, which is not computationally practical. Therefore, we propose a new adaptive method for coordinate descent. First, we define a lower bound on the decrease of the cost function when a coordinate is updated and, instead of calculating this lower bound for all coordinates, we use a multi-armed bandit algorithm to learn which coordinates result in the largest marginal decrease and simultaneously perform coordinate descent. We show that our approach improves the convergence of the coordinate methods both theoretically and experimentally.
PAC-Bayes bounds for stable algorithms with instance-dependent priors
Authors: Emilio Parrado-Hernandez, John S Shawe-Taylor, Shiliang Sun, Csaba Szepesvari Omar Rivasplata
Published in: Advances in Neural Information Processing Systems 31  (NeurIPS 2018) (Main Conference Track), 2018

Abstract: PAC-Bayes bounds have been proposed to get risk estimates based on a training sample. In this paper the PAC-Bayes approach is combined with stability of the hypothesis learned by a Hilbert space valued algorithm. The PAC-Bayes setting is used with a Gaussian prior centered at the expected output. Thus a novelty of our paper is using priors defined in terms of the data-generating distribution. Our main result estimates the risk of the randomized algorithm in terms of the hypothesis stability coefficients. We also provide a new bound for the SVM classifier, which is compared to other known bounds experimentally. Ours appears to be the first uniform hypothesis stability-based bound that evaluates to non-trivial values.
DropMax: Adaptive Variational Softmax
Authors: Juho Lee, Saehoon Kim, Eunho Yang, Sung Ju Hwang Hae Beom Lee
Published in: Advances in Neural Information Processing Systems 31  (NeurIPS 2018) (Main Conference Track), 2018

Abstract: We propose DropMax, a stochastic version of softmax classifier which at each iteration drops non-target classes according to dropout probabilities adaptively decided for each instance. Specifically, we overlay binary masking variables over class output probabilities, which are input-adaptively learned via variational inference. This stochastic regularization has an effect of building an ensemble classifier out of exponentially many classifiers with different decision boundaries. Moreover, the learning of dropout rates for non-target classes on each instance allows the classifier to focus more on classification against the most confusing classes. We validate our model on multiple public datasets for classification, on which it obtains significantly improved accuracy over the regular softmax classifier and other baselines. Further analysis of the learned dropout probabilities shows that our model indeed selects confusing classes more often when it performs classification.
Multi-Layered Gradient Boosting Decision Trees
Authors: Yang Yu, Zhi-Hua Zhou Ji Feng
Published in: Advances in Neural Information Processing Systems 31  (NeurIPS 2018) (Main Conference Track), 2018

Abstract: Multi-layered distributed representation is believed to be the key ingredient of deep neural networks especially in cognitive tasks like computer vision. While non-differentiable models such as gradient boosting decision trees (GBDTs) are still the dominant methods for modeling discrete or tabular data, they are hard to incorporate with such representation learning ability. In this work, we propose the multi-layered GBDT forest (mGBDTs), with an explicit emphasis on exploring the ability to learn hierarchical distributed representations by stacking several layers of regression GBDTs as its building block. The model can be jointly trained by a variant of target propagation across layers, without the need to derive backpropagation nor differentiability. Experiments confirmed the effectiveness of the model in terms of performance and representation learning ability.
Rest-Katyusha: Exploiting the Solution's Structure via Scheduled Restart Schemes
Authors: Mohammad Golbabaee, Francis Bach, Mike E davies Junqi Tang
Published in: Advances in Neural Information Processing Systems 31  (NeurIPS 2018) (Main Conference Track), 2018

Abstract: We propose a structure-adaptive variant of the state-of-the-art stochastic variance-reduced gradient algorithm Katyusha for  regularized empirical risk minimization. The proposed method is able to exploit the intrinsic low-dimensional structure of the solution, such as sparsity or low rank which is enforced by a non-smooth regularization, to achieve even faster convergence rate. This provable algorithmic improvement is done by restarting the Katyusha algorithm according to restricted strong-convexity constants. We demonstrate the effectiveness of our approach via numerical experiments.
Automatic Program Synthesis of Long Programs with a Learned Garbage Collector
Authors: Lior Wolf Amit Zohar
Published in: Advances in Neural Information Processing Systems 31  (NeurIPS 2018) (Main Conference Track), 2018

Abstract: We consider the problem of generating automatic code given sample input-output pairs. We train a neural network to map from the current state and the outputs to the program's next statement. The neural network optimizes multiple tasks concurrently: the next operation out of a set of high level commands, the operands of the next statement, and which variables can be dropped from memory. Using our method we are able to create programs that are more than twice as long as existing state-of-the-art solutions, while improving the success rate for comparable lengths, and cutting the run-time by two orders of magnitude. Our code, including an implementation of various literature baselines, is publicly available at https://github.com/amitz25/PCCoder
Quantifying Learning Guarantees for Convex but Inconsistent Surrogates
Authors: Simon Lacoste-Julien, Anton Osokin Kirill Struminsky
Published in: Advances in Neural Information Processing Systems 31  (NeurIPS 2018) (Main Conference Track), 2018

Abstract: We study consistency properties of machine learning methods based on minimizing convex surrogates. We extend the recent framework of Osokin et al. (2017) for the quantitative analysis of consistency properties to the case of inconsistent surrogates. Our key technical contribution consists in a new lower bound on the calibration function for the quadratic surrogate, which is non-trivial (not always zero) for inconsistent cases. The new bound allows to quantify the level of inconsistency of the setting and shows how learning with inconsistent surrogates can have guarantees on sample complexity and optimization difficulty. We apply our theory to two concrete cases: multi-class classification with the tree-structured loss and ranking with the mean average precision loss. The results show the approximation-computation trade-offs caused by inconsistent surrogates and their potential benefits.
Unsupervised Text Style Transfer using Language Models as Discriminators
Authors: Zhiting Hu, Chris Dyer, Eric P Xing, Taylor Berg-Kirkpatrick Zichao Yang
Published in: Advances in Neural Information Processing Systems 31  (NeurIPS 2018) (Main Conference Track), 2018

Abstract: Binary classifiers are employed as discriminators in GAN-based unsupervised style transfer models to ensure that transferred sentences are similar to sentences in the target domain. One difficulty with the binary discriminator is that error signal is sometimes insufficient to train the model to produce rich-structured language. In this paper, we propose a technique of using a target domain language model as the discriminator to provide richer, token-level feedback during the learning process. Because our language model scores sentences directly using a product of locally normalized probabilities, it offers more stable and more useful training signal to the generator. We train the generator to minimize the negative log likelihood (NLL) of generated sentences evaluated by a language model. By using continuous approximation of the discrete samples, our model can be trained using back-propagation in an end-to-end way. Moreover, we find empirically with a language model as a structured discriminator, it is possible to eliminate the adversarial training steps using negative samples, thus making training more stable. We compare our model with previous work using convolutional neural networks (CNNs) as discriminators and show our model outperforms them significantly in three tasks including word substitution decipherment, sentiment modification and related language translation.
Multi-View Silhouette and Depth Decomposition for High Resolution 3D Object Representation
Authors: Scott Fujimoto, David Meger Edward Smith
Published in: Advances in Neural Information Processing Systems 31  (NeurIPS 2018) (Main Conference Track), 2018

Abstract: We consider the problem of scaling deep generative shape models to high-resolution. Drawing motivation from the canonical view representation of objects, we introduce a novel method for the fast up-sampling of 3D objects in voxel space through networks that perform super-resolution on the six orthographic depth projections. This allows us to generate high-resolution objects with more efficient scaling than methods which work directly in 3D. We decompose the problem of 2D depth super-resolution into silhouette and depth prediction to capture both structure and fine detail. This allows our method to generate sharp edges more easily than an individual network. We evaluate our work on multiple experiments concerning high-resolution 3D objects, and show our system is capable of accurately predicting novel objects at resolutions as large as 512x512x512 -- the highest resolution reported for this task. We achieve state-of-the-art performance on 3D object reconstruction from RGB images on the ShapeNet dataset, and further demonstrate the first effective 3D super-resolution method.
Domain Adaptation by Using Causal Inference to Predict Invariant Conditional Distributions
Authors: Thijs van Ommen, Tom Claassen, Stephan Bongers, Philip Versteeg, Joris M. Mooij Sara Magliacane
Published in: Advances in Neural Information Processing Systems 31  (NeurIPS 2018) (Main Conference Track), 2018

Abstract: An important goal common to domain adaptation and causal inference is to make accurate predictions when the distributions for the source (or training) domain(s) and target (or test) domain(s) differ. In many cases, these different distributions can be modeled as different contexts of a single underlying system, in which each distribution corresponds to a different perturbation of the system, or in causal terms, an intervention. We focus on a class of such causal domain adaptation problems, where data for one or more source domains are given, and the task is to predict the distribution of a certain target variable from measurements of other variables in one or more target domains. We propose an approach for solving these problems that exploits causal inference and does not rely on prior knowledge of the causal graph, the type of interventions or the intervention targets. We demonstrate our approach by evaluating a possible implementation on simulated and real world data.
Confounding-Robust Policy Improvement
Authors: Angela Zhou Nathan Kallus
Published in: Advances in Neural Information Processing Systems 31  (NeurIPS 2018) (Main Conference Track), 2018

Abstract: We study the problem of learning personalized decision policies from observational data while accounting for possible unobserved confounding in the data-generating process. Unlike previous approaches that assume unconfoundedness, i.e., no unobserved confounders affected both treatment assignment and outcomes, we calibrate policy learning for realistic violations of this unverifiable assumption with uncertainty sets motivated by sensitivity analysis in causal inference. Our framework for confounding-robust policy improvement optimizes the minimax regret of a candidate policy against a baseline or reference "status quo" policy, over an uncertainty set around nominal propensity weights. We prove that if the uncertainty set is well-specified, robust policy learning can do no worse than the baseline, and only improve if the data supports it. We characterize the adversarial subproblem and use efficient algorithmic solutions to optimize over parametrized spaces of decision policies such as logistic treatment assignment. We assess our methods on synthetic data and a large clinical trial, demonstrating that confounded selection can hinder policy learning and lead to unwarranted harm, while our robust approach guarantees safety and focuses on well-evidenced improvement.
Near Optimal Exploration-Exploitation in Non-Communicating Markov Decision Processes
Authors: Matteo Pirotta, Alessandro Lazaric Ronan Fruit
Published in: Advances in Neural Information Processing Systems 31  (NeurIPS 2018) (Main Conference Track), 2018

Abstract: While designing the state space of an MDP, it is common to include states that are transient or not reachable by any policy (e.g., in mountain car, the product space of speed and position contains configurations that are not physically reachable). This results in weakly-communicating or multi-chain MDPs. In this paper, we introduce TUCRL, the first algorithm able to perform efficient exploration-exploitation in any finite Markov Decision Process (MDP) without requiring any form of prior knowledge. In particular, for any MDP with $S^c$ communicating states, $A$ actions and $\Gamma^c \leq S^c$ possible communicating next states, we derive a $O(D^c \sqrt{\Gamma^c S^c A T}) regret bound, where $D^c$ is the diameter (i.e., the length of the longest shortest path between any two states) of the communicating part of the MDP. This is in contrast with optimistic algorithms (e.g., UCRL, Optimistic PSRL) that suffer linear regret in weakly-communicating MDPs, as well as posterior sampling or regularised algorithms (e.g., REGAL), which require prior knowledge on the bias span of the optimal policy to bias the exploration to achieve sub-linear regret. We also prove that in weakly-communicating MDPs, no algorithm can ever achieve a logarithmic growth of the regret without first suffering a linear regret for a number of steps that is exponential in the parameters of the MDP. Finally, we report numerical simulations supporting our theoretical findings and showing how TUCRL overcomes the limitations of the state-of-the-art.
Mesh-TensorFlow: Deep Learning for Supercomputers
Authors: Youlong Cheng, Niki Parmar, Dustin Tran, Ashish Vaswani, Penporn Koanantakool, Peter Hawkins, HyoukJoong Lee, Mingsheng Hong, Cliff Young, Ryan Sepassi, Blake Hechtman Noam Shazeer
Published in: Advances in Neural Information Processing Systems 31  (NeurIPS 2018) (Main Conference Track), 2018

Abstract: Batch-splitting (data-parallelism) is the dominant distributed Deep Neural Network (DNN) training strategy, due to its universal applicability and its amenability to Single-Program-Multiple-Data (SPMD) programming.  However, batch-splitting suffers from problems including the inability to train very large models (due to memory constraints), high latency, and inefficiency at small batch sizes.  All of these can be solved by more general distribution strategies (model-parallelism).  Unfortunately, efficient model-parallel algorithms tend to be complicated to discover, describe, and to implement, particularly on large clusters.  We introduce Mesh-TensorFlow, a language for specifying a general class of distributed tensor computations.  Where data-parallelism can be viewed as splitting tensors and operations along the "batch" dimension, in Mesh-TensorFlow, the user can specify any tensor-dimensions to be split across any dimensions of a multi-dimensional mesh of processors.  A Mesh-TensorFlow graph compiles into a SPMD program consisting of parallel operations coupled with collective communication primitives such as Allreduce.  We use Mesh-TensorFlow to implement an efficient data-parallel, model-parallel version of the Transformer sequence-to-sequence model.  Using TPU meshes of up to 512 cores, we train Transformer models with up to 5 billion parameters, surpassing SOTA results on WMT'14 English-to-French translation task and the one-billion-word Language modeling benchmark.  Mesh-Tensorflow is available at https://github.com/tensorflow/mesh
Foreground Clustering for Joint Segmentation and Localization in Videos and Images
Authors: Abhishek Sharma
Published in: Advances in Neural Information Processing Systems 31  (NeurIPS 2018) (Main Conference Track), 2018

Abstract: This paper presents a novel framework in which video/image segmentation and localization are cast into a single optimization problem that integrates information from low level appearance cues with that of high level localization cues in a very weakly supervised manner. The proposed framework leverages two representations at different levels, exploits the spatial relationship between bounding boxes and superpixels as linear constraints and  simultaneously discriminates between foreground and background at bounding box and superpixel level. Different from previous approaches that mainly rely on discriminative clustering, we incorporate a foreground model that minimizes the histogram difference of an object across all image frames. Exploiting the geometric relation between the superpixels and bounding boxes enables the transfer of segmentation cues to improve localization output and vice-versa. Inclusion of the foreground model generalizes our discriminative framework to video data where the background tends to be similar and thus, not discriminative. We demonstrate the effectiveness of our unified framework on the YouTube Object video dataset, Internet Object Discovery dataset and Pascal VOC 2007.
Privacy Amplification by Subsampling: Tight Analyses via Couplings and Divergences
Authors: Gilles Barthe, Marco Gaboardi Borja Balle
Published in: Advances in Neural Information Processing Systems 31  (NeurIPS 2018) (Main Conference Track), 2018

Abstract: Differential privacy comes equipped with multiple analytical tools for the
design of private data analyses. One important tool is the so-called "privacy
amplification by subsampling" principle, which ensures that a differentially
private mechanism run on a random subsample of a population provides higher
privacy guarantees than when run on the entire population. Several instances
of this principle have been studied for different random subsampling methods,
each with an ad-hoc analysis.  In this paper we present a general method that
recovers and improves prior analyses, yields lower bounds and derives new
instances of privacy amplification by subsampling. Our method leverages a
characterization of differential privacy as a divergence which emerged in the
program verification community. Furthermore, it introduces new tools,
including advanced joint convexity and privacy profiles, which might be of
independent interest.
The Description Length of Deep Learning models
Authors: Yann Ollivier Léonard Blier
Published in: Advances in Neural Information Processing Systems 31  (NeurIPS 2018) (Main Conference Track), 2018

Abstract: Deep learning models often have more parameters than observations, and still perform well. This is sometimes described as a paradox. In this work, we show experimentally that despite their huge number of parameters, deep neural networks can compress the data losslessly even when taking the cost of encoding the parameters into account. Such a compression viewpoint originally motivated the use of variational methods in neural networks. However, we show that these variational methods provide surprisingly poor compression bounds, despite being explicitly built to minimize such bounds. This might explain the relatively poor practical performance of variational methods in deep learning. Better encoding methods, imported from the Minimum Description Length (MDL) toolbox, yield much better compression values on deep networks.
Semi-crowdsourced Clustering with Deep Generative Models
Authors: TIAN TIAN, Jiaxin Shi, Jun Zhu, Bo Zhang Yucen Luo
Published in: Advances in Neural Information Processing Systems 31  (NeurIPS 2018) (Main Conference Track), 2018

Abstract: We consider the semi-supervised clustering problem where crowdsourcing provides noisy information about the pairwise comparisons on a small subset of data, i.e., whether a sample pair is in the same cluster. We propose a new approach that includes a deep generative model (DGM) to characterize low-level features of the data, and a statistical relational model for noisy pairwise annotations on its subset. The two parts share the latent variables. To make the model automatically trade-off between its complexity and fitting data, we also develop its fully Bayesian variant. The challenge of inference is addressed by fast (natural-gradient) stochastic variational inference algorithms, where we effectively combine variational message passing for the relational part and amortized learning of the DGM under a unified framework. Empirical results on synthetic and real-world datasets show that our model outperforms previous crowdsourced clustering methods.
Scalable Laplacian K-modes
Authors: Eric Granger, Ismail Ben Ayed Imtiaz Ziko
Published in: Advances in Neural Information Processing Systems 31  (NeurIPS 2018) (Main Conference Track), 2018

Abstract: We advocate Laplacian K-modes for joint clustering and density mode finding,
and propose a concave-convex relaxation of the problem, which yields a parallel
algorithm that scales up to large datasets and high dimensions. We optimize a tight
bound (auxiliary function) of our relaxation, which, at each iteration, amounts to
computing an independent update for each cluster-assignment variable, with guar-
anteed convergence. Therefore, our bound optimizer can be trivially distributed
for large-scale data sets. Furthermore, we show that the density modes can be
obtained as byproducts of the assignment variables via simple maximum-value
operations whose additional computational cost is linear in the number of data
points. Our formulation does not need storing a full affinity matrix and computing
its eigenvalue decomposition, neither does it perform expensive projection steps
and Lagrangian-dual inner iterates for the simplex constraints of each point. Fur-
thermore, unlike mean-shift, our density-mode estimation does not require inner-
loop gradient-ascent iterates. It has a complexity independent of feature-space
dimension, yields modes that are valid data points in the input set and is appli-
cable to discrete domains as well as arbitrary kernels. We report comprehensive
experiments over various data sets, which show that our algorithm yields very
competitive performances in term of optimization quality (i.e., the value of the
discrete-variable objective at convergence) and clustering accuracy.
Early Stopping for Nonparametric Testing
Authors: Guang Cheng Meimei Liu
Published in: Advances in Neural Information Processing Systems 31  (NeurIPS 2018) (Main Conference Track), 2018

Abstract: Early stopping of iterative algorithms is an algorithmic regularization method to avoid over-fitting in estimation and classification. In this paper, we show that early stopping can also be applied to obtain the minimax optimal testing in a general non-parametric setup. Specifically, a Wald-type test statistic is obtained based on an iterated estimate produced by functional gradient descent algorithms in a reproducing kernel Hilbert space. A notable contribution is to establish a ``sharp'' stopping rule: when the number of iterations achieves an optimal order, testing optimality is achievable; otherwise, testing optimality becomes impossible. As a by-product, a similar sharpness result is also derived for minimax optimal estimation under early stopping. All obtained results hold for various kernel classes, including Sobolev smoothness classes and Gaussian kernel classes.
Non-Adversarial Mapping with VAEs
Authors: Yedid Hoshen
Published in: Advances in Neural Information Processing Systems 31  (NeurIPS 2018) (Main Conference Track), 2018

Abstract: The study of cross-domain mapping without supervision has recently attracted much attention. Much of the recent progress was enabled by the use of adversarial training as well as cycle constraints. The practical difficulty of adversarial training motivates research into non-adversarial methods. In a recent paper, it was shown that cross-domain mapping is possible without the use of cycles or GANs. Although promising, this approach suffers from several drawbacks including costly inference and an optimization variable for every training example preventing the method from using large training sets. We present an alternative approach which is able to achieve non-adversarial mapping using a novel form of Variational Auto-Encoder. Our method is much faster at inference time, is able to leverage large datasets and has a simple interpretation.
Deep Reinforcement Learning in a Handful of Trials using Probabilistic Dynamics Models
Authors: Roberto Calandra, Rowan McAllister, Sergey Levine Kurtland Chua
Published in: Advances in Neural Information Processing Systems 31  (NeurIPS 2018) (Main Conference Track), 2018

Abstract: Model-based reinforcement learning (RL) algorithms can attain excellent sample efficiency, but often lag behind the best model-free algorithms in terms of asymptotic performance. This is especially true with high-capacity parametric function approximators, such as deep networks. In this paper, we study how to bridge this gap, by employing uncertainty-aware dynamics models. We propose a new algorithm called probabilistic ensembles with trajectory sampling (PETS) that combines uncertainty-aware deep network dynamics models with sampling-based uncertainty propagation. Our comparison to state-of-the-art model-based and model-free deep RL algorithms shows that our approach matches the asymptotic performance of model-free algorithms on several challenging benchmark tasks, while requiring significantly fewer samples (e.g. 8 and 125 times fewer samples than Soft Actor Critic and Proximal Policy Optimization respectively on the half-cheetah task).
The challenge of realistic music generation: modelling raw audio at scale
Authors: Aaron van den Oord, Karen Simonyan Sander Dieleman
Published in: Advances in Neural Information Processing Systems 31  (NeurIPS 2018) (Main Conference Track), 2018

Abstract: Realistic music generation is a challenging task. When building generative models of music that are learnt from data, typically high-level representations such as scores or MIDI are used that abstract away the idiosyncrasies of a particular performance. But these nuances are very important for our perception of musicality and realism, so in this work we embark on modelling music in the raw audio domain. It has been shown that autoregressive models excel at generating raw audio waveforms of speech, but when applied to music, we find them biased towards capturing local signal structure at the expense of modelling long-range correlations. This is problematic because music exhibits structure at many different timescales. In this work, we explore autoregressive discrete autoencoders (ADAs) as a means to enable autoregressive models to capture long-range correlations in waveforms. We find that they allow us to unconditionally generate piano music directly in the raw audio domain, which shows stylistic consistency across tens of seconds.
Approximation algorithms for stochastic clustering
Authors: Shi Li, Aravind Srinivasan, Khoa Trinh, Thomas Pensyl David Harris
Published in: Advances in Neural Information Processing Systems 31  (NeurIPS 2018) (Main Conference Track), 2018

Abstract: We consider stochastic settings for clustering, and develop provably-good (approximation) algorithms for a number of these notions. These algorithms allow one to obtain better approximation ratios compared to the usual deterministic clustering setting. Additionally, they offer a number of advantages including providing fairer clustering and clustering which has better long-term behavior for each user. In particular, they ensure that every user is guaranteed to get good service (on average). We also complement some of these with impossibility results.
Inexact trust-region algorithms on Riemannian manifolds
Authors: Bamdev Mishra Hiroyuki Kasai
Published in: Advances in Neural Information Processing Systems 31  (NeurIPS 2018) (Main Conference Track), 2018

Abstract: We consider an inexact variant of the popular Riemannian trust-region algorithm for structured big-data minimization problems. The proposed algorithm approximates the gradient and the Hessian in addition to the solution of a trust-region sub-problem. Addressing large-scale finite-sum problems, we specifically propose sub-sampled algorithms with a fixed bound on sub-sampled Hessian and gradient sizes, where the gradient and Hessian are computed by a random sampling technique. Numerical evaluations demonstrate that the proposed algorithms outperform state-of-the-art Riemannian deterministic and stochastic gradient algorithms across different applications.
Towards Robust Interpretability with Self-Explaining Neural Networks
Authors: Tommi Jaakkola David Alvarez Melis
Published in: Advances in Neural Information Processing Systems 31  (NeurIPS 2018) (Main Conference Track), 2018

Abstract: Most recent work on interpretability of complex machine learning models has focused on estimating a-posteriori explanations for previously trained models around specific predictions. Self-explaining models where interpretability plays a key role already during learning have received much less attention. We propose three desiderata for explanations in general -- explicitness, faithfulness, and stability -- and show that existing methods do not satisfy them. In response, we design self-explaining models in stages, progressively generalizing linear classifiers to complex yet architecturally explicit models. Faithfulness and stability are enforced via regularization specifically tailored to such models. Experimental results across various benchmark datasets show that our framework offers a promising direction for reconciling model complexity and interpretability.
Predictive Uncertainty Estimation via Prior Networks
Authors: Mark Gales Andrey Malinin
Published in: Advances in Neural Information Processing Systems 31  (NeurIPS 2018) (Main Conference Track), 2018

Abstract: Estimating how uncertain an AI system is in its predictions is important to improve the safety of such systems. Uncertainty in predictive can result from uncertainty in model parameters, irreducible \emph{data uncertainty} and uncertainty due to distributional mismatch between the test and training data distributions. Different actions might be taken depending on the source of the uncertainty so it is important to be able to distinguish between them. Recently, baseline tasks and metrics have been defined and several practical methods to estimate uncertainty developed. These methods, however, attempt to model uncertainty due to distributional mismatch either implicitly through \emph{model uncertainty} or as \emph{data uncertainty}. This work proposes a new framework for modeling predictive uncertainty called Prior Networks (PNs) which explicitly models \emph{distributional uncertainty}. PNs do this by parameterizing a prior distribution over predictive distributions. This work focuses on uncertainty for classification and evaluates PNs on the tasks of identifying out-of-distribution (OOD) samples and detecting misclassification on the MNIST and CIFAR-10 datasets, where they are found to outperform previous methods. Experiments on synthetic and MNIST and CIFAR-10 data show that unlike previous non-Bayesian methods PNs are able to distinguish between data and distributional uncertainty.
Graph Oracle Models, Lower Bounds, and Gaps for Parallel Stochastic Optimization
Authors: Jialei Wang, Adam Smith, Brendan McMahan, Nati Srebro Blake E Woodworth
Published in: Advances in Neural Information Processing Systems 31  (NeurIPS 2018) (Main Conference Track), 2018

Abstract: We suggest a general oracle-based framework that captures parallel
  stochastic optimization in different parallelization settings
  described by a dependency graph, and derive generic lower bounds 
  in terms of this graph.  We then use the framework and derive lower
  bounds to study several specific parallel optimization settings,
  including delayed updates and parallel processing with intermittent
  communication.  We highlight gaps between lower and upper bounds on
  the oracle complexity, and cases where the ``natural'' algorithms
  are not known to be optimal.
An Off-policy Policy Gradient Theorem Using Emphatic Weightings
Authors: Eric Graves, Martha White Ehsan Imani
Published in: Advances in Neural Information Processing Systems 31  (NeurIPS 2018) (Main Conference Track), 2018

Abstract: Policy gradient methods are widely used for control in reinforcement learning, particularly for the continuous action setting. There have been a host of theoretically sound algorithms proposed for the on-policy setting, due to the existence of the policy gradient theorem which provides a simplified form for the gradient. In off-policy learning, however, where the behaviour policy is not necessarily attempting to learn and follow the optimal policy for the given task, the existence of such a theorem has been elusive. In this work, we solve this open problem by providing the first off-policy policy gradient theorem. The key to the derivation is the use of emphatic weightings. We develop a new actor-critic algorithm—called Actor Critic with Emphatic weightings (ACE)—that approximates the simplified gradients provided by the theorem. We demonstrate in a simple counterexample that previous off-policy policy gradient methods—particularly OffPAC and DPG—converge to the wrong solution whereas ACE finds the optimal solution.
Multiple-Step Greedy Policies in Approximate and Online Reinforcement Learning
Authors: Gal Dalal, Bruno Scherrer, Shie Mannor Yonathan Efroni
Published in: Advances in Neural Information Processing Systems 31  (NeurIPS 2018) (Main Conference Track), 2018

Abstract: Multiple-step lookahead policies have demonstrated high empirical competence in Reinforcement Learning, via the use of Monte Carlo Tree Search or Model Predictive Control. In a recent work (Efroni et al., 2018), multiple-step greedy policies and their use in vanilla Policy Iteration algorithms were proposed and analyzed. In this work, we study multiple-step greedy algorithms in more practical setups. We begin by highlighting a counter-intuitive difficulty, arising with soft-policy updates: even in the absence of approximations, and contrary to the 1-step-greedy case, monotonic policy improvement is not guaranteed unless the update stepsize is sufficiently large. Taking particular care about this difficulty, we formulate and analyze online and approximate algorithms that use such a multi-step greedy operator.