pwc-archive/papers-with-abstracts huggingface dataset:
Confidence Sets for Network Structure
Authors: David S. Choi, Patrick J. Wolfe, Edo M. Airoldi
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12

Latent variable models are frequently used to identify structure in dichotomous network data, in part because they give rise to a Bernoulli product likelihood that is both well understood and consistent with the notion of exchangeable random graphs.  In this article we propose conservative confidence sets that hold with respect to these underlying Bernoulli parameters as a function of any given partition of network nodes, enabling us to assess estimates of \emph{residual} network structure, that is, structure that cannot be explained by known covariates and thus cannot be easily verified by manual inspection. We demonstrate the proposed methodology by analyzing student friendship networks from the National Longitudinal Survey of Adolescent Health that include race, gender, and school year as covariates.  We employ a stochastic expectation-maximization algorithm to fit a logistic regression model that includes these explanatory variables as well as a latent stochastic blockmodel component and additional node-specific effects.  Although maximum-likelihood estimates do not appear consistent in this context, we are able to evaluate confidence sets as a function of different blockmodel partitions, which enables us to qualitatively assess the significance of estimated residual network structure relative to a baseline, which models covariates but lacks block structure.
Prismatic Algorithm for Discrete D.C. Programming Problem
Authors: Yoshinobu Kawahara, Takashi Washio
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: BIG-bench Machine Learning, feature selection

In this paper, we propose the first exact algorithm for minimizing the difference of two submodular functions (D.S.), i.e., the discrete version of the D.C. programming problem. The developed algorithm is a branch-and-bound-based algorithm which responds to the structure of this problem through the relationship between submodularity and convexity. The D.S. programming problem covers a broad range of applications in machine learning because this generalizes the optimization of a wide class of set functions. We empirically investigate the performance of our algorithm, and illustrate the difference between exact and approximate solutions respectively obtained by the proposed and existing algorithms in feature selection and discriminative structure learning.
Multiclass Boosting: Theory and Algorithms
Authors: Mohammad J. Saberian, Nuno Vasconcelos
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12

The problem of  multiclass boosting is considered. A new framework,based on multi-dimensional codewords and predictors is introduced. The optimal set of codewords is derived, and a margin enforcing loss proposed. The resulting risk is minimized by gradient descent on a multidimensional functional space. Two algorithms are proposed: 1) CD-MCBoost, based on coordinate descent, updates one predictor component at a time, 2) GD-MCBoost, based on gradient descent, updates all components jointly. The algorithms differ in the weak learners that they support but are both shown to be 1) Bayes consistent, 2) margin enforcing, and 3) convergent to the global minimum of the risk. They also reduce to AdaBoost when there are only two classes. Experiments show that both methods outperform previous multiclass boosting approaches on a number of datasets.
Learning with the weighted trace-norm under arbitrary sampling distributions
Authors: Rina Foygel, Ohad Shamir, Nati Srebro, Ruslan R. Salakhutdinov
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12

We provide rigorous guarantees on learning with the weighted trace-norm under arbitrary sampling distributions.  We show that the standard weighted-trace norm might fail when the sampling distribution is not a product distribution (i.e. when row and column indexes are not selected independently), present a corrected variant for which we establish strong learning guarantees, and demonstrate that it works better in practice.  We provide guarantees when weighting by either the true or empirical sampling distribution, and suggest that even if the true distribution is known (or is uniform), weighting by the empirical distribution may be beneficial.
Scalable Training of Mixture Models via Coresets
Authors: Dan Feldman, Matthew Faulkner, Andreas Krause
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: Density Estimation

How can we train a statistical mixture model on a massive data set? In this paper, we show how to construct coresets for mixtures of Gaussians and natural generalizations. A coreset is a weighted subset of the data, which guarantees that models fitting the coreset will also provide a good fit for the original data set. We show that, perhaps surprisingly, Gaussian mixtures admit coresets of size independent of the size of the data set. More precisely, we prove that a weighted set of $O(dk^3/\eps^2)$ data points suffices for computing a $(1+\eps)$-approximation for the optimal model on the original $n$ data points. Moreover, such coresets can be efficiently constructed in a map-reduce style computation, as well as in a streaming setting. Our results rely on a novel reduction of statistical estimation to problems in computational geometry, as well as new complexity results about mixtures of Gaussians. We empirically evaluate our algorithms on several real data sets, including a density estimation problem in the context of earthquake detection using accelerometers in  mobile phones.
Generalised Coupled Tensor Factorisation
Authors: Kenan Y. Yılmaz, Ali T. Cemgil, Umut Simsekli
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12

We derive algorithms for generalised tensor factorisation (GTF) by building upon the well-established theory of Generalised Linear Models. Our algorithms are general in the sense that we can compute arbitrary factorisations in a message passing framework, derived for a broad class of exponential family distributions including special cases such as Tweedie's distributions corresponding to $\beta$-divergences. By bounding the step size of the Fisher Scoring iteration of the GLM, we obtain general updates for real data and multiplicative updates for non-negative data. The GTF framework is, then extended easily to address the problems when multiple observed tensors are factorised simultaneously. We illustrate our coupled factorisation approach on synthetic data as well as on a musical audio restoration problem.
Nearest Neighbor based Greedy Coordinate Descent
Authors: Inderjit S. Dhillon, Pradeep K. Ravikumar, Ambuj Tewari
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12

Increasingly, optimization problems in machine learning, especially those arising from high-dimensional statistical estimation, have a large number of variables. Modern statistical estimators developed over the past decade have statistical or sample complexity that depends only weakly on the number of parameters when there is some structure to the problem, such as sparsity. A central question is whether similar advances can be made in their computational complexity as well. In this paper, we propose strategies that indicate that such advances can indeed be made. In particular, we investigate the greedy coordinate descent algorithm, and note that performing the greedy step efficiently weakens the costly dependence on the problem size provided the solution is sparse. We then propose a suite of methods that perform these greedy steps efficiently by a reduction to nearest neighbor search.   We also devise a more amenable form of greedy descent for composite non-smooth objectives; as well as several approximate variants of such greedy descent. We develop a practical implementation of our algorithm that combines greedy coordinate descent with locality sensitive hashing. Without tuning the latter data structure, we are not only able to significantly speed up the vanilla greedy method, but also outperform cyclic descent when the problem size becomes large. Our results indicate the effectiveness of our nearest neighbor strategies, and also point to many open questions regarding the development of computational geometric techniques tailored towards first-order optimization methods.
The Fixed Points of Off-Policy TD
Authors: J. Z. Kolter
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: Open-Ended Question Answering, Reinforcement Learning

Off-policy learning, the ability for an agent to learn about a policy other than the one it is following, is a key element of Reinforcement Learning, and in recent years there has been much work on developing Temporal Different (TD) algorithms that are guaranteed to converge under off-policy sampling.  It has remained an open question, however, whether anything can be said a priori about the quality of the TD solution when off-policy sampling is employed with function approximation.  In general the answer is no: for arbitrary off-policy sampling the error of the TD solution can be unboundedly large, even when the approximator can represent the true value function well.  In this paper we propose a novel approach to address this problem: we show that by considering a certain convex subset of off-policy distributions we can indeed provide guarantees as to the solution quality similar to the on-policy case.  Furthermore, we show that we can efficiently project on to this convex set using only samples generated from the system.  The end result is a novel TD algorithm that has approximation guarantees even in the case of off-policy sampling and which empirically outperforms existing TD methods.
Generalizing from Several Related Classification Tasks to a New Unlabeled Sample
Authors: Gilles Blanchard, Gyemin Lee, Clayton Scott
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: General Classification

We consider the problem of assigning class labels to an unlabeled test  data set, given several labeled training data sets drawn from similar  distributions. This problem arises in several applications where data  distributions fluctuate because of biological, technical, or other sources  of variation. We develop a distribution-free, kernel-based approach to the  problem. This approach involves identifying an appropriate reproducing     kernel Hilbert space and optimizing a regularized empirical risk over the  space.  We present generalization error analysis, describe universal  kernels, and establish universal consistency of the proposed methodology.  Experimental results on flow cytometry data are presented.
Trace Lasso: a trace norm regularization for correlated designs
Authors: Edouard Grave, Guillaume R. Obozinski, Francis R. Bach
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12

Using the $\ell_1$-norm to regularize the estimation of  the parameter vector of a linear model leads to an unstable estimator when covariates are highly correlated. In this paper, we introduce a new penalty function which takes into account the correlation of the design matrix to stabilize the estimation. This norm, called the trace Lasso, uses the trace norm of the selected covariates, which is a convex surrogate of their rank, as the criterion of model complexity. We analyze the properties of our norm, describe an optimization algorithm based on reweighted least-squares, and illustrate the behavior of this norm on synthetic data, showing that it is more adapted to strong correlations than competing methods such as the elastic net.
Statistical Tests for Optimization Efficiency
Authors: Levi Boyles, Anoop Korattikara, Deva Ramanan, Max Welling
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: regression

Learning problems such as logistic regression are typically formulated as pure  optimization problems defined on some loss function. We argue that this view  ignores the fact that the loss function depends on stochastically generated data  which in turn determines an intrinsic scale of precision for statistical estimation.  By considering the statistical properties of the update variables used during  the optimization (e.g. gradients), we can construct frequentist hypothesis tests  to determine the reliability of these updates. We utilize subsets of the data  for computing updates, and use the hypothesis tests for determining when the  batch-size needs to be increased. This provides computational benefits and avoids  overfitting by stopping when the batch-size has become equal to size of the full  dataset. Moreover, the proposed algorithms depend on a single interpretable  parameter – the probability for an update to be in the wrong direction – which is  set to a single value across all algorithms and datasets. In this paper, we illustrate  these ideas on three L1 regularized coordinate algorithms: L1 -regularized L2 -loss  SVMs, L1 -regularized logistic regression, and the Lasso, but we emphasize that  the underlying methods are much more generally applicable.
Generalization Bounds and Consistency for Latent Structural Probit and Ramp Loss
Authors: Joseph Keshet, David A. Mcallester
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: Generalization Bounds

We consider latent structural versions of probit loss and ramp loss. We show that  these surrogate loss functions are consistent in the strong sense that for any feature map  (finite or infinite dimensional) they yield predictors approaching the infimum  task loss achievable by any linear predictor over the given features.  We also give  finite sample generalization bounds (convergence rates) for these loss functions.  These bounds suggest that probit loss converges more rapidly.  However, ramp loss is more easily optimized and may ultimately  be more practical.
A Brain-Machine Interface Operating with a Real-Time Spiking Neural Network Control Algorithm
Authors: Julie Dethier, Paul Nuyujukian, Chris Eliasmith, Terrence C. Stewart, Shauki A. Elasaad, Krishna V. Shenoy, Kwabena A. Boahen
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: Decoder, Translation

Motor prostheses aim to restore function to disabled patients. Despite compelling proof of concept systems, barriers to clinical translation remain. One challenge is to develop a low-power, fully-implantable system that dissipates only minimal power so as not to damage tissue. To this end, we implemented a Kalman-filter based decoder via a spiking neural network (SNN) and tested it in brain-machine interface (BMI) experiments with a rhesus monkey. The Kalman filter was trained to predict the arm’s velocity and mapped on to the SNN using the Neural Engineer- ing Framework (NEF). A 2,000-neuron embedded Matlab SNN implementation runs in real-time and its closed-loop performance is quite comparable to that of the standard Kalman filter. The success of this closed-loop decoder holds promise for hardware SNN implementations of statistical signal processing algorithms on neuromorphic chips, which may offer power savings necessary to overcome a major obstacle to the successful clinical translation of neural motor prostheses.
Multi-Bandit Best Arm Identification
Authors: Victor Gabillon, Mohammad Ghavamzadeh, Alessandro Lazaric, Sébastien Bubeck
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12

We study the problem of identifying the best arm in each of the bandits in a multi-bandit multi-armed setting. We first propose an algorithm called Gap-based Exploration (GapE) that focuses on the arms whose mean is close to the mean of the best arm in the same bandit (i.e., small gap). We then introduce an algorithm, called GapE-V, which takes into account the variance of the arms in addition to their gap. We prove an upper-bound on the probability of error for both algorithms. Since GapE and GapE-V need to tune an exploration parameter that depends on the complexity of the problem, which is often unknown in advance, we also introduce variations of these algorithms that estimate this complexity online. Finally, we evaluate the performance of these algorithms and compare them to other allocation strategies on a number of synthetic problems.
Randomized Algorithms for Comparison-based Search
Authors: Dominique Tschopp, Suhas Diggavi, Payam Delgosha, Soheil Mohajer
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: Object, Retrieval

This paper addresses the problem of finding the nearest neighbor (or    one of the $R$-nearest neighbors) of a query object $q$ in a    database of $n$ objects, when we can only use a comparison    oracle. The comparison oracle, given two reference objects and a    query object, returns the reference object most similar to the query    object.  The main problem we study is how to search the database for    the nearest neighbor (NN) of a query, while minimizing the    questions.  The difficulty of this problem depends on properties of    the underlying database. We show the importance of a    characterization: \emph{combinatorial disorder} $D$ which defines    approximate triangle inequalities on ranks. We present a lower bound    of $\Omega(D\log \frac{n}{D}+D^2)$ average number of questions in    the search phase for any randomized algorithm, which demonstrates    the fundamental role of $D$ for worst case behavior. We develop a    randomized scheme for NN retrieval in $O(D^3\log^2 n+ D\log^2 n    \log\log n^{D^3})$ questions.  The learning requires asking $O(n    D^3\log^2 n+ D \log^2 n \log\log n^{D^3})$ questions and    $O(n\log^2n/\log(2D))$ bits to store.
An Empirical Evaluation of Thompson Sampling
Authors: Olivier Chapelle, Lihong Li
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: Multi-Armed Bandits, Thompson Sampling

Thompson sampling is one of oldest heuristic to address the exploration / exploitation trade-off, but it is surprisingly not very popular in the literature. We present here some empirical results using Thompson sampling on simulated and real data, and show that it is highly competitive. And since this heuristic is very easy to implement, we argue that it should be part of the standard baselines to compare against.
Blending Autonomous Exploration and Apprenticeship Learning
Authors: Thomas J. Walsh, Daniel K. Hewlett, Clayton T. Morrison
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

We present theoretical and empirical results for a framework  that combines the benefits of apprenticeship and autonomous reinforcement learning.  Our approach modifies an existing apprenticeship learning framework that relies on teacher demonstrations and does not necessarily explore the environment.  The first change is replacing previously used Mistake Bound model learners with a recently proposed framework that melds the  KWIK and Mistake Bound supervised learning protocols.  The second change is introducing a communication of expected utility from the student to the teacher.   The resulting system only uses teacher traces when the agent needs to learn concepts it cannot efficiently learn on its own.
Nonnegative dictionary learning in the exponential noise model for adaptive music signal representation
Authors: Onur Dikmen, Cédric Févotte
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: Audio Signal Processing, Dictionary Learning

In this paper we describe a maximum likelihood likelihood approach for dictionary learning in the multiplicative exponential noise model. This model is prevalent in audio signal processing where it underlies a generative composite model of the power spectrogram. Maximum joint likelihood estimation of the dictionary and expansion coefficients leads to a nonnegative matrix factorization problem where the Itakura-Saito divergence is used. The optimality of this approach is in question because the number of parameters (which include the expansion coefficients) grows with the number of observations. In this paper we describe a variational procedure for optimization of the marginal likelihood, i.e., the likelihood of the dictionary where the activation coefficients have been integrated out (given a specific prior). We compare the output of both maximum joint likelihood estimation (i.e., standard Itakura-Saito NMF) and maximum marginal likelihood estimation (MMLE) on real and synthetical datasets. The MMLE approach is shown to embed automatic model order selection, akin to automatic relevance determination.
Sparse Features for PCA-Like Linear Regression
Authors: Christos Boutsidis, Petros Drineas, Malik Magdon-Ismail
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: regression

Principal Components Analysis~(PCA) is often used as a feature extraction procedure. Given a matrix $X \in \mathbb{R}^{n \times d}$, whose rows represent $n$ data points with respect to $d$ features, the top $k$ right singular vectors of $X$ (the so-called \textit{eigenfeatures}), are arbitrary linear combinations of all available features. The eigenfeatures are very useful in data analysis, including the regularization of linear regression. Enforcing sparsity on the eigenfeatures, i.e., forcing them to be linear combinations of only a \textit{small} number of actual features (as opposed to all available features), can promote better generalization error and improve the interpretability of the eigenfeatures. We present deterministic and randomized algorithms that construct such sparse eigenfeatures while \emph{provably} achieving in-sample performance comparable to regularized linear regression. Our algorithms are relatively simple and practically efficient, and we demonstrate their performance on several data sets.
Analytical Results for the Error in Filtering of Gaussian Processes
Authors: Alex K. Susemihl, Ron Meir, Manfred Opper
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: Decoder, Gaussian Processes, Point Processes, State Estimation

Bayesian filtering of stochastic stimuli has received a great deal of attention re- cently. It has been applied to describe the way in which biological systems dy- namically represent and make decisions about the environment. There have been no exact results for the error in the biologically plausible setting of inference on point process, however. We present an exact analysis of the evolution of the mean- squared error in a state estimation task using Gaussian-tuned point processes as sensors. This allows us to study the dynamics of the error of an optimal Bayesian decoder, providing insights into the limits obtainable in this task. This is done for Markovian and a class of non-Markovian Gaussian processes. We find that there is an optimal tuning width for which the error is minimized. This leads to a char- acterization of the optimal encoding for the setting as a function of the statistics of the stimulus, providing a mathematically sound primer for an ecological theory of sensory processing.
Improved Algorithms for Linear Stochastic Bandits
Authors: Yasin Abbasi-Yadkori, Dávid Pál, Csaba Szepesvári
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12

We improve the theoretical analysis and empirical performance of algorithms for the stochastic multi-armed bandit problem and the linear stochastic multi-armed bandit problem. In particular, we show that a simple modification of Auer’s UCB algorithm (Auer, 2002) achieves with high probability constant regret. More importantly, we modify and, consequently, improve the analysis of the algorithm for the for linear stochastic bandit problem studied by Auer (2002), Dani et al. (2008), Rusmevichientong and Tsitsiklis (2010), Li et al. (2010). Our modification improves the regret bound by a logarithmic factor, though experiments show a vast improvement. In both cases, the improvement stems from the construction of smaller confidence sets. For their construction we use a novel tail inequality for vector-valued martingales.