mtybilly/Instruct2DS huggingface dataset:
A memory frontier for complex synapses
Authors: Surya Ganguli Subhaneil Lahiri
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: An incredible gulf separates theoretical models of synapses, often described solely by a single scalar value denoting the size of a postsynaptic potential, from the immense complexity of molecular signaling pathways underlying real synapses. To understand the functional contribution of such molecular complexity to learning and memory, it is essential to expand our theoretical conception of a synapse from a single scalar to an entire dynamical system with many internal molecular functional states. Moreover, theoretical considerations alone demand such an expansion; network models with scalar synapses assuming finite numbers of distinguishable synaptic strengths have strikingly limited memory capacity. This raises the fundamental question, how does synaptic complexity give rise to memory? To address this, we develop new mathematical theorems elucidating the relationship between the structural organization and memory properties of complex synapses that are themselves molecular networks. Moreover, in proving such theorems, we uncover a framework, based on first passage time theory, to impose an order on the internal states of complex synaptic models, thereby simplifying the relationship between synaptic structure and function.
Data-driven Distributionally Robust Polynomial Optimization
Authors: Emanuele Ragnoli, Jia Yuan Yu Martin Mevissen
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: We consider robust optimization for polynomial optimization problems where the uncertainty set is a set of candidate probability density functions. This set is a ball around a density function estimated from data samples, i.e., it is data-driven and random.  Polynomial optimization problems are inherently hard due to nonconvex objectives and constraints.  However, we show that by employing polynomial and histogram density estimates, we can introduce robustness with respect to distributional uncertainty sets without making the problem harder.  We show that the solution to the distributionally robust problem is the limit of a sequence of tractable semidefinite programming relaxations.  We also give finite-sample consistency guarantees for the data-driven uncertainty  sets.  Finally, we apply our model and solution method in a water network problem.
Learning Stochastic Inverses
Authors: Jacob Taylor, Noah Goodman Andreas Stuhlmüller
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: We describe a class of algorithms for amortized inference in Bayesian networks. In this setting, we invest computation upfront to support rapid online inference for a wide range of queries. Our approach is based on learning an inverse factorization of a model's joint distribution: a factorization that turns observations into root nodes.  Our algorithms accumulate information to estimate the local conditional distributions that constitute such a factorization. These stochastic inverses can be used to invert each of the computation steps leading to an observation, sampling backwards in order to quickly find a likely explanation. We show that estimated inverses converge asymptotically in number of (prior or posterior) training samples.  To make use of inverses before convergence, we describe the Inverse MCMC algorithm, which uses stochastic inverses to make block proposals for a Metropolis-Hastings sampler.  We explore the efficiency of this sampler for a variety of parameter regimes and Bayes nets.
Stochastic Ratio Matching of RBMs for Sparse High-Dimensional Inputs
Authors: Yoshua Bengio Yann Dauphin
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: Sparse high-dimensional data vectors are common in many application domains where a very large number of rarely non-zero features can be devised. Unfortunately, this creates a computational bottleneck for unsupervised feature learning algorithms such as those based on auto-encoders and RBMs, because they involve a reconstruction step where the whole input vector is predicted from the current feature values. An algorithm was recently developed to successfully handle the case of auto-encoders, based on an importance sampling  scheme stochastically selecting which input elements to actually reconstruct during training for each particular example.  To generalize this idea to RBMs, we propose a stochastic ratio-matching algorithm that inherits all the computational advantages and unbiasedness of the importance sampling scheme. We show that stochastic ratio matching is a good estimator, allowing the approach to beat the state-of-the-art on two bag-of-word text classification benchmarks (20 Newsgroups and RCV1), while keeping computational cost linear in the number of non-zeros.
Distributed $k$-means and $k$-median Clustering on General Topologies
Authors: Steven Ehrlich, Yingyu Liang Maria-Florina F Balcan
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: This paper provides new algorithms for distributed clustering for two popular center-based objectives, $k$-median and $k$-means. These algorithms have provable guarantees and improve communication complexity over existing approaches. Following a classic approach in clustering by \cite{har2004coresets}, we reduce the problem of finding a clustering with low cost to the problem of finding a `coreset' of small size. We provide a distributed method for constructing a global coreset which improves over the previous methods by reducing the communication complexity, and which works over general communication topologies. We provide experimental evidence for this approach on both synthetic and real data sets.
Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n)
Authors: Eric Moulines Francis Bach
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: We consider the stochastic approximation problem where a convex function has to be minimized, given only the knowledge of unbiased estimates of its gradients at certain points, a framework which includes machine learning methods based on the minimization of the empirical risk. We focus on problems without strong convexity, for which all previously known algorithms achieve a convergence rate for function values of $O(1/\sqrt{n})$. We consider and analyze two algorithms that achieve a rate of $O(1/n)$ for classical   supervised learning problems. For least-squares regression, we show that   averaged stochastic gradient descent with constant step-size achieves the desired rate.  For logistic regression, this is achieved by a simple novel stochastic gradient algorithm that (a) constructs successive local quadratic approximations of the loss functions, while (b) preserving the same running time complexity as stochastic gradient descent. For these algorithms, we provide a non-asymptotic analysis of the generalization error (in expectation, and also in high probability for least-squares), and run extensive experiments showing that they often outperform existing approaches.
Predicting Parameters in Deep Learning
Authors: Babak Shakibi, Laurent Dinh, Marc'Aurelio Ranzato, Nando de Freitas Misha Denil
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: We demonstrate that there is significant redundancy in the parameterization of   several deep learning models.  Given only a few weight values for each feature   it is possible to accurately predict the remaining values.  Moreover, we show   that not only can the parameter values be predicted, but many of them need not   be learned at all.  We train several different architectures by learning only   a small number of weights and predicting the rest.  In the best case we are   able to predict more than 95% of the weights of a network without any drop in   accuracy.
Estimation Bias in Multi-Armed Bandit Algorithms for Search Advertising
Authors: Tao Qin, Tie-Yan Liu Min Xu
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: In search advertising, the search engine needs to select the most profitable advertisements to display, which can be formulated as an instance of online learning with partial feedback, also known as the stochastic multi-armed bandit (MAB) problem. In this paper, we show that the naive application of MAB algorithms to search advertising for advertisement selection will produce sample selection bias that harms the search engine by decreasing expected revenue and “estimation of the largest mean” (ELM) bias that harms the advertisers by increasing game-theoretic player-regret. We then propose simple bias-correction methods with benefits to both the search engine and the advertisers.
Learning Efficient Random Maximum A-Posteriori Predictors with Non-Decomposable Loss Functions
Authors: Subhransu Maji, Joseph Keshet, Tommi Jaakkola Tamir Hazan
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: In this work we develop efficient methods for learning random MAP predictors for structured label problems. In particular, we construct posterior distributions over perturbations that can be adjusted via stochastic gradient methods. We show that every smooth posterior distribution would suffice to define a smooth PAC-Bayesian risk bound suitable for gradient methods. In addition, we relate the posterior distributions to computational properties of the MAP predictors. We suggest multiplicative posteriors to learn super-modular potential functions that accompany specialized MAP predictors such as graph-cuts. We also describe label-augmented posterior models that can use efficient MAP approximations, such as those arising from linear program relaxations.
q-OCSVM: A q-Quantile Estimator for High-Dimensional Distributions
Authors: Michael Lindenbaum, Shaul Markovitch Assaf Glazer
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: In this paper we introduce a novel method that can efficiently estimate a family of hierarchical dense sets in high-dimensional distributions. Our method can be regarded as a natural extension of the one-class SVM (OCSVM) algorithm that finds multiple parallel separating hyperplanes in a reproducing kernel Hilbert space. We call our method q-OCSVM, as it can be used to estimate $q$ quantiles of a high-dimensional distribution. For this purpose, we introduce a new global convex optimization program that finds all estimated sets at once and show that it can be solved efficiently. We prove the correctness of our method and present empirical results that demonstrate its superiority over existing methods.
Fantope Projection and Selection: A near-optimal convex relaxation of sparse PCA
Authors: Juhee Cho, Jing Lei, Karl Rohe Vincent Q. Vu
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: We propose a novel convex relaxation of sparse principal subspace estimation based on the convex hull of rank-$d$ projection matrices (the Fantope). The convex problem can be solved efficiently using alternating direction method of multipliers (ADMM). We establish a near-optimal convergence rate, in terms of the sparsity, ambient dimension, and sample size, for estimation of the principal subspace of a general covariance matrix without assuming the spiked covariance model. In the special case of $d=1$, our result implies the near- optimality of DSPCA even when the solution is not rank 1. We also provide a general theoretical framework for analyzing the statistical  properties of the method for arbitrary input matrices that extends the  applicability and provable guarantees to a wide array of settings.  We  demonstrate this with an application to Kendall's tau correlation matrices  and transelliptical component analysis.
Fast Template Evaluation with Vector Quantization
Authors: David Forsyth Mohammad Amin Sadeghi
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: Applying linear templates is an integral part of many object detection systems and accounts for a significant portion of computation time. We describe a method that achieves a substantial end-to-end speedup over the best current methods, without loss of accuracy. Our method is a combination of approximating scores by vector quantizing feature windows and a number of speedup techniques including cascade. Our procedure allows speed and accuracy to be traded off in two ways: by choosing the number of Vector Quantization levels, and by choosing to rescore windows or not. Our method can be directly plugged into any recognition system that relies on linear templates. We demonstrate our method to speed up the original Exemplar SVM detector [1] by an order of magnitude and Deformable Part models [2] by two orders of magnitude with no loss of accuracy.
Sparse Additive Text Models with Low Rank Background
Authors: Lei Shi
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: The sparse additive model for text modeling involves the sum-of-exp computing, with consuming costs for large scales. Moreover, the assumption of equal background across all classes/topics may be too strong. This paper extends to propose sparse additive model with low rank background (SAM-LRB), and simple yet efficient estimation. Particularly, by employing a double majorization bound, we approximate the log-likelihood into a quadratic lower-bound with the sum-of-exp terms absent. The constraints of low rank and sparsity are then simply embodied by nuclear norm and $\ell_1$-norm regularizers. Interestingly, we find that the optimization task in this manner can be transformed into the same form as that in Robust PCA. Consequently, parameters of supervised SAM-LRB can be efficiently learned using an existing algorithm for Robust PCA based on accelerated proximal gradient. Besides the supervised case, we extend SAM-LRB to also favor unsupervised and multifaceted scenarios. Experiments on real world data demonstrate the effectiveness and efficiency of SAM-LRB, showing state-of-the-art performances.
Correlated random features for fast semi-supervised learning
Authors: David Balduzzi, Joachim M Buhmann Brian McWilliams
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: This paper presents Correlated Nystrom Views (XNV), a fast semi-supervised algorithm for regression and classification. The algorithm draws on two main ideas. First, it generates two views consisting of computationally inexpensive random features. Second, multiview regression, using Canonical Correlation Analysis (CCA) on unlabeled data, biases the regression towards useful features. It has been shown that CCA regression can substantially reduce variance with a minimal increase in bias if the views contains accurate estimators. Recent theoretical and empirical work shows that regression with random features closely approximates kernel regression, implying that the accuracy requirement holds for random views. We show that XNV consistently outperforms a state-of-the-art algorithm for semi-supervised learning: substantially improving predictive performance and reducing the variability of performance on a wide variety of real-world datasets, whilst also reducing runtime by orders of magnitude.
Variational Planning for Graph-based MDPs
Authors: Qiang Liu, Feng Chen, Alex Ihler Qiang Cheng
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: Markov Decision Processes (MDPs) are extremely useful for modeling and solving sequential decision making problems. Graph-based MDPs provide a compact representation for MDPs with large numbers of random variables. However, the complexity of exactly solving a graph-based MDP usually grows exponentially in the number of variables, which limits their application. We present a new variational framework to describe and solve the planning problem of MDPs, and derive both exact and approximate planning algorithms. In particular, by exploiting the graph structure of graph-based MDPs, we propose a factored variational value iteration algorithm in which the value function is first approximated by the multiplication of local-scope value functions, then solved by minimizing a Kullback-Leibler (KL) divergence. The KL divergence is optimized using the belief propagation algorithm, with complexity exponential in only the cluster size of the graph. Experimental comparison on different models shows that our algorithm outperforms existing approximation algorithms at finding good policies.
Adaptive Anonymity via $b$-Matching
Authors: Tony Jebara, Kui Tang Krzysztof M Choromanski
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: The adaptive anonymity problem is formalized where each individual shares their data along with an integer value to indicate their personal level of desired privacy. This problem leads to a generalization of $k$-anonymity to the $b$-matching setting. Novel algorithms and theory are provided to implement this type of anonymity. The relaxation achieves better utility, admits theoretical privacy guarantees that are as strong, and, most importantly, accommodates a variable level of anonymity for each individual. Empirical results confirm improved utility on benchmark and social data-sets.
Statistical Active Learning Algorithms
Authors: Vitaly Feldman Maria-Florina F Balcan
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: We describe a framework for designing efficient active learning algorithms that are tolerant to random classification noise. The framework is based on active learning algorithms that are statistical in the sense that they rely on estimates of expectations of functions of filtered random examples. It builds on the powerful statistical query framework of Kearns (1993).  We show that any efficient active statistical learning algorithm can be automatically converted to an efficient active learning algorithm which is tolerant to random classification noise as well as other forms of uncorrelated" noise. The complexity of the resulting algorithms has information-theoretically optimal quadratic dependence on $1/(1-2\eta)$, where $\eta$ is the noise rate.  We demonstrate the power of our framework by showing that commonly studied concept classes including thresholds, rectangles, and linear separators can be efficiently actively learned in our framework. These results combined with our generic conversion lead to the first known computationally-efficient algorithms for actively learning some of these concept classes in the presence of random classification noise that provide exponential improvement in the dependence on the error $\epsilon$ over their passive counterparts. In addition, we show that our algorithms can be automatically converted to efficient active differentially-private algorithms. This leads to the first differentially-private active learning algorithms with exponential label savings over the passive case."
The Power of Asymmetry in Binary Hashing
Authors: Nati Srebro, Ruslan Salakhutdinov, Yury Makarychev, Payman Yadollahpour Behnam Neyshabur
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: When approximating binary similarity using the hamming distance between short binary hashes, we shown that even if the similarity is symmetric, we can have shorter and more accurate hashes by using two distinct code maps. I.e.~by approximating the similarity between $x$ and $x'$ as the hamming distance between $f(x)$ and $g(x')$, for two distinct binary codes $f,g$, rather than as the hamming distance between $f(x)$ and $f(x')$.
Bayesian Mixture Modelling and Inference based Thompson Sampling in Monte-Carlo Tree Search
Authors: Feng Wu, Xiaoping Chen Aijun Bai
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: Monte-Carlo tree search is drawing great interest in the domain of planning under uncertainty, particularly when little or no domain knowledge is available. One of the central problems is the trade-off between exploration and exploitation. In this paper we present a novel Bayesian mixture modelling and inference based Thompson sampling approach to addressing this dilemma. The proposed Dirichlet-NormalGamma MCTS (DNG-MCTS) algorithm represents the uncertainty of the accumulated reward for actions in the MCTS search tree as a mixture of Normal distributions and inferences on it in Bayesian settings by choosing conjugate priors in the form of combinations of Dirichlet and NormalGamma distributions. Thompson sampling is used to select the best action at each decision node. Experimental results show that our proposed algorithm has achieved the state-of-the-art comparing with popular UCT algorithm in the context of online planning for general Markov decision processes.
Distributed Submodular Maximization: Identifying Representative Elements in Massive Data
Authors: Amin Karbasi, Rik Sarkar, Andreas Krause Baharan Mirzasoleiman
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: Many large-scale machine learning problems (such as clustering, non-parametric learning, kernel machines, etc.) require selecting, out of a massive data set, a manageable, representative subset. Such problems can often be reduced to maximizing a submodular set function subject to cardinality constraints. Classical approaches require centralized access to the full data set; but for truly large-scale problems, rendering the data centrally is often impractical.  In this paper, we consider the problem of submodular function maximization in a distributed fashion. We develop a simple, two-stage protocol GreeDI, that is easily implemented using MapReduce style computations. We theoretically analyze our approach, and show, that under certain natural conditions, performance close to the (impractical) centralized approach can be achieved. In our extensive experiments, we demonstrate the effectiveness of our approach on several applications, including sparse Gaussian process inference on tens of millions of examples using Hadoop.
Analyzing the Harmonic Structure in Graph-Based Learning
Authors: Zhenguo Li, Shih-Fu Chang Xiao-Ming Wu
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: We show that either explicitly or implicitly, various well-known graph-based models exhibit a common significant \emph{harmonic} structure in its target function -- the value of a vertex is approximately the weighted average of the values of its adjacent neighbors. Understanding of such structure and analysis of the loss defined over such structure help reveal important properties of the target function over a graph. In this paper, we show that the variation of the target function across a cut can be upper and lower bounded by the ratio of its harmonic loss and the cut cost. We use this to develop an analytical tool and analyze 5 popular models in graph-based learning: absorbing random walks, partially absorbing random walks, hitting times, pseudo-inverse of graph Laplacian, and eigenvectors of the Laplacian matrices. Our analysis well explains several open questions of these models reported in the literature. Furthermore, it provides theoretical justifications and guidelines for their practical use. Simulations on synthetic and real datasets support our analysis.
Near-optimal Anomaly Detection in Graphs using Lovasz Extended Scan Statistic
Authors: Akshay Krishnamurthy, Aarti Singh James L Sharpnack
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: The detection of anomalous activity in graphs is a statistical problem that arises in many applications, such as network surveillance, disease outbreak detection, and activity monitoring in social networks. Beyond its wide applicability, graph structured anomaly detection serves as a case study in the difficulty of balancing computational complexity with statistical power. In this work, we develop from first principles the generalized likelihood ratio test for determining if there is a well connected region of activation over the vertices in the graph in Gaussian noise. Because this test is computationally infeasible, we provide a relaxation, called the Lov\'asz extended scan statistic (LESS) that uses submodularity to approximate the intractable generalized likelihood ratio. We demonstrate a connection between LESS and maximum a-posteriori inference in Markov random fields, which provides us with a poly-time algorithm for LESS. Using electrical network theory, we are able to control type 1 error for LESS and prove conditions under which LESS is risk consistent. Finally, we consider specific graph models, the torus, $k$-nearest neighbor graphs, and $\epsilon$-random graphs. We show that on these graphs our results provide near-optimal performance by matching our results to known lower bounds.
Bellman Error Based Feature Generation using Random Projections on Sparse Spaces
Authors: Yuri Grinberg, Amir-massoud Farahmand, Joelle Pineau, Doina Precup Mahdi Milani Fard
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: This paper addresses the problem of automatic generation of features for value function approximation in reinforcement learning.  Bellman Error Basis Functions (BEBFs) have been shown to improve the error of policy evaluation with function approximation, with a convergence rate similar to that of value iteration. We propose a simple, fast and robust algorithm based on random projections, which generates BEBFs for sparse feature spaces. We provide a finite sample analysis of the proposed method, and prove that projections logarithmic in the dimension of the original space guarantee a contraction in the error.  Empirical results demonstrate the strength of this method in domains in which choosing a good state representation is challenging.
Similarity Component Analysis
Authors: Kuan Liu, Fei Sha Soravit Changpinyo
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: Measuring similarity is crucial to many learning tasks. It is also a richer and broader notion than what most metric learning algorithms can model. For example, similarity can arise from the process of aggregating the decisions of multiple latent components, where each latent component compares data in its own way by focusing on a different subset of features. In this paper, we propose Similarity Component Analysis (SCA), a probabilistic graphical model that discovers those latent components from data. In SCA, a latent component generates a local similarity value, computed with its own metric, independently of other components. The final similarity measure is then obtained by combining the local similarity values with a (noisy-)OR gate. We derive an EM-based algorithm for fitting the model parameters with similarity-annotated data from pairwise comparisons. We validate the SCA model on synthetic datasets where SCA discovers the ground-truth about the latent components. We also apply SCA to a multiway classification task and a link prediction task. For both tasks, SCA attains significantly better prediction accuracies than competing methods. Moreover, we show how SCA can be instrumental in exploratory analysis of data, where we gain insights about the data by examining patterns hidden in its latent components' local similarity values.
Matrix Completion From any Given Set of Observations
Authors: Adi Shraibman Troy Lee
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: In the matrix completion problem the aim is to recover an unknown real matrix from a subset of its entries.  This problem comes up in many application areas, and has received a great deal of attention in the context of the netflix prize.  A central approach to this problem is to output a matrix of lowest  possible complexity (e.g. rank or trace norm) that agrees with the partially  specified matrix.  The performance of this approach under the assumption that the revealed entries are sampled randomly   has received considerable attention. In practice, often the set of revealed entries is not chosen at random and these results do not apply. We are therefore left with no guarantees on the performance of the algorithm we are using.  We present a means to obtain performance guarantees with respect to any set of initial observations.  The first  step remains the same: find a matrix of lowest possible complexity that agrees with the partially specified matrix.   We give a new way to interpret the output of this algorithm by next finding a probability distribution over  the non-revealed entries with respect to which a bound on the generalization error can be proven.  The more  complex the set of revealed entries according to a certain measure, the better the bound on the generalization  error.
A Deep Architecture for Matching Short Texts
Authors: Hang Li Zhengdong Lu
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: Many machine learning problems can be interpreted as learning for matching two types of objects (e.g., images and captions, users and products, queries and documents). The matching level of two objects is usually measured as the inner product in a certain feature space, while the modeling effort focuses on mapping of objects from the original space to the feature space. This schema, although proven successful on a range of matching tasks, is insufficient for capturing the rich structure in the matching process of more complicated objects.  In this paper, we propose a new deep architecture to more effectively model the complicated matching relations between two objects from heterogeneous domains. More specifically, we apply this model to matching tasks in natural language, e.g., finding sensible responses for a tweet, or  relevant answers to a given question. This new architecture naturally combines the localness and hierarchy intrinsic to the natural language problems, and therefore greatly improves upon the state-of-the-art models.
Sensor Selection in High-Dimensional Gaussian Trees with Nuisances
Authors: Jonathan P How Daniel S Levine
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: We consider the sensor selection problem on multivariate Gaussian distributions where only a \emph{subset} of latent variables is of inferential interest.  For pairs of vertices connected by a unique path in the graph, we show that there exist decompositions of nonlocal mutual information into local information measures that can be computed efficiently from the output of message passing algorithms.  We integrate these decompositions into a computationally efficient greedy selector where the computational expense of quantification can be distributed across nodes in the network.  Experimental results demonstrate the comparative efficiency of our algorithms for sensor selection in high-dimensional distributions. We additionally derive an online-computable performance bound based on augmentations of the relevant latent variable set that, when such a valid augmentation exists, is applicable for \emph{any} distribution with nuisances.
The Total Variation on Hypergraphs - Learning on Hypergraphs Revisited
Authors: Simon Setzer, Leonardo Jost, Syama Sundar Rangapuram Matthias Hein
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: Hypergraphs allow to encode higher-order relationships in data and are thus a very flexible modeling tool. Current learning methods are either based on approximations of the hypergraphs via graphs or  on tensor methods which are only applicable under special conditions. In this paper we present a new learning framework on hypergraphs which fully uses the hypergraph structure. The key element  is a family of regularization functionals based on  the total variation on hypergraphs.
Lasso Screening Rules via Dual Polytope Projection
Authors: Jiayu Zhou, Peter Wonka, Jieping Ye Jie Wang
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: Lasso is a widely used regression technique to find sparse representations. When the dimension of the feature space and the number of samples are extremely large, solving the Lasso problem remains challenging. To improve the efficiency of solving large-scale Lasso problems, El Ghaoui and his colleagues have proposed the SAFE rules which are able to quickly identify the inactive predictors, i.e., predictors that have $0$ components in the solution vector. Then, the inactive predictors or features can be removed from the optimization problem to reduce its scale. By transforming the standard Lasso to its dual form, it can be shown that the inactive predictors include the set of inactive constraints on the optimal dual solution. In this paper, we propose an efficient and effective screening rule via Dual Polytope Projections (DPP), which is mainly based on the uniqueness and nonexpansiveness  of the optimal dual solution due to the fact that the feasible set in the dual space is a convex and closed polytope. Moreover, we show that our screening rule can be extended to identify inactive groups in group Lasso. To the best of our knowledge, there is currently no exact" screening rule for group Lasso. We have evaluated our screening rule using many real data sets. Results show that our rule is more effective to identify inactive predictors than existing state-of-the-art screening rules for Lasso."
Multiscale Dictionary Learning for Estimating Conditional Distributions
Authors: Joshua T Vogelstein, David B Dunson Francesca Petralia
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: Nonparametric estimation of the conditional distribution of a response given high-dimensional features is a challenging problem.  It is important to allow not only the mean but also the variance and shape of the response density to change flexibly with features, which are massive-dimensional.  We propose a multiscale dictionary learning model, which expresses the conditional response density as a convex combination of dictionary densities, with the densities used and their weights dependent on the path through a tree decomposition of the feature space.  A fast graph partitioning algorithm is applied to obtain the tree decomposition, with Bayesian methods then used to adaptively prune and average over different sub-trees in a soft probabilistic manner.  The algorithm scales efficiently to approximately one million features.  State of the art predictive performance is demonstrated for toy examples and two neuroscience applications including up to a million features.
Dirty Statistical Models
Authors: Pradeep K Ravikumar Eunho Yang
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: We provide a unified framework for the high-dimensional analysis of “superposition-structured” or “dirty” statistical models: where the model parameters are a “superposition” of structurally constrained parameters. We allow for any number and types of structures, and any statistical model. We consider the general class of $M$-estimators that minimize the sum of any loss function, and an instance of what we call a “hybrid” regularization, that is the infimal convolution of weighted regularization functions, one for each structural component. We provide corollaries showcasing our unified framework for varied statistical models such as linear regression, multiple regression and principal component analysis, over varied superposition structures.
Online Learning of Nonparametric Mixture Models via Sequential Variational Approximation
Authors: Dahua Lin
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: Reliance on computationally expensive algorithms for inference has been limiting the use of Bayesian nonparametric models in large scale applications. To tackle this problem, we propose a Bayesian learning algorithm for DP mixture models. Instead of following the conventional paradigm -- random initialization plus iterative update, we take an progressive approach. Starting with a given prior, our method recursively transforms it into an approximate posterior through sequential variational approximation. In this process, new components will be incorporated on the fly when needed. The algorithm can reliably estimate a DP mixture model in one pass, making it particularly suited for applications with massive data. Experiments on both synthetic data and real datasets demonstrate remarkable improvement on efficiency -- orders of magnitude speed-up compared to the state-of-the-art.
Exact and Stable Recovery of Pairwise Interaction Tensors
Authors: Michael R Lyu, Irwin King, Zenglin Xu Shouyuan Chen
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: Tensor completion from incomplete observations is a problem of significant practical interest.  However, it is unlikely that there exists an efficient algorithm with provable guarantee to recover a general tensor from a limited number of observations. In this paper, we study the recovery algorithm for pairwise interaction tensors, which has recently gained considerable attention for modeling multiple attribute data due to its simplicity and effectiveness. Specifically, in the absence of noise, we show that one can exactly recover a pairwise interaction tensor by solving a constrained convex program which minimizes the weighted sum of nuclear norms of matrices from $O(nr\log^2(n))$ observations.  For the noisy cases, we also prove error bounds for a constrained convex program for recovering the tensors. Our experiments on the synthetic dataset demonstrate that the recovery performance of our algorithm agrees well with the theory. In addition, we apply our algorithm on a temporal collaborative filtering task and obtain state-of-the-art results.
A* Lasso for Learning a Sparse Bayesian Network Structure for Continuous Variables
Authors: Seyoung Kim Jing Xiang
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: We address the problem of learning a sparse Bayesian network  structure for continuous variables in a high-dimensional space. The constraint that the estimated Bayesian network structure  must be a directed acyclic graph (DAG) makes the problem challenging because of the huge search space of network structures. Most previous methods were based on a two-stage approach that prunes the search space in the first stage and then searches for a network structure that satisfies the DAG constraint in the second stage. Although this approach is effective in a low-dimensional setting, it is difficult to ensure that the correct network structure is not pruned in the first stage in a high-dimensional setting.  In this paper, we propose a single-stage method, called A* lasso, that recovers the optimal  sparse Bayesian network structure by solving a single optimization problem with A* search algorithm that uses lasso in its scoring system. Our approach substantially improves the computational efficiency of the well-known exact methods  based on dynamic programming. We also present a heuristic scheme that further improves the efficiency of A* lasso without significantly compromising the quality of solutions and   demonstrate this on benchmark Bayesian networks and real data.
High-Dimensional Gaussian Process Bandits
Authors: Andreas Krause, Volkan Cevher Josip Djolonga
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: Many applications in machine learning require optimizing unknown functions defined over a high-dimensional space from noisy samples that are expensive to obtain. We address this notoriously hard challenge, under the assumptions that the function varies only along some low-dimensional subspace and is smooth (i.e., it has a low norm in a Reproducible Kernel Hilbert Space). In particular, we present the SI-BO algorithm, which leverages recent low-rank matrix recovery techniques to learn the underlying subspace of the unknown function and applies Gaussian Process Upper Confidence sampling for optimization of the function. We carefully calibrate the exploration–exploitation tradeoff by allocating sampling budget to subspace estimation and function optimization, and obtain the first subexponential cumulative regret bounds and convergence rates for Bayesian optimization in high-dimensions under noisy observations. Numerical results demonstrate the effectiveness of our approach in difficult scenarios.
Generalizing Analytic Shrinkage for Arbitrary Covariance Structures
Authors: Klaus-Robert Müller Daniel Bartz
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: Analytic shrinkage is a statistical technique that offers a fast alternative to cross-validation for the regularization of covariance matrices and has appealing consistency properties. We show that the proof of consistency implies bounds on the growth rates of eigenvalues and their dispersion, which are often violated in data. We prove consistency under assumptions which do not restrict the covariance structure and therefore better match real world data. In addition, we propose an extension of analytic shrinkage --orthogonal complement shrinkage-- which adapts to the covariance structure. Finally we demonstrate the superior performance of our novel approach on data from the domains of finance, spoken letter and optical character recognition, and neuroscience.
Higher Order Priors for Joint Intrinsic Image, Objects, and Attributes Estimation
Authors: Carsten Rother, Philip Torr Vibhav Vineet
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: Many methods have been proposed to recover the intrinsic scene properties such as shape, reflectance and illumination from a single image. However, most of these models have been applied on laboratory datasets. In this work we explore the synergy effects between intrinsic scene properties recovered from an image, and the objects and attributes present in the scene. We cast the problem in a joint energy minimization framework; thus our model is able to encode the strong correlations between intrinsic properties (reflectance, shape, illumination), objects (table, tv-monitor), and materials (wooden, plastic) in a given scene. We tested our approach on the NYU and Pascal datasets, and observe both qualitative and quantitative improvements in the overall accuracy.
Online Robust PCA via Stochastic Optimization
Authors: Huan Xu, Shuicheng Yan Jiashi Feng
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: Robust PCA methods are typically based on batch optimization and have to load all the samples into memory. This prevents them from efficiently processing big data. In this paper, we develop  an Online Robust Principal Component Analysis (OR-PCA) that processes one sample per time instance and hence its memory cost is independent of the data size,  significantly enhancing the computation and storage efficiency. The proposed method is based on stochastic optimization of an equivalent reformulation of the batch RPCA method. Indeed, we show that OR-PCA provides a sequence of subspace estimations converging to the optimum of its batch counterpart and hence is provably robust  to sparse corruption. Moreover, OR-PCA can naturally be applied for tracking dynamic subspace. Comprehensive simulations on subspace recovering and tracking demonstrate the robustness and efficiency advantages of the OR-PCA over online PCA and batch RPCA methods.
Compete to Compute
Authors: Jonathan Masci, Sohrob Kazerounian, Faustino Gomez, Jürgen Schmidhuber Rupesh K Srivastava
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: Local competition among neighboring neurons is common in biological neural networks (NNs). We apply the concept to gradient-based, backprop-trained artificial multilayer NNs. NNs with competing linear units tend to outperform those with non-competing nonlinear units, and avoid catastrophic forgetting when training sets change over time.
Heterogeneous-Neighborhood-based Multi-Task Local Learning Algorithms
Authors: Yu Zhang
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: All the existing multi-task local learning methods are defined on homogeneous neighborhood which consists of all data points from only one task. In this paper, different from existing methods, we propose local learning methods for multi-task classification and regression problems based on heterogeneous neighborhood which is defined on data points from all tasks. Specifically, we extend the k-nearest-neighbor classifier by formulating the decision function for each data point as a weighted voting among the neighbors from all tasks where the weights are task-specific. By defining a regularizer to enforce the task-specific weight matrix to approach a symmetric one, a regularized objective function is proposed and an efficient coordinate descent method is developed to solve it. For regression problems, we extend the kernel regression to multi-task setting in a similar way to the classification case. Experiments on some toy data and real-world datasets demonstrate the effectiveness of our proposed methods.
Scalable Influence Estimation in Continuous-Time Diffusion Networks
Authors: Le Song, Manuel Gomez Rodriguez, Hongyuan Zha Nan Du
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: If a piece of information is released from a media site, can it spread, in 1 month, to a million web pages? This influence estimation problem is very challenging since both the time-sensitive nature of the problem and the issue of scalability need to be addressed simultaneously. In this paper, we propose a randomized algorithm for influence estimation in continuous-time diffusion networks. Our algorithm can estimate the influence of every node in a network with $|\Vcal|$ nodes and $|\Ecal|$ edges to an accuracy of $\epsilon$ using  $n=O(1/\epsilon^2)$ randomizations and up to logarithmic factors $O(n|\Ecal|+n|\Vcal|)$ computations. When used as a subroutine in a greedy influence maximization algorithm, our proposed method is guaranteed to find a set of nodes with an influence of at least $(1 - 1/e)\operatorname{OPT} - 2\epsilon$, where $\operatorname{OPT}$ is the optimal value. Experiments on both synthetic and real-world data show that the proposed method can easily scale up to networks of millions of nodes while significantly improves over previous state-of-the-arts in terms of the accuracy of the estimated influence and the quality of the selected nodes in maximizing the influence.