mtybilly/Instruct2DS huggingface dataset:
Learning Deep Parsimonious Representations
Authors: Alex Schwing, Richard Zemel, Raquel Urtasun Renjie Liao
Published in: Advances in Neural Information Processing Systems 29  (NIPS 2016) (Main Conference Track), 2016

Abstract: In this paper we aim at facilitating generalization for deep networks while supporting interpretability of the learned representations. Towards this goal, we propose a clustering based regularization that encourages parsimonious representations. Our k-means style objective is easy to optimize and flexible  supporting various forms of clustering, including sample and spatial clustering as well as co-clustering. We demonstrate the effectiveness of our approach on the tasks of unsupervised learning, classification, fine grained categorization and zero-shot learning.
Scalable Adaptive Stochastic Optimization Using Random Projections
Authors: Brian McWilliams, Yannic Kilcher, Joachim M Buhmann, Nicolai Meinshausen Gabriel Krummenacher
Published in: Advances in Neural Information Processing Systems 29  (NIPS 2016) (Main Conference Track), 2016

Abstract: Adaptive stochastic gradient methods such as AdaGrad have gained popularity in particular for training deep neural networks. The most commonly used and studied variant maintains a diagonal matrix approximation to second order information by accumulating past gradients which are used to tune the step size adaptively. In certain situations the full-matrix variant of AdaGrad is expected to attain better performance, however in high dimensions it is computationally impractical. We present Ada-LR and RadaGrad two computationally efficient approximations to full-matrix AdaGrad based on randomized dimensionality reduction. They are able to capture dependencies between features and achieve similar performance to full-matrix AdaGrad but at a much smaller computational cost. We show that the regret of Ada-LR is close to the regret of full-matrix AdaGrad which can have an up-to exponentially smaller dependence on the dimension than the diagonal variant. Empirically, we show that Ada-LR and RadaGrad perform similarly to full-matrix AdaGrad. On the task of training convolutional neural networks as well as recurrent neural networks, RadaGrad achieves faster convergence than diagonal AdaGrad.
Graphons, mergeons, and so on!
Authors: Mikhail Belkin, Yusu Wang Justin Eldridge
Published in: Advances in Neural Information Processing Systems 29  (NIPS 2016) (Main Conference Track), 2016

Abstract: In this work we develop a theory of hierarchical clustering for graphs. Our modelling assumption is that graphs are sampled from a graphon, which is a powerful and general model for generating graphs and analyzing large networks.  Graphons are a  far richer class of graph models than stochastic blockmodels, the primary setting for recent progress in the statistical theory of graph clustering. We define what it means for an algorithm to produce the ``correct" clustering, give sufficient conditions in which a method is statistically consistent, and provide an explicit algorithm satisfying these properties.
Man is to Computer Programmer as Woman is to Homemaker? Debiasing Word Embeddings
Authors: Kai-Wei Chang, James Y Zou, Venkatesh Saligrama, Adam T Kalai Tolga Bolukbasi
Published in: Advances in Neural Information Processing Systems 29  (NIPS 2016) (Main Conference Track), 2016

Abstract: The blind application of machine learning runs the risk of amplifying biases present in data. Such a danger is facing us with word embedding, a popular framework to represent text data as vectors which has been used in many machine learning and natural language processing tasks. We show that even word embeddings trained on Google News articles exhibit female/male gender stereotypes to a disturbing extent. This raises concerns because their widespread use, as we describe, often tends to amplify these biases. Geometrically, gender bias is first shown to be captured by a direction in the word embedding. Second, gender neutral words are shown to be linearly separable from gender definition words in the word embedding. Using these properties, we provide a methodology for modifying an embedding to remove gender stereotypes, such as the association between the words receptionist and female, while maintaining desired associations such as between the words queen and female.  Using crowd-worker evaluation as well as standard benchmarks, we empirically demonstrate that our algorithms significantly reduce gender bias in embeddings while preserving the its useful properties such as the ability to cluster related concepts and to solve analogy tasks. The resulting embeddings can be used in applications without amplifying gender bias.
Memory-Efficient Backpropagation Through Time
Authors: Remi Munos, Ivo Danihelka, Marc Lanctot, Alex Graves Audrunas Gruslys
Published in: Advances in Neural Information Processing Systems 29  (NIPS 2016) (Main Conference Track), 2016

Abstract: We propose a novel approach to reduce memory consumption of the backpropagation through time (BPTT) algorithm when training recurrent neural networks (RNNs). Our approach uses dynamic programming to balance a trade-off between caching of intermediate results and recomputation. The algorithm is capable of tightly fitting within almost any user-set memory budget while finding an optimal execution policy minimizing the computational cost. Computational devices have limited memory capacity and maximizing a computational performance given a fixed memory budget is a practical use-case. We provide asymptotic computational upper bounds for various regimes. The algorithm is particularly effective for long sequences. For sequences of length 1000, our algorithm saves 95\% of memory usage while using only one third more time per iteration than the standard BPTT.
Solving Marginal MAP Problems with NP Oracles and Parity Constraints
Authors: Zhiyuan Li, Stefano Ermon, Carla P. Gomes, Bart Selman Yexiang Xue
Published in: Advances in Neural Information Processing Systems 29  (NIPS 2016) (Main Conference Track), 2016

Abstract: Arising from many applications at the intersection of decision-making and machine learning, Marginal Maximum A Posteriori (Marginal MAP) problems unify the two main classes of inference, namely maximization (optimization) and marginal inference (counting), and are believed to have higher complexity than both of them. We propose XORMMAP, a novel approach to solve the Marginal MAP problem, which represents the intractable counting subproblem with queries to NP oracles, subject to additional parity constraints. XORMMAP provides a constant factor approximation to the Marginal MAP problem, by encoding it as a single optimization in a  polynomial size of the original problem. We evaluate our approach in several machine learning and decision-making applications, and show that our approach outperforms several state-of-the-art Marginal MAP solvers.
Differential Privacy without Sensitivity
Authors: HItomi Arai, Issei Sato, Hiroshi Nakagawa Kentaro Minami
Published in: Advances in Neural Information Processing Systems 29  (NIPS 2016) (Main Conference Track), 2016

Abstract: The exponential mechanism is a general method to construct a randomized estimator that satisfies $(\varepsilon, 0)$-differential privacy. Recently, Wang et al. showed that the Gibbs posterior, which is a data-dependent probability distribution that contains the Bayesian posterior, is essentially equivalent to the exponential mechanism under certain boundedness conditions on the loss function. While the exponential mechanism provides a way to build an $(\varepsilon, 0)$-differential private algorithm, it requires boundedness of the loss function, which is quite stringent for some learning problems. In this paper, we focus on $(\varepsilon, \delta)$-differential privacy of Gibbs posteriors with convex and Lipschitz loss functions. Our result extends the classical exponential mechanism, allowing the loss functions to have an unbounded sensitivity.
Adaptive Smoothed Online Multi-Task Learning
Authors: Hanxiao Liu, Jaime Carbonell, Yiming Yang Keerthiram Murugesan
Published in: Advances in Neural Information Processing Systems 29  (NIPS 2016) (Main Conference Track), 2016

Abstract: This paper addresses the challenge of jointly learning both the per-task model parameters and the inter-task relationships in a multi-task online learning setting. The proposed algorithm features probabilistic interpretation, efficient updating rules and flexible modulation on whether learners focus on their specific task or on jointly address all tasks.  The paper also proves a sub-linear regret bound as compared to the best linear predictor in hindsight. Experiments over three multi-task learning benchmark datasets show advantageous performance of the proposed approach over several state-of-the-art online multi-task learning baselines.
Efficient and Robust Spiking Neural Circuit for Navigation Inspired by Echolocating Bats
Authors: Yash H Malviya, Bipin Rajendran Pulkit Tandon
Published in: Advances in Neural Information Processing Systems 29  (NIPS 2016) (Main Conference Track), 2016

Abstract: We demonstrate a spiking neural circuit for azimuth angle detection  inspired by the  echolocation circuits of the Horseshoe bat  Rhinolophus ferrumequinum and utilize it to devise a  model for  navigation and target tracking, capturing several key aspects of information transmission in biology. Our network,  using only  a simple local-information based sensor implementing the cardioid angular gain function, operates at biological  spike rate of  10 Hz.  The network  tracks large angular targets (60 degrees) within 1 sec with a 10%  RMS error. We study the navigational ability of our model for foraging and target localization tasks in  a forest of obstacles  and show that our network requires less than 200X   spike-triggered decisions, while suffering only a 1% loss in performance compared to a  proportional-integral-derivative controller, in the presence of 50% additive noise. Superior performance can be obtained at  a higher average spike rate of  100 Hz  and  1000 Hz, but even the accelerated networks requires 20X and 10X lesser decisions respectively, demonstrating the superior computational efficiency of bio-inspired information processing systems.
Optimal Cluster Recovery in the Labeled Stochastic Block Model
Authors: Alexandre Proutiere Se-Young Yun
Published in: Advances in Neural Information Processing Systems 29  (NIPS 2016) (Main Conference Track), 2016

Abstract: We consider the problem of community detection or clustering in the labeled Stochastic Block Model (LSBM) with a finite number $K$ of clusters of sizes linearly growing with the global population of items $n$. Every pair of items is labeled independently at random, and label $\ell$ appears with probability $p(i,j,\ell)$ between two items in clusters indexed by $i$ and $j$, respectively. The objective is to reconstruct the clusters from the observation of these random labels.   Clustering under the SBM and their extensions has attracted much attention recently. Most existing work aimed at characterizing the set of parameters such that it is possible to infer clusters either positively correlated with the true clusters, or with a vanishing proportion of misclassified items, or exactly matching the true clusters. We find  the set of parameters such that there exists a clustering algorithm with at most $s$ misclassified items in average under the general LSBM and for any $s=o(n)$, which solves one open problem raised in \cite{abbe2015community}. We further develop an algorithm, based on simple spectral methods, that achieves this fundamental performance limit within $O(n \mbox{polylog}(n))$ computations and without the a-priori knowledge of the model parameters.
Relevant sparse codes with variational information bottleneck
Authors: Olivier Marre, Gasper Tkacik Matthew Chalk
Published in: Advances in Neural Information Processing Systems 29  (NIPS 2016) (Main Conference Track), 2016

Abstract: In many applications, it is desirable to extract only the relevant aspects of data. A principled way to do this is the information bottleneck (IB) method, where one seeks a code that maximises information about  a relevance variable, Y, while constraining the information encoded about the original data, X. Unfortunately however, the IB method is computationally demanding when data are high-dimensional and/or non-gaussian. Here we propose an approximate variational scheme for maximising a lower bound on the IB objective, analogous to variational EM. Using this method, we derive an IB algorithm to recover features that are both relevant and sparse. Finally, we demonstrate how kernelised versions of the algorithm can be used to address a broad range of problems with non-linear relation between X and Y.
Learning What and Where to Draw
Authors: Zeynep Akata, Santosh Mohan, Samuel Tenka, Bernt Schiele, Honglak Lee Scott E Reed
Published in: Advances in Neural Information Processing Systems 29  (NIPS 2016) (Main Conference Track), 2016

Abstract: Generative Adversarial Networks (GANs) have recently demonstrated the capability to synthesize compelling real-world images, such as room interiors, album covers, manga, faces, birds, and flowers. While existing models can synthesize images based on global constraints such as a class label or caption, they do not provide control over pose or object location. We propose a new model, the Generative Adversarial What-Where Network (GAWWN), that synthesizes images given instructions describing what content to draw in which location. We show high-quality 128 × 128 image synthesis on the Caltech-UCSD Birds dataset, conditioned on both informal text descriptions and also object location. Our system exposes control over both the bounding box around the bird and its constituent parts. By modeling the conditional distributions over part locations, our system also enables conditioning on arbitrary subsets of parts (e.g. only the beak and tail), yielding an efficient interface for picking part locations.
A Bio-inspired Redundant Sensing Architecture
Authors: Jian Xu, Zhi Yang Anh Tuan Nguyen
Published in: Advances in Neural Information Processing Systems 29  (NIPS 2016) (Main Conference Track), 2016

Abstract: Sensing is the process of deriving signals from the environment that allows artificial systems to interact with the physical world. The Shannon theorem specifies the maximum rate at which information can be acquired. However, this upper bound is hard to achieve in many man-made systems. The biological visual systems, on the other hand, have highly efficient signal representation and processing mechanisms that allow precise sensing. In this work, we argue that redundancy is one of the critical characteristics for such superior performance. We show architectural advantages by utilizing redundant sensing, including correction of mismatch error and significant precision enhancement. For a proof-of-concept demonstration, we have designed a heuristic-based analog-to-digital converter - a zero-dimensional quantizer. Through Monte Carlo simulation with the error probabilistic distribution as a priori, the performance approaching the Shannon limit is feasible. In actual measurements without knowing the error distribution, we observe at least 2-bit extra precision. The results may also help explain biological processes including the dominance of binocular vision, the functional roles of the fixational eye movements, and the structural mechanisms allowing hyperacuity.
Bayesian Optimization with Robust Bayesian Neural Networks
Authors: Aaron Klein, Stefan Falkner, Frank Hutter Jost Tobias Springenberg
Published in: Advances in Neural Information Processing Systems 29  (NIPS 2016) (Main Conference Track), 2016

Abstract: Bayesian optimization is a prominent method for optimizing expensive to evaluate black-box functions that is prominently applied to tuning the hyperparameters of machine learning algorithms. Despite its successes, the prototypical Bayesian optimization approach - using Gaussian process models - does not scale well to either many hyperparameters or many function evaluations. Attacking this lack of scalability and flexibility is thus one of the key challenges of the field. We present a general approach for using flexible parametric models (neural networks) for Bayesian optimization, staying as close to a truly Bayesian treatment as possible. We obtain scalability through stochastic gradient Hamiltonian Monte Carlo, whose robustness we improve via a scale adaptation. Experiments including multi-task Bayesian optimization with 21 tasks, parallel optimization of deep neural networks and deep reinforcement learning show the power and flexibility of this approach.
Statistical Inference for Cluster Trees
Authors: Yen-Chi Chen, Sivaraman Balakrishnan, Alessandro Rinaldo, Larry Wasserman Jisu KIM
Published in: Advances in Neural Information Processing Systems 29  (NIPS 2016) (Main Conference Track), 2016

Abstract: A cluster tree provides an intuitive summary of a density function that reveals essential structure about the high-density clusters. The true cluster tree is estimated from a finite sample from an unknown true density. This paper addresses the basic question of quantifying our  uncertainty by assessing the statistical significance of different features of an empirical cluster tree. We first study a variety of metrics that can be used to compare different trees, analyzing their properties and assessing their suitability for our inference task. We then propose methods to construct and summarize confidence sets for the unknown true cluster tree. We introduce a partial ordering on cluster trees which we use to prune some of the statistically insignificant features of the empirical tree, yielding interpretable and parsimonious cluster trees. Finally, we provide a variety of simulations to illustrate our proposed methods and furthermore demonstrate their utility in the analysis of a Graft-versus-Host Disease (GvHD) data set.
Combinatorial Multi-Armed Bandit with General Reward Functions
Authors: Wei Hu, Fu Li, Jian Li, Yu Liu, Pinyan Lu Wei Chen
Published in: Advances in Neural Information Processing Systems 29  (NIPS 2016) (Main Conference Track), 2016

Abstract: In this paper, we study the stochastic combinatorial multi-armed bandit (CMAB) framework that allows a general nonlinear reward function, whose expected value may not depend only on the means of the input random variables but possibly on the entire distributions of these variables. Our framework enables a much larger class of reward functions such as the $\max()$ function and nonlinear utility functions. Existing techniques relying on accurate estimations of the means of random variables, such as the upper confidence bound (UCB) technique, do not work directly on these functions. We propose a new algorithm called stochastically dominant confidence bound (SDCB), which estimates the distributions of underlying random variables and their stochastically dominant confidence bounds. We prove that SDCB can achieve $O(\log T)$ distribution-dependent regret and $\tilde{O}(\sqrt{T})$ distribution-independent regret, where $T$ is the time horizon. We apply our results to the $K$-MAX problem and expected utility maximization problems. In particular, for $K$-MAX, we provide the first polynomial-time approximation scheme (PTAS) for its offline problem, and give the first $\tilde{O}(\sqrt T)$ bound on the $(1-\epsilon)$-approximation regret of its online problem, for any $\epsilon>0$.
Learning Sensor Multiplexing Design through Back-propagation
Authors: Ayan Chakrabarti
Published in: Advances in Neural Information Processing Systems 29  (NIPS 2016) (Main Conference Track), 2016

Abstract: Recent progress on many imaging and vision tasks has been driven by the use of deep feed-forward neural networks, which are trained by propagating gradients of a loss defined on the final output, back through the network up to the first layer that operates directly on the image. We propose back-propagating one step further---to learn camera sensor designs jointly with networks that carry out inference on the images they capture. In this paper, we specifically consider the design and inference problems in a typical color camera---where the sensor is able to measure only one color channel at each pixel location, and computational inference is required to reconstruct a full color image. We learn the camera sensor's color multiplexing pattern by encoding it as layer whose learnable weights determine which color channel, from among a fixed set, will be measured at each location. These weights are jointly trained with those of a reconstruction network that operates on the corresponding sensor measurements to produce a full color image. Our network achieves significant improvements in accuracy over the traditional Bayer pattern used in most color cameras. It automatically learns to employ a sparse color measurement approach similar to that of a recent design, and moreover, improves upon that design by learning an optimal layout for these measurements.
Short-Dot: Computing Large Linear Transforms Distributedly Using Coded Short Dot Products
Authors: Viveck Cadambe, Pulkit Grover Sanghamitra Dutta
Published in: Advances in Neural Information Processing Systems 29  (NIPS 2016) (Main Conference Track), 2016

Abstract: Faced with saturation of Moore's law and increasing size and dimension of data, system designers have increasingly resorted to parallel and distributed computing to reduce computation time of machine-learning algorithms. However, distributed computing is often bottle necked by a small fraction of slow processors called "stragglers" that reduce the speed of computation because the fusion node has to wait for all processors to complete their processing. To combat the effect of stragglers, recent literature proposes introducing redundancy in computations across processors, e.g., using repetition-based strategies or erasure codes. The fusion node can exploit this redundancy by completing the computation using outputs from only a subset of the processors, ignoring the stragglers. In this paper, we propose a novel technique - that we call "Short-Dot" - to introduce redundant computations in a coding theory inspired fashion, for computing linear transforms of long vectors. Instead of computing long dot products as required in the original linear transform, we construct a larger number of redundant and short dot products that can be computed more efficiently at individual processors. Further, only a subset of these short dot products are required at the fusion node to finish the computation successfully. We demonstrate through probabilistic analysis as well as experiments on computing clusters that Short-Dot offers significant speed-up compared to existing techniques. We also derive trade-offs between the length of the dot-products and the resilience to stragglers (number of processors required to finish), for any such strategy and compare it to that achieved by our strategy.
SEBOOST - Boosting Stochastic Learning Using Subspace Optimization Techniques
Authors: Rom Herskovitz, Boris Ginsburg, Michael Zibulevsky Elad Richardson
Published in: Advances in Neural Information Processing Systems 29  (NIPS 2016) (Main Conference Track), 2016

Abstract: We present SEBOOST, a technique for boosting the performance of existing stochastic optimization methods. SEBOOST applies a secondary optimization process in the subspace spanned by the last steps and descent directions. The method was inspired by the SESOP optimization method for large-scale problems, and has been adapted for the stochastic learning framework. It can be applied on top of any existing optimization method with no need to tweak the internal algorithm. We show that the method is able to boost the performance of different algorithms, and make them more robust to changes in their hyper-parameters. As the boosting steps of SEBOOST are applied between large sets of descent steps, the additional subspace optimization hardly increases the overall computational burden. We introduce two hyper-parameters that control the balance between the baseline method and the secondary optimization process. The method was evaluated on several deep learning tasks, demonstrating promising results.
VIME: Variational Information Maximizing Exploration
Authors: Xi Chen, Xi Chen, Yan Duan, John Schulman, Filip De Turck, Pieter Abbeel Rein Houthooft
Published in: Advances in Neural Information Processing Systems 29  (NIPS 2016) (Main Conference Track), 2016

Abstract: Scalable and effective exploration remains a key challenge in reinforcement learning (RL). While there are methods with optimality guarantees in the setting of discrete state and action spaces, these methods cannot be applied in high-dimensional deep RL scenarios. As such, most contemporary RL relies on simple heuristics such as epsilon-greedy exploration or adding Gaussian noise to the controls. This paper introduces Variational Information Maximizing Exploration (VIME), an exploration strategy based on maximization of information gain about the agent's belief of environment dynamics. We propose a practical implementation, using variational inference in Bayesian neural networks which efficiently handles continuous state and action spaces. VIME modifies the MDP reward function, and can be applied with several different underlying RL algorithms. We demonstrate that VIME achieves significantly better performance compared to heuristic exploration methods across a variety of continuous control tasks and algorithms, including tasks with very sparse rewards.
Toward Deeper Understanding of Neural Networks: The Power of Initialization and a Dual View on Expressivity
Authors: Roy Frostig, Yoram Singer Amit Daniely
Published in: Advances in Neural Information Processing Systems 29  (NIPS 2016) (Main Conference Track), 2016

Abstract: We develop a general duality between neural networks and compositional kernel Hilbert spaces. We introduce the notion of a computation skeleton, an acyclic graph that succinctly describes both a family of neural networks and a kernel space. Random neural networks are generated from a skeleton through node replication followed by sampling from a normal distribution to assign weights. The kernel space consists of functions that arise by compositions, averaging, and non-linear transformations governed by the skeleton's graph topology and activation functions. We prove that random networks induce representations which approximate the kernel space. In particular, it follows that random weight initialization often yields a favorable starting point for optimization despite the worst-case intractability of training neural networks.
Unsupervised Domain Adaptation with Residual Transfer Networks
Authors: Han Zhu, Jianmin Wang, Michael I Jordan Mingsheng Long
Published in: Advances in Neural Information Processing Systems 29  (NIPS 2016) (Main Conference Track), 2016

Abstract: The recent success of deep neural networks relies on massive amounts of labeled data. For a target task where labeled data is unavailable, domain adaptation can transfer a learner from a different source domain. In this paper, we propose a new approach to domain adaptation in deep networks that can jointly learn adaptive classifiers and transferable features from labeled data in the source domain and unlabeled data in the target domain. We relax a shared-classifier assumption made by previous methods and assume that the source classifier and target classifier differ by a residual function. We enable classifier adaptation by plugging several layers into deep network to explicitly learn the residual function with reference to the target classifier. We fuse features of multiple layers with tensor product and embed them into reproducing kernel Hilbert spaces to match distributions for feature adaptation. The adaptation can be achieved in most feed-forward models by extending them with new residual layers and loss functions, which can be trained efficiently via back-propagation. Empirical evidence shows that the new approach outperforms state of the art methods on standard domain adaptation benchmarks.
Stochastic Gradient MCMC with Stale Gradients
Authors: Nan Ding, Chunyuan Li, Yizhe Zhang, Lawrence Carin Changyou Chen
Published in: Advances in Neural Information Processing Systems 29  (NIPS 2016) (Main Conference Track), 2016

Abstract: Stochastic gradient MCMC (SG-MCMC) has played an important role in large-scale Bayesian learning, with well-developed theoretical convergence properties. In such applications of SG-MCMC, it is becoming increasingly popular to employ distributed systems, where stochastic gradients are computed based on some outdated parameters, yielding what are termed stale gradients. While stale gradients could be directly used in SG-MCMC, their impact on convergence properties has not been well studied. In this paper we develop theory to show that while the bias and MSE of an SG-MCMC algorithm depend on the staleness of stochastic gradients, its estimation variance (relative to the expected estimate, based on a prescribed number of samples) is independent of it. In a simple Bayesian distributed system with SG-MCMC, where stale gradients are computed asynchronously by a set of workers, our theory indicates a linear speedup on the decrease of estimation variance w.r.t. the number of workers. Experiments on synthetic data and deep neural networks validate our theory, demonstrating the effectiveness and scalability of SG-MCMC with stale gradients.
Efficient Nonparametric Smoothness Estimation
Authors: Simon S Du, Barnabas Poczos Shashank Singh
Published in: Advances in Neural Information Processing Systems 29  (NIPS 2016) (Main Conference Track), 2016

Abstract: Sobolev quantities (norms, inner products, and distances) of probability density functions are important in the theory of nonparametric statistics, but have rarely been used in practice, partly due to a lack of practical estimators. They also include, as special cases, L^2 quantities which are used in many applications. We propose and analyze a family of estimators for Sobolev quantities of unknown probability density functions. We bound the finite-sample bias and variance of our estimators, finding that they are generally minimax rate-optimal. Our estimators are significantly more computationally tractable than previous estimators, and exhibit a statistical/computational trade-off allowing them to adapt to computational constraints. We also draw theoretical connections to recent work on fast two-sample testing and empirically validate our estimators on synthetic data.
Adversarial Multiclass Classification: A Risk Minimization Perspective
Authors: Anqi Liu, Kaiser Asif, Brian Ziebart Rizal Fathony
Published in: Advances in Neural Information Processing Systems 29  (NIPS 2016) (Main Conference Track), 2016

Abstract: Recently proposed adversarial classification methods have shown promising results for cost sensitive and multivariate losses. In contrast with empirical risk minimization (ERM) methods, which use convex surrogate losses to approximate the desired non-convex target loss function, adversarial methods minimize non-convex losses by treating the properties of the training data as being uncertain and worst case within a minimax game. Despite this difference in formulation, we recast adversarial classification under zero-one loss as an ERM method with a novel prescribed loss function. We demonstrate a number of theoretical and practical advantages over the very closely related hinge loss ERM methods. This establishes adversarial classification under the zero-one loss as a method that fills the long standing gap in multiclass hinge loss classification, simultaneously guaranteeing Fisher consistency and universal consistency, while also providing dual parameter sparsity and high accuracy predictions in practice.
Long-term Causal Effects via Behavioral Game Theory
Authors: David C. Parkes Panagiotis Toulis
Published in: Advances in Neural Information Processing Systems 29  (NIPS 2016) (Main Conference Track), 2016

Abstract: Planned experiments are the gold standard in reliably comparing the causal effect of switching from a baseline policy to a new policy. % One critical shortcoming of classical experimental methods, however, is that they typically do not take into account the dynamic nature of response to policy changes. For instance, in an experiment where we seek to understand the effects of a new ad pricing policy on auction revenue, agents may adapt their bidding in response to the experimental pricing changes. Thus, causal effects of the new pricing policy after such adaptation period, the {\em long-term causal effects}, are not captured by the classical methodology even though they clearly are more indicative of the value of the new policy. %  Here, we formalize a framework to define and estimate long-term causal effects of   policy changes in multiagent economies.  Central to our approach is behavioral game theory, which we leverage   to formulate the ignorability assumptions that are necessary for causal inference.  Under such assumptions we estimate long-term causal effects through a latent space approach, where a behavioral model of how agents act conditional on their latent behaviors is combined with a temporal model of how behaviors evolve over time.
Sampling for Bayesian Program Learning
Authors: Armando Solar-Lezama, Josh Tenenbaum Kevin Ellis
Published in: Advances in Neural Information Processing Systems 29  (NIPS 2016) (Main Conference Track), 2016

Abstract: Towards learning programs from data, we introduce the problem of   sampling programs from posterior distributions conditioned on that   data. Within this setting, we propose an algorithm that uses a   symbolic solver to efficiently sample programs.  The proposal   combines constraint-based program synthesis with sampling via random   parity constraints.  We give theoretical guarantees on how well the   samples approximate the true posterior, and have empirical results   showing the algorithm is efficient in practice, evaluating our   approach on 22 program learning problems in the domains of text   editing and computer-aided programming.
Unifying Count-Based Exploration and Intrinsic Motivation
Authors: Sriram Srinivasan, Georg Ostrovski, Tom Schaul, David Saxton, Remi Munos Marc Bellemare
Published in: Advances in Neural Information Processing Systems 29  (NIPS 2016) (Main Conference Track), 2016

Abstract: We consider an agent's uncertainty about its environment and the problem of generalizing this uncertainty across states. Specifically, we focus on the problem of exploration in non-tabular reinforcement learning. Drawing inspiration from the intrinsic motivation literature, we use density models to measure uncertainty, and propose a novel algorithm for deriving a pseudo-count from an arbitrary density model. This technique enables us to generalize count-based exploration algorithms to the non-tabular case. We apply our ideas to Atari 2600 games, providing sensible pseudo-counts from raw pixels. We transform these pseudo-counts into exploration bonuses and obtain significantly improved exploration in a number of hard games, including the infamously difficult Montezuma's Revenge.
Learning HMMs with Nonparametric Emissions via Spectral Decompositions of Continuous Matrices
Authors: Maruan Al-Shedivat, Eric P Xing Kirthevasan Kandasamy
Published in: Advances in Neural Information Processing Systems 29  (NIPS 2016) (Main Conference Track), 2016

Abstract: Recently, there has been a surge of interest in using spectral methods for estimating latent variable models. However, it is usually assumed that the distribution of the observations conditioned on the latent variables is either discrete or belongs to a parametric family. In this paper, we study the estimation of an $m$-state hidden Markov model (HMM) with only smoothness assumptions, such as H\"olderian conditions, on the emission densities. By leveraging some recent advances in continuous linear algebra and numerical analysis, we develop a computationally efficient spectral algorithm for learning nonparametric HMMs. Our technique is based on computing an SVD on nonparametric estimates of density functions by viewing them as \emph{continuous matrices}. We derive sample complexity bounds via concentration results for nonparametric density estimation and novel perturbation theory results for continuous matrices. We implement our method using Chebyshev polynomial approximations. Our method is competitive with other baselines on synthetic and real problems and is also very computationally efficient.
Observational-Interventional Priors for Dose-Response Learning
Authors: Ricardo Silva
Published in: Advances in Neural Information Processing Systems 29  (NIPS 2016) (Main Conference Track), 2016

Abstract: Controlled interventions provide the most direct source of information for learning causal effects. In particular, a dose-response curve can be learned by varying the treatment level and observing the corresponding outcomes. However, interventions can be expensive and time-consuming. Observational data, where the treatment is not controlled by a known mechanism, is sometimes available. Under some strong assumptions, observational data allows for the estimation of dose-response curves. Estimating such curves nonparametrically is hard: sample sizes for controlled interventions may be small, while in the observational case a large number of measured confounders may need to be marginalized. In this paper, we introduce a hierarchical Gaussian process prior that constructs a distribution over the dose-response curve by learning from observational data, and reshapes the distribution with a nonparametric affine transform learned from controlled interventions. This function composition from different sources is shown to speed-up learning, which we demonstrate with a thorough sensitivity analysis and an application to modeling the effect of therapy on cognitive skills of premature infants.
Improved Error Bounds for Tree Representations of Metric Spaces
Authors: Facundo Mémoli, Zane T Smith Samir Chowdhury
Published in: Advances in Neural Information Processing Systems 29  (NIPS 2016) (Main Conference Track), 2016

Abstract: Estimating optimal phylogenetic trees or hierarchical clustering trees from metric data is an important problem in evolutionary biology and data analysis. Intuitively, the goodness-of-fit of a metric space to a tree depends on its inherent treeness, as well as other metric properties such as intrinsic dimension. Existing algorithms for embedding metric spaces into tree metrics provide distortion bounds depending on cardinality. Because cardinality is a simple property of any set, we argue that such bounds do not fully capture the rich structure endowed by the metric. We consider an embedding of a metric space into a tree proposed by Gromov. By proving a stability result, we obtain an improved additive distortion bound depending only on the hyperbolicity and doubling dimension of the metric. We observe that Gromov's method is dual to the well-known single linkage hierarchical clustering (SLHC) method. By means of this duality, we are able to transport our results to the setting of SLHC, where such additive distortion bounds were previously unknown.
A Bayesian method for reducing bias in neural representational similarity analysis
Authors: Nicolas W Schuck, Jonathan W Pillow, Yael Niv Mingbo Cai
Published in: Advances in Neural Information Processing Systems 29  (NIPS 2016) (Main Conference Track), 2016

Abstract: In neuroscience, the similarity matrix of neural activity patterns in response to different sensory stimuli or under different cognitive states reflects the structure of neural representational space. Existing methods derive point estimations of neural activity patterns from noisy neural imaging data, and the similarity is calculated from these point estimations. We show that this approach translates structured noise from estimated patterns into spurious bias structure in the resulting similarity matrix, which is especially severe when signal-to-noise ratio is low and experimental conditions cannot be fully randomized in a cognitive task. We propose an alternative Bayesian framework for computing representational similarity in which we treat the covariance structure of neural activity patterns as a hyper-parameter in a generative model of the neural data, and directly estimate this covariance structure from imaging data while marginalizing over the unknown activity patterns. Converting the estimated covariance structure into a correlation matrix offers a much less biased estimate of neural representational similarity. Our method can also simultaneously estimate a signal-to-noise map that informs where the learned representational structure is supported more strongly, and the learned covariance matrix can be used as a structured prior to constrain Bayesian estimation of neural activity patterns. Our code is freely available in Brain Imaging Analysis Kit (Brainiak) (https://github.com/IntelPNI/brainiak), a python toolkit for brain imaging analysis.
Multistage Campaigning in Social Networks
Authors: Xiaojing Ye, Sahar Harati, Le Song, Hongyuan Zha Mehrdad Farajtabar
Published in: Advances in Neural Information Processing Systems 29  (NIPS 2016) (Main Conference Track), 2016

Abstract: We consider control problems for multi-stage campaigning over social networks. The dynamic programming framework is employed to balance the high present reward and large penalty on low future outcome in the presence of extensive uncertainties. In particular, we establish theoretical foundations of optimal campaigning over social networks where the user activities are modeled as a multivariate Hawkes process, and we derive a time dependent linear relation between the intensity of exogenous events and several commonly used objective functions of campaigning. We further develop a convex dynamic programming framework for determining the optimal intervention policy that prescribes the required level of external drive at each stage for the desired campaigning result. Experiments on both synthetic data and the real-world MemeTracker dataset show that our algorithm can steer the user activities for optimal campaigning much more accurately than baselines.
Conditional Image Generation with PixelCNN Decoders
Authors: Nal Kalchbrenner, Lasse Espeholt, koray kavukcuoglu, Oriol Vinyals, Alex Graves Aaron van den Oord
Published in: Advances in Neural Information Processing Systems 29  (NIPS 2016) (Main Conference Track), 2016

Abstract: This work explores conditional image generation with a new image density model based on the PixelCNN architecture. The model can be conditioned on any vector, including descriptive labels or tags, or latent embeddings created by other networks. When conditioned on class labels from the ImageNet database, the model is able to generate diverse, realistic scenes representing distinct animals, objects, landscapes and structures. When conditioned on an embedding produced by a convolutional network given a single image of an unseen face, it generates a variety of new portraits of the same person with different facial expressions, poses and lighting conditions. We also show that conditional PixelCNN can serve as a powerful decoder in an image autoencoder. Additionally, the gated convolutional layers in the proposed model improve the log-likelihood of PixelCNN to match the state-of-the-art performance of PixelRNN on ImageNet, with greatly reduced computational cost.
Global Optimality of Local Search for Low Rank Matrix Recovery
Authors: Behnam Neyshabur, Nati Srebro Srinadh Bhojanapalli
Published in: Advances in Neural Information Processing Systems 29  (NIPS 2016) (Main Conference Track), 2016

Abstract: We show that there are no spurious local minima in the non-convex factorized parametrization of low-rank matrix recovery from incoherent linear measurements.  With noisy measurements we show all local minima are very close to a global optimum.  Together with a curvature bound at saddle points, this yields a polynomial time global convergence guarantee for stochastic gradient descent {\em  from random initialization}.
Tensor Switching Networks
Authors: Andrew M Saxe, Andrew M Saxe, David Cox Chuan-Yung Tsai
Published in: Advances in Neural Information Processing Systems 29  (NIPS 2016) (Main Conference Track), 2016

Abstract: We present a novel neural network algorithm, the Tensor Switching (TS) network, which generalizes the Rectified Linear Unit (ReLU) nonlinearity to tensor-valued hidden units. The TS network copies its entire input vector to different locations in an expanded representation, with the location determined by its hidden unit activity. In this way, even a simple linear readout from the TS representation can implement a highly expressive deep-network-like function. The TS network hence avoids the vanishing gradient problem by construction, at the cost of larger representation size. We develop several methods to train the TS network, including equivalent kernels for infinitely wide and deep TS networks, a one-pass linear learning algorithm, and two backpropagation-inspired representation learning algorithms. Our experimental results demonstrate that the TS network is indeed more expressive and consistently learns faster than standard ReLU networks.
Optimistic Bandit Convex Optimization
Authors: Mehryar Mohri Scott Yang
Published in: Advances in Neural Information Processing Systems 29  (NIPS 2016) (Main Conference Track), 2016

Abstract: We introduce the general and powerful scheme of predicting information re-use in optimization algorithms. This allows us to devise a computationally efficient algorithm for bandit convex optimization with new state-of-the-art guarantees for both Lipschitz loss functions and loss functions with Lipschitz gradients. This is the first algorithm admitting both a polynomial time complexity and a regret that is polynomial in the dimension of the action space that improves upon the original regret bound for Lipschitz loss functions, achieving a regret of $\widetilde O(T^{11/16}d^{3/8})$. Our algorithm further improves upon the best existing polynomial-in-dimension bound (both computationally and in terms of regret) for loss functions with Lipschitz gradients, achieving a regret of $\widetilde O(T^{8/13} d^{5/3})$.
Interpretable Nonlinear Dynamic Modeling of Neural Trajectories
Authors: Ill Memming Park Yuan Zhao
Published in: Advances in Neural Information Processing Systems 29  (NIPS 2016) (Main Conference Track), 2016

Abstract: A central challenge in neuroscience is understanding how neural system implements computation through its dynamics. We propose a nonlinear time series model aimed at characterizing interpretable dynamics from neural trajectories. Our model assumes low-dimensional continuous dynamics in a finite volume. It incorporates a prior assumption about globally contractional dynamics to avoid overly enthusiastic extrapolation outside of the support of observed trajectories. We show that our model can recover qualitative features of the phase portrait such as attractors, slow points, and bifurcations, while also producing reliable long-term future predictions in a variety of dynamical models and in real neural data.
Stein Variational Gradient Descent: A General Purpose Bayesian Inference Algorithm
Authors: Dilin Wang Qiang Liu
Published in: Advances in Neural Information Processing Systems 29  (NIPS 2016) (Main Conference Track), 2016

Abstract: We propose a general purpose variational inference algorithm that forms a natural counterpart of gradient descent for optimization. Our method iteratively transports a set of particles to match the target distribution, by applying a form of functional gradient descent that minimizes the KL divergence. Empirical studies are performed on various real world models and datasets, on which our method is competitive with existing state-of-the-art methods. The derivation of our method is based on a new theoretical result that connects the derivative of KL divergence under smooth transforms with Stein’s identity and a recently proposed kernelized Stein discrepancy, which is of independent interest.