pwc-archive/papers-with-abstracts huggingface dataset:
Trading robust representations for sample complexity through self-supervised visual experience
Authors: Andrea Tacchetti, Stephen Voinea, Georgios Evangelopoulos
Date: 2018-12-01 00:00:00
Proceeding: NeurIPS 2018 12
Tasks: One-Shot Learning, Representation Learning, Self-Supervised Learning

Learning in small sample regimes is among the most remarkable features of the human perceptual system. This ability is related to robustness to transformations, which is acquired through visual experience in the form of weak- or self-supervision during development. We explore the idea of allowing artificial systems to learn representations of visual stimuli through weak supervision prior to downstream supervised tasks. We introduce a novel loss function for representation learning using unlabeled image sets and video sequences, and experimentally demonstrate that these representations support one-shot learning and reduce the sample complexity of multiple recognition tasks. We establish the existence of a trade-off between the sizes of weakly supervised, automatically obtained from video sequences, and fully supervised data sets. Our results suggest that equivalence sets other than class labels, which are abundant in unlabeled visual experience, can be used for self-supervised learning of semantically relevant image embeddings.
Invertibility of Convolutional Generative Networks from Partial Measurements
Authors: Fangchang Ma, Ulas Ayaz, Sertac Karaman
Date: 2018-12-01 00:00:00
Proceeding: NeurIPS 2018 12
Tasks: Image Inpainting

In this work, we present new theoretical results on convolutional generative neural networks, in particular their invertibility (i.e., the recovery of input latent code given the network output). The study of network inversion problem is motivated by image inpainting and the mode collapse problem in training GAN. Network inversion is highly non-convex, and thus is typically computationally intractable and without optimality guarantees. However, we rigorously prove that, under some mild technical assumptions, the input of a two-layer convolutional generative network can be deduced from the network output efficiently using simple gradient descent. This new theoretical finding implies that the mapping from the low- dimensional latent space to the high-dimensional image space is bijective (i.e., one-to-one). In addition, the same conclusion holds even when the network output is only partially observed (i.e., with missing pixels). Our theorems hold for 2-layer convolutional generative network with ReLU as the activation function, but we demonstrate empirically that the same conclusion extends to multi-layer networks and networks with other activation functions, including the leaky ReLU, sigmoid and tanh.
Ex ante coordination and collusion in zero-sum multi-player extensive-form games
Authors: Gabriele Farina, Andrea Celli, Nicola Gatti, Tuomas Sandholm
Date: 2018-12-01 00:00:00
Proceeding: NeurIPS 2018 12
Tasks: Form

Recent milestones in equilibrium computation, such as the success of Libratus, show that it is possible to compute strong solutions to two-player zero-sum games in theory and practice. This is not the case for games with more than two players, which remain one of the main open challenges in computational game theory. This paper focuses on zero-sum games where a team of players faces an opponent, as is the case, for example, in Bridge, collusion in poker, and many non-recreational applications such as war, where the colluders do not have time or means of communicating during battle, collusion in bidding, where communication during the auction is illegal, and coordinated swindling in public. The possibility for the team members to communicate before game play—that is, coordinate their strategies ex ante—makes the use of behavioral strategies unsatisfactory. The reasons for this are closely related to the fact that the team can be represented as a single player with imperfect recall. We propose a new game representation, the realization form, that generalizes the sequence form but can also be applied to imperfect-recall games. Then, we use it to derive an auxiliary game that is equivalent to the original one. It provides a sound way to map the problem of finding an optimal ex-ante-correlated strategy for the team to the well-understood Nash equilibrium-finding problem in a (larger) two-player zero-sum perfect-recall game. By reasoning over the auxiliary game, we devise an anytime algorithm, fictitious team-play, that is guaranteed to converge to an optimal coordinated strategy for the team against an optimal opponent, and that is dramatically faster than the prior state-of-the-art algorithm for this problem.
Theoretical guarantees for EM under misspecified Gaussian mixture models
Authors: Raaz Dwivedi, Nhật Hồ, Koulik Khamaru, Martin J. Wainwright, Michael. I. Jordan
Date: 2018-12-01 00:00:00
Proceeding: NeurIPS 2018 12
Tasks: parameter estimation

Recent years have witnessed substantial progress in understanding
  the behavior of EM for mixture models that are correctly specified.
  Given that model misspecification is common in practice, it is
  important to understand EM in this more general setting.  We provide
  non-asymptotic guarantees for population and sample-based EM for
  parameter estimation under a few specific univariate settings of
  misspecified Gaussian mixture models.  Due to misspecification, the
  EM iterates no longer converge to the true model and instead
  converge to the projection of the true model over the set of models
  being searched over.  We provide two classes of theoretical
  guarantees: first, we characterize the bias introduced due to the
  misspecification; and second, we prove that population EM converges
  at a geometric rate to the model projection under a suitable
  initialization condition.  This geometric convergence rate for
  population EM imply a statistical complexity of order $1/\sqrt{n}$
  when running EM with $n$ samples. We validate our theoretical
  findings in different cases via several numerical examples.
Coupled Variational Bayes via Optimization Embedding
Authors: Bo Dai, Hanjun Dai, Niao He, Weiyang Liu, Zhen Liu, Jianshu Chen, Lin Xiao, Le Song
Date: 2018-12-01 00:00:00
Proceeding: NeurIPS 2018 12
Tasks: Variational Inference

Variational inference plays a vital role in learning graphical models, especially on large-scale datasets. Much of its success depends on a proper choice of auxiliary distribution class for posterior approximation. However, how to pursue an auxiliary distribution class that achieves both good approximation ability and computation efficiency remains a core challenge.  In this paper, we proposed coupled variational Bayes which exploits the primal-dual view of the ELBO with the variational distribution class generated by an optimization procedure, which is termed optimization embedding. This flexible function class couples the variational distribution with the original parameters in the graphical models, allowing end-to-end learning of the graphical models by back-propagation through the variational distribution. Theoretically,  we establish an interesting connection to gradient flow and demonstrate the extreme flexibility of this implicit distribution family in the limit sense. Empirically, we demonstrate the effectiveness of the proposed method on multiple graphical models with either continuous or discrete latent variables comparing to state-of-the-art methods.
Adaptive Methods for Nonconvex Optimization
Authors: Manzil Zaheer, Sashank Reddi, Devendra Sachan, Satyen Kale, Sanjiv Kumar
Date: 2018-12-01 00:00:00
Proceeding: NeurIPS 2018 12
Tasks: Stochastic Optimization

Adaptive gradient methods that rely on scaling gradients down by the square root of exponential moving averages of past squared gradients, such RMSProp, Adam, Adadelta have found wide application in optimizing the nonconvex problems that arise in deep learning. However, it has been recently demonstrated that such methods can fail to converge even in simple convex optimization settings. In this work, we provide a new analysis of such methods applied to nonconvex stochastic optimization problems, characterizing the effect of increasing minibatch size. Our analysis shows that under this scenario such methods do converge to stationarity up to the statistical limit of variance in the stochastic gradients (scaled by a constant factor). In particular, our result implies that increasing minibatch sizes enables convergence,  thus providing a way to circumvent the non-convergence issues. Furthermore, we provide a new adaptive optimization algorithm, Yogi, which controls the increase in effective learning rate,  leading to even better performance with similar theoretical guarantees on convergence. Extensive experiments show that Yogi with very little hyperparameter tuning outperforms methods such as Adam in several challenging machine learning tasks.
Variance-Reduced Stochastic Gradient Descent on Streaming Data
Authors: Ellango Jothimurugesan, Ashraf Tahmasbi, Phillip Gibbons, Srikanta Tirthapura
Date: 2018-12-01 00:00:00
Proceeding: NeurIPS 2018 12

We present an algorithm STRSAGA for efficiently maintaining a machine learning model over data points that arrive over time, quickly updating the model as new training data is observed. We present a competitive analysis comparing the sub-optimality of the model maintained by STRSAGA with that of an offline algorithm that is given the entire data beforehand, and analyze the risk-competitiveness of STRSAGA under different arrival patterns. Our theoretical and experimental results show that the risk of STRSAGA is comparable to that of offline algorithms on a variety of input arrival patterns, and its experimental performance is significantly better than prior algorithms suited for streaming data, such as SGD and SSVRG.
Non-delusional Q-learning and value-iteration
Authors: Tyler Lu, Dale Schuurmans, Craig Boutilier
Date: 2018-12-01 00:00:00
Proceeding: NeurIPS 2018 12
Tasks: Q-Learning

We identify a fundamental source of error in Q-learning and other forms of dynamic programming with function approximation. Delusional bias arises when the approximation architecture limits the class of expressible greedy policies. Since standard Q-updates make globally uncoordinated action choices with respect to the expressible policy class, inconsistent or even conflicting Q-value estimates can result, leading to pathological behaviour such as over/under-estimation, instability and even divergence. To solve this problem, we introduce a new notion of policy consistency and define a local backup process that ensures global consistency through the use of information sets---sets that record constraints on policies consistent with backed-up Q-values. We prove that both the model-based and model-free algorithms using this backup remove delusional bias, yielding the first known algorithms that guarantee optimal results under general conditions. These algorithms furthermore only require polynomially many information sets (from a potentially exponential support). Finally, we suggest other practical heuristics for value-iteration and Q-learning that attempt to reduce delusional bias.
Post: Device Placement with Cross-Entropy Minimization and Proximal Policy Optimization
Authors: Yuanxiang Gao, Li Chen, Baochun Li
Date: 2018-12-01 00:00:00
Proceeding: NeurIPS 2018 12
Tasks: CPU, GPU, Reinforcement Learning

Training deep neural networks requires an exorbitant amount of computation resources, including a heterogeneous mix of GPU and CPU devices. It is critical to place operations in a neural network on these devices in an optimal way, so that the training process can complete within the shortest amount of time. The state-of-the-art uses reinforcement learning to learn placement skills by repeatedly performing Monte-Carlo experiments. However, due to its equal treatment of placement samples, we argue that there remains ample room for significant improvements. In this paper, we propose a new joint learning algorithm, called Post, that integrates cross-entropy minimization and proximal policy optimization to achieve theoretically guaranteed optimal efficiency. In order to incorporate the cross-entropy method as a sampling technique, we propose to represent placements using discrete probability distributions, which allows us to estimate an optimal probability mass by maximal likelihood estimation, a powerful tool with the best possible efficiency. We have implemented Post in the Google Cloud platform, and our extensive experiments with several popular neural network training benchmarks have demonstrated clear evidence of superior performance: with the same amount of learning time, it leads to placements that have training times up to 63.7% shorter over the state-of-the-art.
Learning to Reason with Third Order Tensor Products
Authors: Imanol Schlag, Jürgen Schmidhuber
Date: 2018-12-01 00:00:00
Proceeding: NeurIPS 2018 12

We combine Recurrent Neural Networks with Tensor Product Representations to
learn combinatorial representations of sequential data. This improves symbolic
interpretation and systematic generalisation. Our architecture is trained end-to-end
through gradient descent on a variety of simple natural language reasoning tasks,
significantly outperforming the latest state-of-the-art models in single-task and
all-tasks settings. We also augment a subset of the data such that training and test
data exhibit large systematic differences and show that our approach generalises
better than the previous state-of-the-art.
Testing for Families of Distributions via the Fourier Transform
Authors: Alistair Stewart, Ilias Diakonikolas, Clement Canonne
Date: 2018-12-01 00:00:00
Proceeding: NeurIPS 2018 12
Tasks: Two-sample testing

We study the general problem of testing whether an unknown discrete distribution belongs to a specified family of distributions. More specifically, given a distribution family P and sample access to an unknown discrete distribution D , we want to distinguish (with high probability) between the case that D in P and the case that D is ε-far, in total variation distance, from every distribution in P . This is the prototypical hypothesis testing problem that has received significant attention in statistics and, more recently, in computer science. The main contribution of this work is a simple and general testing technique that is applicable to all distribution families whose Fourier spectrum satisfies a certain approximate sparsity property. We apply our Fourier-based framework to obtain near sample-optimal and  computationally efficient testers for the following fundamental distribution families: Sums of Independent Integer Random Variables (SIIRVs), Poisson Multinomial Distributions (PMDs), and Discrete Log-Concave Distributions. For the first two, ours are the first non-trivial testers in the literature, vastly generalizing previous work on testing Poisson Binomial Distributions. For the third, our tester improves on prior work in both sample and time complexity.
Thwarting Adversarial Examples: An L_0-Robust Sparse Fourier Transform
Authors: Mitali Bafna, Jack Murtagh, Nikhil Vyas
Date: 2018-12-01 00:00:00
Proceeding: NeurIPS 2018 12
Tasks: General Classification, image-classification, Image Classification

We give a new algorithm for approximating the Discrete Fourier transform of an approximately sparse signal that is robust to worst-case $L_0$ corruptions, namely that some coordinates of the signal can be corrupt arbitrarily. Our techniques generalize to a wide range of linear transformations that are used in data analysis such as the Discrete Cosine and Sine transforms, the Hadamard transform, and their high-dimensional analogs. We use our algorithm to successfully defend against worst-case $L_0$ adversaries in the setting of image classification. We give experimental results on the Jacobian-based Saliency Map Attack (JSMA) and the CW $L_0$ attack on the MNIST and Fashion-MNIST datasets as well as the Adversarial Patch on the ImageNet dataset.
Low-Rank Tucker Decomposition of Large Tensors Using TensorSketch
Authors: Osman Asif Malik, Stephen Becker
Date: 2018-12-01 00:00:00
Proceeding: NeurIPS 2018 12

We propose two randomized algorithms for low-rank Tucker decomposition of tensors. The algorithms, which incorporate sketching, only require a single pass of the input tensor and can handle tensors whose elements are streamed in any order. To the best of our knowledge, ours are the only algorithms which can do this. We test our algorithms on sparse synthetic data and compare them to multiple other methods. We also apply one of our algorithms to a real dense 38 GB tensor representing a video and use the resulting decomposition to correctly classify frames containing disturbances.
A Simple Cache Model for Image Recognition
Authors: Emin Orhan
Date: 2018-12-01 00:00:00
Proceeding: NeurIPS 2018 12
Tasks: General Classification, Language Modeling, Language Modelling, model

Training large-scale image recognition models is computationally expensive. This raises the question of whether there might be simple ways to improve the test performance of an already trained model without having to re-train or fine-tune it with new data. Here, we show that, surprisingly, this is indeed possible. The key observation we make is that the layers of a deep network close to the output layer contain independent, easily extractable class-relevant information that is not contained in the output layer itself. We propose to extract this extra class-relevant information using a simple key-value cache memory to improve the classification performance of the model at test time. Our cache memory is directly inspired by a similar cache model previously proposed for language modeling (Grave et al., 2017). This cache component does not require any training or fine-tuning; it can be applied to any pre-trained model and, by properly setting only two hyper-parameters, leads to significant improvements in its classification performance. Improvements are observed across several architectures and datasets. In the cache component, using features extracted from layers close to the output (but not from the output layer itself) as keys leads to the largest improvements. Concatenating features from multiple layers to form keys can further improve performance over using single-layer features as keys. The cache component also has a regularizing effect, a simple consequence of which is that it substantially increases the robustness of models against adversarial attacks.
Clebsch–Gordan Nets: a Fully Fourier Space Spherical Convolutional Neural Network
Authors: Risi Kondor, Zhen Lin, Shubhendu Trivedi
Date: 2018-12-01 00:00:00
Proceeding: NeurIPS 2018 12

Recent work by Cohen et al. has achieved state-of-the-art results for learning spherical images in a rotation invariant way by using ideas from group representation theory and noncommutative harmonic analysis. In this paper we propose a generalization of this work that generally exhibits improved performace, but from an implementation point of view is actually simpler. An unusual feature of the proposed architecture is that it uses the Clebsch--Gordan transform as its only source of nonlinearity, thus avoiding repeated forward and backward Fourier transforms. The underlying ideas of the paper generalize to constructing neural networks that are invariant to the action of other compact groups.
Learning To Learn Around A Common Mean
Authors: Giulia Denevi, Carlo Ciliberto, Dimitris Stamos, Massimiliano Pontil
Date: 2018-12-01 00:00:00
Proceeding: NeurIPS 2018 12
Tasks: Meta-Learning

The problem of learning-to-learn (LTL) or meta-learning is gaining increasing attention due to recent empirical evidence of its effectiveness in applications. The goal addressed in LTL is to select an algorithm that works well on tasks sampled from a meta-distribution. In this work, we consider the family of algorithms given by a variant of Ridge Regression, in which the regularizer is the square distance to an unknown mean vector. We show that, in this setting, the LTL problem can be reformulated as a Least Squares (LS) problem and we exploit a novel meta- algorithm to efficiently solve it. At each iteration the meta-algorithm processes only one dataset. Specifically, it firstly estimates the stochastic LS objective function, by splitting this dataset into two subsets used to train and test the inner algorithm, respectively. Secondly, it performs a stochastic gradient step with the estimated value. Under specific assumptions, we present a bound for the generalization error of our meta-algorithm, which suggests the right splitting parameter to choose. When the hyper-parameters of the problem are fixed, this bound is consistent as the number of tasks grows, even if the sample size is kept constant. Preliminary experiments confirm our theoretical findings, highlighting the advantage of our approach, with respect to independent task learning.
Backpropagation with Callbacks: Foundations for Efficient and Expressive Differentiable Programming
Authors: Fei Wang, James Decker, Xilun Wu, Gregory Essertel, Tiark Rompf
Date: 2018-12-01 00:00:00
Proceeding: NeurIPS 2018 12
Tasks: Code Generation, graph construction

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.
Predictive Approximate Bayesian Computation via Saddle Points
Authors: Yingxiang Yang, Bo Dai, Negar Kiyavash, Niao He
Date: 2018-12-01 00:00:00
Proceeding: NeurIPS 2018 12
Tasks: Bayesian Inference, regression

Approximate Bayesian computation (ABC) is an important methodology for Bayesian inference when the likelihood function is intractable. Sampling-based ABC algorithms such as rejection- and K2-ABC are inefficient when the parameters have high dimensions, while the regression-based algorithms such as K- and DR-ABC are hard to scale. In this paper, we introduce an optimization-based ABC framework that addresses these deficiencies. Leveraging a generative model for posterior and joint distribution matching, we show that ABC can be framed as saddle point problems, whose objectives can be accessed directly with samples. We present the predictive ABC algorithm (P-ABC), and provide a probabilistically approximately correct (PAC) bound that guarantees its learning consistency. Numerical experiment shows that P-ABC outperforms both K2- and DR-ABC significantly.