mtybilly/Instruct2DS huggingface dataset:
Boosting with Abstention
Authors: Corinna Cortes, Giulia DeSalvo, Mehryar Mohri
Published in: Advances in Neural Information Processing Systems 29  (NIPS 2016) (Main Conference Track), 2016

Abstract: We present a new boosting algorithm for the key scenario of binary classification with abstention where the algorithm can abstain from predicting the label of a point, at the price of a fixed cost.  At each round, our algorithm selects a pair of functions, a base predictor and a base abstention function.  We define convex upper bounds for the natural loss function associated to this problem, which we prove to be calibrated with respect to the Bayes solution. Our algorithm benefits from general margin-based learning guarantees which we derive for ensembles of pairs of base predictor and abstention functions, in terms of the Rademacher complexities of the corresponding function classes.  We give convergence guarantees for our algorithm along with a linear-time weak-learning algorithm for abstention stumps. We also report the results of several experiments suggesting that our algorithm provides a significant improvement in practice over two confidence-based algorithms.
Linear dynamical neural population models through nonlinear embeddings
Authors: Yuanjun Gao, Evan W Archer, Liam Paninski, John P. Cunningham
Published in: Advances in Neural Information Processing Systems 29  (NIPS 2016) (Main Conference Track), 2016

Abstract: A body of recent work in modeling neural activity focuses on recovering low- dimensional latent features that capture the statistical structure of large-scale neural populations. Most such approaches have focused on linear generative models, where inference is computationally tractable. Here, we propose fLDS, a general class of nonlinear generative models that permits the firing rate of each neuron to vary as an arbitrary smooth function of a latent, linear dynamical state. This extra flexibility allows the model to capture a richer set of neural variability than a purely linear model, but retains an easily visualizable low-dimensional latent space. To fit this class of non-conjugate models we propose a variational inference scheme, along with a novel approximate posterior capable of capturing rich temporal correlations across time. We show that our techniques permit inference in a wide class of generative models.We also show in application to two neural datasets that, compared to state-of-the-art neural population models, fLDS captures a much larger proportion of neural variability with a small number of latent dimensions, providing superior predictive performance and interpretability.
Rényi Divergence Variational Inference
Authors: Yingzhen Li, Richard E Turner
Published in: Advances in Neural Information Processing Systems 29  (NIPS 2016) (Main Conference Track), 2016

Abstract: This paper introduces the variational Rényi bound (VR) that extends traditional variational inference to Rényi's alpha-divergences. This new family of variational methods unifies a number of existing approaches, and enables a smooth interpolation from the evidence lower-bound to the log (marginal) likelihood that is controlled by the value of alpha that parametrises the divergence. The reparameterization trick, Monte Carlo approximation and stochastic optimisation methods are deployed to obtain a tractable and unified framework for optimisation. We further consider negative alpha values and propose a novel variational inference method as a new special case in the proposed framework. Experiments on Bayesian neural networks and variational auto-encoders demonstrate the wide applicability of the VR bound.
Stochastic Gradient Geodesic MCMC Methods
Authors: Chang Liu, Jun Zhu, Yang Song
Published in: Advances in Neural Information Processing Systems 29  (NIPS 2016) (Main Conference Track), 2016

Abstract: We propose two stochastic gradient MCMC methods for sampling from Bayesian posterior distributions defined on Riemann manifolds with a known geodesic flow, e.g. hyperspheres. Our methods are the first scalable sampling methods on these manifolds, with the aid of stochastic gradients. Novel dynamics are conceived and 2nd-order integrators are developed. By adopting embedding techniques and the geodesic integrator, the methods do not require a global coordinate system of the manifold and do not involve inner iterations. Synthetic experiments show the validity of the method, and its application to the challenging inference for spherical topic models indicate practical usability and efficiency.
A posteriori error bounds for joint matrix decomposition problems
Authors: Nicolo Colombo, Nikos Vlassis
Published in: Advances in Neural Information Processing Systems 29  (NIPS 2016) (Main Conference Track), 2016

Abstract: Joint matrix triangularization is often used for estimating the joint eigenstructure of a set M of matrices, with applications in signal processing and machine learning. We consider the problem of approximate joint matrix triangularization when the matrices in M are jointly diagonalizable and real, but we only observe a set M' of noise perturbed versions of the matrices in M. Our main result is a first-order upper bound on the distance between any approximate joint triangularizer of the matrices in M' and any exact joint triangularizer of the matrices in M. The bound depends only on the observable matrices in M' and the noise level. In particular, it does not depend on optimization specific properties of the triangularizer, such as its proximity to critical points, that are typical of existing bounds in the literature. To our knowledge, this is the first a posteriori bound for joint matrix decomposition. We demonstrate the bound on synthetic data for which the ground truth is known.
Global Analysis of Expectation Maximization for Mixtures of Two Gaussians
Authors: Ji Xu, Daniel J. Hsu, Arian Maleki
Published in: Advances in Neural Information Processing Systems 29  (NIPS 2016) (Main Conference Track), 2016

Abstract: Expectation Maximization (EM) is among the most popular algorithms for estimating parameters of statistical models.  However, EM, which is an iterative algorithm based on the maximum likelihood principle, is generally only guaranteed to find stationary points of the likelihood objective, and these points may be far from any maximizer.  This article addresses this disconnect between the statistical principles behind EM and its algorithmic properties.  Specifically, it provides a global analysis of EM for specific models in which the observations comprise an i.i.d. sample from a mixture of two Gaussians.  This is achieved by (i) studying the sequence of parameters from idealized execution of EM in the infinite sample limit, and fully characterizing the limit points of the sequence in terms of the initial parameters; and then (ii) based on this convergence analysis, establishing statistical consistency (or lack thereof) for the actual sequence of parameters produced by EM.
Stochastic Structured Prediction under Bandit Feedback
Authors: Artem Sokolov, Julia Kreutzer, Stefan Riezler, Christopher Lo
Published in: Advances in Neural Information Processing Systems 29  (NIPS 2016) (Main Conference Track), 2016

Abstract: Stochastic structured prediction under bandit feedback follows a learning protocol where on each of a sequence of iterations, the learner receives an input, predicts an output structure, and receives partial feedback in form of a task loss evaluation of the predicted structure. We present applications of this learning scenario to convex and non-convex objectives for structured prediction and analyze them as stochastic first-order methods. We present an experimental evaluation on problems of natural language processing over exponential output spaces, and compare convergence speed across different objectives under the practical criterion of optimal task performance on development data and the optimization-theoretic criterion of minimal squared gradient norm. Best results under both criteria are obtained for a non-convex objective for pairwise preference learning under bandit feedback.
Estimating the class prior and posterior from noisy positives and unlabeled data
Authors: Shantanu Jain, Martha White, Predrag Radivojac
Published in: Advances in Neural Information Processing Systems 29  (NIPS 2016) (Main Conference Track), 2016

Abstract: We develop a classification algorithm for estimating posterior distributions from positive-unlabeled data, that is robust to noise in the positive labels and effective for high-dimensional data. In recent years, several algorithms have been proposed to learn from positive-unlabeled data; however, many of these contributions remain theoretical, performing poorly on real high-dimensional data that is typically contaminated with noise. We build on this previous work to develop two practical classification algorithms that explicitly model the noise in the positive labels and utilize univariate transforms built on discriminative classifiers. We prove that these univariate transforms preserve the class prior, enabling estimation in the univariate space and avoiding kernel density estimation for high-dimensional data. The theoretical development and parametric and nonparametric algorithms proposed here constitute an important step towards wide-spread use of robust classification algorithms for positive-unlabeled data.
A Minimax Approach to Supervised Learning
Authors: Farzan Farnia, David Tse
Published in: Advances in Neural Information Processing Systems 29  (NIPS 2016) (Main Conference Track), 2016

Abstract: Given a task of predicting Y from X, a loss function L, and a set of probability distributions Gamma on (X,Y), what is the optimal decision rule minimizing the worst-case expected loss over Gamma? In this paper, we address this question by introducing a generalization of the maximum entropy principle. Applying this principle to sets of distributions with marginal on X constrained to be the empirical marginal, we provide a minimax interpretation of the maximum likelihood problem over generalized linear models as well as some popular regularization schemes. For quadratic and logarithmic loss functions we revisit well-known linear and logistic regression models. Moreover, for the 0-1 loss we derive a classifier which we call the minimax SVM. The minimax SVM minimizes the worst-case expected 0-1 loss over the proposed Gamma by solving a tractable optimization problem. We perform several numerical experiments to show the power of the minimax SVM in outperforming the SVM.
Blazing the trails before beating the path: Sample-efficient Monte-Carlo planning
Authors: Jean-Bastien Grill, Michal Valko, Remi Munos
Published in: Advances in Neural Information Processing Systems 29  (NIPS 2016) (Main Conference Track), 2016

Abstract: We study the sampling-based planning problem in Markov decision processes (MDPs) that we can access only through a generative model, usually referred to as Monte-Carlo planning. Our objective is to return a good estimate of the optimal value function at any state while minimizing the number of calls to the generative model, i.e. the sample complexity. We propose a new algorithm, TrailBlazer, able to handle MDPs with a finite or an infinite number of transitions from state-action to next states. TrailBlazer is an adaptive algorithm that exploits possible structures of the MDP by exploring only a subset of states reachable by following near-optimal policies. We provide bounds on its sample complexity that depend on a measure of the quantity of near-optimal states. The algorithm behavior can be considered as an extension of Monte-Carlo sampling (for estimating an expectation) to problems that alternate maximization (over actions) and expectation (over next states). Finally, another appealing feature of TrailBlazer is that it is simple to implement and computationally efficient.
Scaling Factorial Hidden Markov Models: Stochastic Variational Inference without Messages
Authors: Yin Cheng Ng, Pawel M Chilinski, Ricardo Silva
Published in: Advances in Neural Information Processing Systems 29  (NIPS 2016) (Main Conference Track), 2016

Abstract: Factorial Hidden Markov Models (FHMMs) are powerful models for sequential data but they do not scale well with long sequences. We propose a scalable inference and learning algorithm for FHMMs that draws on ideas from the stochastic variational inference, neural network and copula literatures. Unlike existing approaches, the proposed algorithm requires no message passing procedure among latent variables and can be distributed to a network of computers to speed up learning. Our experiments corroborate that the proposed algorithm does not introduce further approximation bias compared to the proven structured mean-field algorithm, and achieves better performance with long sequences and large FHMMs.
Improved Dropout for Shallow and Deep Learning
Authors: Zhe Li, Boqing Gong, Tianbao Yang
Published in: Advances in Neural Information Processing Systems 29  (NIPS 2016) (Main Conference Track), 2016

Abstract: Dropout has been witnessed with great success in training deep neural networks by independently   zeroing  out the outputs of neurons at random. It has also received a surge of interest for shallow learning, e.g., logistic regression.  However, the independent  sampling for dropout could be suboptimal for the sake of convergence. In this paper, we propose to use multinomial  sampling for dropout, i.e., sampling features or neurons according to  a multinomial distribution with different probabilities for different features/neurons. To exhibit the optimal dropout probabilities, we analyze the shallow learning with multinomial  dropout and establish the risk bound for stochastic optimization. By minimizing a sampling dependent factor in the risk bound, we obtain a distribution-dependent dropout with sampling probabilities dependent on the second order statistics of the data distribution. To tackle the issue of evolving  distribution of neurons in deep learning, we propose an efficient adaptive  dropout (named \textbf{evolutional dropout}) that computes the sampling probabilities on-the-fly from a mini-batch of examples. Empirical studies on several benchmark datasets demonstrate that the proposed dropouts achieve  not only much faster convergence and  but also a smaller testing error than the standard dropout.  For example, on the CIFAR-100 data, the evolutional  dropout achieves relative improvements  over 10\% on the prediction performance and over 50\% on the convergence speed compared to the standard dropout.
Clustering Signed Networks with the Geometric Mean of Laplacians
Authors: Pedro Mercado, Francesco Tudisco, Matthias Hein
Published in: Advances in Neural Information Processing Systems 29  (NIPS 2016) (Main Conference Track), 2016

Abstract: Signed networks allow to model positive and negative relationships. We analyze existing extensions of spectral clustering to signed networks. It turns out that existing approaches do not recover the ground truth clustering in several situations where either the positive or the negative network structures contain no noise. Our analysis shows that these problems arise as existing approaches take some form of arithmetic mean of the Laplacians of the positive and negative part. As a solution we propose to use the geometric mean of the Laplacians of positive and negative part and show that it outperforms the existing approaches. While the geometric mean of matrices is computationally expensive, we show that eigenvectors of the geometric mean can be computed efficiently, leading to a numerical scheme for sparse matrices which is of independent interest.
Selective inference for group-sparse linear models
Authors: Fan Yang, Rina Foygel Barber, Prateek Jain, John Lafferty
Published in: Advances in Neural Information Processing Systems 29  (NIPS 2016) (Main Conference Track), 2016

Abstract: We develop tools for selective inference in the setting of group sparsity, including the construction of confidence intervals and p-values for testing selected groups of variables. Our main technical result gives the precise distribution of the magnitude of the projection of the data onto a given subspace, and enables us to develop inference procedures for a broad class of group-sparse selection methods, including the group lasso, iterative hard thresholding, and forward stepwise regression. We give numerical results to illustrate these tools on simulated data and on health record data.
InfoGAN: Interpretable Representation Learning by Information Maximizing Generative Adversarial Nets
Authors: Xi Chen, Yan Duan, Rein Houthooft, John Schulman, Ilya Sutskever, Pieter Abbeel
Published in: Advances in Neural Information Processing Systems 29  (NIPS 2016) (Main Conference Track), 2016

Abstract: This paper describes InfoGAN, an information-theoretic extension to the Generative Adversarial Network that is able to learn disentangled representations in a completely unsupervised manner. InfoGAN is a generative adversarial network that also maximizes the mutual information between a small subset of the latent variables and the observation. We derive a lower bound to the mutual information objective that can be optimized efficiently, and show that our training procedure can be interpreted as a variation of the Wake-Sleep algorithm. Specifically, InfoGAN successfully disentangles writing styles from digit shapes on the MNIST dataset, pose from lighting of 3D rendered images, and background digits from the central digit on the SVHN dataset. It also discovers visual concepts that include hair styles, presence/absence of eyeglasses, and emotions on the CelebA face dataset. Experiments show that InfoGAN learns interpretable representations that are competitive with representations learned by existing fully supervised methods.
Automated scalable segmentation of neurons from multispectral images
Authors: Uygar Sümbül, Douglas Roossien, Dawen Cai, Fei Chen, Nicholas Barry, John P. Cunningham, Edward Boyden, Liam Paninski
Published in: Advances in Neural Information Processing Systems 29  (NIPS 2016) (Main Conference Track), 2016

Abstract: Reconstruction of neuroanatomy is a fundamental problem in neuroscience. Stochastic expression of colors in individual cells is a promising tool, although its use in the nervous system has been limited due to various sources of variability in expression. Moreover, the intermingled anatomy of neuronal trees is challenging for existing segmentation algorithms. Here, we propose a method to automate the segmentation of neurons in such (potentially pseudo-colored) images. The method uses spatio-color relations between the voxels, generates supervoxels to reduce the problem size by four orders of magnitude before the final segmentation, and is parallelizable over the supervoxels. To quantify performance and gain insight, we generate simulated images, where the noise level and characteristics, the density of expression, and the number of fluorophore types are variable. We also present segmentations of real Brainbow images of the mouse hippocampus, which reveal many of the dendritic segments.
Robustness of classifiers: from adversarial to random noise
Authors: Alhussein Fawzi, Seyed-Mohsen Moosavi-Dezfooli, Pascal Frossard
Published in: Advances in Neural Information Processing Systems 29  (NIPS 2016) (Main Conference Track), 2016

Abstract: Several recent works have shown that state-of-the-art classifiers are vulnerable to worst-case (i.e., adversarial) perturbations of the datapoints. On the other hand, it has been empirically observed that these same classifiers are relatively robust to random noise. In this paper, we propose to study a semi-random noise regime that generalizes both the random and worst-case noise regimes. We propose the first quantitative analysis of the robustness of nonlinear classifiers in this general noise regime. We establish precise theoretical bounds on the robustness of classifiers in this general regime, which depend on the curvature of the classifier's decision boundary. Our bounds confirm and quantify the empirical observations that classifiers satisfying curvature constraints are robust to random noise. Moreover, we quantify the robustness of classifiers in terms of the subspace dimension in the semi-random noise regime, and show that our bounds remarkably interpolate between the worst-case and random noise regimes. We perform experiments and show that the derived bounds provide very accurate estimates when applied to various state-of-the-art deep neural networks and datasets. This result suggests bounds on the curvature of the classifiers' decision boundaries that we support experimentally, and more generally offers important insights onto the geometry of high dimensional classification problems.
Composing graphical models with neural networks for structured representations and fast inference
Authors: Matthew J Johnson, David K. Duvenaud, Alex Wiltschko, Ryan P. Adams, Sandeep R Datta
Published in: Advances in Neural Information Processing Systems 29  (NIPS 2016) (Main Conference Track), 2016

Abstract: We propose a general modeling and inference framework that combines the complementary strengths of probabilistic graphical models and deep learning methods. Our model family composes latent graphical models with neural network observation likelihoods. For inference, we use recognition networks to produce local evidence potentials, then combine them with the model distribution using efficient message-passing algorithms. All components are trained simultaneously with a single stochastic variational inference objective. We illustrate this framework by automatically segmenting and categorizing mouse behavior from raw depth video, and demonstrate several other example models.
SoundNet: Learning Sound Representations from Unlabeled Video
Authors: Yusuf Aytar, Carl Vondrick, Antonio Torralba
Published in: Advances in Neural Information Processing Systems 29  (NIPS 2016) (Main Conference Track), 2016

Abstract: We learn rich natural sound representations by capitalizing on large amounts of unlabeled sound data collected in the wild. We leverage the natural synchronization between vision and sound to learn an acoustic representation using two-million unlabeled videos. Unlabeled video has the advantage that it can be economically acquired at massive scales, yet contains useful signals about natural sound. We propose a student-teacher training procedure which transfers discriminative visual knowledge from well established visual recognition models into the sound modality using unlabeled video as a bridge. Our sound representation yields significant performance improvements over the state-of-the-art results on standard benchmarks for acoustic scene/object classification. Visualizations suggest some high-level semantics automatically emerge in the sound network, even though it is trained without ground truth labels.
Dual Decomposed Learning with Factorwise Oracle for Structural SVM of Large Output Domain
Authors: Ian En-Hsu Yen, Xiangru Huang, Kai Zhong, Ruohan Zhang, Pradeep K Ravikumar, Inderjit S Dhillon
Published in: Advances in Neural Information Processing Systems 29  (NIPS 2016) (Main Conference Track), 2016

Abstract: Many applications of machine learning involve structured output with large domain, where learning of structured predictor is prohibitive due to repetitive calls to expensive inference oracle. In this work, we show that, by decomposing training of Structural Support Vector Machine (SVM) into a series of multiclass SVM problems connected through messages, one can replace expensive structured oracle with Factorwise Maximization Oracle (FMO) that allows efficient implementation of complexity sublinear to the factor domain. A Greedy Direction Method of Multiplier (GDMM) algorithm is proposed to exploit sparsity of messages which guarantees $\epsilon$ sub-optimality after $O(log(1/\epsilon))$ passes of FMO calls. We conduct experiments on chain-structured problems and fully-connected problems of large output domains. The proposed approach is orders-of-magnitude faster than the state-of-the-art training algorithms for Structural SVM.
Deep Learning for Predicting Human Strategic Behavior
Authors: Jason S Hartford, James R Wright, Kevin Leyton-Brown
Published in: Advances in Neural Information Processing Systems 29  (NIPS 2016) (Main Conference Track), 2016

Abstract: Predicting the behavior of human participants in strategic settings is an important problem in many domains. Most existing work either assumes that participants are perfectly rational, or attempts to directly model each participant's cognitive processes based on insights from cognitive psychology and experimental economics. In this work, we present an alternative, a deep learning approach that automatically performs cognitive modeling without relying on such expert knowledge.  We introduce a novel architecture that allows a single network to generalize across different input and output dimensions by using matrix units rather than scalar units, and show that its performance significantly outperforms that of the previous state of the art, which relies on expert-constructed features.
Online and Differentially-Private Tensor Decomposition
Authors: Yining Wang, Anima Anandkumar
Published in: Advances in Neural Information Processing Systems 29  (NIPS 2016) (Main Conference Track), 2016

Abstract: Tensor decomposition is positioned to be a pervasive tool in the era of big data. In this paper, we resolve many of the key algorithmic questions regarding robustness, memory efficiency, and differential privacy of tensor decomposition. We propose simple variants of the tensor power method which enjoy these strong properties. We propose the first streaming method with a linear memory requirement. Moreover, we present a noise calibrated tensor power method with efficient privacy guarantees. At the heart of all these guarantees lies a careful perturbation analysis derived in this paper which improves up on the existing results significantly.
Multivariate tests of association based on univariate tests
Authors: Ruth Heller, Yair Heller
Published in: Advances in Neural Information Processing Systems 29  (NIPS 2016) (Main Conference Track), 2016

Abstract: For testing two vector random variables for independence, we  propose testing whether the distance of one vector from an arbitrary  center point is independent from the distance of the other vector from another arbitrary center point by a univariate test. We prove that under minimal assumptions, it is enough to have a consistent univariate independence test on the distances, to guarantee that the power to detect dependence between the random vectors increases to one with sample size.  If the univariate test is  distribution-free, the multivariate test will also be distribution-free. If we consider multiple center points and aggregate the  center-specific univariate tests, the power may be further improved, and the resulting multivariate test may be distribution-free for specific aggregation methods (if the univariate test is distribution-free).  We show that certain multivariate tests recently proposed in the literature can be viewed as instances of this general approach. Moreover, we show in experiments that novel tests constructed using our approach can have better power and computational time than competing approaches.
Variational Information Maximization for Feature Selection
Authors: Shuyang Gao, Greg Ver Steeg, Aram Galstyan
Published in: Advances in Neural Information Processing Systems 29  (NIPS 2016) (Main Conference Track), 2016

Abstract: Feature selection is one of the most fundamental problems in machine learning. An extensive body of work on information-theoretic feature selection exists which is based on maximizing mutual information between subsets of features and class labels. Practical methods are forced to rely on approximations due to the difficulty of estimating mutual information. We demonstrate that approximations made by existing methods are based on unrealistic assumptions. We formulate a more flexible and general class of assumptions based on variational distributions and use them to tractably generate lower bounds for mutual information. These bounds define a novel information-theoretic framework for feature selection, which we prove to be optimal under tree graphical models with proper choice of variational distributions. Our experiments demonstrate that the proposed method strongly outperforms existing information-theoretic feature selection approaches.
Matrix Completion has No Spurious Local Minimum
Authors: Rong Ge, Jason Lee, Tengyu Ma
Published in: Advances in Neural Information Processing Systems 29  (NIPS 2016) (Main Conference Track), 2016

Abstract: Matrix completion is a basic machine learning problem that has wide applications, especially in collaborative filtering and recommender systems. Simple non-convex optimization algorithms are popular and effective in practice. Despite recent progress in proving various non-convex algorithms converge from a good initial point, it remains unclear why random or arbitrary initialization suffices in practice. We prove that the commonly used non-convex objective function for matrix completion has no spurious local minima --- all local minima must also be global. Therefore, many popular optimization algorithms such as (stochastic) gradient descent can provably solve matrix completion with \textit{arbitrary} initialization in polynomial time.
Deep Submodular Functions: Definitions and Learning
Authors: Brian W Dolhansky, Jeff A. Bilmes
Published in: Advances in Neural Information Processing Systems 29  (NIPS 2016) (Main Conference Track), 2016

Abstract: We propose and study a new class of submodular functions called deep submodular functions (DSFs). We define DSFs and situate them within the broader context of classes of submodular functions in relationship both to various matroid ranks and sums of concave composed with modular functions (SCMs). Notably, we find that DSFs constitute a strictly broader class than SCMs, thus motivating their use, but that they do not comprise all submodular functions.  Interestingly, some DSFs can be seen as special cases of certain deep neural networks (DNNs), hence the name.  Finally, we provide a method to learn DSFs in a max-margin framework, and offer preliminary results applying this both to synthetic and real-world data instances.
Adaptive optimal training of animal behavior
Authors: Ji Hyun Bak, Jung Yoon Choi, Athena Akrami, Ilana Witten, Jonathan W Pillow
Published in: Advances in Neural Information Processing Systems 29  (NIPS 2016) (Main Conference Track), 2016

Abstract: Neuroscience experiments often require training animals to perform tasks designed to elicit various sensory, cognitive, and motor behaviors. Training typically involves a series of gradual adjustments of stimulus conditions and rewards in order to bring about learning. However, training protocols are usually hand-designed, relying on a combination of intuition, guesswork, and trial-and-error, and often require weeks or months to achieve a desired level of task performance. Here we combine ideas from reinforcement learning and adaptive optimal experimental design to formulate methods for adaptive optimal training of animal behavior. Our work addresses two intriguing problems at once: first, it seeks to infer the learning rules underlying an animal's behavioral changes during training; second, it seeks to exploit these rules to select stimuli that will maximize the rate of learning toward a desired objective.  We develop and test these methods using data collected from rats during training on a two-interval sensory discrimination task.  We show that we can accurately infer the parameters of a policy-gradient-based learning algorithm that describes how the animal's internal model of the task evolves over the course of training.  We then formulate a theory for optimal training, which involves selecting sequences of stimuli that will drive the animal's internal policy toward a desired location in the parameter space. Simulations show that our method can in theory provide a substantial speedup over standard training methods. We feel these results will hold considerable theoretical and practical implications both for researchers in reinforcement learning and for experimentalists seeking to train animals.
Structured Matrix Recovery via the Generalized Dantzig Selector
Authors: Sheng Chen, Arindam Banerjee
Published in: Advances in Neural Information Processing Systems 29  (NIPS 2016) (Main Conference Track), 2016

Abstract: In recent years, structured matrix recovery problems have gained considerable attention for its real world applications, such as recommender systems and computer vision. Much of the existing work has focused on matrices with low-rank structure, and limited progress has been made on matrices with other types of structure. In this paper we present non-asymptotic analysis for estimation of generally structured matrices via the generalized Dantzig selector based on sub-Gaussian measurements. We show that the estimation error can always be succinctly expressed in terms of a few geometric measures such as Gaussian widths of suitable sets associated with the structure of the underlying true matrix. Further, we derive general bounds on these geometric measures for structures characterized by unitarily invariant norms, a large family covering most matrix norms of practical interest. Examples are provided to illustrate the utility of our theoretical development.
Tree-Structured Reinforcement Learning for Sequential Object Localization
Authors: Zequn Jie, Xiaodan Liang, Jiashi Feng, Xiaojie Jin, Wen Lu, Shuicheng Yan
Published in: Advances in Neural Information Processing Systems 29  (NIPS 2016) (Main Conference Track), 2016

Abstract: Existing object proposal algorithms usually search for possible object regions over multiple locations and scales \emph{ separately}, which ignore the interdependency among different objects and deviate from the human perception procedure. To incorporate global interdependency between objects into object localization, we propose an effective Tree-structured Reinforcement Learning (Tree-RL) approach to sequentially search for objects by fully exploiting both the current observation and  historical search paths. The Tree-RL approach learns multiple  searching policies through maximizing the long-term reward that reflects localization accuracies over all the objects. Starting with taking the entire image as a proposal, the Tree-RL approach allows the agent to sequentially discover multiple objects via a  tree-structured traversing scheme.  Allowing multiple near-optimal policies, Tree-RL  offers more diversity in search paths and is able to find multiple objects with a single feed-forward pass. Therefore, Tree-RL can better cover different objects with various scales which is quite appealing in the context of object proposal. Experiments on PASCAL VOC 2007 and 2012 validate the effectiveness of the Tree-RL, which can achieve comparable recalls with current object proposal algorithms via much fewer candidate windows.
Poisson-Gamma dynamical systems
Authors: Aaron Schein, Hanna Wallach, Mingyuan Zhou
Published in: Advances in Neural Information Processing Systems 29  (NIPS 2016) (Main Conference Track), 2016

Abstract: This paper presents a dynamical system based on the Poisson-Gamma construction for sequentially observed multivariate count data.  Inherent to the model is a novel Bayesian nonparametric prior that ties and shrinks parameters in a powerful way. We develop theory about the model's infinite limit and its steady-state.  The model's inductive bias is demonstrated on a variety of real-world datasets where it is shown to learn interpretable structure and have superior predictive performance.
Convergence guarantees for kernel-based quadrature rules in misspecified settings
Authors: Motonobu Kanagawa, Bharath K. Sriperumbudur, Kenji Fukumizu
Published in: Advances in Neural Information Processing Systems 29  (NIPS 2016) (Main Conference Track), 2016

Abstract: Kernel-based quadrature rules are becoming important in machine learning and statistics, as they achieve super-$¥sqrt{n}$ convergence rates in numerical integration, and thus provide alternatives to Monte Carlo integration in challenging settings where integrands are expensive to evaluate or where integrands are high dimensional. These rules are based on the assumption that the integrand has a certain degree of smoothness, which is expressed as that the integrand belongs to a certain reproducing kernel Hilbert space (RKHS). However, this assumption can be violated in practice (e.g., when the integrand is a black box function), and no general theory has been established for the convergence of kernel quadratures in such misspecified settings. Our contribution is in proving that kernel quadratures can be consistent even when the integrand does not belong to the assumed RKHS, i.e.,  when the integrand is less smooth than assumed. Specifically, we derive convergence rates that depend on the (unknown) lesser smoothness of the integrand, where the degree of smoothness is expressed via powers of RKHSs or via Sobolev spaces.
Maximization of Approximately Submodular Functions
Authors: Thibaut Horel, Yaron Singer
Published in: Advances in Neural Information Processing Systems 29  (NIPS 2016) (Main Conference Track), 2016

Abstract: We study the problem of maximizing a function that is approximately submodular under a cardinality constraint. Approximate submodularity implicitly appears in a wide range of applications as in many cases errors in evaluation of a submodular function break submodularity. Say that $F$ is $\eps$-approximately submodular if there exists a submodular function $f$ such that $(1-\eps)f(S) \leq F(S)\leq (1+\eps)f(S)$ for all subsets $S$. We are interested in characterizing the query-complexity of maximizing $F$ subject to a cardinality constraint $k$ as a function of the error level $\eps > 0$.  We provide both lower and upper bounds: for $\eps > n^{-1/2}$ we show an exponential query-complexity lower bound.  In contrast, when $\eps < {1}/{k}$ or under a stronger bounded curvature assumption, we give constant approximation algorithms.
Causal meets Submodular: Subset Selection with Directed Information
Authors: Yuxun Zhou, Costas J Spanos
Published in: Advances in Neural Information Processing Systems 29  (NIPS 2016) (Main Conference Track), 2016

Abstract: We study causal subset selection with Directed Information as the measure of prediction causality. Two typical tasks, causal sensor placement and covariate selection, are correspondingly formulated into cardinality constrained directed information maximizations. To attack the NP-hard problems, we show that the first problem is submodular while not necessarily monotonic. And the second one is ``nearly'' submodular.  To substantiate the idea of approximate submodularity, we introduce a novel quantity, namely submodularity index (SmI), for general set functions. Moreover, we show that based on SmI, greedy algorithm has performance guarantee for the maximization of possibly non-monotonic and non-submodular functions, justifying its usage for a much broader class of problems. We evaluate the theoretical results with several case studies, and also illustrate the application of the subset selection to causal structure learning.
Linear Feature Encoding for Reinforcement Learning
Authors: Zhao Song, Ronald E Parr, Xuejun Liao, Lawrence Carin
Published in: Advances in Neural Information Processing Systems 29  (NIPS 2016) (Main Conference Track), 2016

Abstract: Feature construction is of vital importance in reinforcement learning, as the quality of a value function or policy is largely determined by the corresponding features. The recent successes of deep reinforcement learning (RL) only increase the importance of understanding feature construction. Typical deep RL approaches use a linear output layer, which means that deep RL can be interpreted as a feature construction/encoding network followed by linear value function approximation. This paper develops and evaluates a theory of linear feature encoding. We extend theoretical results on feature quality for linear value function approximation from the uncontrolled case to the controlled case. We then develop a supervised linear feature encoding method that is motivated by insights from linear value function approximation theory, as well as empirical successes from deep RL. The resulting encoder is a surprisingly effective method for linear value function approximation using raw images as inputs.
Mixed Linear Regression with Multiple Components
Authors: Kai Zhong, Prateek Jain, Inderjit S Dhillon
Published in: Advances in Neural Information Processing Systems 29  (NIPS 2016) (Main Conference Track), 2016

Abstract: In this paper, we study the mixed linear regression (MLR) problem, where the goal is to recover multiple underlying linear models from their unlabeled linear measurements. We propose a non-convex objective function which we show is {\em locally strongly convex} in the neighborhood of the ground truth. We use a tensor method for initialization so that the initial models are in the local strong convexity region. We then employ general convex optimization algorithms to minimize the objective function. To the best of our knowledge, our approach provides first exact recovery guarantees for the MLR problem with $K \geq 2$ components. Moreover,  our method has near-optimal computational complexity $\tilde O (Nd)$ as well as near-optimal sample complexity $\tilde O (d)$ for {\em constant} $K$. Furthermore, we show that our non-convex formulation can be extended to solving the {\em subspace clustering} problem as well. In particular, when initialized within a small constant distance to the true subspaces, our method converges to the global optima (and recovers true subspaces) in time {\em linear} in the number of points. Furthermore, our empirical results indicate that even with random initialization, our approach converges to the global optima in linear time, providing speed-up of up to two orders of magnitude.
Unsupervised Learning of Spoken Language with Visual Context
Authors: David Harwath, Antonio Torralba, James Glass
Published in: Advances in Neural Information Processing Systems 29  (NIPS 2016) (Main Conference Track), 2016

Abstract: Humans learn to speak before they can read or write, so why can’t computers do the same? In this paper, we present a deep neural network model capable of rudimentary spoken language acquisition using untranscribed audio training data, whose only supervision comes in the form of contextually relevant visual images. We describe the collection of our data comprised of over 120,000 spoken audio captions for the Places image dataset and evaluate our model on an image search and annotation task. We also provide some visualizations which suggest that our model is learning to recognize meaningful words within the caption spectrograms.
Crowdsourced Clustering: Querying Edges vs Triangles
Authors: Ramya Korlakai Vinayak, Babak Hassibi
Published in: Advances in Neural Information Processing Systems 29  (NIPS 2016) (Main Conference Track), 2016

Abstract: We consider the task of clustering items using answers from non-expert crowd workers. In such cases, the workers are often not able to label the items directly, however, it is reasonable to assume that they can compare items and judge whether they are similar or not. An important question is what queries to make, and we compare two types: random edge queries, where a pair of items is revealed, and random triangles, where a triple is. Since it is far too expensive to query all possible edges and/or triangles, we need to work with partial observations subject to a fixed query budget constraint. When a generative model for the data is available (and we consider a few of these) we determine the cost of a query by its entropy; when such models do not exist we use the average response time per query of the workers as a surrogate for the cost. In addition to theoretical justification, through several simulations and experiments on two real data sets on Amazon Mechanical Turk, we empirically demonstrate that, for a fixed budget, triangle queries uniformly outperform edge queries. Even though, in contrast to edge queries, triangle queries reveal dependent edges, they provide more reliable edges and, for a fixed budget, many more of them. We also provide a sufficient condition on the number of observations, edge densities inside and outside the clusters and the minimum cluster size required for the exact recovery of the true adjacency matrix via triangle queries using a convex optimization-based clustering algorithm.
Learning feed-forward one-shot learners
Authors: Luca Bertinetto, João F. Henriques, Jack Valmadre, Philip Torr, Andrea Vedaldi
Published in: Advances in Neural Information Processing Systems 29  (NIPS 2016) (Main Conference Track), 2016

Abstract: One-shot learning is usually tackled by using generative models or discriminative embeddings. Discriminative methods based on deep learning, which are very effective in other learning scenarios, are ill-suited for one-shot learning as they need large amounts of training data. In this paper, we propose a method to learn the parameters of a deep model in one shot. We construct the learner as a second deep network, called a learnet, which predicts the parameters of a pupil network from a single exemplar. In this manner we obtain an efficient feed-forward one-shot learner, trained end-to-end by minimizing a one-shot classification objective in a learning to learn formulation. In order to make the construction feasible, we propose a number of factorizations of the parameters of the pupil network. We demonstrate encouraging results by learning characters from single exemplars in Omniglot, and by tracking visual objects from a single initial exemplar in the Visual Object Tracking benchmark.
Reshaped Wirtinger Flow for Solving Quadratic System of Equations
Authors: Huishuai Zhang, Yingbin Liang
Published in: Advances in Neural Information Processing Systems 29  (NIPS 2016) (Main Conference Track), 2016

Abstract: We study the problem of recovering a vector $\bx\in \bbR^n$ from its magnitude measurements $y_i=|\langle \ba_i, \bx\rangle|, i=1,..., m$. Our work is along the line of the Wirtinger flow (WF) approach \citet{candes2015phase}, which solves the problem by minimizing a nonconvex loss function via a gradient algorithm and can be shown to converge to a global optimal point under good initialization. In contrast to the smooth loss function used in WF, we adopt a nonsmooth but lower-order loss function, and design a gradient-like algorithm (referred to as reshaped-WF). We show that for random Gaussian measurements, reshaped-WF enjoys geometric convergence to a global optimal point as long as the number $m$ of measurements is at the order of $\cO(n)$, where $n$ is the dimension of the unknown $\bx$. This improves the sample complexity of WF, and achieves  the same sample complexity as truncated-WF \citet{chen2015solving} but without truncation at gradient step. Furthermore, reshaped-WF costs less computationally than WF, and runs faster numerically than both WF and truncated-WF. Bypassing higher-order variables in the loss function and truncations in the gradient loop, analysis of reshaped-WF is simplified.