pwc-archive/papers-with-abstracts huggingface dataset:
Buy-in-Bulk Active Learning
Authors: Liu Yang, Jaime Carbonell
Date: 2013-12-01 00:00:00
Proceeding: NeurIPS 2013 12
Tasks: Active Learning

In many practical applications of active learning, it is more cost-effective to request labels in large batches, rather than one-at-a-time. This is because the cost of labeling a large batch of examples at once is often sublinear in the number of examples in the batch. In this work, we study the label complexity of active learning algorithms that request labels in a given number of batches, as well as the tradeoff between the total number of queries and the number of rounds allowed. We additionally study the total cost sufficient for learning, for an abstract notion of the cost of requesting the labels of a given number of examples at once. In particular, we find that for sublinear cost functions, it is often desirable to request labels in large batches (i.e., buying in bulk); although this may increase the total number of labels requested, it reduces the total cost required for learning.
Contrastive Learning Using Spectral Methods
Authors: James Y. Zou, Daniel J. Hsu, David C. Parkes, Ryan P. Adams
Date: 2013-12-01 00:00:00
Proceeding: NeurIPS 2013 12
Tasks: Articles, Contrastive Learning

In many natural settings, the analysis goal is not to characterize a single data set in isolation, but rather to understand the difference between one set of observations and another. For example, given a background corpus of news articles together with writings of a particular author, one may want a topic model that explains word patterns and themes specific to the author. Another example comes from genomics, in which biological signals may be collected from different regions of a genome, and one wants a model that captures the differential statistics observed in these regions. This paper formalizes this notion of contrastive learning for  mixture models, and develops spectral algorithms for inferring mixture components specific to a foreground data set when contrasted with a background data set. The method builds on recent moment-based estimators and tensor decompositions for latent variable models, and has the intuitive feature of using background data statistics to appropriately modify moments estimated from foreground data. A key advantage of the method is that the background data need only be coarsely modeled, which is important when the background is too complex, noisy, or not of interest. The method is demonstrated on applications in contrastive topic modeling and genomic sequence analysis.
Message Passing Inference with Chemical Reaction Networks
Authors: Nils E. Napp, Ryan P. Adams
Date: 2013-12-01 00:00:00
Proceeding: NeurIPS 2013 12

Recent work on molecular programming has explored new possibilities for computational abstractions with biomolecules, including logic gates, neural networks, and linear systems.  In the future such abstractions might enable nanoscale devices that can sense and control the world at a molecular scale.  Just as in macroscale robotics, it is critical that such devices can learn about their environment and reason under uncertainty. At this small scale, systems are typically modeled as chemical reaction networks. In this work, we develop a procedure that can take arbitrary probabilistic graphical models, represented as factor graphs over discrete random variables, and compile them into chemical reaction networks that implement inference.  In particular, we show that marginalization based on sum-product message passing can be implemented in terms of reactions between chemical species whose concentrations represent probabilities.  We show algebraically that the steady state concentration of these species correspond to the marginal distributions of the random variables in the graph and validate the results in simulations.  As with standard sum-product inference, this procedure yields exact results for tree-structured graphs, and approximate solutions for loopy graphs.
Eluder Dimension and the Sample Complexity of Optimistic Exploration
Authors: Daniel Russo, Benjamin Van Roy
Date: 2013-12-01 00:00:00
Proceeding: NeurIPS 2013 12
Tasks: Thompson Sampling

This paper considers the sample complexity of the multi-armed bandit with dependencies among the arms. Some of the most successful algorithms for this problem use the principle of optimism in the face of uncertainty to guide exploration. The clearest example of this is the class of upper confidence bound (UCB) algorithms, but recent work has shown that a simple posterior sampling algorithm, sometimes called Thompson sampling, also shares a close theoretical connection with optimistic approaches. In this paper, we develop a regret bound that holds for both classes of algorithms. This bound applies broadly and can be specialized to many model classes. It depends on a new notion we refer to as the eluder dimension, which measures the degree of dependence among action rewards. Compared to UCB algorithm regret bounds for specific model classes, our general bound matches the best available for linear models and is stronger than the best available for generalized linear models.
Learning word embeddings efficiently with noise-contrastive estimation
Authors: Andriy Mnih, Koray Kavukcuoglu
Date: 2013-12-01 00:00:00
Proceeding: NeurIPS 2013 12
Tasks: Learning Word Embeddings, Word Embeddings, Word Similarity

Continuous-valued word embeddings learned by neural language models have recently been shown to capture semantic and syntactic information about words very well, setting performance records on several word similarity tasks.  The best results are obtained by learning high-dimensional embeddings from very large quantities of data, which makes scalability of the training method a critical factor.  We propose a simple and scalable new approach to learning word embeddings based on training log-bilinear models with noise-contrastive estimation.  Our approach is simpler, faster, and produces better results than the current state-of-the art method of Mikolov et al. (2013a). We achieve results comparable to the best ones reported, which were obtained on a cluster, using four times less data and more than an order of magnitude less computing time. We also investigate several model types and find that the embeddings learned by the simpler models perform at least as well as those learned by the more complex ones.
Sparse Inverse Covariance Estimation with Calibration
Authors: Tuo Zhao, Han Liu
Date: 2013-12-01 00:00:00
Proceeding: NeurIPS 2013 12
Tasks: Model Selection, parameter estimation

We propose a semiparametric procedure for estimating high dimensional sparse inverse covariance matrix. Our method, named ALICE, is applicable to the elliptical family. Computationally, we develop an efficient dual inexact iterative projection (${\rm D_2}$P) algorithm based on the alternating direction method of multipliers (ADMM). Theoretically, we prove that the ALICE estimator achieves the parametric rate of convergence in both parameter estimation and model selection. Moreover, ALICE calibrates regularizations when estimating each column of the inverse covariance matrix. So it not only is asymptotically tuning free, but also achieves an improved finite sample performance. We present numerical simulations to support our theory, and a real data example to illustrate the effectiveness of the proposed estimator.
Sinkhorn Distances: Lightspeed Computation of Optimal Transport
Authors: Marco Cuturi
Date: 2013-12-01 00:00:00
Proceeding: NeurIPS 2013 12

Optimal transportation distances are a fundamental family of parameterized distances for histograms in the probability simplex. Despite their appealing theoretical properties, excellent performance and intuitive formulation, their computation involves the resolution of a linear program whose cost is prohibitive whenever the histograms' dimension exceeds a few hundreds. We propose in this work a new family of optimal transportation distances that look at transportation problems from a maximum-entropy perspective. We smooth the classical optimal transportation problem with an entropic regularization term, and show that the resulting optimum is also a distance which can be computed through Sinkhorn's matrix scaling algorithm at a speed that is several orders of magnitude faster than that of transportation solvers. We also report improved performance on the MNIST benchmark problem over competing distances.
Speedup Matrix Completion with Side Information: Application to Multi-Label Learning
Authors: Miao Xu, Rong Jin, Zhi-Hua Zhou
Date: 2013-12-01 00:00:00
Proceeding: NeurIPS 2013 12
Tasks: Matrix Completion, Multi-Label Learning

In standard matrix completion theory, it is required to have at least $O(n\ln^2 n)$ observed entries to perfectly recover a low-rank matrix $M$ of size $n\times n$, leading to a large number of observations when $n$ is large. In many real tasks, side information in addition to the observed entries is often available. In this work, we develop a novel theory of matrix completion that explicitly explore the side information to reduce the requirement on the number of observed entries. We show that, under appropriate conditions, with the assistance of side information matrices, the number of observed entries needed for a perfect recovery of matrix $M$ can be dramatically reduced to $O(\ln n)$. We demonstrate the effectiveness of the proposed approach for matrix completion in transductive incomplete multi-label learning.
Compete to Compute
Authors: Rupesh K. Srivastava, Jonathan Masci, Sohrob Kazerounian, Faustino Gomez, Jürgen Schmidhuber
Date: 2013-12-01 00:00:00
Proceeding: NeurIPS 2013 12

Local competition among neighboring neurons is common in biological neural networks (NNs). We apply the concept to gradient-based, backprop-trained artificial multilayer NNs. NNs with competing linear units tend to outperform those with non-competing nonlinear units, and avoid catastrophic forgetting when training sets change over time.
Fast Determinantal Point Process Sampling with Application to Clustering
Authors: Byungkon Kang
Date: 2013-12-01 00:00:00
Proceeding: NeurIPS 2013 12
Tasks: Clustering

Determinantal Point Process (DPP) has gained much popularity for modeling sets of diverse items. The gist of DPP is that the probability of choosing a particular set of items is proportional to the determinant of a positive definite matrix that defines the similarity of those items. However, computing the determinant requires time cubic in the number of items, and is hence impractical for large sets. In this paper, we address this problem by constructing a rapidly mixing Markov chain, from which we can acquire a sample from the given DPP in sub-cubic time.  In addition, we show that this framework can be extended to sampling from cardinality-constrained DPPs. As an application, we show how our sampling algorithm can be used to provide a fast heuristic for determining the number of clusters, resulting in better clustering.
Information-theoretic lower bounds for distributed statistical estimation with communication constraints
Authors: Yuchen Zhang, John Duchi, Michael. I. Jordan, Martin J. Wainwright
Date: 2013-12-01 00:00:00
Proceeding: NeurIPS 2013 12
Tasks: Binary Classification, General Classification, regression

We establish minimax risk lower bounds for distributed statistical estimation given a budget $B$ of the total number of bits that may be communicated. Such lower bounds in turn reveal the minimum amount of communication required by any procedure to achieve the classical optimal rate for statistical estimation. We study two classes of protocols in which machines send messages either independently or interactively. The lower bounds are established for a variety of problems, from estimating the mean of a population to estimating parameters in linear regression or binary classification.
Projected Natural Actor-Critic
Authors: Philip S. Thomas, William C. Dabney, Stephen Giguere, Sridhar Mahadevan
Date: 2013-12-01 00:00:00
Proceeding: NeurIPS 2013 12
Tasks: reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

Natural actor-critics are a popular class of policy search algorithms for finding locally optimal policies for Markov decision processes. In this paper we address a drawback of natural actor-critics that limits their real-world applicability - their lack of safety guarantees. We present a principled algorithm for performing natural gradient descent over a constrained domain. In the context of reinforcement learning, this allows for natural actor-critic algorithms that are guaranteed to remain within a known safe region of policy space. While deriving our class of constrained natural actor-critic algorithms, which we call Projected Natural Actor-Critics (PNACs), we also elucidate the relationship between natural gradient descent and mirror descent.
How to Hedge an Option Against an Adversary: Black-Scholes Pricing is Minimax Optimal
Authors: Jacob Abernethy, Peter L. Bartlett, Rafael Frongillo, Andre Wibisono
Date: 2013-12-01 00:00:00
Proceeding: NeurIPS 2013 12

We consider a popular problem in finance, option pricing, through the lens of an online learning game between Nature and an Investor.  In the Black-Scholes option pricing model from 1973, the Investor can continuously hedge the risk of an option by trading the underlying asset, assuming that the asset's price fluctuates according to Geometric Brownian Motion (GBM). We consider a worst-case model, in which Nature chooses a sequence of price fluctuations under a cumulative quadratic volatility constraint, and the Investor can make a sequence of hedging decisions. Our main result is to show that the value of our proposed game, which is the regret'' of hedging strategy, converges to the Black-Scholes option price. We use significantly weaker assumptions than previous work---for instance, we allow large jumps in the asset price---and show that the Black-Scholes hedging strategy is near-optimal for the Investor even in this non-stochastic framework."
Discovering Hidden Variables in Noisy-Or Networks using Quartet Tests
Authors: Yacine Jernite, Yonatan Halpern, David Sontag
Date: 2013-12-01 00:00:00
Proceeding: NeurIPS 2013 12

We give a polynomial-time algorithm for provably learning the structure and parameters of bipartite noisy-or Bayesian networks of binary variables where the top layer is completely hidden. Unsupervised learning of these models is a form of discrete factor analysis, enabling the discovery of hidden variables and their causal relationships with observed data. We obtain an efficient learning algorithm for a family of Bayesian networks that we call quartet-learnable, meaning that every latent variable has four children that do not have any other parents in common. We show that the existence of such a quartet allows us to uniquely identify each latent variable and to learn all parameters involving that latent variable. Underlying our algorithm are two new techniques for structure learning: a quartet test to determine whether a set of binary variables are singly coupled, and a conditional mutual information test that we use to learn parameters. We also show how to subtract already learned latent variables from the model to create new singly-coupled quartets, which substantially expands the class of structures that we can learn. Finally, we give a proof of the polynomial sample complexity of our learning algorithm, and experimentally compare it to variational EM.
Error-Minimizing Estimates and Universal Entry-Wise Error Bounds for Low-Rank Matrix Completion
Authors: Franz Kiraly, Louis Theran
Date: 2013-12-01 00:00:00
Proceeding: NeurIPS 2013 12
Tasks: Denoising, Low-Rank Matrix Completion, Matrix Completion

We propose a general framework for reconstructing and denoising single entries of incomplete and noisy entries. We describe: effective algorithms for deciding if and entry can be reconstructed and, if so, for reconstructing and denoising it; and a priori bounds on the error of each entry, individually.  In the noiseless case our algorithm is exact. For rank-one matrices, the new algorithm is fast, admits a highly-parallel implementation, and produces an error minimizing estimate that is qualitatively close to our theoretical and the state-of-the-art Nuclear Norm and OptSpace methods.
Learning the Local Statistics of Optical Flow
Authors: Dan Rosenbaum, Daniel Zoran, Yair Weiss
Date: 2013-12-01 00:00:00
Proceeding: NeurIPS 2013 12
Tasks: Optical Flow Estimation

Motivated by recent progress in natural image statistics, we use newly available datasets with ground truth optical flow to learn the  local statistics of optical flow and rigorously compare the learned model to prior models assumed by computer vision optical flow algorithms.  We find that a Gaussian mixture model with 64 components provides a significantly better model for local flow statistics when compared to commonly used models. We investigate the source of the GMMs success and show it is related to an explicit representation of flow boundaries. We also learn a model that jointly models the local intensity pattern and the local optical flow. In accordance with the assumptions often made in computer vision, the model learns that flow boundaries are more likely at intensity boundaries. However, when evaluated on a large dataset, this dependency is very weak and the benefit of conditioning flow estimation on the local intensity pattern is marginal.
Aggregating Optimistic Planning Trees for Solving Markov Decision Processes
Authors: Gunnar Kedenburg, Raphael Fonteneau, Remi Munos
Date: 2013-12-01 00:00:00
Proceeding: NeurIPS 2013 12
Tasks: Decision Making

This paper addresses the problem of online planning in Markov Decision Processes using only a generative model. We propose a new algorithm which is based on the construction of a forest of single successor state planning trees. For every explored state-action, such a tree contains exactly one successor state, drawn from the generative model. The trees are built using a planning algorithm which follows the optimism in the face of uncertainty principle, in assuming the most favorable outcome in the absence of further information. In the decision making step of the algorithm, the individual trees are combined. We discuss the approach, prove that our proposed algorithm is consistent, and empirically show that it performs better than a related algorithm which additionally assumes the knowledge of all transition distributions.
Robust learning of low-dimensional dynamics from large neural ensembles
Authors: David Pfau, Eftychios A. Pnevmatikakis, Liam Paninski
Date: 2013-12-01 00:00:00
Proceeding: NeurIPS 2013 12
Tasks: Dimensionality Reduction

Recordings from large populations of neurons make it possible to search for hypothesized low-dimensional dynamics. Finding these dynamics requires models that take into account biophysical constraints and can be fit efficiently and robustly. Here, we present an approach to dimensionality reduction for neural data that is convex, does not make strong assumptions about dynamics, does not require averaging over many trials and is extensible to more complex statistical models that combine local and global influences. The results can be combined with spectral methods to learn dynamical systems models. The basic method can be seen as an extension of PCA to the exponential family using nuclear norm minimization. We evaluate the effectiveness of this method using an exact decomposition of the Bregman divergence that is analogous to variance explained for PCA. We show on model data that the parameters of latent linear dynamical systems can be recovered, and that even if the dynamics are not stationary we can still recover the true latent subspace. We also demonstrate an extension of nuclear norm minimization that can separate sparse local connections from global latent dynamics. Finally, we demonstrate improved prediction on real neural data from monkey motor cortex compared to fitting linear dynamical models without nuclear norm smoothing.
Estimation Bias in Multi-Armed Bandit Algorithms for Search Advertising
Authors: Min Xu, Tao Qin, Tie-Yan Liu
Date: 2013-12-01 00:00:00
Proceeding: NeurIPS 2013 12
Tasks: Selection bias

In search advertising, the search engine needs to select the most profitable advertisements to display, which can be formulated as an instance of online learning with partial feedback, also known as the stochastic multi-armed bandit (MAB) problem. In this paper, we show that the naive application of MAB algorithms to search advertising for advertisement selection will produce sample selection bias that harms the search engine by decreasing expected revenue and “estimation of the largest mean” (ELM) bias that harms the advertisers by increasing game-theoretic player-regret. We then propose simple bias-correction methods with benefits to both the search engine and the advertisers.
Action is in the Eye of the Beholder: Eye-gaze Driven Model for Spatio-Temporal Action Localization
Authors: Nataliya Shapovalova, Michalis Raptis, Leonid Sigal, Greg Mori
Date: 2013-12-01 00:00:00
Proceeding: NeurIPS 2013 12
Tasks: Action Localization, Classification, General Classification, Spatio-Temporal Action Localization, Temporal Action Localization, Temporal Localization

We propose a new weakly-supervised structured learning approach for recognition and spatio-temporal localization of actions in video. As part of the proposed approach we develop a generalization of the Max-Path search algorithm, which allows us to efficiently search over a structured space of multiple spatio-temporal paths, while also allowing to incorporate context information into the model. Instead of using spatial annotations, in the form of bounding boxes, to guide the latent model during training, we utilize human gaze data in the form of a weak supervisory signal. This is achieved by incorporating gaze, along with the classification, into the structured loss within the latent SVM learning framework. Experiments on a challenging benchmark dataset, UCF-Sports, show that our model is more accurate, in terms of classification, and achieves state-of-the-art results in localization. In addition, we show how our model can produce top-down saliency maps conditioned on the classification label and localized latent paths.
A* Lasso for Learning a Sparse Bayesian Network Structure for Continuous Variables
Authors: Jing Xiang, Seyoung Kim
Date: 2013-12-01 00:00:00
Proceeding: NeurIPS 2013 12
Tasks: Computational Efficiency

We address the problem of learning a sparse Bayesian network  structure for continuous variables in a high-dimensional space. The constraint that the estimated Bayesian network structure  must be a directed acyclic graph (DAG) makes the problem challenging because of the huge search space of network structures. Most previous methods were based on a two-stage approach that prunes the search space in the first stage and then searches for a network structure that satisfies the DAG constraint in the second stage. Although this approach is effective in a low-dimensional setting, it is difficult to ensure that the correct network structure is not pruned in the first stage in a high-dimensional setting.  In this paper, we propose a single-stage method, called A* lasso, that recovers the optimal  sparse Bayesian network structure by solving a single optimization problem with A* search algorithm that uses lasso in its scoring system. Our approach substantially improves the computational efficiency of the well-known exact methods  based on dynamic programming. We also present a heuristic scheme that further improves the efficiency of A* lasso without significantly compromising the quality of solutions and   demonstrate this on benchmark Bayesian networks and real data.