pwc-archive/papers-with-abstracts huggingface dataset:
Efficient state-space modularization for planning: theory, behavioral and neural signatures
Authors: Daniel McNamee, Daniel M. Wolpert, Mate Lengyel
Date: 2016-12-01 00:00:00
Proceeding: NeurIPS 2016 12

Even in state-spaces of modest size, planning is plagued by the “curse of dimensionality”. This problem is particularly acute in human and animal cognition given the limited capacity of working memory, and the time pressures under which planning often occurs in the natural environment. Hierarchically organized modular representations have long been suggested to underlie the capacity of biological systems to efficiently and flexibly plan in complex environments. However, the principles underlying efficient modularization remain obscure, making it difficult to identify its behavioral and neural signatures. Here, we develop a normative theory of efficient state-space representations which partitions an environment into distinct modules by minimizing the average (information theoretic) description length of planning within the environment, thereby optimally trading off the complexity of planning across and within modules. We show that such optimal representations provide a unifying account for a diverse range of hitherto unrelated phenomena at multiple levels of behavior and neural representation.
Online Bayesian Moment Matching for Topic Modeling with Unknown Number of Topics
Authors: Wei-Shou Hsu, Pascal Poupart
Date: 2016-12-01 00:00:00
Proceeding: NeurIPS 2016 12

Latent Dirichlet Allocation (LDA) is a very popular model for topic modeling as well as many other problems with latent groups.  It is both simple and effective.  When the number of topics (or latent groups) is unknown, the Hierarchical Dirichlet Process (HDP) provides an elegant non-parametric extension; however, it is a complex model and it is difficult to incorporate prior knowledge since the distribution over topics is implicit.  We propose two new models that extend LDA in a simple and intuitive fashion by directly expressing a distribution over the number of topics.  We also propose a new online Bayesian moment matching technique to learn the parameters and the number of topics of those models based on streaming data.  The approach achieves higher log-likelihood than batch and online HDP with fixed hyperparameters on several corpora.
Computing and maximizing influence in linear threshold and triggering models
Authors: Justin T. Khim, Varun Jog, Po-Ling Loh
Date: 2016-12-01 00:00:00
Proceeding: NeurIPS 2016 12

We establish upper and lower bounds for the influence of a set of nodes in certain types of contagion models. We derive two sets of bounds, the first designed for linear threshold models, and the second more broadly applicable to a general class of triggering models, which subsumes the popular independent cascade models, as well. We quantify the gap between our upper and lower bounds in the case of the linear threshold model and illustrate the gains of our upper bounds for independent cascade models in relation to existing results. Importantly, our lower bounds are monotonic and submodular, implying that a greedy algorithm for influence maximization is guaranteed to produce a maximizer within a (1 - 1/e)-factor of the truth. Although the problem of exact influence computation is NP-hard in general, our bounds may be evaluated efficiently. This leads to an attractive, highly scalable algorithm for influence maximization with rigorous theoretical guarantees.
Coevolutionary Latent Feature Processes for Continuous-Time User-Item Interactions
Authors: Yichen Wang, Nan Du, Rakshit Trivedi, Le Song
Date: 2016-12-01 00:00:00
Proceeding: NeurIPS 2016 12
Tasks: Recommendation Systems

Matching users to the right items at the right time is a fundamental task in recommendation systems. As users interact with different items over time, users' and items' feature may evolve and co-evolve over time. Traditional models based on static latent features or discretizing time into epochs can become ineffective for capturing the fine-grained temporal dynamics in the user-item interactions. We propose a coevolutionary latent feature process model that accurately captures the coevolving nature of users' and items' feature. To learn parameters, we design an efficient convex optimization algorithm with a novel low rank space sharing constraints. Extensive experiments on diverse real-world datasets demonstrate significant improvements in user behavior prediction compared to state-of-the-arts.
Optimal Learning for Multi-pass Stochastic Gradient Methods
Authors: Junhong Lin, Lorenzo Rosasco
Date: 2016-12-01 00:00:00
Proceeding: NeurIPS 2016 12

We analyze the learning  properties of the stochastic gradient method when multiple passes over the data and mini-batches are allowed. In particular, we consider the square loss and show that    for  a universal step-size choice, the number of passes acts as a regularization parameter, and optimal finite sample bounds  can be achieved by early-stopping. Moreover, we show that larger step-sizes are allowed when considering mini-batches. Our analysis is based on  a unifying approach, encompassing both batch and stochastic gradient methods as special cases.
Dual Space Gradient Descent for Online Learning
Authors: Trung Le, Tu Nguyen, Vu Nguyen, Dinh Phung
Date: 2016-12-01 00:00:00
Proceeding: NeurIPS 2016 12

One crucial goal in kernel online learning is to bound the model size. Common approaches employ budget maintenance procedures to restrict the model sizes using removal, projection, or merging strategies. Although projection and merging, in the literature, are known to be the most effective strategies, they demand extensive computation whilst removal strategy fails to retain information of the removed vectors. An alternative way to address the model size problem is to apply random features to approximate the kernel function. This allows the model to be maintained directly in the random feature space, hence effectively resolve the curse of kernelization. However, this approach still suffers from a serious shortcoming as it needs to use a high dimensional random feature space to achieve a sufficiently accurate kernel approximation. Consequently, it leads to a significant increase in the computational cost. To address all of these aforementioned challenges, we present in this paper the Dual Space Gradient Descent (DualSGD), a novel framework that utilizes random features as an auxiliary space to maintain information from data points removed during budget maintenance. Consequently, our approach permits the budget to be maintained in a simple, direct and elegant way while simultaneously mitigating the impact of the dimensionality issue on learning performance. We further provide convergence analysis and extensively conduct experiments on five real-world datasets to demonstrate the predictive performance and scalability of our proposed method in comparison with the state-of-the-art baselines.
Learning brain regions via large-scale online structured sparse dictionary learning
Authors: Elvis Dohmatob, Arthur Mensch, Gael Varoquaux, Bertrand Thirion
Date: 2016-12-01 00:00:00
Proceeding: NeurIPS 2016 12
Tasks: Dictionary Learning

We propose a multivariate online dictionary-learning method for obtaining decompositions of brain images with structured and sparse components (aka atoms). Sparsity is to be understood in the usual sense: the dictionary atoms are constrained to contain mostly zeros. This is imposed via an $\ell_1$-norm constraint. By "structured", we mean that the atoms are piece-wise smooth and compact, thus making up blobs, as opposed to scattered patterns of activation. We propose to use a Sobolev (Laplacian) penalty to impose this type of structure. Combining the two penalties, we obtain decompositions that properly delineate brain structures from functional images. This non-trivially extends the online dictionary-learning  work of Mairal et al. (2010), at the price of only a factor of 2 or 3 on the overall running time. Just like the Mairal et al. (2010) reference method, the online nature of our proposed algorithm allows it to scale to arbitrarily sized datasets. Experiments on brain data show that our proposed method extracts structured and denoised dictionaries that are more intepretable and better capture inter-subject variability in small medium, and large-scale regimes alike, compared to state-of-the-art models.
Efficient Neural Codes under Metabolic Constraints
Authors: Zhuo Wang, Xue-Xin Wei, Alan A. Stocker, Daniel D. Lee
Date: 2016-12-01 00:00:00
Proceeding: NeurIPS 2016 12

Neural codes are inevitably shaped by various kinds of biological constraints, \emph{e.g.} noise and metabolic cost. Here we formulate a coding framework which explicitly deals with noise and the metabolic costs associated with the neural representation of information, and analytically derive the optimal neural code for monotonic response functions and arbitrary stimulus distributions. For a single neuron, the theory predicts a family of optimal response functions depending on the metabolic budget and noise characteristics. Interestingly, the well-known histogram equalization solution can be viewed as a special case when metabolic resources are unlimited. For a pair of neurons, our theory suggests that under more severe metabolic constraints, ON-OFF coding is an increasingly more efficient coding scheme compared to ON-ON or OFF-OFF. The advantage could be as large as one-fold, substantially larger than the previous estimation. Some of these predictions could be generalized to the case of large neural populations. In particular, these analytical results may provide a theoretical basis for the predominant segregation into ON- and OFF-cells in early visual processing areas. Overall, we provide a unified framework for optimal neural codes with monotonic tuning curves in the brain, and makes predictions that can be directly tested with physiology experiments.
Efficient High-Order Interaction-Aware Feature Selection Based on Conditional Mutual Information
Authors: Alexander Shishkin, Anastasia Bezzubtseva, Alexey Drutsa, Ilia Shishkov, Ekaterina Gladkikh, Gleb Gusev, Pavel Serdyukov
Date: 2016-12-01 00:00:00
Proceeding: NeurIPS 2016 12
Tasks: feature selection

This study introduces a novel feature selection approach CMICOT, which is a further evolution of filter methods with sequential  forward selection (SFS) whose scoring functions are based on conditional mutual information (MI). We state and study a novel saddle point (max-min) optimization problem to build a scoring function that is able to identify joint interactions between several  features. This method fills the gap of MI-based SFS techniques with high-order dependencies. In this high-dimensional case, the estimation of MI has prohibitively high sample complexity. We mitigate this cost using a greedy approximation and binary representatives what makes our technique able to be effectively used. The superiority of our approach is demonstrated by comparison with recently proposed interaction-aware filters and several interaction-agnostic state-of-the-art ones on ten publicly available benchmark datasets.
Bayesian Intermittent Demand Forecasting for Large Inventories
Authors: Matthias W. Seeger, David Salinas, Valentin Flunkert
Date: 2016-12-01 00:00:00
Proceeding: NeurIPS 2016 12
Tasks: Demand Forecasting

We present a scalable and robust Bayesian method for demand forecasting in the context of a large e-commerce platform, paying special attention to intermittent and bursty target statistics. Inference is approximated by the Newton-Raphson algorithm, reduced to linear-time Kalman smoothing, which allows us to operate on several orders of magnitude larger problems than previous related work. In a study on large real-world sales datasets, our method outperforms competing approaches on fast and medium moving items.
Visual Question Answering with Question Representation Update (QRU)
Authors: Ruiyu Li, Jiaya Jia
Date: 2016-12-01 00:00:00
Proceeding: NeurIPS 2016 12
Tasks: Question Answering, Visual Question Answering, Visual Question Answering (VQA)

Our method aims at reasoning over natural language questions and visual images. Given a natural language question about an image, our model updates the question representation iteratively by selecting image regions relevant to the query and learns to give the correct answer. Our model contains several reasoning layers, exploiting complex visual relations in the visual question answering (VQA) task. The proposed network is end-to-end trainable through back-propagation, where its weights are initialized using pre-trained convolutional neural network (CNN) and gated recurrent unit (GRU). Our method is evaluated on challenging datasets of COCO-QA and VQA and yields state-of-the-art performance.
Learning Parametric Sparse Models for Image Super-Resolution
Authors: Yongbo Li, Weisheng Dong, Xuemei Xie, Guangming Shi, Xin Li, Donglai Xu
Date: 2016-12-01 00:00:00
Proceeding: NeurIPS 2016 12
Tasks: Image Super-Resolution, Super-Resolution

Learning accurate prior knowledge of natural images is of great importance for single image super-resolution (SR). Existing SR methods either learn the prior from the low/high-resolution patch pairs or estimate the prior models from the input low-resolution (LR) image. Specifically, high-frequency details are learned in the former methods. Though effective, they are heuristic and have limitations in dealing with blurred LR images; while the latter suffers from the limitations of frequency aliasing. In this paper, we propose to combine those two lines of ideas for image super-resolution. More specifically, the parametric sparse prior of the desirable high-resolution (HR) image patches are learned from both the input low-resolution (LR) image and a training image dataset. With the learned sparse priors, the sparse codes and thus the HR image patches can be accurately recovered by solving a sparse coding problem. Experimental results show that the proposed SR method outperforms existing state-of-the-art methods in terms of both subjective and objective image qualities.
Blazing the trails before beating the path: Sample-efficient Monte-Carlo planning
Authors: Jean-bastien Grill, Michal Valko, Remi Munos
Date: 2016-12-01 00:00:00
Proceeding: NeurIPS 2016 12

We study the sampling-based planning problem in Markov decision processes (MDPs) that we can access only through a generative model, usually referred to as Monte-Carlo planning. Our objective is to return a good estimate of the optimal value function at any state while minimizing the number of calls to the generative model, i.e. the sample complexity. We propose a new algorithm, TrailBlazer, able to handle MDPs with a finite or an infinite number of transitions from state-action to next states. TrailBlazer is an adaptive algorithm that exploits possible structures of the MDP by exploring only a subset of states reachable by following near-optimal policies. We provide bounds on its sample complexity that depend on a measure of the quantity of near-optimal states. The algorithm behavior can be considered as an extension of Monte-Carlo sampling (for estimating an expectation) to problems that alternate maximization (over actions) and expectation (over next states). Finally, another appealing feature of TrailBlazer is that it is simple to implement and computationally efficient.
Asynchronous Parallel Greedy Coordinate Descent
Authors: Yang You, Xiangru Lian, Ji Liu, Hsiang-Fu Yu, Inderjit S. Dhillon, James Demmel, Cho-Jui Hsieh
Date: 2016-12-01 00:00:00
Proceeding: NeurIPS 2016 12

n this paper, we propose and study an Asynchronous parallel Greedy Coordinate Descent (Asy-GCD) algorithm for minimizing a smooth function with bounded constraints. At each iteration, workers asynchronously conduct greedy coordinate descent updates on a block of variables.  In the first part of the paper, we analyze the theoretical behavior of Asy-GCD and prove a linear convergence rate.  In the second part, we develop an efficient kernel SVM solver based on Asy-GCD in the shared memory multi-core setting.  Since our algorithm is fully asynchronous---each core does not need to idle and wait for the other cores---the  resulting algorithm enjoys good speedup and outperforms existing multi-core kernel SVM solvers including asynchronous stochastic coordinate descent and multi-core LIBSVM.
Assortment Optimization Under the Mallows model
Authors: Antoine Desir, Vineet Goyal, Srikanth Jagabathula, Danny Segev
Date: 2016-12-01 00:00:00
Proceeding: NeurIPS 2016 12
Tasks: Assortment Optimization, Form, model

We consider the assortment optimization problem when customer preferences follow a mixture of Mallows distributions. The assortment optimization problem focuses on determining the revenue/profit maximizing subset of products from a large universe of products; it is an important decision that is commonly faced by retailers in determining what to offer their customers. There are two key challenges: (a) the Mallows distribution lacks a closed-form expression (and requires summing an exponential number of terms) to compute the choice probability and, hence, the expected revenue/profit per customer; and (b) finding the best subset may require an exhaustive search. Our key contributions are an efficiently computable closed-form expression for the choice probability under the Mallows model and a compact mixed integer linear program (MIP) formulation for the assortment problem.
Improved Variational Inference with Inverse Autoregressive Flow
Authors: Durk P. Kingma, Tim Salimans, Rafal Jozefowicz, Xi Chen, Ilya Sutskever, Max Welling
Date: 2016-12-01 00:00:00
Proceeding: NeurIPS 2016 12
Tasks: Image Generation, Variational Inference

The framework of normalizing flows provides a general strategy for flexible variational inference of posteriors over latent variables. We propose a new type of normalizing flow, inverse autoregressive flow (IAF), that, in contrast to earlier published flows, scales well to high-dimensional latent spaces. The proposed flow consists of a chain of invertible transformations, where each transformation is based on an autoregressive neural network. In experiments, we show that IAF significantly improves upon diagonal Gaussian approximate posteriors. In addition, we demonstrate that a novel type of variational autoencoder, coupled with IAF, is competitive with neural autoregressive models in terms of attained log-likelihood on natural images, while allowing significantly faster synthesis.
Algorithms and matching lower bounds for approximately-convex optimization
Authors: Andrej Risteski, Yuanzhi Li
Date: 2016-12-01 00:00:00
Proceeding: NeurIPS 2016 12

In recent years, a rapidly increasing number of applications in practice requires solving non-convex objectives, like training neural networks, learning graphical models, maximum likelihood estimation etc. Though simple heuristics such as gradient descent with very few modifications tend to work well, theoretical understanding is very weak.   We consider possibly the most natural class of non-convex functions where one could hope to obtain provable guarantees: functions that are ``approximately convex'', i.e. functions $\tf: \Real^d \to \Real$ for which there exists a \emph{convex function} $f$ such that for all $x$, $|\tf(x) - f(x)| \le \errnoise$ for a fixed value $\errnoise$. We then want to minimize $\tf$, i.e. output a point $\tx$ such that $\tf(\tx) \le \min_{x} \tf(x) + \err$.   It is quite natural to conjecture that for fixed $\err$, the problem gets harder for larger $\errnoise$, however, the exact dependency of $\err$ and $\errnoise$ is not known. In this paper, we strengthen the known \emph{information theoretic} lower bounds on the trade-off between $\err$ and $\errnoise$ substantially, and exhibit an algorithm that matches these lower bounds for a large class of convex bodies.
Unified Methods for Exploiting Piecewise Linear Structure in Convex Optimization
Authors: Tyler B. Johnson, Carlos Guestrin
Date: 2016-12-01 00:00:00
Proceeding: NeurIPS 2016 12

We develop methods for rapidly identifying important components of a convex optimization problem for the purpose of achieving fast convergence times. By considering a novel problem formulation—the minimization of a sum of piecewise functions—we describe a principled and general mechanism for exploiting piecewise linear structure in convex optimization. This result leads to a theoretically justified working set algorithm and a novel screening test, which generalize and improve upon many prior results on exploiting structure in convex optimization. In empirical comparisons, we study the scalability of our methods. We find that screening scales surprisingly poorly with the size of the problem, while our working set algorithm convincingly outperforms alternative approaches.
Optimal Architectures in a Solvable Model of Deep Networks
Authors: Jonathan Kadmon, Haim Sompolinsky
Date: 2016-12-01 00:00:00
Proceeding: NeurIPS 2016 12

Deep neural networks have received a considerable attention due to the success of their training for real world machine learning applications. They are also of great interest to the understanding of sensory processing in cortical sensory hierarchies. The purpose of this work is to advance our theoretical understanding of the computational benefits of these architectures. Using a simple model of clustered noisy inputs and a simple learning rule, we provide analytically derived recursion relations describing the propagation of the signals along the deep network. By analysis of these equations, and defining performance measures, we show that these model networks have optimal depths. We further explore the dependence of the optimal architecture on the system parameters.
Supervised Learning with Tensor Networks
Authors: Edwin Stoudenmire, David J. Schwab
Date: 2016-12-01 00:00:00
Proceeding: NeurIPS 2016 12
Tasks: General Classification, Tensor Networks

Tensor networks are approximations of high-order tensors which are efficient to work with and have been very successful for physics and mathematics applications. We demonstrate how algorithms for optimizing tensor networks can be adapted to supervised learning tasks by using matrix product states (tensor trains) to parameterize non-linear kernel learning models. For the MNIST data set we obtain less than 1% test set classification error. We discuss an interpretation of the additional structure imparted by the tensor network to the learned model.