pwc-archive/papers-with-abstracts huggingface dataset:
Proximal Deep Structured Models
Authors: Shenlong Wang, Sanja Fidler, Raquel Urtasun
Date: 2016-12-01 00:00:00
Proceeding: NeurIPS 2016 12
Tasks: Denoising, Image Denoising, Optical Flow Estimation

Many problems in real-world applications involve predicting continuous-valued random variables that are statistically related.  In this paper, we propose a powerful deep structured model that is able to learn complex non-linear functions which encode the   dependencies between continuous output variables.  We show that  inference in our  model using proximal methods can be efficiently solved as a feed-foward pass of a special  type of  deep recurrent neural network. We demonstrate the  effectiveness of our approach in the tasks of image denoising, depth refinement and optical flow estimation.
Bayesian Optimization with a Finite Budget: An Approximate Dynamic Programming Approach
Authors: Remi Lam, Karen Willcox, David H. Wolpert
Date: 2016-12-01 00:00:00
Proceeding: NeurIPS 2016 12
Tasks: Bayesian Optimization

We consider the problem of optimizing an expensive objective function when a finite budget of total evaluations is prescribed. In that context, the optimal solution strategy for Bayesian optimization can be formulated as a dynamic programming instance. This results in a complex problem with uncountable, dimension-increasing state space and an uncountable control space. We show how to approximate the solution of this dynamic programming problem  using rollout, and propose rollout heuristics specifically designed for the Bayesian optimization setting. We present numerical experiments showing that the resulting algorithm for optimization with a finite budget outperforms several popular Bayesian optimization algorithms.
Dynamic Mode Decomposition with Reproducing Kernels for Koopman Spectral Analysis
Authors: Yoshinobu Kawahara
Date: 2016-12-01 00:00:00
Proceeding: NeurIPS 2016 12

A spectral analysis of the Koopman operator, which is an infinite dimensional linear operator on an observable, gives a (modal) description of the global behavior of a nonlinear dynamical system without any explicit prior knowledge of its governing equations. In this paper, we consider a spectral analysis of the Koopman operator in a reproducing kernel Hilbert space (RKHS). We propose a modal decomposition algorithm to perform the analysis using finite-length data sequences generated from a nonlinear system. The algorithm is in essence reduced to the calculation of a set of orthogonal bases for the Krylov matrix in RKHS and the eigendecomposition of the projection of the Koopman operator onto the subspace spanned by the bases. The algorithm returns a decomposition of the dynamics into a finite number of modes, and thus it can be thought of as a feature extraction procedure for a nonlinear dynamical system. Therefore, we further consider applications in machine learning using extracted features with the presented analysis. We illustrate the method on the applications using synthetic and real-world data.
Efficient and Robust Spiking Neural Circuit for Navigation Inspired by Echolocating Bats
Authors: Pulkit Tandon, Yash H. Malviya, Bipin Rajendran
Date: 2016-12-01 00:00:00
Proceeding: NeurIPS 2016 12
Tasks: Computational Efficiency

We demonstrate a spiking neural circuit for azimuth angle detection  inspired by the  echolocation circuits of the Horseshoe bat  Rhinolophus ferrumequinum and utilize it to devise a  model for  navigation and target tracking, capturing several key aspects of information transmission in biology. Our network,  using only  a simple local-information based sensor implementing the cardioid angular gain function, operates at biological  spike rate of  10 Hz.  The network  tracks large angular targets (60 degrees) within 1 sec with a 10%  RMS error. We study the navigational ability of our model for foraging and target localization tasks in  a forest of obstacles  and show that our network requires less than 200X   spike-triggered decisions, while suffering only a 1% loss in performance compared to a  proportional-integral-derivative controller, in the presence of 50% additive noise. Superior performance can be obtained at  a higher average spike rate of  100 Hz  and  1000 Hz, but even the accelerated networks requires 20X and 10X lesser decisions respectively, demonstrating the superior computational efficiency of bio-inspired information processing systems.
Differential Privacy without Sensitivity
Authors: Kentaro Minami, Hitomi Arai, Issei Sato, Hiroshi Nakagawa
Date: 2016-12-01 00:00:00
Proceeding: NeurIPS 2016 12
Tasks: Sensitivity

The exponential mechanism is a general method to construct a randomized estimator that satisfies $(\varepsilon, 0)$-differential privacy. Recently, Wang et al. showed that the Gibbs posterior, which is a data-dependent probability distribution that contains the Bayesian posterior, is essentially equivalent to the exponential mechanism under certain boundedness conditions on the loss function. While the exponential mechanism provides a way to build an $(\varepsilon, 0)$-differential private algorithm, it requires boundedness of the loss function, which is quite stringent for some learning problems. In this paper, we focus on $(\varepsilon, \delta)$-differential privacy of Gibbs posteriors with convex and Lipschitz loss functions. Our result extends the classical exponential mechanism, allowing the loss functions to have an unbounded sensitivity.
An algorithm for L1 nearest neighbor search via monotonic embedding
Authors: Xinan Wang, Sanjoy Dasgupta
Date: 2016-12-01 00:00:00
Proceeding: NeurIPS 2016 12

Fast algorithms for nearest neighbor (NN) search have in large part focused on L2 distance. Here we develop an approach for L1 distance that begins with an explicit and exact embedding of the points into L2. We show how this embedding can efficiently be combined with random projection methods for L2 NN search, such as locality-sensitive hashing or random projection trees. We rigorously establish the correctness of the methodology and show by experimentation that it is competitive in practice with available alternatives.
Gaussian Process Bandit Optimisation with Multi-fidelity Evaluations
Authors: Kirthevasan Kandasamy, Gautam Dasarathy, Junier B. Oliva, Jeff Schneider, Barnabas Poczos
Date: 2016-12-01 00:00:00
Proceeding: NeurIPS 2016 12

In many scientific and engineering applications, we are tasked with the optimisation of an expensive to evaluate black box function $\func$. Traditional methods for this problem assume just the availability of this single function. However, in many cases, cheap approximations to $\func$ may be obtainable. For example, the expensive real world behaviour of a robot can be approximated by a cheap computer simulation. We can use these approximations to eliminate low function value regions cheaply and use the expensive evaluations of $\func$ in a small but promising region and speedily identify the optimum. We formalise this task as a \emph{multi-fidelity} bandit problem where the target function and its approximations are sampled from a Gaussian process. We develop \mfgpucb, a novel method based on upper confidence bound techniques. In our theoretical analysis we demonstrate that it exhibits precisely the above behaviour, and achieves better regret than strategies which ignore multi-fidelity information. \mfgpucbs outperforms such naive strategies and other multi-fidelity methods  on several synthetic and real experiments.
Fast ε-free Inference of Simulation Models with Bayesian Conditional Density Estimation
Authors: George Papamakarios, Iain Murray
Date: 2016-12-01 00:00:00
Proceeding: NeurIPS 2016 12
Tasks: Density Estimation

Many statistical models can be simulated forwards but have intractable likelihoods. Approximate Bayesian Computation (ABC) methods are used to infer properties of these models from data. Traditionally these methods approximate the posterior over parameters by conditioning on data being inside an ε-ball around the observed data, which is only correct in the limit ε→0. Monte Carlo methods can then draw samples from the approximate posterior to approximate predictions or error bars on parameters. These algorithms critically slow down as ε→0, and in practice draw samples from a broader distribution than the posterior. We propose a new approach to likelihood-free inference based on Bayesian conditional density estimation. Preliminary inferences based on limited simulation data are used to guide later simulations. In some cases, learning an accurate parametric representation of the entire true posterior distribution requires fewer model simulations than Monte Carlo ABC methods need to produce a single sample from an approximate posterior.
Semiparametric Differential Graph Models
Authors: Pan Xu, Quanquan Gu
Date: 2016-12-01 00:00:00
Proceeding: NeurIPS 2016 12
Tasks: parameter estimation

In many cases of network analysis, it is more attractive to study how a network varies under  different conditions than an individual static network. We propose a novel graphical model, namely Latent Differential Graph Model, where the networks under two different conditions are represented by two semiparametric elliptical distributions respectively, and the variation of these two networks (i.e., differential graph) is characterized by the difference between their latent precision matrices. We propose an estimator for the differential graph based on quasi likelihood maximization with nonconvex regularization. We show that our estimator attains a faster statistical rate in parameter estimation than the state-of-the-art methods, and enjoys oracle property under mild conditions. Thorough experiments on both synthetic and real world data support our theory.
Generalized Correspondence-LDA Models (GC-LDA) for Identifying Functional Regions in the Brain
Authors: Timothy Rubin, Oluwasanmi O. Koyejo, Michael N. Jones, Tal Yarkoni
Date: 2016-12-01 00:00:00
Proceeding: NeurIPS 2016 12

This paper presents Generalized Correspondence-LDA (GC-LDA), a generalization of the Correspondence-LDA model that allows for variable spatial representations to be associated with topics, and increased flexibility in terms of the strength of the correspondence between data types induced by the model. We present three variants of GC-LDA, each of which associates topics with a different spatial representation, and apply them to a corpus of neuroimaging data. In the context of this dataset, each topic corresponds to a functional brain region, where the region's spatial extent is captured by a probability distribution over neural activity, and the region's cognitive function is captured by a probability distribution over linguistic terms. We illustrate the qualitative improvements offered by GC-LDA in terms of the types of topics extracted with alternative spatial representations, as well as the model's ability to incorporate a-priori knowledge from the neuroimaging literature. We furthermore demonstrate that the novel features of GC-LDA improve predictions for missing data.
Multi-view Anomaly Detection via Robust Probabilistic Latent Variable Models
Authors: Tomoharu Iwata, Makoto Yamada
Date: 2016-12-01 00:00:00
Proceeding: NeurIPS 2016 12
Tasks: Anomaly Detection, Bayesian Inference

We propose probabilistic latent variable models for multi-view anomaly detection, which is the task of finding instances that have inconsistent views given multi-view data. With the proposed model, all views of a non-anomalous instance are assumed to be generated from a single latent vector. On the other hand, an anomalous instance is assumed to have multiple latent vectors, and its different views are generated from different latent vectors. By inferring the number of latent vectors used for each instance with Dirichlet process priors, we obtain multi-view anomaly scores. The proposed model can be seen as a robust extension of probabilistic canonical correlation analysis for noisy multi-view data. We present Bayesian inference procedures for the proposed model based on a stochastic EM algorithm. The effectiveness of the proposed model is demonstrated in terms of performance when detecting multi-view anomalies.
Proximal Stochastic Methods for Nonsmooth Nonconvex Finite-Sum Optimization
Authors: Sashank J. Reddi, Suvrit Sra, Barnabas Poczos, Alexander J. Smola
Date: 2016-12-01 00:00:00
Proceeding: NeurIPS 2016 12

We analyze stochastic algorithms for optimizing nonconvex, nonsmooth finite-sum problems, where the nonsmooth part is convex.  Surprisingly, unlike the smooth case, our knowledge of this fundamental problem is very limited. For example, it is not known whether the proximal stochastic gradient method with constant minibatch converges to a stationary point. To tackle this issue, we develop fast stochastic algorithms that provably converge to a stationary point for constant minibatches. Furthermore, using a variant of these algorithms, we obtain provably faster convergence than batch proximal gradient descent. Our results are based on the recent variance reduction techniques for convex optimization but with a novel analysis for handling nonconvex and nonsmooth functions. We also prove global linear convergence rate for an interesting subclass of nonsmooth nonconvex functions, which subsumes several recent works.
Variance Reduction in Stochastic Gradient Langevin Dynamics
Authors: Kumar Avinava Dubey, Sashank J. Reddi, Sinead A. Williamson, Barnabas Poczos, Alexander J. Smola, Eric P. Xing
Date: 2016-12-01 00:00:00
Proceeding: NeurIPS 2016 12
Tasks: BIG-bench Machine Learning

Stochastic gradient-based Monte Carlo methods such as stochastic gradient Langevin dynamics are useful tools for posterior inference on large scale datasets in many machine learning applications. These methods scale to large datasets by using noisy gradients calculated using a mini-batch or subset of the dataset. However, the high variance inherent in these noisy gradients degrades performance and leads to slower mixing. In this paper, we present techniques for reducing variance in stochastic gradient Langevin dynamics, yielding novel  stochastic Monte Carlo methods that improve performance by reducing the variance in the stochastic gradient. We show that our proposed method has better theoretical guarantees on convergence rate than stochastic Langevin dynamics. This is complemented by impressive empirical results obtained on  a variety of real world datasets, and on four different machine learning tasks (regression, classification, independent component analysis and mixture modeling). These theoretical and empirical contributions combine to make a compelling case for using variance reduction in stochastic Monte Carlo methods.
Homotopy Smoothing for Non-Smooth Problems with Lower Complexity than O(1/\epsilon)
Authors: Yi Xu, Yan Yan, Qihang Lin, Tianbao Yang
Date: 2016-12-01 00:00:00
Proceeding: NeurIPS 2016 12

In this paper, we develop a novel {\bf ho}moto{\bf p}y  {\bf s}moothing (HOPS) algorithm for solving a family of non-smooth problems that is composed of a non-smooth term with an explicit max-structure and  a smooth term or  a simple non-smooth term whose proximal mapping is easy to compute. The best known iteration complexity for solving such non-smooth optimization problems is $O(1/\epsilon)$ without any assumption on the strong convexity. In this work, we will show that the proposed  HOPS achieved a lower iteration complexity of $\tilde O(1/\epsilon^{1-\theta})$ with $\theta\in(0,1]$ capturing the local sharpness of the objective function around the optimal solutions. To the best of our knowledge, this is the lowest iteration complexity achieved so far for the considered non-smooth optimization problems without strong convexity assumption.  The HOPS algorithm employs Nesterov's smoothing technique and Nesterov's accelerated gradient method and runs in stages, which gradually decreases the smoothing parameter in a stage-wise manner until it yields a sufficiently good approximation of the original function. We show that HOPS enjoys a linear convergence for many well-known non-smooth problems (e.g., empirical risk minimization with a piece-wise linear loss function and $\ell_1$ norm regularizer, finding a point in a polyhedron, cone programming, etc). Experimental results verify the effectiveness of HOPS in comparison with Nesterov's smoothing algorithm and the primal-dual style of first-order methods.
A state-space model of cross-region dynamic connectivity in MEG/EEG
Authors: Ying Yang, Elissa Aminoff, Michael Tarr, Kass E. Robert
Date: 2016-12-01 00:00:00
Proceeding: NeurIPS 2016 12
Tasks: EEG, Electroencephalogram (EEG)

Cross-region dynamic connectivity, which describes spatio-temporal dependence of neural activity among multiple brain regions of interest (ROIs), can provide important information for understanding cognition. For estimating such connectivity, magnetoencephalography (MEG) and electroencephalography (EEG) are well-suited tools because of their millisecond temporal resolution. However, localizing source activity in the brain requires solving an under-determined linear problem. In typical two-step approaches, researchers first solve the linear problem with general priors assuming independence across ROIs, and secondly quantify cross-region connectivity. In this work, we propose a one-step state-space model to improve estimation of dynamic connectivity. The model treats the mean activity in individual ROIs as the state variable, and describes non-stationary dynamic dependence across ROIs using time-varying auto-regression. Compared with a two-step method, which first obtains the commonly used minimum-norm estimates of source activity, and then fits the auto-regressive model, our state-space model yielded smaller estimation errors on simulated data where the model assumptions held. When applied on empirical MEG data from one participant in a scene-processing experiment, our state-space model also demonstrated intriguing preliminary results, indicating leading and lagged linear dependence between the early visual cortex and a higher-level scene-sensitive region, which could reflect feed-forward and feedback information flow within the visual cortex during scene processing.
What Makes Objects Similar: A Unified Multi-Metric Learning Approach
Authors: Han-Jia Ye, De-Chuan Zhan, Xue-Min Si, Yuan Jiang, Zhi-Hua Zhou
Date: 2016-12-01 00:00:00
Proceeding: NeurIPS 2016 12
Tasks: Metric Learning

Linkages are essentially determined by similarity measures that may be derived from multiple perspectives. For example, spatial linkages are usually generated based on localities of heterogeneous data, whereas semantic linkages can come from various properties, such as different physical meanings behind social relations. Many existing metric learning models focus on spatial linkages, but leave the rich semantic factors unconsidered. Similarities based on these models are usually overdetermined on linkages. We propose a Unified Multi-Metric Learning (UM2L) framework to exploit multiple types of metrics. In UM2L, a type of combination operator is introduced for distance characterization from multiple perspectives, and thus can introduce flexibilities for representing and utilizing both spatial and semantic linkages. Besides, we propose a uniform solver for UM2L which is guaranteed to converge. Extensive experiments on diverse applications exhibit the superior classification performance and comprehensibility of UM2L. Visualization results also validate its ability on physical meanings discovery.
Dueling Bandits: Beyond Condorcet Winners to General Tournament Solutions
Authors: Siddartha Y. Ramamohan, Arun Rajkumar, Shivani Agarwal
Date: 2016-12-01 00:00:00
Proceeding: NeurIPS 2016 12

Recent work on deriving $O(\log T)$ anytime regret bounds for stochastic dueling bandit problems has considered mostly Condorcet winners, which do not always exist, and more recently, winners defined by the Copeland set, which do always exist. In this work, we consider a broad notion of winners defined by tournament solutions in social choice theory, which include the Copeland set as a special case but also include several other notions of winners such as the top cycle, uncovered set, and Banks set, and which, like the Copeland set, always exist. We develop a family of UCB-style dueling bandit algorithms for such general tournament solutions, and show $O(\log T)$ anytime regret bounds for them. Experiments confirm the ability of our algorithms to achieve low regret relative to the target winning set of interest.
Convex Two-Layer Modeling with Latent Structure
Authors: Vignesh Ganapathiraman, Xinhua Zhang, Yao-Liang Yu, Junfeng Wen
Date: 2016-12-01 00:00:00
Proceeding: NeurIPS 2016 12
Tasks: Graph Matching, Vocal Bursts Valence Prediction

Unsupervised learning of structured predictors has been a long standing pursuit in machine learning.  Recently a conditional random field auto-encoder has been proposed in a two-layer setting, allowing latent structured representation to be automatically inferred.  Aside from being nonconvex, it also requires the demanding inference of normalization.  In this paper, we develop a convex relaxation of two-layer conditional model which captures latent structure and estimates model parameters, jointly and optimally.  We further expand its applicability by resorting to a weaker form of inference---maximum a-posteriori.  The flexibility of the model is demonstrated on two structures based on total unimodularity---graph matching and linear chain.  Experimental results confirm the promise of the method.
Sampling for Bayesian Program Learning
Authors: Kevin Ellis, Armando Solar-Lezama, Josh Tenenbaum
Date: 2016-12-01 00:00:00
Proceeding: NeurIPS 2016 12
Tasks: Program Synthesis

Towards learning programs from data, we introduce the problem of   sampling programs from posterior distributions conditioned on that   data. Within this setting, we propose an algorithm that uses a   symbolic solver to efficiently sample programs.  The proposal   combines constraint-based program synthesis with sampling via random   parity constraints.  We give theoretical guarantees on how well the   samples approximate the true posterior, and have empirical results   showing the algorithm is efficient in practice, evaluating our   approach on 22 program learning problems in the domains of text   editing and computer-aided programming.
Learning Kernels with Random Features
Authors: Aman Sinha, John C. Duchi
Date: 2016-12-01 00:00:00
Proceeding: NeurIPS 2016 12
Tasks: Generalization Bounds

Randomized features provide a computationally efficient way to approximate kernel machines in machine learning tasks. However, such methods require a user-defined kernel as input. We extend the randomized-feature approach to the task of learning a kernel (via its associated random features). Specifically, we present an efficient optimization problem that learns a kernel in a supervised manner. We prove the consistency of the estimated kernel as well as generalization bounds for the class of estimators induced by the optimized kernel, and we experimentally evaluate our technique on several datasets. Our approach is efficient and highly scalable, and we attain competitive results with a fraction of the training cost of other techniques.