pwc-archive/papers-with-abstracts huggingface dataset:
Wasserstein Training of Restricted Boltzmann Machines
Authors: Grégoire Montavon, Klaus-Robert Müller, Marco Cuturi
Date: 2016-12-01 00:00:00
Proceeding: NeurIPS 2016 12
Tasks: Denoising

Boltzmann machines are able to learn highly complex, multimodal, structured and multiscale real-world data distributions. Parameters of the model are usually learned by minimizing the Kullback-Leibler (KL) divergence from training samples to the learned model. We propose in this work a novel approach for Boltzmann machine training which assumes that a meaningful metric between observations is known. This metric between observations can then be used to define the Wasserstein distance between the distribution induced by the Boltzmann machine on the one hand, and that given by the training sample on the other hand. We derive a gradient of that distance with respect to the model parameters. Minimization of this new objective leads to generative models with different statistical properties. We demonstrate their practical potential on data completion and denoising, for which the metric between observations plays a crucial role.
Probing the Compositionality of Intuitive Functions
Authors: Eric Schulz, Josh Tenenbaum, David K. Duvenaud, Maarten Speekenbrink, Samuel J. Gershman
Date: 2016-12-01 00:00:00
Proceeding: NeurIPS 2016 12
Tasks: regression

How do people learn about complex functional structure? Taking inspiration from other areas of cognitive science, we propose that this is accomplished by harnessing compositionality: complex structure is decomposed into simpler building blocks. We formalize this idea within the framework of Bayesian regression using a grammar over Gaussian process kernels. We show that participants prefer compositional over non-compositional function extrapolations, that samples from the human prior over functions are best described by a compositional model, and that people perceive compositional functions as more predictable than their non-compositional but otherwise similar counterparts. We argue that the compositional nature of intuitive functions is consistent with broad principles of human cognition.
Threshold Learning for Optimal Decision Making
Authors: Nathan F. Lepora
Date: 2016-12-01 00:00:00
Proceeding: NeurIPS 2016 12
Tasks: Bayesian Optimization, Decision Making, Decision Making Under Uncertainty

Decision making under uncertainty is commonly modelled as a process of competitive stochastic evidence accumulation to threshold (the drift-diffusion model). However, it is unknown how animals learn these decision thresholds. We examine threshold learning by constructing a reward function that averages over many trials to Wald's cost function that defines decision optimality. These rewards are highly stochastic and hence challenging to optimize, which we address in two ways: first, a simple two-factor reward-modulated learning rule derived from Williams' REINFORCE method for neural networks; and second, Bayesian optimization of the reward function with a Gaussian process. Bayesian optimization converges in fewer trials than REINFORCE but is slower computationally with greater variance. The REINFORCE method is also a better model of acquisition behaviour in animals and a similar learning rule has been proposed for modelling basal ganglia function.
Minimax Optimal Alternating Minimization for Kernel Nonparametric Tensor Learning
Authors: Taiji Suzuki, Heishiro Kanagawa, Hayato Kobayashi, Nobuyuki Shimizu, Yukihiro Tagami
Date: 2016-12-01 00:00:00
Proceeding: NeurIPS 2016 12
Tasks: Computational Efficiency

We investigate the statistical performance and computational efficiency of the  alternating minimization procedure for nonparametric tensor learning. Tensor modeling has been widely used for capturing the higher order relations between  multimodal data sources. In addition to a linear model,  a nonlinear tensor model has been received much attention recently because of its high flexibility. We consider  an alternating minimization procedure for  a general nonlinear model where the true function  consists of components in a reproducing kernel Hilbert space (RKHS). In this paper, we show that the alternating minimization method achieves linear convergence as an optimization algorithm  and that the generalization error of the resultant estimator yields the minimax optimality. We apply our algorithm to some multitask learning problems and show that the method actually shows favorable performances.
The Product Cut
Authors: Thomas Laurent, James Von Brecht, Xavier Bresson, Arthur Szlam
Date: 2016-12-01 00:00:00
Proceeding: NeurIPS 2016 12
Tasks: graph partitioning

We introduce a theoretical and algorithmic framework for multi-way graph partitioning that relies on a multiplicative cut-based objective. We refer to this objective as the Product Cut. We provide a detailed investigation of the mathematical properties of this objective and an effective algorithm for its optimization. The proposed model has strong mathematical underpinnings, and the corresponding algorithm achieves state-of-the-art performance on benchmark data sets.
Learning Sparse Gaussian Graphical Models with Overlapping Blocks
Authors: Mohammad Javad Hosseini, Su-In Lee
Date: 2016-12-01 00:00:00
Proceeding: NeurIPS 2016 12

We present a novel framework, called GRAB (GRaphical models with overlApping Blocks), to capture densely connected components in a network estimate. GRAB takes as input a data matrix of p variables and n samples, and jointly learns both a network among p variables and densely connected groups of variables (called `blocks'). GRAB has four major novelties as compared to existing network estimation methods: 1) It does not require the blocks to be given a priori. 2) Blocks can overlap. 3) It can jointly learn a network structure and overlapping blocks. 4) It solves a joint optimization problem with the block coordinate descent method that is convex in each step. We show that GRAB reveals the underlying network structure substantially better than four state-of-the-art competitors on synthetic data. When applied to cancer gene expression data, GRAB outperforms its competitors in revealing known functional gene sets and potentially novel genes that drive cancer.
Yggdrasil: An Optimized System for Training Deep Decision Trees at Scale
Authors: Firas Abuzaid, Joseph K. Bradley, Feynman T. Liang, Andrew Feng, Lee Yang, Matei Zaharia, Ameet S. Talwalkar
Date: 2016-12-01 00:00:00
Proceeding: NeurIPS 2016 12
Tasks: CPU

Deep distributed decision trees and tree ensembles have grown in importance due to the need to model increasingly large datasets.  However, PLANET, the standard distributed tree learning algorithm implemented in systems such as \xgboost and Spark MLlib, scales poorly as data dimensionality and tree depths grow.  We present Yggdrasil, a new distributed tree learning method that outperforms existing methods by up to 24x.  Unlike PLANET, Yggdrasil is based on vertical partitioning of the data (i.e., partitioning by feature), along with a set of optimized data structures to reduce the CPU and communication costs of training. Yggdrasil (1) trains directly on compressed data for compressible features and labels; (2) introduces efficient data structures for training on uncompressed data; and (3) minimizes communication between nodes by using sparse bitvectors.  Moreover, while PLANET approximates split points through feature binning, Yggdrasil does not require binning, and we analytically characterize the impact of this approximation. We evaluate Yggdrasil against the MNIST 8M dataset and a high-dimensional dataset at Yahoo; for both, Yggdrasil is faster by up to an order of magnitude.
A forward model at Purkinje cell synapses facilitates cerebellar anticipatory control
Authors: Ivan Herreros, Xerxes Arsiwalla, Paul Verschure
Date: 2016-12-01 00:00:00
Proceeding: NeurIPS 2016 12
Tasks: counterfactual

How does our motor system solve the problem of anticipatory control in spite of a wide spectrum of response dynamics from different musculo-skeletal systems, transport delays as well as response latencies throughout the central nervous system? To a great extent, our highly-skilled motor responses are a result of a reactive feedback system, originating in the brain-stem and spinal cord, combined with a feed-forward anticipatory system, that is adaptively fine-tuned by sensory experience and originates in the cerebellum. Based on that interaction we design the counterfactual predictive control (CFPC) architecture, an anticipatory adaptive motor control scheme in which a feed-forward module, based on the cerebellum, steers an error feedback controller with counterfactual error signals. Those are signals that trigger reactions as actual errors would, but that do not code for any current of forthcoming errors. In order to determine the optimal learning strategy, we derive a novel learning rule for the feed-forward module that involves an eligibility trace and operates at the synaptic level. In particular, our eligibility trace provides a mechanism beyond co-incidence detection in that it convolves a history of prior synaptic inputs with error signals. In the context of cerebellar physiology, this solution implies that Purkinje cell synapses should generate eligibility traces using a forward model of the system being controlled. From an engineering perspective, CFPC provides a general-purpose anticipatory control architecture equipped with a learning rule that exploits the full dynamics of the closed-loop system.
Large-Scale Price Optimization via Network Flow
Authors: Shinji Ito, Ryohei Fujimaki
Date: 2016-12-01 00:00:00
Proceeding: NeurIPS 2016 12
Tasks: Demand Forecasting

This paper deals with price optimization, which is to find the best pricing strategy that maximizes revenue or profit, on the basis of demand forecasting models. Though recent advances in regression technologies have made it possible to reveal price-demand relationship of a number of multiple products, most existing price optimization methods, such as mixed integer programming formulation, cannot handle tens or hundreds of products because of their high computational costs. To cope with this problem, this paper proposes a novel approach based on network flow algorithms. We reveal a connection between supermodularity of the revenue and cross elasticity of demand. On the basis of this connection, we propose an efficient algorithm that employs network flow algorithms. The proposed algorithm can handle hundreds or thousands of products, and returns an exact optimal solution under an assumption regarding cross elasticity of demand. Even in case in which the assumption does not hold, the proposed algorithm can efficiently find approximate solutions as good as can other state-of-the-art methods, as empirical results show.
Online Pricing with Strategic and Patient Buyers
Authors: Michal Feldman, Tomer Koren, Roi Livni, Yishay Mansour, Aviv Zohar
Date: 2016-12-01 00:00:00
Proceeding: NeurIPS 2016 12

We consider a seller with an unlimited supply of a single good, who is faced with a stream of $T$ buyers. Each buyer has a window of time in which she would like to purchase, and would buy at the lowest price in that window, provided that this price is lower than her private value (and otherwise, would not buy at all). In this setting, we give an algorithm that attains $O(T^{2/3})$ regret over any sequence of $T$ buyers with respect to the best fixed price in hindsight, and prove that no algorithm can perform better in the worst case.
Improving PAC Exploration Using the Median Of Means
Authors: Jason Pazis, Ronald E. Parr, Jonathan P. How
Date: 2016-12-01 00:00:00
Proceeding: NeurIPS 2016 12

We present the first application of the median of means in a PAC exploration algorithm for MDPs. Using the median of means allows us to significantly reduce the dependence of our bounds on the range of values that the value function can take, while introducing a dependence on the (potentially much smaller) variance of the Bellman operator. Additionally, our algorithm is the first algorithm with PAC bounds that can be applied to MDPs with unbounded rewards.
Infinite Hidden Semi-Markov Modulated Interaction Point Process
Authors: Matt Zhang, Peng Lin, Ting Guo, Yang Wang, Fang Chen
Date: 2016-12-01 00:00:00
Proceeding: NeurIPS 2016 12
Tasks: State Space Models

The correlation between events is ubiquitous and important for temporal events modelling. In many cases, the correlation exists between not only events' emitted observations, but also their arrival times. State space models (e.g., hidden Markov model) and stochastic interaction point process models (e.g., Hawkes process) have been studied extensively yet separately for the two types of correlations in the past. In this paper, we propose a Bayesian nonparametric approach that considers both types of correlations via unifying and generalizing hidden semi-Markov model and interaction point process model. The proposed approach can simultaneously model both the observations and arrival times of temporal events, and determine the number of latent states from data. A Metropolis-within-particle-Gibbs sampler with ancestor resampling is developed for efficient posterior inference. The approach is tested on both synthetic and real-world data with promising outcomes.
Spatio-Temporal Hilbert Maps for Continuous Occupancy Representation in Dynamic Environments
Authors: Ransalu Senanayake, Lionel Ott, Simon O'Callaghan, Fabio T. Ramos
Date: 2016-12-01 00:00:00
Proceeding: NeurIPS 2016 12
Tasks: Trajectory Planning

We consider the problem of building continuous occupancy representations in  dynamic environments for robotics applications. The problem has hardly been discussed previously due to the complexity of patterns in urban environments,  which have both spatial and temporal dependencies. We address the problem  as learning a kernel classifier on an efficient feature space. The key novelty of  our approach is the incorporation of variations in the time domain into the spatial  domain. We propose a method to propagate motion uncertainty into the kernel using a hierarchical model. The main benefit of this approach is that it can directly predict  the occupancy state of the map in the future from past observations, being a valuable  tool for robot trajectory planning under uncertainty. Our approach preserves the  main computational benefits of static Hilbert maps — using stochastic gradient  descent for fast optimization of model parameters and incremental updates as  new data are captured. Experiments conducted in road intersections of an urban  environment demonstrated that spatio-temporal Hilbert maps can accurately model  changes in the map while outperforming other techniques on various aspects.
Select-and-Sample for Spike-and-Slab Sparse Coding
Authors: Abdul-Saboor Sheikh, Jörg Lücke
Date: 2016-12-01 00:00:00
Proceeding: NeurIPS 2016 12
Tasks: Denoising

Probabilistic inference serves as a popular model for neural processing. It is still unclear, however, how approximate probabilistic inference can be accurate and scalable to very high-dimensional continuous latent spaces. Especially as typical posteriors for sensory data can be expected to exhibit complex latent dependencies including multiple modes. Here, we study an approach that can efficiently be scaled while maintaining a richly structured posterior approximation under these conditions. As example model we use spike-and-slab sparse coding for V1 processing, and combine latent subspace selection with Gibbs sampling (select-and-sample). Unlike factored variational approaches, the method can maintain large numbers of posterior modes and complex latent dependencies. Unlike pure sampling, the method is scalable to very high-dimensional latent spaces. Among all sparse coding approaches with non-trivial posterior approximations (MAP or ICA-like models), we report the largest-scale results. In applications we firstly verify the approach by showing competitiveness in standard denoising benchmarks. Secondly, we use its scalability to, for the first time, study highly-overcomplete settings for V1 encoding using sophisticated posterior representations. More generally, our study shows that very accurate probabilistic inference for multi-modal posteriors with complex dependencies is tractable, functionally desirable and consistent with models for neural inference.
Tractable Operations for Arithmetic Circuits of Probabilistic Models
Authors: Yujia Shen, Arthur Choi, Adnan Darwiche
Date: 2016-12-01 00:00:00
Proceeding: NeurIPS 2016 12

We consider tractable representations of probability distributions and the polytime operations they support.  In particular, we consider a recently proposed arithmetic circuit representation, the Probabilistic Sentential Decision Diagram (PSDD).  We show that PSDD supports a polytime multiplication operator, while they do not support a polytime operator for summing-out variables.  A polytime multiplication operator make PSDDs suitable for a broader class of applications compared to arithmetic circuits, which do not in general support multiplication.  As one example, we show that PSDD multiplication leads to a very simple but effective compilation algorithm for probabilistic graphical models: represent each model factor as a PSDD, and then multiply them.
Greedy Feature Construction
Authors: Dino Oglic, Thomas Gärtner
Date: 2016-12-01 00:00:00
Proceeding: NeurIPS 2016 12
Tasks: regression

We present an effective method for supervised feature construction. The main goal of the approach is to construct a feature representation for which a set of linear hypotheses is of sufficient capacity -- large enough to contain a satisfactory solution to the considered problem and small enough to allow good generalization from a small number of training examples. We achieve this goal with a greedy procedure that constructs features by empirically fitting squared error residuals. The proposed constructive procedure is consistent and can output a rich set of features. The effectiveness of the approach is evaluated empirically by fitting a linear ridge regression model in the constructed feature space and our empirical results indicate a superior performance of our approach over competing methods.
Mistake Bounds for Binary Matrix Completion
Authors: Mark Herbster, Stephen Pasteris, Massimiliano Pontil
Date: 2016-12-01 00:00:00
Proceeding: NeurIPS 2016 12
Tasks: Matrix Completion

We study the problem of completing a binary matrix in an online learning setting. On each trial we predict a matrix entry and then receive the true entry. We propose a Matrix Exponentiated Gradient algorithm [1] to solve this problem. We provide a mistake bound for the algorithm, which scales with the margin complexity [2, 3] of the underlying matrix. The bound suggests an interpretation where each row of the matrix is a prediction task over a finite set of objects, the columns. Using this we show that the algorithm makes a number of mistakes which is comparable up to a logarithmic factor to the number of mistakes made by the Kernel Perceptron with an optimal kernel in hindsight. We discuss applications of the algorithm to predicting as well as the best biclustering and to the problem of predicting the labeling of a graph without knowing the graph in advance.
Kernel Observers: Systems-Theoretic Modeling and Inference of Spatiotemporally Evolving Processes
Authors: Hassan A. Kingravi, Harshal R. Maske, Girish Chowdhary
Date: 2016-12-01 00:00:00
Proceeding: NeurIPS 2016 12
Tasks: valid

We consider the problem of estimating the latent state of a spatiotemporally evolving continuous function using very few sensor measurements. We show that layering a dynamical systems prior over temporal evolution of weights of a kernel model is a valid approach to spatiotemporal modeling that does not necessarily require the design of complex nonstationary kernels. Furthermore, we show that such a predictive model can be utilized to determine sensing locations that guarantee that the hidden state of the phenomena can be recovered with very few measurements. We provide sufficient conditions on the number and spatial location of samples required to guarantee state recovery, and provide a lower bound on the minimum number of samples required to robustly infer the hidden states. Our approach outperforms existing methods in numerical experiments.
Guided Policy Search via Approximate Mirror Descent
Authors: William H. Montgomery, Sergey Levine
Date: 2016-12-01 00:00:00
Proceeding: NeurIPS 2016 12
Tasks: Reinforcement Learning

Guided policy search algorithms can be used to optimize complex nonlinear policies, such as deep neural networks, without directly computing policy gradients in the high-dimensional parameter space. Instead, these methods use supervised learning to train the policy to mimic a “teacher” algorithm, such as a trajectory optimizer or a trajectory-centric reinforcement learning method. Guided policy search methods provide asymptotic local convergence guarantees by construction, but it is not clear how much the policy improves within a small, finite number of iterations. We show that guided policy search algorithms can be interpreted as an approximate variant of mirror descent, where the projection onto the constraint manifold is not exact. We derive a new guided policy search algorithm that is simpler and provides appealing improvement and convergence guarantees in simplified convex and linear settings, and show that in the more general nonlinear setting, the error in the projection step can be bounded. We provide empirical results on several simulated robotic manipulation tasks that show that our method is stable and achieves similar or better performance when compared to prior guided policy search methods, with a simpler formulation and fewer hyperparameters.
The Power of Optimization from Samples
Authors: Eric Balkanski, Aviad Rubinstein, Yaron Singer
Date: 2016-12-01 00:00:00
Proceeding: NeurIPS 2016 12

We consider the problem of optimization from samples of monotone submodular functions with bounded curvature. In numerous applications, the function optimized is not known a priori, but instead learned from data. What are the guarantees we have when optimizing functions from sampled data?  In this paper we show that for any monotone submodular function with curvature c there is a (1 - c)/(1 + c - c^2) approximation algorithm for maximization under cardinality constraints when polynomially-many samples are drawn from the uniform distribution over feasible sets. Moreover, we show that this algorithm is optimal. That is, for any c < 1, there exists a submodular function with curvature c for which no algorithm can achieve a better approximation. The curvature assumption is crucial as for general monotone submodular functions no algorithm can obtain a constant-factor approximation for maximization under a cardinality constraint when observing polynomially-many samples drawn from any distribution over feasible sets, even when the function is statistically learnable.
A Multi-step Inertial Forward-Backward Splitting Method for Non-convex Optimization
Authors: Jingwei Liang, Jalal Fadili, Gabriel Peyré
Date: 2016-12-01 00:00:00
Proceeding: NeurIPS 2016 12
Tasks: BIG-bench Machine Learning

In this paper, we propose a multi-step inertial Forward--Backward splitting algorithm for minimizing the sum of two non-necessarily convex functions, one of which is proper lower semi-continuous while the other is differentiable with a Lipschitz continuous gradient. We first prove global convergence of the scheme with the help of the Kurdyka–Łojasiewicz property. Then, when the non-smooth part is also partly smooth relative to a smooth submanifold, we establish finite identification of the latter and provide sharp local linear convergence analysis. The proposed method is illustrated on a few problems arising from statistics and machine learning.