mtybilly/Instruct2DS huggingface dataset:
Scalable Inference for Logistic-Normal Topic Models
Authors: Jianfei Chen, Jun Zhu, Zi Wang, Xun Zheng, Bo Zhang
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: Logistic-normal topic models can effectively discover correlation structures among latent topics. However, their inference remains a challenge because of the non-conjugacy between the logistic-normal prior and multinomial topic mixing proportions. Existing algorithms either make restricting mean-field assumptions or are not scalable to large-scale applications. This paper presents a partially collapsed Gibbs sampling algorithm that approaches the provably correct distribution by exploring the ideas of data augmentation. To improve time efficiency, we further present a parallel implementation that can deal with large-scale applications and learn the correlation structures of thousands of topics from millions of documents. Extensive empirical results demonstrate the promise.
A multi-agent control framework for co-adaptation in brain-computer interfaces
Authors: Josh S Merel, Roy Fox, Tony Jebara, Liam Paninski
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: In a closed-loop brain-computer interface (BCI), adaptive decoders are used to learn parameters suited to decoding the user's neural response. Feedback to the user provides information which permits the neural tuning to also adapt. We present an approach to model this process of co-adaptation between the encoding model of the neural signal and the decoding algorithm as a multi-agent formulation of the linear quadratic Gaussian (LQG) control problem. In simulation we characterize how decoding performance improves as the neural encoding and adaptive decoder optimize, qualitatively resembling experimentally demonstrated closed-loop improvement. We then propose a novel, modified decoder update rule which is aware of the fact that the encoder is also changing and show it can improve simulated co-adaptation dynamics. Our modeling approach offers promise for gaining insights into co-adaptation as well as improving user learning of BCI control in practical settings.
Conditional Random Fields via Univariate Exponential Families
Authors: Eunho Yang, Pradeep K Ravikumar, Genevera I Allen, Zhandong Liu
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: Conditional random fields, which model the distribution of a multivariate response conditioned on a set of covariates using undirected graphs, are widely used in a variety of multivariate prediction applications. Popular instances of this class of models such as categorical-discrete CRFs, Ising CRFs, and conditional Gaussian based CRFs, are not however best suited to the varied types of response variables in many applications, including count-valued responses. We thus introduce a “novel subclass of CRFs”, derived by imposing node-wise conditional distributions of response variables conditioned on the rest of the responses and the covariates as arising from univariate exponential families.  This allows us to derive novel multivariate CRFs given any univariate exponential distribution, including the Poisson, negative binomial, and exponential distributions. Also in particular, it addresses the common CRF problem of specifying feature'' functions determining the interactions between response variables and covariates. We develop a class of tractable penalized $M$-estimators to learn these CRF distributions from data, as well as a unified sparsistency analysis for this general class of CRFs showing exact structure recovery can be achieved with high probability."
Adaptivity to Local Smoothness and Dimension in Kernel Regression
Authors: Samory Kpotufe, Vikas Garg
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: We present the first result for kernel regression where the procedure adapts locally at a point $x$ to both the unknown local dimension of the metric and the unknown H\{o}lder-continuity of the regression function at $x$. The result holds with high probability simultaneously at all points $x$ in a metric space of unknown structure."
Online Learning with Costly Features and Labels
Authors: Navid Zolghadr, Gabor Bartok, Russell Greiner, András György, Csaba Szepesvari
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: This paper introduces the online probing" problem: In each round, the learner is able to purchase the values of a subset of feature values. After the learner uses this information to come up with a prediction for the given round, he then has the option of paying for seeing the loss that he is evaluated against. Either way, the learner pays for the imperfections of his predictions and whatever he chooses to observe, including the cost of observing the loss function for the given round and the cost of the observed features. We consider two variations of this problem, depending on whether the learner can observe the label for free or not. We provide algorithms and upper and lower bounds on the regret for both variants. We show that a positive cost for observing the label significantly increases the regret of the problem."
An Approximate, Efficient LP Solver for LP Rounding
Authors: Srikrishna Sridhar, Stephen Wright, Christopher Re, Ji Liu, Victor Bittorf, Ce Zhang
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: Many problems in machine learning can be solved by rounding the solution of an appropriate linear program. We propose a scheme that is based on a quadratic program relaxation which allows us to use parallel stochastic-coordinate-descent to approximately solve large linear programs efficiently. Our software is an order of magnitude faster than Cplex (a commercial linear programming solver) and yields similar solution quality. Our results include a novel perturbation analysis of a quadratic-penalty formulation of linear programming and a convergence result, which we use to derive running time and quality guarantees.
Regression-tree Tuning in a Streaming Setting
Authors: Samory Kpotufe, Francesco Orabona
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: We consider the problem of maintaining the data-structures of a partition-based regression procedure in a setting where the training data arrives sequentially over time. We prove that it is possible to maintain such a structure in time $O(\log n)$ at any time step $n$ while achieving a nearly-optimal regression rate of $\tilde{O}(n^{-2/(2+d)})$ in terms of the unknown metric dimension $d$. Finally we prove a new regression lower-bound which is independent of a given data size, and hence is more appropriate for the streaming setting.
Estimating LASSO Risk and Noise Level
Authors: Mohsen Bayati, Murat A Erdogdu, Andrea Montanari
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: We study the fundamental problems of variance and risk estimation in high dimensional statistical modeling. In particular, we consider the problem of learning a coefficient vector $\theta_0\in R^p$ from noisy linear observation $y=X\theta_0+w\in R^n$ and the popular estimation procedure of solving an $\ell_1$-penalized least squares objective known as the LASSO or Basis Pursuit DeNoising (BPDN). In this context, we develop new estimators for the $\ell_2$ estimation risk $\|\hat{\theta}-\theta_0\|_2$ and the variance of the noise. These can be used to select the regularization parameter optimally. Our approach combines Stein unbiased risk estimate (Stein'81) and recent results of (Bayati and Montanari'11-12) on the analysis of approximate message passing and risk of LASSO.  We establish high-dimensional consistency of our estimators for sequences of matrices $X$ of increasing dimensions, with independent Gaussian entries. We establish validity for a broader class of Gaussian designs, conditional on the validity of a certain conjecture from statistical physics.  Our approach is the first that provides an asymptotically consistent risk estimator. In addition, we demonstrate through simulation that our variance estimation outperforms several existing methods in the literature.
Demixing odors - fast inference in olfaction
Authors: Agnieszka Grabska-Barwinska, Jeff Beck, Alexandre Pouget, Peter Latham
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: The olfactory system faces a difficult inference problem: it has to determine what odors are present based on the distributed activation of its receptor neurons. Here we derive neural implementations of two approximate inference algorithms that could be used by the brain. One is a variational algorithm (which builds on the work of Beck. et al., 2012), the other is based on sampling. Importantly, we use a more realistic prior distribution over odors than has been used in the past: we use a spike and slab'' prior, for which most odors have zero concentration. After mapping the two algorithms onto neural dynamics, we find that both can infer correct odors in less than 100 ms, although it takes ~500 ms to eliminate false positives. Thus, at the behavioral level, the two algorithms make very similar predictions. However, they make different assumptions about connectivity and neural computations, and make different predictions about neural activity. Thus, they should be distinguishable experimentally.  If so, that would provide insight into the mechanisms employed by the olfactory system, and, because the two algorithms use very different coding strategies, that would also provide insight into how networks represent probabilities."
Zero-Shot Learning Through Cross-Modal Transfer
Authors: Richard Socher, Milind Ganjoo, Christopher D. Manning, Andrew Ng
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: This work introduces a model that can recognize objects in images even if no training data is available for the object class. The only necessary knowledge about unseen categories comes from unsupervised text corpora.  Unlike previous zero-shot learning models, which can only differentiate between unseen classes, our model can operate on a mixture of objects, simultaneously obtaining state of the art performance on classes with thousands of training images and reasonable performance on unseen classes.  This is achieved by seeing the distributions of words in texts as a semantic space for understanding what objects look like. Our deep learning model does not require any manually defined semantic or visual features for either words or images.  Images are mapped to be close to semantic word vectors corresponding to their classes, and the resulting image embeddings can be used to distinguish whether an image is of a seen or unseen class. Then, a separate recognition model can be employed for each type. We demonstrate two strategies, the first gives high accuracy on unseen classes, while the second is conservative in its prediction of novelty and keeps the seen classes' accuracy high.
Bayesian Inference and Learning in Gaussian Process State-Space Models with Particle MCMC
Authors: Roger Frigola, Fredrik Lindsten, Thomas B Schön, Carl Edward Rasmussen
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: State-space models are successfully used in many areas of science, engineering and economics to model time series and dynamical systems. We present a fully Bayesian approach to inference and learning in nonlinear nonparametric state-space models. We place a Gaussian process prior over the transition dynamics, resulting in a flexible model able to capture complex dynamical phenomena. However, to enable efficient inference, we marginalize over the dynamics of the model and instead infer directly the joint smoothing distribution through the use of specially tailored Particle Markov Chain Monte Carlo samplers. Once an approximation of the smoothing distribution is computed, the state transition predictive distribution can be formulated analytically. We make use of sparse Gaussian process models to greatly reduce the computational complexity of the approach.
Stochastic Gradient Riemannian Langevin Dynamics on the Probability Simplex
Authors: Sam Patterson, Yee Whye Teh
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: In this paper we investigate the use of Langevin Monte Carlo methods on the probability simplex and propose a new method, Stochastic gradient Riemannian Langevin dynamics, which is simple to implement and can be applied online. We apply this method to latent Dirichlet allocation in an online setting, and demonstrate that it achieves substantial performance improvements to the state of the art online variational Bayesian methods.
When are Overcomplete Topic Models Identifiable? Uniqueness of Tensor Tucker Decompositions with Structured Sparsity
Authors: Anima Anandkumar, Daniel J. Hsu, Majid Janzamin, Sham M. Kakade
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: Overcomplete latent representations have been very popular for unsupervised feature learning in recent years. In this paper, we specify which overcomplete models can be identified given observable moments of a certain order. We consider   probabilistic admixture or topic models  in the overcomplete regime, where the number of latent topics can greatly exceed the size of the observed word vocabulary. While   general  overcomplete topic models are not   identifiable, we establish {\em generic} identifiability under  a  constraint, referred to as  {\em topic persistence}. Our sufficient conditions for identifiability involve a novel set of higher order'' expansion conditions on   the {\em topic-word matrix} or the {\em population structure}   of the   model. This set of higher-order expansion conditions allow for overcomplete models, and require  the existence of a perfect  matching from latent topics to higher order observed words. We establish that random structured topic models are identifiable w.h.p. in the overcomplete regime. Our identifiability results allow for   general (non-degenerate) distributions for modeling the topic proportions, and thus, we can handle arbitrarily correlated topics in our framework.  Our identifiability results imply uniqueness of a class of tensor decompositions with structured sparsity which is contained in the class of {\em Tucker} decompositions, but is more general than the {\em Candecomp/Parafac} (CP)   decomposition."
Sign Cauchy Projections and Chi-Square Kernel
Authors: Ping Li, Gennady Samorodnitsk, John Hopcroft
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: The method of Cauchy random projections is popular  for computing the $l_1$ distance in high dimension. In this paper, we propose to use only the signs of the projected data and show that the  probability of collision (i.e., when the two signs differ) can be accurately approximated as a function of the chi-square ($\chi^2$) similarity, which is a popular  measure for nonnegative data (e.g., when features are generated from histograms as common in text and vision applications). Our experiments   confirm that this method of sign Cauchy random projections is promising for large-scale  learning applications. Furthermore, we extend the idea to sign $\alpha$-stable random projections and derive a bound of the collision probability.
Transfer Learning in a Transductive Setting
Authors: Marcus Rohrbach, Sandra Ebert, Bernt Schiele
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: Category models for objects or activities typically rely on supervised learning requiring sufficiently large training sets. Transferring knowledge from known categories to novel classes with no or only a few labels however is far less researched even though it is a common scenario. In this work, we extend transfer learning with semi-supervised learning to exploit unlabeled instances of (novel) categories with no or only a few labeled instances. Our proposed approach Propagated Semantic Transfer combines three main ingredients. First, we transfer information from known to novel categories by incorporating external knowledge, such as linguistic or expert-specified information, e.g., by a mid-level layer of semantic attributes. Second, we exploit the manifold structure of novel classes. More specifically we adapt a graph-based learning algorithm - so far only used for semi-supervised learning - to zero-shot and few-shot learning. Third, we improve the local neighborhood in such graph structures by replacing the raw feature-based representation with a mid-level object- or attribute-based representation. We evaluate our approach on three challenging datasets in two different applications, namely on Animals with Attributes and ImageNet for image classification and on MPII Composites for activity recognition. Our approach consistently outperforms state-of-the-art transfer and semi-supervised approaches on all datasets.
Solving inverse problem of Markov chain with partial observations
Authors: Tetsuro Morimura, Takayuki Osogami, Tsuyoshi Ide
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: The Markov chain is a convenient tool to represent the dynamics of complex systems such as traffic and social systems, where probabilistic transition takes place between internal states. A Markov chain is characterized by initial-state probabilities and a state-transition probability matrix. In the traditional setting, a major goal is to figure out properties of a Markov chain when those probabilities are known. This paper tackles an inverse version of the problem: we find those probabilities from partial observations at a limited number of states. The observations include the frequency of visiting a state and the rate of reaching a state from another. Practical examples of this task include traffic monitoring systems in cities, where we need to infer the traffic volume on every single link on a road network from a very limited number of observation points. We formulate this task as a regularized optimization problem for probability functions, which is efficiently solved using the notion of natural gradient. Using synthetic and real-world data sets including city traffic monitoring data, we demonstrate the effectiveness of our method.
Wavelets on Graphs via Deep Learning
Authors: Raif Rustamov, Leonidas Guibas
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: An increasing number of applications require processing of signals defined on weighted graphs. While wavelets provide a flexible tool for signal processing in the classical setting of regular domains, the existing graph wavelet constructions are less flexible -- they are guided solely by the structure of the underlying graph and do not take directly into consideration the particular class of signals to be processed. This paper introduces a machine learning framework for constructing graph wavelets that can sparsely represent a given class of signals. Our construction uses the lifting scheme, and is based on the observation that the recurrent nature of the lifting scheme gives rise to a structure resembling a deep auto-encoder network. Particular properties that the resulting wavelets must satisfy determine the training objective and the structure of the involved neural networks. The training is unsupervised, and is conducted similarly to the greedy pre-training of a stack of auto-encoders. After training is completed, we obtain a linear wavelet transform that can be applied to any graph signal in time and memory linear in the size of the graph. Improved sparsity of our wavelet transform for the test signals is confirmed via experiments both on synthetic and real data.
Stochastic Convex Optimization with Multiple  Objectives
Authors: Mehrdad Mahdavi, Tianbao Yang, Rong Jin
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: 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.
Bayesian Hierarchical Community Discovery
Authors: Charles Blundell, Yee Whye Teh
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: We propose an efficient Bayesian nonparametric model for discovering hierarchical community structure in social networks. Our model is a tree-structured mixture of potentially exponentially many stochastic blockmodels. We describe a family of greedy agglomerative model selection algorithms whose worst case scales quadratically in the number of vertices of the network, but independent of the number of communities. Our algorithms are two orders of magnitude faster than the infinite relational model, achieving comparable or better accuracy.
Contrastive Learning Using Spectral Methods
Authors: James Y Zou, Daniel J. Hsu, David C. Parkes, Ryan P. Adams
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: In many natural settings, the analysis goal is not to characterize a single data set in isolation, but rather to understand the difference between one set of observations and another. For example, given a background corpus of news articles together with writings of a particular author, one may want a topic model that explains word patterns and themes specific to the author. Another example comes from genomics, in which biological signals may be collected from different regions of a genome, and one wants a model that captures the differential statistics observed in these regions. This paper formalizes this notion of contrastive learning for  mixture models, and develops spectral algorithms for inferring mixture components specific to a foreground data set when contrasted with a background data set. The method builds on recent moment-based estimators and tensor decompositions for latent variable models, and has the intuitive feature of using background data statistics to appropriately modify moments estimated from foreground data. A key advantage of the method is that the background data need only be coarsely modeled, which is important when the background is too complex, noisy, or not of interest. The method is demonstrated on applications in contrastive topic modeling and genomic sequence analysis.
Deep Fisher Networks for Large-Scale Image Classification
Authors: Karen Simonyan, Andrea Vedaldi, Andrew Zisserman
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: As massively parallel computations have become broadly available with modern GPUs, deep architectures trained on very large datasets have risen in popularity. Discriminatively trained convolutional neural networks, in particular, were recently shown to yield state-of-the-art performance in challenging image classification benchmarks such as ImageNet. However, elements of these architectures are similar to standard hand-crafted representations used in computer vision. In this paper, we explore the extent of this analogy, proposing a version of the state-of-the-art Fisher vector image encoding that can be stacked in multiple layers. This architecture significantly improves on standard Fisher vectors, and obtains competitive results with deep convolutional networks at a significantly smaller computational cost. Our hybrid architecture allows us to measure the performance improvement brought by a deeper image classification pipeline, while staying in the realms of conventional SIFT features and FV encodings.
Linear Convergence with Condition Number Independent Access of Full Gradients
Authors: Lijun Zhang, Mehrdad Mahdavi, Rong Jin
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: For smooth and strongly convex optimization, the optimal iteration complexity of the gradient-based algorithm is $O(\sqrt{\kappa}\log 1/\epsilon)$, where $\kappa$ is the conditional number. In the case that the optimization problem is ill-conditioned, we need to evaluate a larger number of full gradients, which could be computationally expensive. In this paper, we propose to reduce the number of full gradient required by allowing the algorithm to access the stochastic gradients of the objective function. To this end, we present a novel algorithm named Epoch Mixed Gradient Descent (EMGD) that is able to utilize two kinds of gradients.  A distinctive step in EMGD is the mixed gradient descent, where we use an combination of the gradient and the stochastic gradient to update the intermediate solutions. By performing a fixed number of mixed gradient descents, we are able to improve the sub-optimality of the solution by a constant factor, and thus achieve a linear convergence rate. Theoretical analysis shows that EMGD is able to find an $\epsilon$-optimal solution by computing $O(\log 1/\epsilon)$ full gradients and $O(\kappa^2\log 1/\epsilon)$ stochastic gradients.
Learning with Noisy Labels
Authors: Nagarajan Natarajan, Inderjit S Dhillon, Pradeep K Ravikumar, Ambuj Tewari
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: 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.
Variational Policy Search via Trajectory Optimization
Authors: Sergey Levine, Vladlen Koltun
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: In order to learn effective control policies for dynamical systems, policy search methods must be able to discover successful executions of the desired task. While random exploration can work well in simple domains, complex and high-dimensional tasks present a serious challenge, particularly when combined with high-dimensional policies that make parameter-space exploration infeasible. We present a method that uses trajectory optimization as a powerful exploration strategy that guides the policy search. A variational decomposition of a maximum likelihood policy objective allows us to use standard trajectory optimization algorithms such as differential dynamic programming, interleaved with standard supervised learning for the policy itself. We demonstrate that the resulting algorithm can outperform prior methods on two challenging locomotion tasks.
Dropout Training as Adaptive Regularization
Authors: Stefan Wager, Sida Wang, Percy Liang
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: Dropout and other feature noising schemes control overfitting by artificially corrupting the training data. For generalized linear models, dropout performs a form of adaptive regularization. Using this viewpoint, we show that the dropout regularizer is first-order equivalent to an $\LII$ regularizer applied after scaling the features by an estimate of the inverse diagonal Fisher information matrix. We also establish a connection to AdaGrad, an online learner, and find that a close relative of AdaGrad operates by repeatedly solving linear dropout-regularized problems. By casting dropout as regularization, we develop a natural semi-supervised algorithm that uses unlabeled data to create a better adaptive regularizer. We apply this idea to document classification tasks, and show that it consistently boosts the performance of dropout training, improving on state-of-the-art results on the IMDB reviews dataset.
Prior-free and prior-dependent regret bounds for Thompson Sampling
Authors: Sebastien Bubeck, Che-Yu Liu
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: We consider the stochastic multi-armed bandit problem with a prior distribution on the reward distributions. We are interested in studying prior-free and prior-dependent regret bounds, very much in the same spirit than the usual distribution-free and distribution-dependent bounds for the non-Bayesian stochastic bandit. We first show that Thompson Sampling attains an optimal prior-free bound in the sense that for any prior distribution its Bayesian regret is bounded from above by $14 \sqrt{n K}$. This result is unimprovable in the sense that there exists a prior distribution such that any algorithm has a Bayesian regret bounded from below by $\frac{1}{20} \sqrt{n K}$. We also study the case of priors for the setting of Bubeck et al. [2013] (where the optimal mean is known as well as a lower bound on the smallest gap) and we show that in this case the regret of Thompson Sampling is in fact uniformly bounded over time, thus showing that Thompson Sampling can greatly take advantage of the nice properties of these priors.
Geometric optimisation on positive definite matrices for elliptically contoured distributions
Authors: Suvrit Sra, Reshad Hosseini
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: Hermitian positive definite matrices (HPD) recur throughout statistics and machine learning. In this paper we develop \emph{geometric optimisation} for globally optimising certain nonconvex loss functions arising in the modelling of data via elliptically contoured distributions (ECDs). We exploit the remarkable structure of the convex cone of positive definite matrices which allows one to uncover hidden geodesic convexity of objective functions that are nonconvex in the ordinary Euclidean sense. Going even beyond manifold convexity we show how further metric properties of HPD matrices can be exploited to globally optimise several ECD log-likelihoods that are not even geodesic convex. We present key results that help recognise this geometric structure, as well as obtain efficient fixed-point algorithms to optimise the corresponding objective functions. To our knowledge, ours are the most general results on geometric optimisation of HPD matrices known so far. Experiments reveal the benefits of our approach---it avoids any eigenvalue computations which makes it very competitive.
Manifold-based Similarity Adaptation for Label Propagation
Authors: Masayuki Karasuyama, Hiroshi Mamitsuka
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: Label propagation is one of the state-of-the-art methods for semi-supervised learning, which estimates labels by propagating label information through a graph. Label propagation assumes that data points (nodes) connected in a graph should have similar labels. Consequently, the label estimation heavily depends on edge weights in a graph which represent similarity of each node pair. We propose a method for a graph to capture the manifold structure of input features using edge weights parameterized by a similarity function. In this approach, edge weights represent both similarity and local reconstruction weight simultaneously, both being reasonable for label propagation. For further justification, we provide analytical considerations including an interpretation as a cross-validation of a propagation model in the feature space, and an error analysis based on a low dimensional manifold model. Experimental results demonstrated the effectiveness of our approach both in synthetic and real datasets.
New Subsampling Algorithms for Fast Least Squares Regression
Authors: Paramveer Dhillon, Yichao Lu, Dean P. Foster, Lyle Ungar
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: We address the problem of fast estimation of ordinary least squares (OLS) from large amounts of data ($n \gg p$). We propose three methods which solve the big data problem by subsampling the covariance matrix using either a single or two stage estimation. All three run in the order of size of input i.e. O($np$) and our best method, {\it Uluru}, gives an error bound of $O(\sqrt{p/n})$ which is independent of the amount of subsampling as long as it is above a threshold.  We provide theoretical bounds for our algorithms in the fixed design (with Randomized Hadamard preconditioning) as well as sub-Gaussian random design setting. We also compare the performance of our methods on synthetic and real-world datasets and show that if observations are i.i.d., sub-Gaussian then one can directly subsample without the expensive Randomized Hadamard preconditioning without loss of accuracy.
A message-passing algorithm for multi-agent trajectory planning
Authors: José Bento, Nate Derbinsky, Javier Alonso-Mora, Jonathan S. Yedidia
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: We describe a novel approach for computing collision-free \emph{global} trajectories for $p$ agents with specified initial and final configurations, based on an improved version of the alternating direction method of multipliers (ADMM) algorithm. Compared with existing methods, our approach is naturally parallelizable and allows for incorporating different cost functionals with only minor adjustments. We apply our method to classical challenging instances and observe that its computational requirements scale well with $p$ for several cost functionals. We also show that a specialization of our algorithm can be used for {\em local} motion planning by solving the problem of joint optimization in velocity space.
Solving the multi-way matching problem by permutation synchronization
Authors: Deepti Pachauri, Risi Kondor, Vikas Singh
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: The problem of matching not just two, but m different sets of objects to each other arises in a variety of contexts, including finding the correspondence between feature points across multiple images in computer vision. At present it is usually solved by matching the sets pairwise, in series. In contrast, we propose a new method, permutation synchronization, which finds all the matchings jointly, in one shot, via a relaxation to eigenvector decomposition. The resulting algorithm is both computationally efficient, and, as we demonstrate with theoretical arguments as well as experimental results, much more stable to noise than previous methods.
Auditing: Active Learning with Outcome-Dependent Query Costs
Authors: Sivan Sabato, Anand D Sarwate, Nati Srebro
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: We propose a learning setting in which unlabeled data is free, and the cost of a label depends on its value, which is not known in advance. We study binary classification in an extreme case, where the algorithm only pays for negative labels. Our motivation are applications such as fraud detection, in which investigating an honest transaction should be avoided if possible. We term the setting auditing, and consider the auditing complexity of an algorithm: The number of negative points it labels to learn a hypothesis with low relative error. We design auditing algorithms for thresholds on the line and axis-aligned rectangles, and show that with these algorithms, the auditing complexity can be significantly lower than the active label complexity. We discuss a general approach for auditing for a general hypothesis class, and describe several interesting directions for future work.
Restricting exchangeable nonparametric distributions
Authors: Sinead A Williamson, Steve N MacEachern, Eric P Xing
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: Distributions over exchangeable matrices with infinitely many columns are useful in constructing nonparametric latent variable models. However, the distribution implied by such models over the number of features exhibited by each data point may be poorly-suited for many modeling tasks. In this paper, we propose a class of exchangeable nonparametric priors obtained by restricting the domain of existing models. Such models allow us to specify the distribution over the number of features per data point, and can achieve better performance on data sets where the number of features is not well-modeled by the original distribution.
On the Linear Convergence of the Proximal Gradient Method for Trace Norm Regularization
Authors: Ke Hou, Zirui Zhou, Anthony Man-Cho So, Zhi-Quan Luo
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: Motivated by various applications in machine learning, the problem of minimizing a convex smooth loss function with trace norm regularization has received much attention lately.  Currently, a popular method for solving such problem is the proximal gradient method (PGM), which is known to have a sublinear rate of convergence.  In this paper, we show that for a large class of loss functions, the convergence rate of the PGM is in fact linear.  Our result is established without any strong convexity assumption on the loss function.  A key ingredient in our proof is a new Lipschitzian error bound for the aforementioned trace norm-regularized problem, which may be of independent interest.
Eluder Dimension and the Sample Complexity of Optimistic Exploration
Authors: Daniel Russo, Benjamin Van Roy
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: This paper considers the sample complexity of the multi-armed bandit with dependencies among the arms. Some of the most successful algorithms for this problem use the principle of optimism in the face of uncertainty to guide exploration. The clearest example of this is the class of upper confidence bound (UCB) algorithms, but recent work has shown that a simple posterior sampling algorithm, sometimes called Thompson sampling, also shares a close theoretical connection with optimistic approaches. In this paper, we develop a regret bound that holds for both classes of algorithms. This bound applies broadly and can be specialized to many model classes. It depends on a new notion we refer to as the eluder dimension, which measures the degree of dependence among action rewards. Compared to UCB algorithm regret bounds for specific model classes, our general bound matches the best available for linear models and is stronger than the best available for generalized linear models.
Efficient Algorithm for Privately Releasing Smooth Queries
Authors: Ziteng Wang, Kai Fan, Jiaqi Zhang, Liwei Wang
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: We study differentially private mechanisms for answering \emph{smooth} queries on databases consisting of data points in $\mathbb{R}^d$. A $K$-smooth query is specified by a function whose partial derivatives up to order $K$ are all bounded. We develop an $\epsilon$-differentially private mechanism which for the class of $K$-smooth queries has accuracy $O (\left(\frac{1}{n}\right)^{\frac{K}{2d+K}}/\epsilon)$. The mechanism first outputs a summary of the database. To obtain an answer of a query, the user runs a public evaluation algorithm which contains no information of the database. Outputting the summary runs in time $O(n^{1+\frac{d}{2d+K}})$, and the evaluation algorithm for answering a query runs in time $\tilde O (n^{\frac{d+2+\frac{2d}{K}}{2d+K}} )$. Our mechanism is based on $L_{\infty}$-approximation of (transformed) smooth functions by low degree even trigonometric polynomials with small and efficiently computable coefficients.
Buy-in-Bulk Active Learning
Authors: Liu Yang, Jaime Carbonell
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: In many practical applications of active learning, it is more cost-effective to request labels in large batches, rather than one-at-a-time. This is because the cost of labeling a large batch of examples at once is often sublinear in the number of examples in the batch. In this work, we study the label complexity of active learning algorithms that request labels in a given number of batches, as well as the tradeoff between the total number of queries and the number of rounds allowed. We additionally study the total cost sufficient for learning, for an abstract notion of the cost of requesting the labels of a given number of examples at once. In particular, we find that for sublinear cost functions, it is often desirable to request labels in large batches (i.e., buying in bulk); although this may increase the total number of labels requested, it reduces the total cost required for learning.
On Poisson Graphical Models
Authors: Eunho Yang, Pradeep K Ravikumar, Genevera I Allen, Zhandong Liu
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: Undirected graphical models, such as Gaussian graphical models, Ising, and multinomial/categorical graphical models, are widely used in a variety of applications for modeling distributions over a large number of variables. These standard instances, however, are ill-suited to modeling count data, which are increasingly ubiquitous in big-data settings such as genomic sequencing data, user-ratings data, spatial incidence data, climate studies, and site visits. Existing classes of Poisson graphical models, which arise as the joint distributions that correspond to Poisson distributed node-conditional distributions, have a major drawback: they can only model negative conditional dependencies for reasons of normalizability given its infinite domain. In this paper, our objective is to modify the Poisson graphical model distribution so that it can capture a rich dependence structure between count-valued variables. We begin by discussing two strategies for truncating the Poisson distribution and show that only one of these leads to a valid joint distribution; even this model, however, has limitations on the types of variables and dependencies that may be modeled. To address this, we propose two novel variants of the Poisson distribution and their corresponding joint graphical model distributions.  These models provide a class of Poisson graphical models that can capture both positive and negative conditional dependencies between count-valued variables. One can learn the graph structure of our model via penalized neighborhood selection, and we demonstrate the performance of our methods by learning simulated networks as well as a network from microRNA-Sequencing data.
On Sampling from the Gibbs Distribution with Random Maximum A-Posteriori Perturbations
Authors: Tamir Hazan, Subhransu Maji, Tommi Jaakkola
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: In this paper we describe how MAP inference can be used to sample efficiently from Gibbs distributions. Specifically, we provide  means for drawing either approximate or unbiased samples from Gibbs' distributions by introducing low dimensional perturbations and solving the corresponding MAP assignments. Our approach also leads to new ways to derive lower bounds on partition functions. We demonstrate empirically that our method excels in the typical high signal - high coupling'' regime. The setting results in ragged energy landscapes that are challenging for alternative approaches to sampling and/or lower bounds. "
Factorized Asymptotic Bayesian Inference for Latent Feature Models
Authors: Kohei Hayashi, Ryohei Fujimaki
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: 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."
Minimax Theory for High-dimensional Gaussian Mixtures with Sparse Mean Separation
Authors: Martin Azizyan, Aarti Singh, Larry Wasserman
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: While several papers have investigated computationally and statistically efficient methods for learning Gaussian mixtures, precise minimax bounds for their statistical performance as well as fundamental limits in high-dimensional settings are not well-understood. In this paper, we provide precise information theoretic bounds on the clustering accuracy and sample complexity of learning a mixture of two isotropic Gaussians in high dimensions under small mean separation. If there is a sparse subset of relevant dimensions that determine the mean separation, then the sample complexity only depends on the number of relevant dimensions and mean separation, and can be achieved by a simple computationally efficient procedure. Our results provide the first step of a theoretical basis for recent methods that combine feature selection and clustering.