pwc-archive/papers-with-abstracts huggingface dataset:
Crowdsourced Clustering: Querying Edges vs Triangles
Authors: Ramya Korlakai Vinayak, Babak Hassibi
Date: 2016-12-01 00:00:00
Proceeding: NeurIPS 2016 12
Tasks: Clustering

We consider the task of clustering items using answers from non-expert crowd workers. In such cases, the workers are often not able to label the items directly, however, it is reasonable to assume that they can compare items and judge whether they are similar or not. An important question is what queries to make, and we compare two types: random edge queries, where a pair of items is revealed, and random triangles, where a triple is. Since it is far too expensive to query all possible edges and/or triangles, we need to work with partial observations subject to a fixed query budget constraint. When a generative model for the data is available (and we consider a few of these) we determine the cost of a query by its entropy; when such models do not exist we use the average response time per query of the workers as a surrogate for the cost. In addition to theoretical justification, through several simulations and experiments on two real data sets on Amazon Mechanical Turk, we empirically demonstrate that, for a fixed budget, triangle queries uniformly outperform edge queries. Even though, in contrast to edge queries, triangle queries reveal dependent edges, they provide more reliable edges and, for a fixed budget, many more of them. We also provide a sufficient condition on the number of observations, edge densities inside and outside the clusters and the minimum cluster size required for the exact recovery of the true adjacency matrix via triangle queries using a convex optimization-based clustering algorithm.
Mixed vine copulas as joint models of spike counts and local field potentials
Authors: Arno Onken, Stefano Panzeri
Date: 2016-12-01 00:00:00
Proceeding: NeurIPS 2016 12
Tasks: Mutual Information Estimation

Concurrent measurements of neural activity at multiple scales, sometimes performed with multimodal techniques, become increasingly important for studying brain function. However, statistical methods for their concurrent analysis are currently lacking. Here we introduce such techniques in a framework based on vine copulas with mixed margins to construct multivariate stochastic models. These models can describe detailed mixed interactions between discrete variables such as neural spike counts, and continuous variables such as local field potentials. We propose efficient methods for likelihood calculation, inference, sampling and mutual information estimation within this framework. We test our methods on simulated data and demonstrate applicability on mixed data generated by a biologically realistic neural network. Our methods hold the promise to considerably improve statistical analysis of neural data recorded simultaneously at different scales.
Achieving the KS threshold in the general stochastic block model with linearized acyclic belief propagation
Authors: Emmanuel Abbe, Colin Sandon
Date: 2016-12-01 00:00:00
Proceeding: NeurIPS 2016 12
Tasks: Clustering, Community Detection, Stochastic Block Model

The stochastic block model (SBM) has long been studied in machine learning and network science as a canonical model for clustering and community detection. In the recent years, new developments have demonstrated the presence of threshold phenomena for this model, which have set new challenges for algorithms. For the {\it detection} problem in symmetric SBMs, Decelle et al.\ conjectured that the so-called Kesten-Stigum (KS) threshold can be achieved efficiently. This was proved for two communities, but remained open from three communities. We prove this conjecture here, obtaining a more general result that applies to arbitrary SBMs with linear size communities. The developed algorithm is a linearized acyclic belief propagation (ABP) algorithm, which mitigates the effects of cycles while provably achieving the KS threshold in $O(n \ln n)$ time. This extends prior methods by achieving universally the KS threshold while reducing or preserving the computational complexity. ABP is also connected to a power iteration method on a generalized nonbacktracking operator, formalizing the spectral-message passing interplay described in Krzakala et al., and extending results from Bordenave et al.
Adaptive Concentration Inequalities for Sequential Decision Problems
Authors: Shengjia Zhao, Enze Zhou, Ashish Sabharwal, Stefano Ermon
Date: 2016-12-01 00:00:00
Proceeding: NeurIPS 2016 12
Tasks: Two-sample testing

A key challenge in sequential decision problems is to determine how many samples are needed for an agent to make reliable decisions with good probabilistic guarantees.   We introduce Hoeffding-like concentration inequalities that hold for a random, adaptively chosen number of samples. Our inequalities are tight under natural assumptions and can greatly simplify the analysis of common sequential decision problems. In particular, we apply them to sequential hypothesis testing, best arm identification, and sorting. The resulting algorithms rival or exceed the state of the art both theoretically and empirically.
A Pseudo-Bayesian Algorithm for Robust PCA
Authors: Tae-Hyun Oh, Yasuyuki Matsushita, In Kweon, David Wipf
Date: 2016-12-01 00:00:00
Proceeding: NeurIPS 2016 12

Commonly used in many applications, robust PCA represents an algorithmic attempt to reduce the sensitivity of classical PCA to outliers.  The basic idea is to learn a decomposition of some data matrix of interest into low rank and sparse components, the latter representing unwanted outliers.  Although the resulting problem is typically NP-hard, convex relaxations provide a computationally-expedient alternative with theoretical support.  However, in practical regimes performance guarantees break down and a variety of non-convex alternatives, including Bayesian-inspired models, have been proposed to boost estimation quality.  Unfortunately though, without additional a priori knowledge none of these methods can significantly expand the critical operational range such that exact principal subspace recovery is possible.  Into this mix we propose a novel pseudo-Bayesian algorithm that explicitly compensates for design weaknesses in many existing non-convex approaches leading to state-of-the-art performance with a sound analytical foundation.
Catching heuristics are optimal control policies
Authors: Boris Belousov, Gerhard Neumann, Constantin A. Rothkopf, Jan R. Peters
Date: 2016-12-01 00:00:00
Proceeding: NeurIPS 2016 12

Two seemingly contradictory theories attempt to explain how humans move to intercept an airborne ball. One theory posits that humans predict the ball trajectory to optimally plan future actions; the other claims that, instead of performing such complicated computations, humans employ heuristics to reactively choose appropriate actions based on immediate visual feedback. In this paper, we show that interception strategies appearing to be heuristics can be understood as computational solutions to the optimal control problem faced by a ball-catching agent acting under uncertainty. Modeling catching as a continuous partially observable Markov decision process and employing stochastic optimal control theory, we discover that the four main heuristics described in the literature are optimal solutions if the catcher has sufficient time to continuously visually track the ball. Specifically, by varying model parameters such as noise, time to ground contact, and perceptual latency, we show that different strategies arise under different circumstances. The catcher's policy switches between generating reactive and predictive behavior based on the ratio of system to observation noise and the ratio between reaction time and task duration. Thus, we provide a rational account of human ball-catching behavior and a unifying explanation for seemingly contradictory theories of target interception on the basis of stochastic optimal control.
Synthesis of MCMC and Belief Propagation
Authors: Sung-Soo Ahn, Michael Chertkov, Jinwoo Shin
Date: 2016-12-01 00:00:00
Proceeding: NeurIPS 2016 12

Markov Chain Monte Carlo (MCMC) and Belief Propagation (BP) are the most popular algorithms for computational inference in Graphical Models (GM).  In principle, MCMC is an exact probabilistic method which, however, often suffers from exponentially slow mixing. In contrast, BP  is a deterministic method, which is typically fast,  empirically very successful, however in general lacking control of accuracy over loopy graphs.  In this paper, we introduce MCMC algorithms correcting the approximation error of BP, i.e.,  we provide a way to compensate for BP errors via a consecutive BP-aware MCMC.  Our framework is based on the Loop Calculus (LC) approach  which allows to express the BP error  as a sum of weighted generalized loops. Although the full series is computationally intractable,  it is known that a truncated series, summing up all 2-regular loops, is computable in polynomial-time for planar pair-wise binary GMs and it also provides a highly accurate approximation empirically. Motivated by this, we, first, propose a polynomial-time approximation MCMC scheme for the truncated series of general (non-planar) pair-wise binary models.  Our main idea here is to use the Worm algorithm, known to provide fast mixing in other (related) problems, and then  design an appropriate rejection scheme to sample 2-regular loops. Furthermore, we also design an efficient rejection-free MCMC scheme  for approximating the full series.  The main novelty underlying our design  is in utilizing the concept of cycle basis, which provides an efficient decomposition of the generalized loops. In essence, the proposed MCMC schemes run on transformed GM built upon  the non-trivial BP solution, and our experiments show that this synthesis of BP and MCMC  outperforms both direct MCMC and bare BP schemes.
Learning Treewidth-Bounded Bayesian Networks with Thousands of Variables
Authors: Mauro Scanagatta, Giorgio Corani, Cassio P. de Campos, Marco Zaffalon
Date: 2016-12-01 00:00:00
Proceeding: NeurIPS 2016 12

We present a method for learning treewidth-bounded Bayesian networks from data sets containing thousands of variables. Bounding the treewidth of a Bayesian network greatly reduces the complexity of inferences.  Yet, being a global property of the graph, it considerably increases the difficulty of the learning process. Our novel algorithm accomplishes this task, scaling both to large domains and to large treewidths. Our novel approach consistently outperforms the state of the art on experiments with up to thousands of variables.
Large Margin Discriminant Dimensionality Reduction in Prediction Space
Authors: Mohammad Saberian, Jose Costa Pereira, Can Xu, Jian Yang, Nuno Nvasconcelos
Date: 2016-12-01 00:00:00
Proceeding: NeurIPS 2016 12
Tasks: Dimensionality Reduction, General Classification, Prediction, Scene Classification

In this paper we establish a duality between boosting and SVM, and use this to derive a novel discriminant dimensionality reduction algorithm. In particular, using the multiclass formulation of boosting and SVM we note that both use a combination of mapping and linear classification to maximize the multiclass margin. In SVM this is implemented using a pre-defined mapping (induced by the kernel) and optimizing the linear classifiers. In boosting the linear classifiers are pre-defined and the mapping (predictor) is learned through combination of weak learners. We argue that the intermediate mapping, e.g. boosting predictor, is preserving the discriminant aspects of the data and by controlling the dimension of this mapping it is possible to achieve discriminant low dimensional representations for the data. We use the aforementioned duality and propose a new method, Large Margin Discriminant Dimensionality Reduction (LADDER) that jointly learns the mapping and the linear classifiers in an efficient manner. This leads to a data-driven mapping which can embed data into any number of dimensions. Experimental results show that this embedding can significantly improve performance on tasks such as hashing and image/scene classification.
Simple and Efficient Weighted Minwise Hashing
Authors: Anshumali Shrivastava
Date: 2016-12-01 00:00:00
Proceeding: NeurIPS 2016 12

Weighted minwise hashing (WMH) is one of the fundamental subroutine, required by many celebrated approximation algorithms, commonly adopted in industrial practice for large -scale search and learning. The resource bottleneck with WMH is the computation of multiple (typically a few hundreds to thousands) independent hashes of the data.  We propose a simple rejection type sampling scheme based on a carefully designed red-green map, where we show that the number of rejected sample has exactly the same distribution as weighted minwise sampling. The running time of our method,  for many practical datasets, is an order of magnitude smaller than existing methods. Experimental evaluations, on real datasets, show that for computing 500 WMH, our proposal can be 60000x faster than the Ioffe's method without losing any accuracy. Our method is also around 100x faster than approximate heuristics capitalizing on the efficient ``densified" one permutation hashing schemes~\cite{Proc:OneHashLSH_ICML14,Proc:Shrivastava_UAI14}. Given the simplicity of our approach and its significant advantages, we hope that it will replace existing implementations in practice.
Structured Sparse Regression via Greedy Hard Thresholding
Authors: Prateek Jain, Nikhil Rao, Inderjit S. Dhillon
Date: 2016-12-01 00:00:00
Proceeding: NeurIPS 2016 12
Tasks: regression

Several learning applications require solving high-dimensional regression problems where the relevant features belong to a small number of (overlapping) groups. For very large datasets and under standard sparsity constraints, hard thresholding methods have proven to be extremely efficient, but such methods require NP hard projections when dealing with overlapping groups. In this paper, we show that such NP-hard projections can not only be avoided by appealing to submodular optimization, but such methods come with strong theoretical guarantees even in the presence of poorly conditioned data (i.e. say when two features have correlation  $\geq 0.99$), which existing analyses cannot handle. These methods exhibit an interesting computation-accuracy trade-off and can be extended to significantly harder problems such as sparse overlapping groups. Experiments on both real and synthetic data validate our claims and demonstrate that the proposed methods are orders of magnitude faster than other greedy and convex relaxation techniques for learning with group-structured sparsity.
Learning Tree Structured Potential Games
Authors: Vikas Garg, Tommi Jaakkola
Date: 2016-12-01 00:00:00
Proceeding: NeurIPS 2016 12

Many real phenomena, including behaviors, involve strategic interactions that can be learned from data. We focus on learning tree structured potential games where equilibria are represented by local maxima of an underlying potential function. We cast the learning problem within a max margin setting and show that the problem is NP-hard even when the strategic interactions form a tree. We develop a variant of dual decomposition to estimate the underlying game and demonstrate with synthetic and real decision/voting data that the game theoretic perspective (carving out local maxima) enables meaningful recovery.
Identification and Overidentification of Linear Structural Equation Models
Authors: Bryant Chen
Date: 2016-12-01 00:00:00
Proceeding: NeurIPS 2016 12

In this paper, we address the problems of identifying linear structural equation models and discovering the constraints they imply. We first extend the half-trek criterion to cover a broader class of models and apply our extension to finding testable constraints implied by the model. We then show that any semi-Markovian linear model can be recursively decomposed into simpler sub-models, resulting in improved identification and constraint discovery power. Finally, we show that, unlike the existing methods developed for linear models, the resulting method subsumes the identification and constraint discovery algorithms for non-parametric models.
Adaptive Skills Adaptive Partitions (ASAP)
Authors: Daniel J. Mankowitz, Timothy A. Mann, Shie Mannor
Date: 2016-12-01 00:00:00
Proceeding: NeurIPS 2016 12
Tasks: Lifelong learning

We introduce the Adaptive Skills, Adaptive Partitions (ASAP) framework that (1) learns skills (i.e., temporally extended actions or options) as well as (2) where to apply them. We believe that both (1) and (2) are necessary for a truly general skill learning framework, which is a key building block needed to scale up to lifelong learning agents. The ASAP framework is also able to  solve related new tasks simply by adapting where it applies its existing learned skills. We prove that ASAP converges to a local optimum under natural conditions. Finally, our experimental results, which include a RoboCup domain, demonstrate the ability of ASAP to learn where to reuse skills as well as solve multiple tasks with considerably less experience than solving each task from scratch.
Boosting with Abstention
Authors: Corinna Cortes, Giulia Desalvo, Mehryar Mohri
Date: 2016-12-01 00:00:00
Proceeding: NeurIPS 2016 12
Tasks: Binary Classification

We present a new boosting algorithm for the key scenario of binary classification with abstention where the algorithm can abstain from predicting the label of a point, at the price of a fixed cost.  At each round, our algorithm selects a pair of functions, a base predictor and a base abstention function.  We define convex upper bounds for the natural loss function associated to this problem, which we prove to be calibrated with respect to the Bayes solution. Our algorithm benefits from general margin-based learning guarantees which we derive for ensembles of pairs of base predictor and abstention functions, in terms of the Rademacher complexities of the corresponding function classes.  We give convergence guarantees for our algorithm along with a linear-time weak-learning algorithm for abstention stumps. We also report the results of several experiments suggesting that our algorithm provides a significant improvement in practice over two confidence-based algorithms.
Regret of Queueing Bandits
Authors: Subhashini Krishnasamy, Rajat Sen, Ramesh Johari, Sanjay Shakkottai
Date: 2016-12-01 00:00:00
Proceeding: NeurIPS 2016 12

We consider a variant of the multiarmed bandit problem where jobs queue for service, and service rates of different servers may be unknown.  We study algorithms that minimize queue-regret: the (expected) difference between the queue-lengths obtained by the algorithm, and those obtained by a genie-aided matching algorithm that knows exact service rates.  A naive view of this problem would suggest that queue-regret should grow logarithmically: since queue-regret cannot be larger than classical regret, results for the standard MAB problem give algorithms that ensure queue-regret increases no more than logarithmically in time. Our paper shows surprisingly more complex behavior.  In particular, the naive intuition is correct as long as the bandit algorithm's queues have relatively long regenerative cycles: in this case queue-regret is similar to cumulative regret, and scales (essentially) logarithmically.  However, we show that this "early stage" of the queueing bandit eventually gives way to a "late stage", where the optimal queue-regret scaling is O(1/t).  We demonstrate an algorithm that (order-wise) achieves this asymptotic queue-regret, and also exhibits close to optimal switching time from the early stage to the late stage.
Deep Learning Games
Authors: Dale Schuurmans, Martin A. Zinkevich
Date: 2016-12-01 00:00:00
Proceeding: NeurIPS 2016 12
Tasks: Deep Learning

We investigate a reduction of supervised learning to game playing that reveals new connections and learning methods.  For convex one-layer problems, we demonstrate an equivalence between global minimizers of the training problem and Nash equilibria in a simple game.  We then show how the game can be extended to general acyclic neural networks with differentiable convex gates, establishing a bijection between the Nash equilibria and critical (or KKT) points of the deep learning problem.  Based on these connections we investigate alternative learning methods, and find that regret matching can achieve competitive training performance while producing sparser models than current deep learning approaches.
Variational Inference in Mixed Probabilistic Submodular Models
Authors: Josip Djolonga, Sebastian Tschiatschek, Andreas Krause
Date: 2016-12-01 00:00:00
Proceeding: NeurIPS 2016 12
Tasks: Variational Inference

We consider the problem of variational inference in probabilistic models with both log-submodular and log-supermodular higher-order potentials. These models can represent arbitrary distributions over binary variables, and thus generalize the commonly used pairwise Markov random fields and models with log-supermodular potentials only, for which efficient approximate inference algorithms are known. While inference in the considered models is #P-hard in general, we present efficient approximate algorithms exploiting recent advances in the field of discrete optimization. We demonstrate the effectiveness of our approach in a large set of experiments, where our model allows reasoning about preferences over sets of items with complements and substitutes.
A Bandit Framework for Strategic Regression
Authors: Yang Liu, Yi-Ling Chen
Date: 2016-12-01 00:00:00
Proceeding: NeurIPS 2016 12
Tasks: regression

We consider a learner's problem of acquiring data dynamically for training a regression model, where the training data are collected from strategic data sources. A fundamental challenge is to incentivize data holders to exert effort to improve the quality of their reported data, despite that the quality is not directly verifiable by the learner. In this work, we study a dynamic data acquisition process where data holders can contribute multiple times. Using a bandit framework, we leverage on the long-term incentive of future job opportunities to incentivize high-quality contributions. We propose a Strategic Regression-Upper Confidence Bound (SR-UCB) framework, an UCB-style index combined with a simple payment rule, where the index of a worker approximates the quality of his past contributions and is used by the learner to determine whether the worker receives future work. For linear regression and certain family of non-linear regression problems, we show that SR-UCB enables a $O(\sqrt{\log T/T})$-Bayesian Nash Equilibrium (BNE) where each worker exerting a target effort level that the learner has chosen, with $T$ being the number of data acquisition stages. The SR-UCB framework also has some other desirable properties: (1) The indexes can be updated in an online fashion (hence computationally light). (2) A slight variant, namely Private SR-UCB (PSR-UCB), is able to preserve $(O(\log^{-1} T), O(\log^{-1} T))$-differential privacy for workers' data, with only a small compromise on incentives (achieving $O(\log^{6} T/\sqrt{T})$-BNE).