pwc-archive/papers-with-abstracts huggingface dataset:
Spherical Random Features for Polynomial Kernels
Authors: Jeffrey Pennington, Felix Xinnan X. Yu, Sanjiv Kumar
Date: 2015-12-01 00:00:00
Proceeding: NeurIPS 2015 12
Tasks: General Classification

Compact explicit feature maps provide a practical framework to scale kernel methods to large-scale learning, but deriving such maps for many types of kernels remains a challenging open problem. Among the commonly used kernels for nonlinear classification are polynomial kernels, for which low approximation error has thus far necessitated explicit feature maps of large dimensionality, especially for higher-order polynomials. Meanwhile, because polynomial kernels are unbounded, they are frequently applied to data that has been normalized to unit l2 norm. The question we address in this work is: if we know a priori that data is so normalized, can we devise a more compact map? We show that a putative affirmative answer to this question based on Random Fourier Features is impossible in this setting, and introduce a new approximation paradigm, Spherical Random Fourier (SRF) features, which circumvents these issues and delivers a compact approximation to polynomial kernels for data on the unit sphere. Compared to prior work, SRF features are less rank-deficient, more compact, and achieve better kernel approximation, especially for higher-order polynomials. The resulting predictions have lower variance and typically yield better classification accuracy.
Learning Bayesian Networks with Thousands of Variables
Authors: Mauro Scanagatta, Cassio P. de Campos, Giorgio Corani, Marco Zaffalon
Date: 2015-12-01 00:00:00
Proceeding: NeurIPS 2015 12

We present a method for learning Bayesian networks from data sets containingthousands of variables without the need for structure constraints. Our approachis made of two parts. The first is a novel algorithm that effectively explores thespace of possible parent sets of a node. It guides the exploration towards themost promising parent sets on the basis of an approximated score function thatis computed in constant time. The second part is an improvement of an existingordering-based algorithm for structure optimization. The new algorithm provablyachieves a higher score compared to its original formulation. On very large datasets containing up to ten thousand nodes, our novel approach consistently outper-forms the state of the art.
Streaming Min-max Hypergraph Partitioning
Authors: Dan Alistarh, Jennifer Iglesias, Milan Vojnovic
Date: 2015-12-01 00:00:00
Proceeding: NeurIPS 2015 12
Tasks: Clustering, hypergraph partitioning

In many applications, the data is of rich structure that can be represented by a hypergraph, where the data items are represented by vertices and the associations among items are represented by hyperedges. Equivalently, we are given an input bipartite graph with two types of vertices: items, and associations (which we refer to as topics). We consider the problem of partitioning the set of items into a given number of parts such that the maximum number of topics covered by a part of the partition is minimized. This is a natural clustering problem, with various applications, e.g. partitioning of a set of  information objects such as documents, images, and videos, and load balancing in the context of computation platforms.In this paper, we focus on the streaming computation model for this problem, in which items arrive online one at a time and each item must be assigned irrevocably to a part of the partition at its arrival time. Motivated by scalability requirements, we focus on the class of streaming computation algorithms with memory limited to be at most linear in the number of the parts of the partition. We show that a greedy assignment strategy is able to recover a hidden co-clustering of items under a natural set of recovery conditions. We also report results of an extensive empirical evaluation, which demonstrate that this greedy strategy yields superior performance when compared with alternative approaches.
Robust PCA with compressed data
Authors: Wooseok Ha, Rina Foygel Barber
Date: 2015-12-01 00:00:00
Proceeding: NeurIPS 2015 12
Tasks: Data Compression

The robust principal component analysis (RPCA) problem seeks to separate low-rank trends from sparse outlierswithin a data matrix, that is, to approximate a $n\times d$ matrix $D$ as the sum of a low-rank matrix $L$ and a sparse matrix $S$.We examine the robust principal component analysis (RPCA) problem under data compression, wherethe data $Y$ is approximately given by $(L + S)\cdot C$, that is, a low-rank $+$ sparse data matrix that has been compressed to size $n\times m$ (with $m$ substantially smaller than the original dimension $d$) via multiplication witha compression matrix $C$. We give a convex program for recovering the sparse component $S$ along with the compressed low-rank component $L\cdot C$, along with upper bounds on the error of this reconstructionthat scales naturally with the compression dimension $m$ and coincides with existing results for the uncompressedsetting $m=d$. Our results can also handle error introduced through additive noise or through missing data.The scaling of dimension, compression, and signal complexity in our theoretical results is verified empirically through simulations, and we also apply our method to a data set measuring chlorine concentration acrossa network of sensors, to test its performance in practice.
Sampling from Probabilistic Submodular Models
Authors: Alkis Gotovos, Hamed Hassani, Andreas Krause
Date: 2015-12-01 00:00:00
Proceeding: NeurIPS 2015 12
Tasks: Diversity, Point Processes

Submodular and supermodular functions have found wide applicability in machine learning, capturing  notions such as diversity and regularity, respectively. These notions have deep consequences for optimization, and the problem of (approximately) optimizing submodular functions has received much attention. However, beyond optimization, these notions allow specifying expressive probabilistic models that can be used to quantify predictive uncertainty via marginal inference. Prominent, well-studied special cases include Ising models and determinantal point processes, but the general class of log-submodular and log-supermodular models is much richer and little studied. In this paper, we investigate the use of Markov chain Monte Carlo sampling to perform approximate inference in general log-submodular and log-supermodular models. In particular, we consider a simple Gibbs sampling procedure, and establish two sufficient conditions, the first guaranteeing polynomial-time, and the second fast (O(nlogn)) mixing. We also evaluate the efficiency of the Gibbs sampler on three examples of such models, and compare against a recently proposed variational approach.
Regret-Based Pruning in Extensive-Form Games
Authors: Noam Brown, Tuomas Sandholm
Date: 2015-12-01 00:00:00
Proceeding: NeurIPS 2015 12
Tasks: counterfactual, Form

Counterfactual Regret Minimization (CFR) is a leading algorithm for finding a Nash equilibrium in large zero-sum imperfect-information games. CFR is an iterative algorithm that repeatedly traverses the game tree, updating regrets at each information set.We introduce an improvement to CFR that prunes any path of play in the tree, and its descendants, that has negative regret. It revisits that sequence at the earliest subsequent CFR iteration where the regret could have become positive, had that path been explored on every iteration. The new algorithm maintains CFR's convergence guarantees while making iterations significantly faster---even if previously known pruning techniques are used in the comparison. This improvement carries over to CFR+, a recent variant of CFR. Experiments show an order of magnitude speed improvement, and the relative speed improvement increases with the size of the game.
GP Kernels for Cross-Spectrum Analysis
Authors: Kyle R. Ulrich, David E. Carlson, Kafui Dzirasa, Lawrence Carin
Date: 2015-12-01 00:00:00
Proceeding: NeurIPS 2015 12
Tasks: Gaussian Processes, Time Series, Time Series Analysis

Multi-output Gaussian processes provide a convenient framework for multi-task problems.  An illustrative and motivating example of a multi-task problem is multi-region electrophysiological time-series data, where experimentalists are interested in both power and phase coherence between channels.  Recently, Wilson and Adams (2013) proposed the spectral mixture (SM) kernel to model the spectral density of a single task in a Gaussian process framework.  In this paper, we develop a novel covariance kernel for multiple outputs, called the cross-spectral mixture (CSM) kernel.  This new, flexible kernel represents both the power and phase relationship between multiple observation channels.  We demonstrate the expressive capabilities of the CSM kernel through implementation of a Bayesian hidden Markov model, where the emission distribution is a multi-output Gaussian process with a CSM covariance kernel.  Results are presented for measured multi-region electrophysiological data.
Secure Multi-party Differential Privacy
Authors: Peter Kairouz, Sewoong Oh, Pramod Viswanath
Date: 2015-12-01 00:00:00
Proceeding: NeurIPS 2015 12
Tasks: All

We study the problem of multi-party interactive function computation under differential privacy. In this setting, each party is interested in computing a function on its private bit and all the other parties' bits. The function to be computed can vary from one party to the other. Moreover, there could be a central observer who is interested in computing a separate function on all the parties' bits. Differential privacy ensures that there remains an uncertainty in any party's bit even when given the transcript of interactions and all other parties' bits. Performance at each party is measured via the accuracy of the function to be computed. We allow for an arbitrary cost metric to measure the distortion between the true and the computed function values. Our main result is the optimality of a simple non-interactive protocol: each party randomizes its bit (sufficiently) and shares the privatized version with the other parties. This optimality result is very general: it holds for all types of functions, heterogeneous privacy conditions on the parties, all types of cost metrics, and both average and worst-case (over the inputs) measures of accuracy.
Anytime Influence Bounds and the Explosive Behavior of Continuous-Time Diffusion Networks
Authors: Kevin Scaman, Rémi Lemonnier, Nicolas Vayatis
Date: 2015-12-01 00:00:00
Proceeding: NeurIPS 2015 12
Tasks: Epidemiology, Marketing

The paper studies transition phenomena in information cascades observed along a diffusion process over some graph. We introduce the Laplace Hazard matrix and show that its spectral radius fully characterizes the dynamics of the contagion both in terms of influence and of explosion time. Using this concept, we prove tight non-asymptotic bounds for the influence of a set of nodes, and we also provide an in-depth analysis of the critical time after which the contagion becomes super-critical. Our contributions include formal definitions and tight lower bounds of critical explosion time. We illustrate the relevance of our theoretical results through several examples of information cascades used in epidemiology and viral marketing models. Finally, we provide a series of numerical experiments for various types of networks which confirm the tightness of the theoretical bounds.
High-dimensional neural spike train analysis with generalized count linear dynamical systems
Authors: Yuanjun Gao, Lars Busing, Krishna V. Shenoy, John P. Cunningham
Date: 2015-12-01 00:00:00
Proceeding: NeurIPS 2015 12
Tasks: Variational Inference

Latent factor models have been widely used to analyze simultaneous recordings of spike trains from large, heterogeneous neural populations.  These models assume  the signal of interest in the population is a low-dimensional latent intensity that evolves over time, which is observed in high dimension via noisy point-process observations.  These techniques have been well used to capture neural correlations across a population and to provide a smooth, denoised, and concise representation of high-dimensional spiking data.  One limitation of many current models is that the observation model is assumed to be Poisson, which lacks the flexibility to capture under- and over-dispersion that is common in recorded neural data, thereby introducing bias into estimates of covariance.  Here we develop the generalized count linear dynamical system, which relaxes the Poisson assumption by using a more general exponential family for count data.  In addition to containing Poisson, Bernoulli, negative binomial, and other common count distributions as special cases, we show that this model can be tractably learned by extending recent advances in variational inference techniques.  We apply our model to data from primate motor cortex and demonstrate performance improvements over state-of-the-art methods, both in capturing the variance structure of the data and in held-out prediction.
b-bit Marginal Regression
Authors: Martin Slawski, Ping Li
Date: 2015-12-01 00:00:00
Proceeding: NeurIPS 2015 12
Tasks: Quantization, regression

We consider the problem of sparse signal recovery from $m$ linear measurements quantized to $b$ bits. $b$-bit Marginal Regression is proposed as recovery algorithm. We study the question of choosing $b$ in the setting of a given budget of bits $B = m \cdot b$ and derive a single easy-to-compute expression characterizing the trade-off between $m$ and $b$. The choice $b = 1$ turns out to be optimal for estimating the unit vector corresponding to the signal for any level of additive Gaussian noise before quantization as well as for adversarial noise. For $b \geq 2$, we show that Lloyd-Max quantization constitutes an optimal quantization scheme and that the norm of the signal canbe estimated consistently by maximum likelihood.
Adaptive Primal-Dual Splitting Methods for Statistical Learning and Image Processing
Authors: Tom Goldstein, Min Li, Xiaoming Yuan
Date: 2015-12-01 00:00:00
Proceeding: NeurIPS 2015 12

The alternating direction method of multipliers (ADMM) is an important tool for solving complex optimization problems, but it involves minimization sub-steps that are often difficult to solve efficiently.   The Primal-Dual Hybrid Gradient (PDHG) method is a powerful alternative that often has simpler substeps than ADMM, thus producing lower complexity solvers. Despite the flexibility of this method, PDHG is often impractical because it requires the careful choice of multiple stepsize parameters. There is often no intuitive way to choose these parameters to maximize efficiency, or even achieve convergence.  We propose self-adaptive stepsize rules that automatically tune PDHG parameters for optimal convergence.  We rigorously analyze our methods, and identify convergence rates.  Numerical experiments show that adaptive PDHG has strong advantages over non-adaptive methods in terms of both efficiency and simplicity for the user.
Collaborative Filtering with Graph Information: Consistency and Scalable Methods
Authors: Nikhil Rao, Hsiang-Fu Yu, Pradeep K. Ravikumar, Inderjit S. Dhillon
Date: 2015-12-01 00:00:00
Proceeding: NeurIPS 2015 12
Tasks: Collaborative Filtering, Low-Rank Matrix Completion, Matrix Completion, Recommendation Systems

Low rank matrix completion plays a fundamental role in collaborative filtering applications, the key idea being that the variables lie in a smaller subspace than the ambient space. Often, additional information about the variables is known, and it is reasonable to assume that incorporating this information will lead to better predictions. We tackle the problem of matrix completion when pairwise relationships among variables are known, via a graph. We formulate and derive a highly efficient, conjugate gradient based alternating minimization scheme that solves optimizations with over 55 million observations up to 2 orders of magnitude faster than state-of-the-art (stochastic) gradient-descent based methods. On the theoretical front, we show that such methods generalize weighted nuclear norm formulations, and derive statistical consistency guarantees. We validate our results on both real and synthetic datasets.
A Structural Smoothing Framework For Robust Graph Comparison
Authors: Pinar Yanardag, S. V. N. Vishwanathan
Date: 2015-12-01 00:00:00
Proceeding: NeurIPS 2015 12

In this paper, we propose a general smoothing framework for graph kernels by  taking \textit{structural similarity} into account, and apply it to  derive smoothed variants of popular graph kernels. Our framework is inspired by state-of-the-art smoothing  techniques used in natural language processing (NLP). However, unlike  NLP applications which primarily deal with strings, we show how one  can apply smoothing to a richer class of inter-dependent  sub-structures that naturally arise in graphs. Moreover, we discuss  extensions of the Pitman-Yor process that can be adapted to smooth  structured objects thereby leading to novel graph kernels. Our  kernels are able to tackle the diagonal dominance problem, while  respecting the structural similarity between sub-structures,   especially under the presence of edge or label noise.  Experimental evaluation shows that not only our kernels outperform  the unsmoothed variants, but also achieve statistically significant  improvements in classification accuracy over several other graph  kernels that have been recently proposed in literature. Our kernels  are competitive in terms of runtime, and offer a viable option for  practitioners.
Competitive Distribution Estimation: Why is Good-Turing Good
Authors: Alon Orlitsky, Ananda Theertha Suresh
Date: 2015-12-01 00:00:00
Proceeding: NeurIPS 2015 12

Estimating distributions over large alphabets is a fundamental machine-learning tenet. Yet no method is known to estimate all distributions well.  For example, add-constant estimators are nearly min-max optimal but often perform poorly in practice, and practical estimators such as absolute discounting, Jelinek-Mercer, and Good-Turing are not known to be near optimal for essentially any distribution.We describe the first universally near-optimal probability estimators. For every discrete distribution, they are provably nearly the best in the following two competitive ways. First they estimate every distribution nearly as well as the best estimator designed with prior knowledge of the distribution up to a permutation. Second, they estimate every distribution nearly as well as the best estimator designed with prior knowledge of the exact distribution, but as all natural estimators, restricted to assign the same probability to all symbols appearing the same number of times.Specifically, for distributions over $k$ symbols and $n$ samples, we show that for both comparisons, a simple variant of Good-Turing estimator is always within KL divergence of $(3+o(1))/n^{1/3}$ from the best estimator, and that a more involved estimator is within $\tilde{\mathcal{O}}(\min(k/n,1/\sqrt n))$.  Conversely, we show that any estimator must have a KL divergence $\ge\tilde\Omega(\min(k/n,1/ n^{2/3}))$ over the best estimator for the first comparison, and $\ge\tilde\Omega(\min(k/n,1/\sqrt{n}))$ for the second.
An Active Learning Framework using Sparse-Graph Codes for Sparse Polynomials and Graph Sketching
Authors: Xiao Li, Kannan Ramchandran
Date: 2015-12-01 00:00:00
Proceeding: NeurIPS 2015 12
Tasks: Active Learning

Let $f: \{-1,1\}^n \rightarrow \mathbb{R}$ be an $n$-variate polynomial consisting of $2^n$ monomials, in which only $s\ll 2^n$ coefficients are non-zero. The goal is to learn the polynomial by querying the values of $f$. We introduce an active learning framework that is associated with a low query cost and computational runtime. The significant savings are enabled by leveraging sampling strategies based on modern coding theory, specifically, the design and analysis of {\it sparse-graph codes}, such as Low-Density-Parity-Check (LDPC) codes, which represent the state-of-the-art of modern packet communications. More significantly, we show how this design perspective leads to exciting, and to the best of our knowledge, largely unexplored intellectual connections between learning and coding. The key is to relax the worst-case assumption with an ensemble-average setting, where the polynomial is assumed to be drawn uniformly at random from the ensemble of all polynomials (of a given size $n$ and sparsity $s$). Our framework succeeds with high probability with respect to the polynomial ensemble with sparsity up to $s={O}(2^{\delta n})$ for any $\delta\in(0,1)$, where $f$ is exactly learned using ${O}(ns)$ queries in time ${O}(n s \log s)$, even if the queries are perturbed by Gaussian noise. We further apply the proposed framework to graph sketching, which is the problem of inferring sparse graphs by querying graph cuts. By writing the cut function as a polynomial and exploiting the graph structure, we propose a sketching algorithm to learn the an arbitrary $n$-node unknown graph using only few cut queries, which scales {\it almost linearly} in the number of edges and {\it sub-linearly} in the graph size $n$. Experiments on real datasets show significant reductions in the runtime and query complexity compared with competitive schemes.
Local Smoothness in Variance Reduced Optimization
Authors: Daniel Vainsencher, Han Liu, Tong Zhang
Date: 2015-12-01 00:00:00
Proceeding: NeurIPS 2015 12
Tasks: Stochastic Optimization

Abstract We propose a family of non-uniform sampling strategies to provably speed up a class of stochastic optimization algorithms with linear convergence including Stochastic Variance Reduced Gradient (SVRG) and Stochastic Dual Coordinate Ascent (SDCA). For a large family of penalized empirical risk minimization problems, our methods exploit data dependent local smoothness of the loss functions near the optimum, while maintaining convergence guarantees. Our bounds are the first to quantify the advantage gained from local smoothness which are significant for some problems significantly better. Empirically, we provide thorough numerical results to back up our theory. Additionally we present algorithms exploiting local smoothness in more aggressive ways, which perform even better in practice.
Saliency, Scale and Information: Towards a Unifying Theory
Authors: Shafin Rahman, Neil Bruce
Date: 2015-12-01 00:00:00
Proceeding: NeurIPS 2015 12
Tasks: Interest Point Detection

In this paper we present a definition for visual saliency grounded in information theory. This proposal is shown to relate to a variety of classic research contributions in scale-space theory, interest point detection, bilateral filtering, and to existing models of visual saliency. Based on the proposed definition of visual saliency, we demonstrate results competitive with the state-of-the art for both prediction of human fixations, and segmentation of salient objects. We also characterize different properties of this model including robustness to image transformations, and extension to a wide range of other data types with 3D mesh models serving as an example. Finally, we relate this proposal more generally to the role of saliency computation in visual information processing and draw connections to putative mechanisms for saliency computation in human vision.