pwc-archive/papers-with-abstracts huggingface dataset:
A Comparative Framework for Preconditioned Lasso Algorithms
Authors: Fabian L. Wauthier, Nebojsa Jojic, Michael. I. Jordan
Date: 2013-12-01 00:00:00
Proceeding: NeurIPS 2013 12

The Lasso is a cornerstone of modern multivariate data analysis, yet its performance suffers in the common situation in which covariates are correlated. This limitation has led to a growing number of \emph{Preconditioned Lasso} algorithms that pre-multiply $X$ and $y$ by matrices $P_X$, $P_y$ prior to running the standard Lasso. A direct comparison of these and similar Lasso-style algorithms to the original Lasso is difficult because the performance of all of these methods depends critically on an auxiliary penalty parameter $\lambda$. In this paper we propose an agnostic, theoretical framework for comparing Preconditioned Lasso algorithms to the Lasso without having to choose $\lambda$. We apply our framework to three Preconditioned Lasso instances and highlight when they will outperform the Lasso. Additionally, our theory offers insights into the fragilities of these algorithms to which we provide partial solutions.
Binary to Bushy: Bayesian Hierarchical Clustering with the Beta Coalescent
Authors: Yuening Hu, Jordan L. Ying, Hal Daume III, Z. Irene Ying
Date: 2013-12-01 00:00:00
Proceeding: NeurIPS 2013 12
Tasks: Clustering

Discovering hierarchical regularities in data is a key problem in interacting   with large datasets, modeling cognition, and encoding knowledge. A previous   Bayesian solution---Kingman's coalescent---provides a convenient probabilistic   model for data represented as a binary tree. Unfortunately, this is   inappropriate for data better described by bushier trees. We generalize an   existing belief propagation framework of Kingman's coalescent to the   beta coalescent, which models a wider range of tree structures.   Because of the complex combinatorial search over possible structures, we   develop new sampling schemes using sequential Monte Carlo and Dirichlet   process mixture models, which render inference efficient and tractable.     We present results on both synthetic and real data that show the beta coalescent      outperforms Kingman's coalescent on real datasets and is qualitatively better at    capturing data in bushy hierarchies.
Lexical and Hierarchical Topic Regression
Authors: Viet-An Nguyen, Jordan L. Ying, Philip Resnik
Date: 2013-12-01 00:00:00
Proceeding: NeurIPS 2013 12
Tasks: regression, Sentiment Analysis

Inspired by a two-level theory that unifies agenda setting and ideological  framing, we propose supervised hierarchical latent Dirichlet allocation  (SHLDA) which jointly captures documents' multi-level topic structure and  their polar response variables. Our model extends the nested Chinese restaurant  process to discover a tree-structured topic hierarchy and uses both per-topic  hierarchical and per-word lexical regression parameters to model the response  variables. Experiments in a political domain and on sentiment analysis tasks  show that SHLDA improves predictive accuracy while adding a new dimension of  insight into how topics under discussion are framed.
Stochastic Convex Optimization with Multiple Objectives
Authors: Mehrdad Mahdavi, Tianbao Yang, Rong Jin
Date: 2013-12-01 00:00:00
Proceeding: NeurIPS 2013 12
Tasks: Stochastic Optimization

In this paper, we are interested in the development of efficient algorithms  for convex optimization problems in the simultaneous presence of multiple objectives and stochasticity in the first-order information.   We  cast the stochastic multiple objective optimization problem into a constrained optimization problem by choosing one function as the objective and try to bound other objectives by appropriate thresholds.  We first examine  a two stages exploration-exploitation based algorithm which first approximates  the stochastic objectives by sampling  and  then solves a constrained stochastic optimization problem by projected gradient method. This method  attains a  suboptimal  convergence rate  even under  strong assumption on the objectives. Our second approach is an efficient primal-dual stochastic algorithm. It leverages on the theory of Lagrangian method in constrained optimization and attains  the optimal convergence rate of $[O(1/ \sqrt{T})]$ in high probability for general Lipschitz continuous objectives.
Memoized Online Variational Inference for Dirichlet Process Mixture Models
Authors: Michael C. Hughes, Erik Sudderth
Date: 2013-12-01 00:00:00
Proceeding: NeurIPS 2013 12
Tasks: Clustering, Denoising, Image Clustering, Variational Inference

Variational inference algorithms provide the most effective framework for large-scale training  of Bayesian nonparametric models. Stochastic online approaches are promising, but are sensitive to the chosen learning rate and often converge to poor local optima.  We present a new algorithm, memoized online variational inference, which scales to very large (yet finite) datasets while avoiding the complexities of stochastic gradient.  Our algorithm maintains finite-dimensional sufficient statistics from batches of the full dataset, requiring some additional memory but still scaling to millions of examples.  Exploiting nested families of variational bounds for infinite nonparametric models, we develop principled birth and merge moves allowing non-local optimization.  Births adaptively add components to the model to escape local optima, while merges remove redundancy and improve speed.  Using Dirichlet process mixture models for image clustering and denoising, we demonstrate major improvements in robustness and accuracy.
Designed Measurements for Vector Count Data
Authors: Liming Wang, David E. Carlson, Miguel Rodrigues, David Wilcox, Robert Calderbank, Lawrence Carin
Date: 2013-12-01 00:00:00
Proceeding: NeurIPS 2013 12
Tasks: Compressive Sensing

We consider design of linear projection measurements for a vector Poisson signal model. The projections are performed on the vector Poisson rate, $X\in\mathbb{R}_+^n$, and the observed data are a vector of counts, $Y\in\mathbb{Z}_+^m$. The projection matrix is designed by maximizing mutual information between $Y$ and $X$, $I(Y;X)$. When there is a latent class label $C\in\{1,\dots,L\}$ associated with $X$, we consider the mutual information with respect to $Y$ and $C$, $I(Y;C)$. New analytic expressions for the gradient of $I(Y;X)$ and $I(Y;C)$ are presented, with gradient performed with respect to the measurement matrix. Connections are made to the more widely studied Gaussian measurement model. Example results are presented for compressive topic modeling of a document corpora (word counting), and hyperspectral compressive sensing for chemical classification (photon counting).
Robust Transfer Principal Component Analysis with Rank Constraints
Authors: Yuhong Guo
Date: 2013-12-01 00:00:00
Proceeding: NeurIPS 2013 12
Tasks: Denoising, Dimensionality Reduction, Image Denoising

Principal component analysis (PCA), a well-established technique for data analysis and processing, provides a convenient form of dimensionality reduction that is effective for cleaning small Gaussian noises presented in the data. However, the applicability of standard principal component analysis in real scenarios is limited by its sensitivity to large errors. In this paper, we tackle the challenge problem of recovering data corrupted with errors of high magnitude by developing a novel robust transfer principal component analysis method. Our method is based on the assumption that useful information for the recovery of a corrupted data matrix can be gained from an uncorrupted related data matrix. Speciﬁcally, we formulate the data recovery problem as a joint robust principal component analysis problem on the two data matrices, with shared common principal components across matrices and individual principal components speciﬁc to each data matrix. The formulated optimization problem is a minimization problem over a convex objective function but with non-convex rank constraints. We develop an efﬁcient proximal projected gradient descent algorithm to solve the proposed optimization problem with convergence guarantees. Our empirical results over image denoising tasks show the proposed method can effectively recover images with random large errors, and signiﬁcantly outperform both standard PCA and robust PCA.
Probabilistic Principal Geodesic Analysis
Authors: Miaomiao Zhang, Tom Fletcher
Date: 2013-12-01 00:00:00
Proceeding: NeurIPS 2013 12
Tasks: Dimensionality Reduction

Principal geodesic analysis (PGA) is a generalization of principal component analysis (PCA) for dimensionality reduction of data on a Riemannian manifold. Currently PGA is defined as a geometric fit to the data, rather than as a probabilistic model. Inspired by probabilistic PCA, we present a latent variable model for PGA that provides a probabilistic framework for factor analysis on manifolds. To compute maximum likelihood estimates of the parameters in our model, we develop a Monte Carlo Expectation Maximization algorithm, where the expectation is approximated by Hamiltonian Monte Carlo sampling of the latent variables. We demonstrate the ability of our method to recover the ground truth parameters in simulated sphere data, as well as its effectiveness in analyzing shape variability of a corpus callosum data set from human brain images.
Confidence Intervals and Hypothesis Testing for High-Dimensional Statistical Models
Authors: Adel Javanmard, Andrea Montanari
Date: 2013-12-01 00:00:00
Proceeding: NeurIPS 2013 12
Tasks: Diabetes Prediction, parameter estimation, Two-sample testing, Vocal Bursts Intensity Prediction

Fitting high-dimensional statistical models often requires the use of non-linear parameter estimation procedures. As a consequence, it is generally impossible to obtain an exact characterization of the probability distribution of the parameter estimates. This in turn implies that it is extremely challenging to quantify the `uncertainty' associated with a certain parameter estimate. Concretely, no commonly accepted procedure exists for computing classical measures of uncertainty and statistical significance as confidence intervals or p-values.  We consider here a broad class of regression problems, and propose  an efficient algorithm  for constructing confidence intervals and p-values.  The resulting confidence intervals have nearly optimal size. When testing for the null hypothesis that a certain parameter is vanishing, our method has nearly optimal power.  Our approach is based on constructing a `de-biased' version of regularized M-estimators. The new construction  improves over recent work in the field in that it does not assume a special structure on the design matrix. Furthermore, proofs are remarkably simple. We test our method on a diabetes prediction problem.
Learning with Noisy Labels
Authors: Nagarajan Natarajan, Inderjit S. Dhillon, Pradeep K. Ravikumar, Ambuj Tewari
Date: 2013-12-01 00:00:00
Proceeding: NeurIPS 2013 12
Tasks: Binary Classification, General Classification, Learning with noisy labels

In this paper, we theoretically study the problem of binary classification in the presence of random classification noise --- the learner, instead of seeing the true labels, sees labels that have independently been flipped with some small probability. Moreover, random label noise is \emph{class-conditional} --- the flip probability depends on the class. We provide two approaches to suitably modify any given surrogate loss function. First, we provide a simple unbiased estimator of any loss, and obtain performance bounds for empirical risk minimization in the presence of iid data with noisy labels. If the loss function satisfies a simple symmetry condition, we show that the method leads to an efficient algorithm for empirical minimization. Second, by leveraging a reduction of risk minimization under noisy labels to classification with weighted 0-1 loss, we suggest the use of a simple weighted surrogate loss, for which we are able to obtain strong empirical risk bounds. This approach has a very remarkable consequence --- methods used in practice such as biased SVM and weighted logistic regression are provably noise-tolerant. On a synthetic non-separable dataset, our methods achieve over 88\% accuracy even when 40\% of the labels are corrupted, and are competitive with respect to recently proposed methods for dealing with label noise in several benchmark datasets.
Tracking Time-varying Graphical Structure
Authors: Erich Kummerfeld, David Danks
Date: 2013-12-01 00:00:00
Proceeding: NeurIPS 2013 12

Structure learning algorithms for graphical models have focused almost exclusively on stable environments in which the underlying generative process does not change; that is, they assume that the generating model is globally stationary. In real-world environments, however, such changes often occur without warning or signal. Real-world data often come from generating models that are only locally stationary. In this paper, we present LoSST, a novel, heuristic structure learning algorithm that tracks changes in graphical model structure or parameters in a dynamic, real-time manner. We show by simulation that the algorithm performs comparably to batch-mode learning when the generating graphical structure is globally stationary, and significantly better when it is only locally stationary.
Factorized Asymptotic Bayesian Inference for Latent Feature Models
Authors: Kohei Hayashi, Ryohei Fujimaki
Date: 2013-12-01 00:00:00
Proceeding: NeurIPS 2013 12
Tasks: Bayesian Inference, Computational Efficiency, Model Selection

This paper extends factorized asymptotic Bayesian (FAB) inference for latent feature models~(LFMs). FAB inference has not been applicable to models, including LFMs, without a specific condition on the Hesqsian matrix of a complete log-likelihood, which is required to derive a factorized information criterion''~(FIC). Our asymptotic analysis of the Hessian matrix of LFMs shows that FIC of LFMs has the same form as those of mixture models.  FAB/LFMs have several desirable properties (e.g., automatic hidden states selection and parameter identifiability) and empirically perform better than state-of-the-art Indian Buffet processes in terms of model selection, prediction, and computational efficiency."
More Effective Distributed ML via a Stale Synchronous Parallel Parameter Server
Authors: Qirong Ho, James Cipar, Henggang Cui, Seunghak Lee, Jin Kyu Kim, Phillip B. Gibbons, Garth A. Gibson, Greg Ganger, Eric P. Xing
Date: 2013-12-01 00:00:00
Proceeding: NeurIPS 2013 12

We propose a parameter server system for distributed ML, which follows a Stale Synchronous Parallel (SSP) model of computation that maximizes the time computational workers spend doing useful work on ML algorithms, while still providing correctness guarantees. The parameter server provides an easy-to-use shared interface for read/write access to an ML model's values (parameters and variables), and the SSP model allows distributed workers to read older, stale versions of these values from a local cache, instead of waiting to get them from a central storage. This significantly increases the proportion of time workers spend computing, as opposed to waiting. Furthermore, the SSP model ensures ML algorithm correctness by limiting the maximum age of the stale values. We provide a proof of correctness under SSP, as well as empirical results demonstrating that the SSP model achieves faster algorithm convergence on several different ML problems, compared to fully-synchronous and asynchronous schemes.
Bayesian Estimation of Latently-grouped Parameters in Undirected Graphical Models
Authors: Jie Liu, David Page
Date: 2013-12-01 00:00:00
Proceeding: NeurIPS 2013 12

In large-scale applications of undirected graphical models, such as social networks and biological networks, similar patterns occur frequently and give rise to similar parameters. In this situation, it is beneficial to group the parameters for more efficient learning. We show that even when the grouping is unknown, we can infer these parameter groups during learning via a Bayesian approach. We impose a Dirichlet process prior on the parameters. Posterior inference usually involves calculating intractable terms, and we propose two approximation algorithms, namely a Metropolis-Hastings algorithm with auxiliary variables and a Gibbs sampling algorithm with stripped Beta approximation (Gibbs_SBA). Simulations show that both algorithms outperform conventional maximum likelihood estimation (MLE). Gibbs_SBA's performance is close to Gibbs sampling with exact likelihood calculation. Models learned with Gibbs_SBA also generalize better than the models learned by MLE on real-world Senate voting data.
Online Learning with Costly Features and Labels
Authors: Nicolò Cesa-Bianchi, Ofer Dekel, Ohad Shamir
Date: 2013-12-01 00:00:00
Proceeding: NeurIPS 2013 12

We study the power of different types of adaptive (nonoblivious) adversaries in the setting of prediction with expert advice, under both full-information and bandit feedback. We measure the player's performance using a new notion of regret, also known as policy regret, which better captures the adversary's adaptiveness to the player's behavior. In a setting where losses are allowed to drift, we characterize ---in a nearly complete manner--- the power of adaptive adversaries with bounded memories and switching costs. In particular, we show that with switching costs, the attainable rate with bandit feedback is $T^{2/3}$. Interestingly, this rate is significantly worse than the $\sqrt{T}$ rate attainable with switching costs in the full-information case. Via a novel reduction from experts to bandits, we also show that a bounded memory adversary can force $T^{2/3}$ regret even in the full information case, proving that switching costs are easier to control than bounded memory adversaries. Our lower bounds rely on a new stochastic adversary strategy that generates loss processes with strong dependencies.
Sparse nonnegative deconvolution for compressive calcium imaging: algorithms and phase transitions
Authors: Eftychios A. Pnevmatikakis, Liam Paninski
Date: 2013-12-01 00:00:00
Proceeding: NeurIPS 2013 12
Tasks: compressed sensing, Time Series, Time Series Analysis

We propose a compressed sensing (CS) calcium imaging framework for monitoring large neuronal populations, where we image randomized projections of the spatial calcium concentration at each timestep, instead of measuring the concentration at individual locations. We develop scalable nonnegative deconvolution methods for extracting the neuronal spike time series from such observations. We also address the problem of demixing the spatial locations of the neurons using rank-penalized matrix factorization methods. By exploiting the sparsity of neural spiking we demonstrate that the number of measurements needed per timestep is significantly smaller than the total number of neurons, a result that can potentially enable imaging of larger populations at considerably faster rates compared to traditional raster-scanning techniques. Unlike traditional CS setups, our problem involves a block-diagonal sensing matrix and a non-orthogonal sparse basis that spans multiple timesteps. We study the effect of these distinctive features in a noiseless setup using recent results relating conic geometry to CS. We provide tight approximations to the number of measurements needed for perfect deconvolution for certain classes of spiking processes, and show that this number displays a phase transition," similar to phenomena observed in more standard CS settings; however, in this case the required measurement rate depends not just on the mean sparsity level but also on other details of the underlying spiking process."
A Novel Two-Step Method for Cross Language Representation Learning
Authors: Min Xiao, Yuhong Guo
Date: 2013-12-01 00:00:00
Proceeding: NeurIPS 2013 12
Tasks: Matrix Completion, Representation Learning, Vocal Bursts Valence Prediction

Cross language text classiﬁcation is an important learning task in natural language processing. A critical challenge of cross language learning lies in that words of different languages are in disjoint feature spaces. In this paper, we propose a two-step representation learning method to bridge the feature spaces of different languages by exploiting a set of parallel bilingual documents. Speciﬁcally, we ﬁrst formulate a matrix completion problem to produce a complete parallel document-term matrix for all documents in two languages, and then induce a cross-lingual document representation by applying latent semantic indexing on the obtained matrix. We use a projected gradient descent algorithm to solve the formulated matrix completion problem with convergence guarantees. The proposed approach is evaluated by conducting a set of experiments with cross language sentiment classiﬁcation tasks on Amazon product reviews. The experimental results demonstrate that the proposed learning approach outperforms a number of comparison cross language representation learning methods, especially when the number of parallel bilingual documents is small.
Graphical Models for Inference with Missing Data
Authors: Karthika Mohan, Judea Pearl, Jin Tian
Date: 2013-12-01 00:00:00
Proceeding: NeurIPS 2013 12

We address the problem of deciding whether there exists a consistent estimator of a given relation Q, when data are missing not at random. We employ a formal representation called `Missingness Graphs' to explicitly portray the causal mechanisms responsible for missingness and to encode dependencies between these mechanisms and the variables being measured. Using this representation, we define the notion of \textit{recoverability} which ensures that, for a given missingness-graph $G$ and a given query $Q$ an algorithm exists such that in the limit of large samples, it produces an estimate of $Q$ \textit{as if} no data were missing. We further present conditions that the graph should satisfy in order for recoverability to hold and devise algorithms to detect the presence of these conditions.
Reshaping Visual Datasets for Domain Adaptation
Authors: Boqing Gong, Kristen Grauman, Fei Sha
Date: 2013-12-01 00:00:00
Proceeding: NeurIPS 2013 12
Tasks: Activity Recognition, Domain Adaptation, Human Activity Recognition, Object Recognition

In visual recognition problems, the common data distribution mismatches between training and testing make domain adaptation essential. However, image data is difficult to manually divide into the discrete domains required by adaptation algorithms, and the standard practice of equating datasets with domains is a weak proxy for all the real conditions that alter the statistics in complex ways (lighting, pose, background, resolution, etc.) We propose an approach to automatically discover latent domains in image or video datasets. Our formulation imposes two key properties on domains: maximum distinctiveness and maximum learnability. By maximum distinctiveness, we require the underlying distributions of the identified domains to be different from each other; by maximum learnability, we ensure that a strong discriminative model can be learned from the domain. We devise a nonparametric representation and efficient optimization procedure for distinctiveness, which, when coupled with our learnability constraint, can successfully discover domains among both training and test data. We extensively evaluate our approach on object recognition and human activity recognition tasks.