pwc-archive/papers-with-abstracts huggingface dataset:
A Gaussian Process Model of Quasar Spectral Energy Distributions
Authors: Andrew Miller, Albert Wu, Jeff Regier, Jon McAuliffe, Dustin Lang, Mr. Prabhat, David Schlegel, Ryan P. Adams
Date: 2015-12-01 00:00:00
Proceeding: NeurIPS 2015 12

We propose a method for combining two sources of astronomical data, spectroscopy and photometry, that carry information about sources of light (e.g., stars, galaxies, and quasars) at extremely different spectral resolutions.  Our model treats the spectral energy distribution (SED) of the radiation from a source as a latent variable that jointly explains both photometric and spectroscopic observations.  We place a flexible, nonparametric prior over the SED of a light source that admits a physically interpretable decomposition, and allows us to tractably perform inference.  We use our model to predict the distribution of the redshift of a quasar from five-band (low spectral resolution) photometric data, the so called ``photo-z'' problem. Our method shows that tools from machine learning and Bayesian statistics allow us to leverage multiple resolutions of information to make accurate predictions with well-characterized uncertainties.
Hidden Technical Debt in Machine Learning Systems
Authors: D. Sculley, Gary Holt, Daniel Golovin, Eugene Davydov, Todd Phillips, Dietmar Ebner, Vinay Chaudhary, Michael Young, Jean-François Crespo, Dan Dennison
Date: 2015-12-01 00:00:00
Proceeding: NeurIPS 2015 12
Tasks: BIG-bench Machine Learning

Machine learning offers a fantastically powerful toolkit for building useful complexprediction systems quickly. This paper argues it is dangerous to think ofthese quick wins as coming for free. Using the software engineering frameworkof technical debt, we find it is common to incur massive ongoing maintenancecosts in real-world ML systems. We explore several ML-specific risk factors toaccount for in system design. These include boundary erosion, entanglement,hidden feedback loops, undeclared consumers, data dependencies, configurationissues, changes in the external world, and a variety of system-level anti-patterns.
Local Causal Discovery of Direct Causes and Effects
Authors: Tian Gao, Qiang Ji
Date: 2015-12-01 00:00:00
Proceeding: NeurIPS 2015 12
Tasks: Causal Discovery

We focus on the discovery and identification of direct causes and effects of a target variable in a causal network. State-of-the-art algorithms generally need to find the global causal structures in the form of complete partial directed acyclic graphs in order to identify the direct causes and effects of a target variable. While these algorithms are effective, it is often unnecessary and wasteful to find the global structures when we are only interested in one target variable (such as class labels). We propose a new local causal discovery algorithm, called Causal Markov Blanket (CMB), to identify the direct causes and effects of a target variable based on Markov Blanket Discovery. CMB is designed to conduct causal discovery among multiple variables, but focuses only on finding causal relationships between a specific target variable and other variables. Under standard assumptions, we show both theoretically and experimentally that the proposed local causal discovery algorithm can obtain the comparable identification accuracy as global methods but significantly improve their efficiency, often by more than one order of magnitude.
High Dimensional EM Algorithm: Statistical Optimization and Asymptotic Normality
Authors: Zhaoran Wang, Quanquan Gu, Yang Ning, Han Liu
Date: 2015-12-01 00:00:00
Proceeding: NeurIPS 2015 12
Tasks: parameter estimation, Vocal Bursts Intensity Prediction

We provide a general theory of the expectation-maximization (EM) algorithm for inferring high dimensional latent variable models.   In particular, we make two contributions: (i) For parameter estimation, we propose a novel high dimensional EM algorithm which naturally incorporates sparsity structure into parameter estimation.  With an appropriate initialization, this algorithm converges at a geometric rate and attains an estimator with the (near-)optimal statistical rate of convergence.  (ii) Based on the obtained estimator, we propose a new inferential procedure for testing hypotheses for low dimensional components of high dimensional parameters.  For a broad family of statistical models,  our framework establishes the first computationally feasible approach for optimal estimation and asymptotic inference in high dimensions.
Revenue Optimization against Strategic Buyers
Authors: Mehryar Mohri, Andres Munoz
Date: 2015-12-01 00:00:00
Proceeding: NeurIPS 2015 12

We present a revenue optimization algorithm for posted-price auctions when facing a buyer with random valuations who seeks to optimize his $\gamma$-discounted surplus. To analyze this problem, we introduce the notion of  epsilon-strategic buyer, a more natural notion of strategic behavior than what has been used in the past.  We improve upon the previous state-of-the-art and achieve an optimal regret bound in  $O\Big( \log T + \frac{1}{\log(1/\gamma)} \Big)$ when the seller can offer prices from a finite set $\cP$ and provide a regret bound in  $\widetilde O \Big(\sqrt{T} + \frac{T^{1/4}}{\log(1/\gamma)} \Big)$ when the buyer is offered prices from the interval $[0, 1]$.
Sparse and Low-Rank Tensor Decomposition
Authors: Parikshit Shah, Nikhil Rao, Gongguo Tang
Date: 2015-12-01 00:00:00
Proceeding: NeurIPS 2015 12
Tasks: Tensor Decomposition

Motivated by the problem of robust factorization of a low-rank tensor, we study the question of sparse and low-rank tensor decomposition. We present an efficient computational algorithm that modifies Leurgans' algoirthm for tensor factorization. Our method relies on a reduction of the problem to sparse and low-rank matrix decomposition via the notion of tensor contraction. We use well-understood convex techniques for solving the reduced matrix sub-problem which then allows us to perform the full decomposition of the tensor. We delineate situations where the problem is recoverable and provide theoretical guarantees for our algorithm. We validate our algorithm with numerical experiments.
Minimax Time Series Prediction
Authors: Wouter M. Koolen, Alan Malek, Peter L. Bartlett, Yasin Abbasi
Date: 2015-12-01 00:00:00
Proceeding: NeurIPS 2015 12
Tasks: Prediction, Time Series, Time Series Analysis, Time Series Prediction

We consider an adversarial formulation of the problem ofpredicting a time series with square loss.  The aim is to predictan arbitrary sequence of vectors almost as well as the bestsmooth comparator sequence in retrospect.  Our approach allowsnatural measures of smoothness such as the squared norm ofincrements. More generally, we consider a linear time seriesmodel and penalize the comparator sequence through the energy ofthe implied driving noise terms.  We derive the minimax strategyfor all problems of this type and show that it can be implementedefficiently.  The optimal predictions are linear in the previousobservations.  We obtain an explicit expression for the regret interms of the parameters defining the problem.  For typical,simple definitions of smoothness, the computation of the optimalpredictions involves only sparse matrices.  In the case ofnorm-constrained data, where the smoothness is defined in termsof the squared norm of the comparator's increments, we show thatthe regret grows as $T/\sqrt{\lambda_T}$, where $T$ is the lengthof the game and $\lambda_T$ is an increasing limit on comparatorsmoothness.
Differentially Private Learning of Structured Discrete Distributions
Authors: Ilias Diakonikolas, Moritz Hardt, Ludwig Schmidt
Date: 2015-12-01 00:00:00
Proceeding: NeurIPS 2015 12

We investigate the problem of learning an unknown probability distribution over a discrete population from random samples. Our goal is to design efficient algorithms that simultaneously achieve low error in total variation norm while guaranteeing Differential Privacy to the individuals of the population.We describe a general approach that yields near sample-optimal and computationally efficient differentially private estimators for a wide range of well-studied and natural distribution families. Our theoretical results show that for a wide variety of structured distributions there exist private estimation algorithms that are nearly as efficient - both in terms of sample size and running time - as their non-private counterparts. We complement our theoretical guarantees with an experimental evaluation. Our experiments illustrate the speed and accuracy of our private estimators on both synthetic mixture models and a large public data set.
Estimating Jaccard Index with Missing Observations: A Matrix Calibration Approach
Authors: Wenye Li
Date: 2015-12-01 00:00:00
Proceeding: NeurIPS 2015 12

The Jaccard index is a standard statistics for comparing the pairwise similarity between data samples. This paper investigates the problem of estimating a Jaccard index matrix when there are missing observations in data samples. Starting from a Jaccard index matrix approximated from the incomplete data, our method calibrates the matrix to meet the requirement of positive semi-definiteness and other constraints, through a simple alternating projection algorithm. Compared with conventional approaches that estimate the similarity matrix based on the imputed data, our method has a strong advantage in that the calibrated matrix is guaranteed to be closer to the unknown ground truth in the Frobenius norm than the un-calibrated matrix (except in special cases they are identical). We carried out a series of empirical experiments and the results confirmed our theoretical justification. The evaluation also reported significantly improved results in real learning tasks on benchmarked datasets.
Local Expectation Gradients for Black Box Variational Inference
Authors: Michalis Titsias Rc Aueb, Miguel Lázaro-Gredilla
Date: 2015-12-01 00:00:00
Proceeding: NeurIPS 2015 12
Tasks: Variational Inference

We introduce local expectation gradients which is a general purpose stochastic variational inference algorithm for constructing stochastic gradients by sampling from the variational distribution. This algorithm divides the problem of estimating the stochastic gradients over multiple variational parameters into smaller sub-tasks so that each sub-task explores intelligently the most relevant part of the variational distribution. This is achieved by performing an exact expectation over the single random variable that most correlates with the variational parameter of interest resulting in a Rao-Blackwellized estimate that has low variance. Our method works efficiently for both continuous and discrete random variables. Furthermore, the proposed algorithm has interesting similarities with Gibbs sampling but at the same time, unlike Gibbs sampling, can be trivially parallelized.
NEXT: A System for Real-World Development, Evaluation, and Application of Active Learning
Authors: Kevin G. Jamieson, Lalit Jain, Chris Fernandez, Nicholas J. Glattard, Rob Nowak
Date: 2015-12-01 00:00:00
Proceeding: NeurIPS 2015 12
Tasks: Active Learning, BIG-bench Machine Learning

Active learning methods automatically adapt data collection by selecting the most informative samples in order to accelerate machine learning. Because of this, real-world testing and comparing active learning algorithms requires collecting new datasets (adaptively), rather than simply applying algorithms to benchmark datasets, as is the norm in (passive) machine learning research. To facilitate the development, testing and deployment of active learning for real applications, we have built an open-source software system for large-scale active learning research and experimentation.  The system, called NEXT,  provides a unique platform for real-world, reproducible active learning research. This paper details the challenges of building the system and demonstrates its capabilities with several experiments.  The results show how experimentation can help expose strengths and weaknesses of active learning algorithms, in sometimes unexpected and enlightening ways.
Taming the Wild: A Unified Analysis of Hogwild-Style Algorithms
Authors: Christopher M. De Sa, Ce Zhang, Kunle Olukotun, Christopher Ré
Date: 2015-12-01 00:00:00
Proceeding: NeurIPS 2015 12
Tasks: Matrix Completion

Stochastic gradient descent (SGD) is a ubiquitous algorithm for a variety of machine learning problems. Researchers and industry have developed several techniques to optimize SGD's runtime performance, including asynchronous execution and reduced precision. Our main result is a martingale-based analysis that enables us to capture the rich noise models that may arise from such techniques. Specifically, we useour new analysis in three ways: (1) we derive convergence rates for the convex case (Hogwild) with relaxed assumptions on the sparsity of the problem; (2) we analyze asynchronous SGD algorithms for non-convex matrix problems including matrix completion; and (3) we design and analyze an asynchronous SGD algorithm, called Buckwild, that uses lower-precision arithmetic. We show experimentally that our algorithms run efficiently for a variety of problems on modern hardware.
The Return of the Gating Network: Combining Generative Models and Discriminative Training in Natural Image Priors
Authors: Dan Rosenbaum, Yair Weiss
Date: 2015-12-01 00:00:00
Proceeding: NeurIPS 2015 12
Tasks: Image Restoration

In recent years, approaches based on machine learning have achieved state-of-the-art performance on image restoration problems. Successful approaches include both generative models of natural images as well as discriminative training of deep neural networks. Discriminative training of feed forward architectures allows explicit control over the computational cost of performing restoration and therefore often leads to better performance at the same cost at run time.  In contrast, generative models have the advantage that they can be trained once and then adapted to any image restoration task by a simple use of Bayes' rule. In this paper we show how to combine the strengths of both approaches by training a discriminative, feed-forward architecture to predict the state of latent variables in a generative model of natural images. We apply this idea to the very successful Gaussian Mixture Model (GMM) of natural images. We show that it is possible to achieve comparable performance as the original GMM but with two orders of magnitude improvement in run time while maintaining the advantage of generative models.
Associative Memory via a Sparse Recovery Model
Authors: Arya Mazumdar, Ankit Singh Rawat
Date: 2015-12-01 00:00:00
Proceeding: NeurIPS 2015 12
Tasks: model, valid

An associative memory is a structure learned from a dataset $\mathcal{M}$ of vectors (signals) in a way such that, given a noisy version of one of the vectors as input, the nearest valid  vector from $\mathcal{M}$ (nearest neighbor) is provided as output, preferably via a fast iterative algorithm. Traditionally, binary (or $q$-ary) Hopfield neural networks are used to  model the above structure. In this paper, for the first time, we propose a model of associative memory based on sparse recovery of signals. Our basic premise is simple. For a dataset, we learn a set of linear constraints that every vector in the  dataset must satisfy. Provided these linear constraints possess  some special properties, it is possible to cast the task of finding nearest neighbor as a sparse recovery problem. Assuming  generic random models for the dataset, we show that it is possible to store super-polynomial or exponential number of $n$-length vectors in a neural network of size $O(n)$. Furthermore, given a noisy version of one of the  stored vectors corrupted in near-linear number of coordinates, the vector can be correctly recalled using a neurally feasible algorithm.
Fast, Provable Algorithms for Isotonic Regression in all L_p-norms
Authors: Rasmus Kyng, Anup Rao, Sushant Sachdeva
Date: 2015-12-01 00:00:00
Proceeding: NeurIPS 2015 12
Tasks: All, regression

Given a directed acyclic graph $G,$ and a set of values $y$ on the vertices, the Isotonic Regression of $y$ is a vector $x$ that respects the partial order described by $G,$ and minimizes $\|x-y\|,$ for a specified norm.  This paper gives improved algorithms for computing the Isotonic Regression for all weighted $\ell_{p}$-norms with rigorous performance guarantees. Our algorithms are quite practical, and their variants can be implemented to run fast in practice.
Adversarial Prediction Games for Multivariate Losses
Authors: Hong Wang, Wei Xing, Kaiser Asif, Brian Ziebart
Date: 2015-12-01 00:00:00
Proceeding: NeurIPS 2015 12
Tasks: Information Retrieval, Prediction, Retrieval

Multivariate loss functions are used to assess performance in many modern prediction tasks, including information retrieval and ranking applications. Convex approximations are typically optimized in their place to avoid NP-hard empirical risk minimization problems. We propose to approximate the training data instead of the loss function by posing multivariate prediction as an adversarial game between a loss-minimizing prediction player and a loss-maximizing evaluation player constrained to match specified properties of training data. This avoids the non-convexity of empirical risk minimization, but game sizes are exponential in the number of predicted variables. We overcome this intractability using the double oracle constraint generation method. We demonstrate the efficiency and predictive performance of our approach on tasks evaluated using the precision at k, the F-score and the discounted cumulative gain.
Softstar: Heuristic-Guided Probabilistic Inference
Authors: Mathew Monfort, Brenden M. Lake, Brian Ziebart, Patrick Lucey, Josh Tenenbaum
Date: 2015-12-01 00:00:00
Proceeding: NeurIPS 2015 12
Tasks: BIG-bench Machine Learning, Prediction

Recent machine learning methods for sequential behavior prediction estimate the motives of behavior rather than the behavior itself. This higher-level abstraction improves generalization in different prediction settings, but computing predictions often becomes intractable in large decision spaces.  We propose the Softstar algorithm, a softened heuristic-guided search technique for the maximum entropy inverse optimal control model of sequential behavior.  This approach supports probabilistic search with bounded approximation error at a significantly reduced computational cost when compared to sampling based methods.  We present the algorithm, analyze approximation guarantees, and compare performance with simulation-based inference on two distinct complex decision tasks.
Deep Poisson Factor Modeling
Authors: Ricardo Henao, Zhe Gan, James Lu, Lawrence Carin
Date: 2015-12-01 00:00:00
Proceeding: NeurIPS 2015 12
Tasks: Topic Models

We propose a new deep architecture for topic modeling, based on Poisson Factor Analysis (PFA) modules. The model is composed of a Poisson distribution to model observed vectors of counts, as well as a deep hierarchy of hidden binary units. Rather than using logistic functions to characterize the probability that a latent binary unit is on, we employ a Bernoulli-Poisson link, which allows PFA modules to be used repeatedly in the deep architecture. We also describe an approach to build discriminative topic models, by adapting PFA modules. We derive efficient inference via MCMC and stochastic variational methods, that scale with the number of non-zeros in the data and binary units, yielding significant efficiency, relative to models based on logistic links. Experiments on several corpora demonstrate the advantages of our model when compared to related deep models.
Learning with Relaxed Supervision
Authors: Jacob Steinhardt, Percy S. Liang
Date: 2015-12-01 00:00:00
Proceeding: NeurIPS 2015 12
Tasks: valid

For weakly-supervised problems with deterministic constraints between the latent variables and observed output, learning necessitates performing inference over latent variables conditioned on the output, which can be intractable no matter how simple the model family is. Even finding a single latent variable setting that satisfies the constraints could be difficult; for instance, the observed output may be the result of a latent database query or graphics program which must be inferred. Here, the difficulty lies in not the model but the supervision, and poor approximations at this stage could lead to following the wrong learning signal entirely. In this paper, we develop a rigorous approach to relaxing the supervision, which yields asymptotically consistent parameter estimates despite altering the supervision. Our approach parameterizes a family of increasingly accurate relaxations, and jointly optimizes both the model and relaxation parameters, while formulating constraints between these parameters to ensure efficient inference. These efficiency constraints allow us to learn in otherwise intractable settings, while asymptotic consistency ensures that we always follow a valid learning signal.
Accelerated Mirror Descent in Continuous and Discrete Time
Authors: Walid Krichene, Alexandre Bayen, Peter L. Bartlett
Date: 2015-12-01 00:00:00
Proceeding: NeurIPS 2015 12

We study accelerated mirror descent dynamics in continuous and discrete time. Combining the original continuous-time motivation of mirror descent with a recent ODE interpretation of Nesterov's accelerated method, we propose a family of continuous-time descent dynamics for convex functions with Lipschitz gradients, such that the solution trajectories are guaranteed to converge to the optimum at a $O(1/t^2)$ rate. We then show that a large family of first-order accelerated methods can be obtained as a discretization of the ODE, and these methods converge at a $O(1/k^2)$ rate. This connection between accelerated mirror descent and the ODE provides an intuitive approach to the design and analysis of accelerated first-order algorithms.
Distributed Submodular Cover: Succinctly Summarizing Massive Data
Authors: Baharan Mirzasoleiman, Amin Karbasi, Ashwinkumar Badanidiyuru, Andreas Krause
Date: 2015-12-01 00:00:00
Proceeding: NeurIPS 2015 12
Tasks: Clustering, Data Summarization

How can one find a subset, ideally as small as possible, that well represents a massive dataset? I.e., its corresponding utility, measured according to a suitable utility function, should be comparable to that of the whole dataset. In this paper, we formalize this challenge as a submodular cover problem. Here, the utility is assumed to exhibit submodularity, a natural diminishing returns condition preva- lent in many data summarization applications. The classical greedy algorithm is known to provide solutions with logarithmic approximation guarantees compared to the optimum solution. However, this sequential, centralized approach is imprac- tical for truly large-scale problems. In this work, we develop the first distributed algorithm – DISCOVER – for submodular set cover that is easily implementable using MapReduce-style computations. We theoretically analyze our approach, and present approximation guarantees for the solutions returned by DISCOVER. We also study a natural trade-off between the communication cost and the num- ber of rounds required to obtain such a solution. In our extensive experiments, we demonstrate the effectiveness of our approach on several applications, includ- ing active set selection, exemplar based clustering, and vertex cover on tens of millions of data points using Spark.