mtybilly/Instruct2DS huggingface dataset:
Non-convex Statistical Optimization for Sparse Tensor Graphical Model
Authors: Zhaoran Wang, Han Liu, Guang Cheng Wei Sun
Published in: Advances in Neural Information Processing Systems 28  (NIPS 2015) (Main Conference Track), 2015

Abstract: We consider the estimation of sparse graphical models that characterize the dependency structure of high-dimensional tensor-valued data. To facilitate the estimation of the precision matrix corresponding to each way of the tensor, we assume the data follow a tensor normal distribution whose covariance has a Kronecker product structure. The penalized maximum likelihood estimation of this model involves minimizing a non-convex objective function. In spite of the non-convexity of this estimation problem, we prove that an alternating minimization algorithm, which iteratively estimates each sparse precision matrix while fixing the others, attains an estimator with the optimal statistical rate of convergence as well as consistent graph recovery. Notably, such an estimator achieves estimation consistency with only one tensor sample, which is unobserved in previous work. Our theoretical results are backed by thorough numerical studies.
Lifted Symmetry Detection and Breaking for MAP Inference
Authors: Parag Singla, Henry Kautz Timothy Kopp
Published in: Advances in Neural Information Processing Systems 28  (NIPS 2015) (Main Conference Track), 2015

Abstract: Symmetry breaking is a technique for speeding up propositional satisfiability testing by adding constraints to the theory that restrict the search space while preserving satisfiability. In this work, we extend symmetry breaking to the problem of model finding in weighted and unweighted relational theories, a class of problems that includes MAP inference in Markov Logic and similar statistical-relational languages. We introduce term symmetries, which are induced by an evidence set and extend to symmetries over a relational theory. We provide the important special case of term equivalent symmetries, showing that such symmetries can be found in low-degree polynomial time. We show how to break an exponential number of these symmetries with added constraints whose number is linear in the size of the domain. We demonstrate the effectiveness of these techniques through experiments in two relational domains. We also discuss the connections between relational symmetry breaking and work on lifted inference in statistical-relational reasoning.
Private Graphon Estimation for Sparse Graphs
Authors: Jennifer Chayes, Adam Smith Christian Borgs
Published in: Advances in Neural Information Processing Systems 28  (NIPS 2015) (Main Conference Track), 2015

Abstract: We design algorithms for fitting a high-dimensional statistical model to a large, sparse network without revealing sensitive information of individual members.  Given a sparse input graph $G$, our algorithms output a node-differentially private nonparametric block model approximation.  By node-differentially private, we mean that our output hides the insertion or removal of a vertex and all its adjacent edges.  If $G$ is an instance of the network obtained from a generative nonparametric model defined in terms of a graphon $W$, our model guarantees consistency: as the number of vertices tends to infinity, the output of our algorithm converges to $W$ in an appropriate version of the $L_2$ norm. In particular, this means we can estimate the sizes of all multi-way cuts in $G$.  Our results hold as long as $W$ is bounded, the average degree of $G$ grows at least like the log of the number of vertices, and the number of blocks goes to infinity at an appropriate rate.  We give explicit error bounds in terms of the parameters of the model; in several settings, our bounds improve on or match known nonprivate results.
Online Learning with Adversarial Delays
Authors: Daniel Khashabi Kent Quanrud
Published in: Advances in Neural Information Processing Systems 28  (NIPS 2015) (Main Conference Track), 2015

Abstract: We study the performance of standard online learning algorithms when the feedback is delayed by an adversary. We show that \texttt{online-gradient-descent} and \texttt{follow-the-perturbed-leader} achieve regret $O(\sqrt{D})$ in the delayed setting, where $D$ is the sum of delays of each round's feedback. This bound collapses to an optimal $O(\sqrt{T})$ bound in the usual setting of no delays (where $D = T$).  Our main contribution is to show that standard algorithms for online learning already have simple regret bounds in the most general setting of delayed feedback, making adjustments to the analysis and not to the algorithms themselves.  Our results help affirm and clarify the success of recent algorithms in optimization and machine learning that operate in a delayed feedback model.
Solving Random Quadratic Systems of Equations Is Nearly as Easy as Solving Linear Systems
Authors: Emmanuel Candes Yuxin Chen
Published in: Advances in Neural Information Processing Systems 28  (NIPS 2015) (Main Conference Track), 2015

Abstract: This paper is concerned with finding a solution x to a quadratic system of equations yi = |< ai, x >|^2,  i = 1, 2, ..., m. We prove that it is possible to solve unstructured quadratic systems in n variables exactly from O(n) equations in linear time, that is, in time proportional to reading and evaluating the data. This is accomplished by a novel procedure, which starting from an initial guess given by a spectral initialization procedure, attempts to minimize a non-convex objective. The proposed algorithm distinguishes from prior approaches by regularizing the initialization and descent procedures in an adaptive fashion, which discard terms bearing too much influence on the initial estimate or search directions. These careful selection rules---which effectively serve as a variance reduction scheme---provide a tighter initial guess, more robust descent directions, and thus enhanced practical performance. Further, this procedure also achieves a near-optimal statistical accuracy in the presence of noise. Finally, we demonstrate empirically that the computational cost of our algorithm is about four times that of solving a least-squares problem of the same size.
Statistical Topological Data Analysis - A Kernel Perspective
Authors: Stefan Huber, Marc Niethammer, Weili Lin, Ulrich Bauer Roland Kwitt
Published in: Advances in Neural Information Processing Systems 28  (NIPS 2015) (Main Conference Track), 2015

Abstract: We consider the problem of statistical computations with persistence diagrams, a summary representation of topological features in data. These diagrams encode persistent homology, a widely used invariant in topological data analysis. While several avenues towards a statistical treatment of the diagrams have been explored recently, we follow an alternative route that is motivated by the success of methods based on the embedding of probability measures into reproducing kernel Hilbert spaces. In fact, a positive definite kernel on persistence diagrams has recently been proposed, connecting persistent homology to popular kernel-based learning techniques such as support vector machines. However, important properties of that kernel which would enable a principled use in the context of probability measure embeddings remain to be explored. Our contribution is to close this gap by proving universality of a variant of the original kernel, and to demonstrate its effective use in two-sample hypothesis testing on synthetic as well as real-world data.
A Structural Smoothing Framework For Robust Graph Comparison
Authors: S.V.N. Vishwanathan Pinar Yanardag
Published in: Advances in Neural Information Processing Systems 28  (NIPS 2015) (Main Conference Track), 2015

Abstract: 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.
Bandits with Unobserved Confounders: A Causal Approach
Authors: Andrew Forney, Judea Pearl Elias Bareinboim
Published in: Advances in Neural Information Processing Systems 28  (NIPS 2015) (Main Conference Track), 2015

Abstract: The Multi-Armed Bandit problem constitutes an archetypal setting for sequential decision-making, permeating multiple domains including engineering, business, and medicine. One of the hallmarks of a bandit setting is the agent's capacity to explore its environment through active intervention, which contrasts with the ability to collect passive data by estimating associational relationships between actions and payouts. The existence of unobserved confounders, namely unmeasured variables affecting both the action and the outcome variables, implies that these two data-collection modes will in general not coincide. In this paper, we show that formalizing this distinction has conceptual and algorithmic implications to the bandit setting. The current generation of bandit algorithms implicitly try to maximize rewards based on estimation of the experimental distribution, which we show is not always the best strategy to pursue. Indeed, to achieve low regret in certain realistic classes of bandit problems (namely, in the face of unobserved confounders), both experimental and observational quantities are required by the rational agent. After this realization, we propose an optimization metric (employing both experimental and observational distributions) that bandit agents should pursue, and illustrate its benefits over traditional algorithms.
Scale Up Nonlinear Component Analysis with Doubly Stochastic Gradients
Authors: Yingyu Liang, Le Song Bo Xie
Published in: Advances in Neural Information Processing Systems 28  (NIPS 2015) (Main Conference Track), 2015

Abstract: Nonlinear component analysis such as kernel Principle Component Analysis (KPCA) and kernel Canonical Correlation Analysis (KCCA) are widely used in machine learning, statistics and data analysis, but they can not scale up to big datasets. Recent attempts have employed random feature approximations to convert the problem to the primal form for linear computational complexity. However, to obtain high quality solutions, the number of random features should be the same order of magnitude as the number of data points, making such approach not directly applicable to the regime with millions of data points.We propose a simple, computationally efficient, and memory friendly algorithm based on the ``doubly stochastic gradients'' to scale up a range of kernel nonlinear component analysis, such as kernel PCA, CCA and SVD. Despite the \emph{non-convex} nature of these problems, our method enjoys theoretical guarantees that it converges at the rate $\Otil(1/t)$ to the global optimum, even for the top $k$ eigen subspace. Unlike many alternatives, our algorithm does not require explicit orthogonalization, which is infeasible on big datasets. We demonstrate the effectiveness and scalability of our algorithm on large scale synthetic and real world datasets.
A Market Framework for Eliciting Private Data
Authors: Rafael Frongillo, Jacob D. Abernethy Bo Waggoner
Published in: Advances in Neural Information Processing Systems 28  (NIPS 2015) (Main Conference Track), 2015

Abstract: We propose a mechanism for purchasing information from a sequence of participants.The participants may simply hold data points they wish to sell, or may have more sophisticated information; either way, they are incentivized to participate as long as they believe their data points are representative or their information will improve the mechanism's future prediction on a test set.The mechanism, which draws on the principles of prediction markets, has a bounded budget and minimizes generalization error for Bregman divergence loss functions.We then show how to modify this mechanism to preserve the privacy of participants' information: At any given time, the current prices and predictions of the mechanism reveal almost no information about any one participant, yet in total over all participants, information is accurately aggregated.
A Generalization of Submodular Cover via the Diminishing Return Property on the Integer Lattice
Authors: Yuichi Yoshida Tasuku Soma
Published in: Advances in Neural Information Processing Systems 28  (NIPS 2015) (Main Conference Track), 2015

Abstract: We consider a generalization of the submodular cover problem based on the concept of diminishing return property on the integer lattice. We are motivated by real scenarios in machine learning that cannot be captured by (traditional) submodular set functions.  We show that the generalized submodular cover problem can be applied to various problems and devise a bicriteria approximation algorithm.  Our algorithm is guaranteed to output a log-factor approximate solution that satisfies the constraints with the desired accuracy. The running time of our algorithm is roughly $O(n\log (nr) \log{r})$, where $n$ is the size of the ground set and $r$ is the maximum value of a coordinate.  The dependency on $r$ is exponentially better than the naive reduction algorithms. Several experiments on real and artificial datasets demonstrate that the solution quality of our algorithm is comparable to naive algorithms, while the running time is several orders of magnitude faster.
Space-Time Local Embeddings
Authors: Jun Wang, Alexandros Kalousis, Stephane Marchand-Maillet Ke Sun
Published in: Advances in Neural Information Processing Systems 28  (NIPS 2015) (Main Conference Track), 2015

Abstract: Space-time is a profound concept in physics. This concept was shown to be useful for dimensionality reduction. We present basic definitions with interesting counter-intuitions. We give theoretical propositions to show that space-time is a more powerful representation than Euclidean space. We apply this concept to manifold learning for preserving local information. Empirical results on non-metric datasets show that more information can be preserved in space-time.
Mixing Time Estimation in Reversible Markov Chains from a Single Sample Path
Authors: Aryeh Kontorovich, Csaba Szepesvari Daniel J. Hsu
Published in: Advances in Neural Information Processing Systems 28  (NIPS 2015) (Main Conference Track), 2015

Abstract: This article provides the first procedure for computing a fully data-dependent interval that traps the mixing time $t_{mix}$ of a finite reversible ergodic Markov chain at a prescribed confidence level.  The interval is computed from a single finite-length sample path from the Markov chain, and does not require the knowledge of any parameters of the chain.  This stands in contrast to previous approaches, which either only provide point estimates, or require a reset mechanism, or additional prior knowledge.  The interval is constructed around the relaxation time $t_{relax}$, which is strongly related to the mixing time, and the width of the interval converges to zero roughly at a $\sqrt{n}$ rate, where $n$ is the length of the sample path.  Upper and lower bounds are given on the number of samples required to achieve constant-factor multiplicative accuracy.  The lower bounds indicate that, unless further restrictions are placed on the chain, no procedure can achieve this accuracy level before seeing each state at least $\Omega(t_{relax})$ times on the average.  Finally, future directions of research are identified.
Online Rank Elicitation for Plackett-Luce: A Dueling Bandits Approach
Authors: Róbert Busa-Fekete, Adil Paul, Eyke Hüllermeier Balázs Szörényi
Published in: Advances in Neural Information Processing Systems 28  (NIPS 2015) (Main Conference Track), 2015

Abstract: We study the problem of online rank elicitation, assuming that rankings of a set of alternatives obey the Plackett-Luce distribution. Following the setting of the dueling bandits problem, the learner is allowed to query pairwise comparisons between alternatives, i.e., to sample pairwise marginals of the distribution in an online fashion. Using this information, the learner seeks to reliably predict the most probable ranking (or top-alternative). Our approach is based on constructing a surrogate probability distribution over rankings based on a sorting procedure, for which the pairwise marginals provably coincide with the marginals of the Plackett-Luce distribution. In addition to a formal performance and complexity analysis, we present first experimental studies.
Efficient Exact Gradient Update for training Deep Networks with Very Large Sparse Targets
Authors: Alexandre de Brébisson, Xavier Bouthillier Pascal Vincent
Published in: Advances in Neural Information Processing Systems 28  (NIPS 2015) (Main Conference Track), 2015

Abstract: An important class of problems involves training deep neural networks with sparse prediction targets of very high dimension D. These occur naturally in e.g. neural language models or the learning of word-embeddings, often posed as predicting the probability of next words among a vocabulary of size D (e.g. 200,000). Computing the equally large, but typically non-sparse D-dimensional output vector from a last hidden layer of reasonable dimension d (e.g. 500) incurs a prohibitive $O(Dd)$ computational cost for each example, as does updating the $D \times d$ output weight matrix and computing the gradient needed for backpropagation to previous layers. While efficient handling of large sparse network inputs is trivial, this case of large sparse targets is not, and has thus so far been sidestepped with approximate alternatives such as hierarchical softmax or sampling-based approximations during training. In this work we develop an original algorithmic approach that, for a family of loss functions that includes squared error and spherical softmax, can compute the exact loss, gradient update for the output weights, and gradient for backpropagation, all in $O(d^2)$  per example instead of $O(Dd)$, remarkably without ever computing the D-dimensional output. The proposed algorithm yields a speedup of $\frac{D}{4d}$, i.e. two orders of magnitude for typical sizes, for that critical part of the computations that often dominates the training time in this kind of network architecture.
A Gaussian Process Model of Quasar Spectral Energy Distributions
Authors: Albert Wu, Jeff Regier, Jon McAuliffe, Dustin Lang, Mr. Prabhat, David Schlegel, Ryan P. Adams Andrew Miller
Published in: Advances in Neural Information Processing Systems 28  (NIPS 2015) (Main Conference Track), 2015

Abstract: 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.
Fast Convergence of Regularized Learning in Games
Authors: Alekh Agarwal, Haipeng Luo, Robert E. Schapire Vasilis Syrgkanis
Published in: Advances in Neural Information Processing Systems 28  (NIPS 2015) (Main Conference Track), 2015

Abstract: We show that natural classes of regularized learning algorithms with a form of recency bias achieve faster convergence rates to approximate efficiency and to coarse correlated equilibria in multiplayer normal form games. When each player in a game uses an algorithm from our class, their individual regret decays at $O(T^{-3/4})$, while the sum of utilities converges to an approximate optimum at $O(T^{-1})$--an improvement upon the worst case $O(T^{-1/2})$ rates. We show a black-box reduction for any algorithm in the class to achieve $\tilde{O}(T^{-1/2})$ rates against an adversary, while maintaining the faster rates against algorithms in the class. Our results extend those of Rakhlin and Shridharan~\cite{Rakhlin2013} and Daskalakis et al.~\cite{Daskalakis2014}, who only analyzed two-player zero-sum games for specific algorithms.
Communication Complexity of Distributed Convex Learning and Optimization
Authors: Ohad Shamir Yossi Arjevani
Published in: Advances in Neural Information Processing Systems 28  (NIPS 2015) (Main Conference Track), 2015

Abstract: We study the fundamental limits to communication-efficient distributed methods for convex learning and optimization, under different assumptions on the information available to individual machines, and the types of functions considered. We identify cases where existing algorithms are already worst-case optimal, as well as cases where room for further improvement is still possible. Among other things, our results indicate that without similarity between the local objective functions (due to statistical data similarity or otherwise) many communication rounds may be required, even if the machines have unbounded computational power.
Large-Scale Bayesian Multi-Label Learning via Topic-Based Label Embeddings
Authors: Changwei Hu, Ricardo Henao, Lawrence Carin Piyush Rai
Published in: Advances in Neural Information Processing Systems 28  (NIPS 2015) (Main Conference Track), 2015

Abstract: We present a scalable Bayesian multi-label learning model based on learning low-dimensional label embeddings. Our model assumes that each label vector is generated as a weighted combination of a set of topics (each topic being a distribution over labels), where the combination weights (i.e., the embeddings) for each label vector are conditioned on the observed feature vector. This construction, coupled with a Bernoulli-Poisson link function for each label of the binary label vector, leads to a model with a computational cost that scales in the number of positive labels in the label matrix. This makes the model particularly appealing for real-world multi-label learning problems where the label matrix is usually very massive but highly sparse. Using a data-augmentation strategy leads to full local conjugacy in our model, facilitating simple and very efficient Gibbs sampling, as well as an Expectation Maximization algorithm for inference. Also, predicting the label vector at test time does not require doing an inference for the label embeddings and can be done in closed form. We report results on several benchmark data sets, comparing our model with various state-of-the art methods.
Probabilistic Line Searches for Stochastic Optimization
Authors: Philipp Hennig Maren Mahsereci
Published in: Advances in Neural Information Processing Systems 28  (NIPS 2015) (Main Conference Track), 2015

Abstract: In deterministic optimization, line searches are a standard tool ensuring stability and efficiency. Where only stochastic gradients are available, no direct equivalent has so far been formulated, because uncertain gradients do not allow for a strict sequence of decisions collapsing the search space. We construct a probabilistic line search by combining the structure of existing deterministic methods with notions from Bayesian optimization. Our method retains a Gaussian process surrogate of the univariate optimization objective, and uses a probabilistic belief over the Wolfe conditions to monitor the descent. The algorithm has very low computational cost, and no user-controlled parameters. Experiments show that it effectively removes the need to define a learning rate for stochastic gradient descent.
Sample Complexity of Learning Mahalanobis Distance Metrics
Authors: Kristin Branson Nakul Verma
Published in: Advances in Neural Information Processing Systems 28  (NIPS 2015) (Main Conference Track), 2015

Abstract: Metric learning seeks a transformation of the feature space that enhances prediction quality for a given task. In this work we provide PAC-style sample complexity rates for supervised metric learning. We give matching lower- and upper-bounds showing that sample complexity scales with the representation dimension when no assumptions are made about the underlying data distribution. In addition, by leveraging the structure of the data distribution, we provide rates fine-tuned to a specific notion of the intrinsic complexity of a given dataset, allowing us to relax the dependence on representation dimension. We show both theoretically and empirically that augmenting the metric learning optimization criterion with a simple norm-based regularization is important and can help adapt to a dataset’s intrinsic complexity yielding better generalization, thus partly explaining the empirical success of similar regularizations reported in previous works.
Sample Efficient Path Integral Control under Uncertainty
Authors: Evangelos Theodorou, Michail Kontitsis Yunpeng Pan
Published in: Advances in Neural Information Processing Systems 28  (NIPS 2015) (Main Conference Track), 2015

Abstract: We present a data-driven stochastic optimal control framework that is derived using the path integral (PI) control approach. We find iterative control laws analytically without a priori policy parameterization based on probabilistic representation of the learned dynamics model. The proposed algorithm operates in a forward-backward sweep manner which differentiate it from other PI-related methods that perform forward sampling to find open-loop optimal controls.    Our method uses significantly less sampled data to find analytic control laws compared to other approaches within the PI control family that rely on extensive sampling from given dynamics models or trials on physical systems in a model-free fashion. In addition, the learned controllers can be generalized to new tasks without re-sampling based on the compositionality theory for the linearly-solvable optimal control framework.We provide experimental results on three different systems and comparisons with state-of-the-art model-based methods to demonstrate the efficiency and generalizability of the proposed framework.
Mind the Gap: A Generative Approach to Interpretable Feature Selection and Extraction
Authors: Julie A Shah, Finale Doshi-Velez Been Kim
Published in: Advances in Neural Information Processing Systems 28  (NIPS 2015) (Main Conference Track), 2015

Abstract: We present the Mind the Gap Model (MGM), an approach for interpretable feature extraction and selection.  By placing interpretability criteria directly into the model, we allow for the model to both optimize parameters related to interpretability and to directly report a global set of distinguishable dimensions to assist with further data exploration and hypothesis generation. MGM extracts distinguishing features on real-world datasets of animal features, recipes ingredients, and disease co-occurrence.  It also maintains or improves performance when compared to related approaches.  We perform a user study with domain experts to show the MGM's ability to help with dataset exploration.
Regularization Path of Cross-Validation Error Lower Bounds
Authors: Yoshiki Suzuki, Masayuki Karasuyama, Ichiro Takeuchi Atsushi Shibagaki
Published in: Advances in Neural Information Processing Systems 28  (NIPS 2015) (Main Conference Track), 2015

Abstract: Careful tuning of a regularization parameter is indispensable in many machine learning tasks because it has a significant impact on generalization performances.Nevertheless, current practice of regularization parameter tuning is more of an art than a science, e.g., it is hard to tell how many grid-points would be needed in cross-validation (CV) for obtaining a solution with sufficiently small CV error.In this paper we propose a novel framework for computing a lower bound of the CV errors as a function of the regularization parameter, which we call regularization path of CV error lower bounds.The proposed framework can be used for providing a theoretical approximation guarantee on a set of solutions in the sense that how far the CV error of the current best solution could be away from best possible CV error in the entire range of the regularization parameters.We demonstrate through numerical experiments that a theoretically guaranteed a choice of regularization parameter in the above sense is possible with reasonable computational costs.
Reflection, Refraction, and Hamiltonian Monte Carlo
Authors: Justin Domke Hadi Mohasel Afshar
Published in: Advances in Neural Information Processing Systems 28  (NIPS 2015) (Main Conference Track), 2015

Abstract: Hamiltonian Monte Carlo (HMC) is a successful approach for sampling from continuous densities. However, it has difficulty simulating Hamiltonian dynamics with non-smooth functions, leading to poor performance. This paper is motivated by the behavior of Hamiltonian dynamics in physical systems like optics. We introduce a modification of the Leapfrog discretization of Hamiltonian dynamics on piecewise continuous energies, where intersections of the trajectory with discontinuities are detected, and the momentum is reflected or refracted to compensate for the change in energy. We prove that this method preserves the correct stationary distribution when boundaries are affine. Experiments show that by reducing the number of rejected samples, this method improves on traditional HMC.
Exploring Models and Data for Image Question Answering
Authors: Ryan Kiros, Richard Zemel Mengye Ren
Published in: Advances in Neural Information Processing Systems 28  (NIPS 2015) (Main Conference Track), 2015

Abstract: This work aims to address the problem of image-based question-answering (QA) with new models and datasets. In our work, we propose to use neural networks and visual semantic embeddings, without intermediate stages such as object detection and image segmentation, to predict answers to simple questions about images. Our model performs 1.8 times better than the only published results on an existing image QA dataset. We also present a question generation algorithm that converts image descriptions, which are widely available, into QA form. We used this algorithm to produce an order-of-magnitude larger dataset, with more evenly distributed answers. A suite of baseline results on this new dataset are also presented.
Learning structured densities via infinite dimensional exponential families
Authors: Mladen Kolar, Jinbo Xu Siqi Sun
Published in: Advances in Neural Information Processing Systems 28  (NIPS 2015) (Main Conference Track), 2015

Abstract: Learning the structure of a probabilistic graphical models is a well studied problem in the machine learning community due to its importance in many applications. Current approaches are mainly focused on learning the structure under restrictive parametric assumptions, which limits the applicability of these methods. In this paper, we study the problem of estimating the structure of a probabilistic graphical model without assuming a particular parametric model. We consider probabilities that are members of an infinite dimensional exponential family, which is parametrized by a reproducing kernel Hilbert space (RKHS) H and its kernel $k$. One difficulty in learning nonparametric densities is evaluation of the normalizing constant. In order to avoid this issue, our procedure minimizes the penalized score matching objective. We show how to efficiently minimize the proposed objective using existing group lasso solvers. Furthermore, we prove that our procedure recovers the graph structure with high-probability under mild conditions. Simulation studies illustrate ability of our procedure to recover the true graph structure without the knowledge of the data generating process.
Streaming Min-max Hypergraph Partitioning
Authors: Jennifer Iglesias, Milan Vojnovic Dan Alistarh
Published in: Advances in Neural Information Processing Systems 28  (NIPS 2015) (Main Conference Track), 2015

Abstract: 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.
Principal Differences Analysis: Interpretable Characterization of Differences between Distributions
Authors: Tommi Jaakkola Jonas W Mueller
Published in: Advances in Neural Information Processing Systems 28  (NIPS 2015) (Main Conference Track), 2015

Abstract: We introduce principal differences analysis for analyzing differences between high-dimensional distributions. The method operates by finding the projection that maximizes the Wasserstein divergence between the resulting univariate populations. Relying on the Cramer-Wold device, it requires no assumptions about the form of the underlying distributions, nor the nature of their inter-class differences. A sparse variant of the method is introduced to identify features responsible for the differences. We provide algorithms for both the original minimax formulation as well as its semidefinite relaxation.  In addition to deriving some convergence results, we illustrate how the approach may be applied to identify differences between cell populations in the somatosensory cortex and hippocampus as manifested by single cell RNA-seq. Our broader framework extends beyond the specific choice of Wasserstein divergence.
An Active Learning Framework using Sparse-Graph Codes for Sparse Polynomials and Graph Sketching
Authors: Kannan Ramchandran Xiao Li
Published in: Advances in Neural Information Processing Systems 28  (NIPS 2015) (Main Conference Track), 2015

Abstract: 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.
Efficient Thompson Sampling for Online ￼Matrix-Factorization Recommendation
Authors: Hung H Bui, Branislav Kveton, Long Tran-Thanh, Sanjay Chawla Jaya Kawale
Published in: Advances in Neural Information Processing Systems 28  (NIPS 2015) (Main Conference Track), 2015

Abstract: Matrix factorization (MF) collaborative filtering is an effective and widely used method in recommendation systems. However, the problem of finding an optimal trade-off between exploration and exploitation (otherwise known as the bandit problem), a crucial problem in collaborative filtering from cold-start, has not been previously addressed.In this paper, we present a novel algorithm for online MF recommendation that automatically combines finding the most relevantitems with exploring new or less-recommended items.Our approach, called Particle Thompson Sampling for Matrix-Factorization, is based on the general Thompson sampling framework, but augmented with a novel efficient online Bayesian probabilistic matrix factorization method based on the Rao-Blackwellized particle filter.Extensive experiments in collaborative filtering using several real-world datasets demonstrate that our proposed algorithm significantly outperforms the current state-of-the-arts.
Structured Transforms for Small-Footprint Deep Learning
Authors: Tara Sainath, Sanjiv Kumar Vikas Sindhwani
Published in: Advances in Neural Information Processing Systems 28  (NIPS 2015) (Main Conference Track), 2015

Abstract: We consider the task of building compact deep learning pipelines suitable for deploymenton storage and power constrained mobile devices. We propose a uni-fied framework to learn a broad family of structured parameter matrices that arecharacterized by the notion of low displacement rank. Our structured transformsadmit fast function and gradient evaluation, and span a rich range of parametersharing configurations whose statistical modeling capacity can be explicitly tunedalong a continuum from structured to unstructured. Experimental results showthat these transforms can significantly accelerate inference and forward/backwardpasses during training, and offer superior accuracy-compactness-speed tradeoffsin comparison to a number of existing techniques. In keyword spotting applicationsin mobile speech recognition, our methods are much more effective thanstandard linear low-rank bottleneck layers and nearly retain the performance ofstate of the art models, while providing more than 3.5-fold compression.
Linear Multi-Resource Allocation with Semi-Bandit Feedback
Authors: Koby Crammer, Csaba Szepesvari Tor Lattimore
Published in: Advances in Neural Information Processing Systems 28  (NIPS 2015) (Main Conference Track), 2015

Abstract: We study an idealised sequential resource allocation problem. In each time step the learner chooses an allocation of several resource types between a number of tasks. Assigning more resources to a task increases the probability that it is completed. The problem is challenging because the alignment of the tasks to the resource types is unknown and the feedback is noisy. Our main contribution is the new setting and an algorithm with nearly-optimal regret analysis. Along the way we draw connections to the problem of minimising regret for stochastic linear bandits with heteroscedastic noise. We also present some new results for stochastic linear bandits on the hypercube that significantly out-performs existing work, especially in the sparse case.
On the Optimality of Classifier Chain for Multi-label Classification
Authors: Ivor Tsang Weiwei Liu
Published in: Advances in Neural Information Processing Systems 28  (NIPS 2015) (Main Conference Track), 2015

Abstract: To capture the interdependencies between labels in multi-label classification problems, classifier chain (CC)  tries to take the multiple labels of each instance into account under a deterministic high-order Markov Chain model. Since its  performance is sensitive to the choice of label order, the key issue is how to determine the optimal label order for CC. In this work, we first generalize the CC model over a random label order. Then, we present a theoretical analysis of the generalization error for the proposed generalized model. Based on our results, we propose a dynamic programming based classifier chain (CC-DP) algorithm to search the globally optimal label order for CC and a greedy classifier chain (CC-Greedy) algorithm to find a locally optimal CC. Comprehensive experiments on a number of real-world multi-label data sets from various domains demonstrate that our proposed CC-DP algorithm outperforms state-of-the-art approaches and the CC-Greedy algorithm achieves comparable prediction performance with CC-DP.
Consistent Multilabel Classification
Authors: Nagarajan Natarajan, Pradeep K Ravikumar, Inderjit S Dhillon Oluwasanmi O Koyejo
Published in: Advances in Neural Information Processing Systems 28  (NIPS 2015) (Main Conference Track), 2015

Abstract: Multilabel classification is rapidly developing as an important aspect of modern predictive modeling, motivating study of its theoretical aspects. To this end, we propose a framework for constructing and analyzing multilabel classification metrics which reveals novel results on a parametric form for population optimal classifiers, and additional insight into the role of label correlations. In particular, we show that for multilabel metrics constructed as instance-, micro- and macro-averages, the population optimal classifier can be decomposed into binary classifiers based on the marginal instance-conditional distribution of each label, with a weak association between labels via the threshold. Thus, our analysis extends the state of the art from a few known multilabel classification metrics such as Hamming loss, to a general framework applicable to many of the classification metrics in common use. Based on the population-optimal classifier, we propose a computationally efficient and general-purpose plug-in classification algorithm, and prove its consistency with respect to the metric of interest. Empirical results on synthetic and benchmark datasets are supportive of our theoretical findings.
A Normative Theory of Adaptive Dimensionality Reduction in Neural Networks
Authors: Dmitri Chklovskii Cengiz Pehlevan
Published in: Advances in Neural Information Processing Systems 28  (NIPS 2015) (Main Conference Track), 2015

Abstract: To make sense of the world our brains must analyze high-dimensional datasets streamed by our sensory organs. Because such analysis begins with dimensionality reduction, modelling early sensory processing requires biologically plausible online dimensionality reduction algorithms. Recently, we derived such an algorithm, termed similarity matching, from a Multidimensional Scaling (MDS) objective function. However, in the existing algorithm, the number of output dimensions is set a priori by the number of output neurons and cannot be changed. Because the number of informative dimensions in sensory inputs is variable there is a need for adaptive dimensionality reduction. Here, we derive biologically plausible dimensionality reduction algorithms which adapt the number of output dimensions to the eigenspectrum of the input covariance matrix. We formulate three objective functions which, in the offline setting, are optimized by the projections of the input dataset onto its principal subspace scaled by the eigenvalues of the output covariance matrix. In turn, the output eigenvalues are computed as i) soft-thresholded, ii) hard-thresholded, iii) equalized thresholded eigenvalues of the input covariance matrix. In the online setting, we derive the three corresponding adaptive algorithms and map them onto the dynamics of neuronal activity in networks with biologically plausible local learning rules. Remarkably, in the last two networks, neurons are divided into two classes which we identify with principal neurons and interneurons in biological circuits.
Hidden Technical Debt in Machine Learning Systems
Authors: Gary Holt, Daniel Golovin, Eugene Davydov, Todd Phillips, Dietmar Ebner, Vinay Chaudhary, Michael Young, Jean-François Crespo, Dan Dennison D. Sculley
Published in: Advances in Neural Information Processing Systems 28  (NIPS 2015) (Main Conference Track), 2015

Abstract: 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.
NEXT: A System for Real-World Development, Evaluation, and Application of Active Learning
Authors: Lalit Jain, Chris Fernandez, Nicholas J. Glattard, Rob Nowak Kevin G. Jamieson
Published in: Advances in Neural Information Processing Systems 28  (NIPS 2015) (Main Conference Track), 2015

Abstract: 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.