pwc-archive/papers-with-abstracts huggingface dataset:
Contour location via entropy reduction leveraging multiple information sources
Authors: Alexandre Marques, Remi Lam, Karen Willcox
Date: 2018-12-01 00:00:00
Proceeding: NeurIPS 2018 12
Tasks: General Classification

We introduce an algorithm to locate contours of functions that are expensive to evaluate. The problem of locating contours arises in many applications, including classification, constrained optimization, and  performance analysis of mechanical and dynamical systems (reliability, probability of failure, stability, etc.). Our algorithm locates contours using information from multiple sources, which are available in the form of relatively inexpensive, biased, and possibly noisy
 approximations to the original function. Considering multiple information sources can lead to significant cost savings. We also introduce the concept of contour entropy, a formal measure of uncertainty about the location of the zero contour of a function approximated by a statistical surrogate model. Our algorithm locates contours efficiently by maximizing the reduction of contour entropy per unit cost.
Multiple-Step Greedy Policies in Approximate and Online Reinforcement Learning
Authors: Yonathan Efroni, Gal Dalal, Bruno Scherrer, Shie Mannor
Date: 2018-12-01 00:00:00
Proceeding: NeurIPS 2018 12
Tasks: Model Predictive Control, reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

Multiple-step lookahead policies have demonstrated high empirical competence in Reinforcement Learning, via the use of Monte Carlo Tree Search or Model Predictive Control. In a recent work (Efroni et al., 2018), multiple-step greedy policies and their use in vanilla Policy Iteration algorithms were proposed and analyzed. In this work, we study multiple-step greedy algorithms in more practical setups. We begin by highlighting a counter-intuitive difficulty, arising with soft-policy updates: even in the absence of approximations, and contrary to the 1-step-greedy case, monotonic policy improvement is not guaranteed unless the update stepsize is sufficiently large. Taking particular care about this difficulty, we formulate and analyze online and approximate algorithms that use such a multi-step greedy operator.
Horizon-Independent Minimax Linear Regression
Authors: Alan Malek, Peter L. Bartlett
Date: 2018-12-01 00:00:00
Proceeding: NeurIPS 2018 12
Tasks: regression

We consider online linear regression: at each round, an adversary reveals a covariate vector, the learner predicts a real value, the adversary reveals a label, and the learner suffers the squared prediction error. The aim is to minimize the difference between the cumulative loss and that of the linear predictor that is best in hindsight. Previous work demonstrated that the minimax optimal strategy is easy to compute recursively from the end of the game; this requires the entire sequence of covariate vectors in advance. We show that, once provided with a measure of the scale of the problem, we can invert the recursion and play the minimax strategy without knowing the future covariates. Further, we show that this forward recursion remains optimal even against adaptively chosen labels and covariates, provided that the adversary adheres to a set of constraints that prevent misrepresentation of the scale of the problem. This strategy is horizon-independent in that the regret and minimax strategies depend on the size of the constraint set and not on the time-horizon, and hence it incurs no more regret than the optimal strategy that knows in advance the number of rounds of the game. We also provide an interpretation of the minimax algorithm as a follow-the-regularized-leader strategy with a data-dependent regularizer and obtain an explicit expression for the minimax regret.
Learning a latent manifold of odor representations from neural responses in piriform cortex
Authors: Anqi Wu, Stan Pashkovski, Sandeep R. Datta, Jonathan W. Pillow
Date: 2018-12-01 00:00:00
Proceeding: NeurIPS 2018 12

A major difficulty in studying the neural mechanisms underlying olfactory perception is the lack of obvious structure in the relationship between odorants and the neural activity patterns they elicit. Here we use odor-evoked responses in piriform cortex to identify a latent manifold specifying latent distance relationships between olfactory stimuli. Our approach is based on the Gaussian process latent variable model, and seeks to map odorants to points in a low-dimensional embedding space, where distances between points in the embedding space relate to the similarity of population responses they elicit. The model is specified by an explicit continuous mapping from a latent embedding space to the space of high-dimensional neural population firing rates via nonlinear tuning curves, each parametrized by a Gaussian process. Population responses are then generated by the addition of correlated, odor-dependent Gaussian noise. We fit this model to large-scale calcium fluorescence imaging measurements of population activity in layers 2 and 3 of mouse piriform cortex following the presentation of a diverse set of odorants. The model identifies a low-dimensional embedding of each odor, and a smooth tuning curve over the latent embedding space that accurately captures each neuron's response to different odorants. The model captures both signal and noise correlations across more than 500 neurons. We validate the model using a cross-validation analysis known as co-smoothing to show that the model can accurately predict the responses of a population of held-out neurons to test odorants.
The Spectrum of the Fisher Information Matrix of a Single-Hidden-Layer Neural Network
Authors: Jeffrey Pennington, Pratik Worah
Date: 2018-12-01 00:00:00
Proceeding: NeurIPS 2018 12

An important factor contributing to the success of deep learning has been the remarkable ability to optimize large neural networks using simple first-order optimization algorithms like stochastic gradient descent. While the efficiency of such methods depends crucially on the local curvature of the loss surface, very little is actually known about how this geometry depends on network architecture and hyperparameters. In this work, we extend a recently-developed framework for studying spectra of nonlinear random matrices to characterize an important measure of curvature, namely the eigenvalues of the Fisher information matrix. We focus on a single-hidden-layer neural network with Gaussian data and weights and provide an exact expression for the spectrum in the limit of infinite width. We find that linear networks suffer worse conditioning than nonlinear networks and that nonlinear networks are generically non-degenerate. We also predict and demonstrate empirically that by adjusting the nonlinearity, the spectrum can be tuned so as to improve the efficiency of first-order optimization methods.
Algorithmic Assurance: An Active Approach to Algorithmic Testing using Bayesian Optimisation
Authors: Shivapratap Gopakumar, Sunil Gupta, Santu Rana, Vu Nguyen, Svetha Venkatesh
Date: 2018-12-01 00:00:00
Proceeding: NeurIPS 2018 12
Tasks: Active Learning, Bayesian Optimisation

We introduce algorithmic assurance, the problem of testing whether
machine learning algorithms are conforming to their intended design
goal. We address this problem by proposing an efficient framework
for algorithmic testing. To provide assurance, we need to efficiently
discover scenarios where an algorithm decision deviates maximally
from its intended gold standard. We mathematically formulate this
task as an optimisation problem of an expensive, black-box function.
We use an active learning approach based on Bayesian optimisation
to solve this optimisation problem. We extend this framework to algorithms
with vector-valued outputs by making appropriate modification in Bayesian
optimisation via the EXP3 algorithm. We theoretically analyse our
methods for convergence. Using two real-world applications, we demonstrate
the efficiency of our methods. The significance of our problem formulation
and initial solutions is that it will serve as the foundation in assuring
humans about machines making complex decisions.
Learning Others' Intentional Models in Multi-Agent Settings Using Interactive POMDPs
Authors: Yanlin Han, Piotr Gmytrasiewicz
Date: 2018-12-01 00:00:00
Proceeding: NeurIPS 2018 12
Tasks: Bayesian Inference

Interactive partially observable Markov decision processes (I-POMDPs) provide a principled framework for planning and acting in a partially observable, stochastic and multi-agent environment. It extends POMDPs to multi-agent settings by including models of other agents in the state space and forming a hierarchical belief structure. In order to predict other agents' actions using I-POMDPs, we propose an approach that effectively uses Bayesian inference and sequential Monte Carlo sampling to learn others' intentional models which ascribe to them beliefs, preferences and rationality in action selection. Empirical results show that our algorithm accurately learns models of the other agent and has superior performance than methods that use subintentional models. Our approach serves as a generalized Bayesian learning algorithm that learns other agents' beliefs, strategy levels, and transition, observation and reward functions. It also effectively mitigates the belief space complexity due to the nested belief hierarchy.
Contextual Pricing for Lipschitz Buyers
Authors: Jieming Mao, Renato Leme, Jon Schneider
Date: 2018-12-01 00:00:00
Proceeding: NeurIPS 2018 12

We investigate the problem of learning a Lipschitz function from binary
  feedback. In this problem, a learner is trying to learn a Lipschitz function
  $f:[0,1]^d \rightarrow [0,1]$ over the course of $T$ rounds. On round $t$, an
  adversary provides the learner with an input $x_t$, the learner submits a
  guess $y_t$ for $f(x_t)$, and learns whether $y_t > f(x_t)$ or $y_t \leq
  f(x_t)$. The learner's goal is to minimize their total loss $\sum_t\ell(f(x_t),
  y_t)$ (for some loss function $\ell$). The problem is motivated by \textit{contextual dynamic pricing},
  where a firm must sell a stream of differentiated products to a collection of
  buyers with non-linear valuations for the items and observes only whether the
  item was sold or not at the posted price.

  For the symmetric loss $\ell(f(x_t), y_t) = \vert f(x_t) - y_t \vert$,  we
  provide an algorithm for this problem achieving total loss $O(\log T)$
  when $d=1$ and $O(T^{(d-1)/d})$ when $d>1$, and show that both bounds are
  tight (up to a factor of $\sqrt{\log T}$). For the pricing loss function
  $\ell(f(x_t), y_t) = f(x_t) - y_t {\bf 1}\{y_t \leq f(x_t)\}$ we show a regret
  bound of $O(T^{d/(d+1)})$ and show that this bound is tight. We present
  improved bounds in the special case of a population of linear buyers.
Bandit Learning in Concave N-Person Games
Authors: Mario Bravo, David Leslie, Panayotis Mertikopoulos
Date: 2018-12-01 00:00:00
Proceeding: NeurIPS 2018 12
Tasks: Stochastic Optimization

This paper examines the long-run behavior of learning with bandit feedback in non-cooperative concave games. The bandit framework accounts for extremely low-information environments where the agents may not even know they are playing a game; as such, the agents’ most sensible choice in this setting would be to employ a no-regret learning algorithm. In general, this does not mean that the players' behavior stabilizes in the long run: no-regret learning may lead to cycles, even with perfect gradient information. However, if a standard monotonicity condition is satisfied, our analysis shows that no-regret learning based on mirror descent with bandit feedback converges to Nash equilibrium with probability 1. We also derive an upper bound for the convergence rate of the process that nearly matches the best attainable rate for single-agent bandit stochastic optimization.
Efficient inference for time-varying behavior during learning
Authors: Nicholas G. Roy, Ji Hyun Bak, Athena Akrami, Carlos Brody, Jonathan W. Pillow
Date: 2018-12-01 00:00:00
Proceeding: NeurIPS 2018 12

The process of learning new behaviors over time is a problem of great interest in both neuroscience and artificial intelligence. However, most standard analyses of animal training data either treat behavior as fixed or track only coarse performance statistics (e.g., accuracy, bias), providing limited insight into the evolution of the policies governing behavior. To overcome these limitations, we propose a dynamic psychophysical model that efficiently tracks trial-to-trial changes in behavior over the course of training. Our model consists of a dynamic logistic regression model, parametrized by a set of time-varying weights that express dependence on sensory stimuli as well as task-irrelevant covariates, such as stimulus, choice, and answer history. Our implementation scales to large behavioral datasets, allowing us to infer 500K parameters (e.g. 10 weights over 50K trials) in minutes on a desktop computer. We optimize hyperparameters governing how rapidly each weight evolves over time using the decoupled Laplace approximation, an efficient method for maximizing marginal likelihood in non-conjugate models. To illustrate performance, we apply our method to psychophysical data from both rats and human subjects learning a delayed sensory discrimination task. The model successfully tracks the psychophysical weights of rats over the course of training, capturing day-to-day and trial-to-trial fluctuations that underlie changes in performance, choice bias, and dependencies on task history. Finally, we investigate why rats frequently make mistakes on easy trials, and suggest that apparent lapses can be explained by sub-optimal weighting of known task covariates.
Computing Kantorovich-Wasserstein Distances on d-dimensional histograms using (d+1)-partite graphs
Authors: Gennaro Auricchio, Federico Bassetti, Stefano Gualandi, Marco Veneroni
Date: 2018-12-01 00:00:00
Proceeding: NeurIPS 2018 12

This paper presents a novel method to compute the exact Kantorovich-Wasserstein distance between a pair of $d$-dimensional histograms having $n$ bins each. We prove that this problem is equivalent to an uncapacitated minimum cost flow problem on a $(d+1)$-partite graph with $(d+1)n$ nodes and $dn^{\frac{d+1}{d}}$ arcs, whenever the cost is separable along the principal $d$-dimensional directions. We show numerically the benefits of our approach by computing the Kantorovich-Wasserstein distance of order 2 among two sets of instances: gray scale images and $d$-dimensional biomedical histograms. On these types of instances, our approach is competitive with state-of-the-art optimal transport algorithms.
Neural Interaction Transparency (NIT): Disentangling Learned Interactions for Improved Interpretability
Authors: Michael Tsang, Hanpeng Liu, Sanjay Purushotham, Pavankumar Murali, Yan Liu
Date: 2018-12-01 00:00:00
Proceeding: NeurIPS 2018 12
Tasks: Additive models, Representation Learning

Neural networks are known to model statistical interactions, but they entangle the interactions at intermediate hidden layers for shared representation learning. We propose a framework, Neural Interaction Transparency (NIT), that disentangles the shared learning across different interactions to obtain their intrinsic lower-order and interpretable structure. This is done through a novel regularizer that directly penalizes interaction order. We show that disentangling interactions reduces a feedforward neural network to a generalized additive model with interactions, which can lead to transparent models that perform comparably to the state-of-the-art models. NIT is also flexible and efficient; it can learn generalized additive models with maximum $K$-order interactions by training only $O(1)$ models.
Gamma-Poisson Dynamic Matrix Factorization Embedded with Metadata Influence
Authors: Trong Dinh Thac Do, Longbing Cao
Date: 2018-12-01 00:00:00
Proceeding: NeurIPS 2018 12
Tasks: Variational Inference

A conjugate Gamma-Poisson model for Dynamic Matrix Factorization incorporated with metadata influence (mGDMF for short) is proposed to effectively and efficiently model massive, sparse and dynamic data in recommendations. Modeling recommendation problems with a massive number of ratings and very sparse or even no ratings on some users/items in a dynamic setting is very demanding and poses critical challenges to well-studied matrix factorization models due to the large-scale, sparse and dynamic nature of the data. Our proposed mGDMF tackles these challenges by introducing three strategies: (1) constructing a stable Gamma-Markov chain model that smoothly drifts over time by combining both static and dynamic latent features of data; (2) incorporating the user/item metadata into the model to tackle sparse ratings; and (3) undertaking stochastic variational inference to  efficiently handle massive data. mGDMF is conjugate, dynamic and scalable. Experiments show that mGDMF significantly (both effectively and efficiently) outperforms the state-of-the-art static and dynamic models on large, sparse and dynamic data.
Diverse Ensemble Evolution: Curriculum Data-Model Marriage
Authors: Tianyi Zhou, Shengjie Wang, Jeff A. Bilmes
Date: 2018-12-01 00:00:00
Proceeding: NeurIPS 2018 12
Tasks: Diversity, model

We study a new method (``Diverse Ensemble Evolution (DivE$^2$)'') to train an ensemble of machine learning models that assigns data to models at each training epoch based on each model's current expertise and an intra- and inter-model diversity reward.  DivE$^2$ schedules, over the course of training epochs, the relative importance of these characteristics; it starts by selecting easy samples for each model, and then gradually adjusts towards the models having specialized and complementary expertise on subsets of the training data, thereby encouraging high accuracy of the ensemble.  We utilize an intra-model diversity term on data assigned to each model, and an inter-model diversity term on data assigned to pairs of models, to penalize both within-model and cross-model redundancy.  We formulate the data-model marriage problem as a generalized bipartite matching, represented as submodular maximization subject to two matroid constraints. DivE$^2$ solves a sequence of continuous-combinatorial optimizations with slowly varying objectives and constraints. The combinatorial part handles the data-model marriage while the continuous part updates model parameters based on the assignments. In experiments, DivE$^2$ outperforms other ensemble training methods under a variety of model aggregation techniques, while also maintaining competitive efficiency.
Exact natural gradient in deep linear networks and its application to the nonlinear case
Authors: Alberto Bernacchia, Mate Lengyel, Guillaume Hennequin
Date: 2018-12-01 00:00:00
Proceeding: NeurIPS 2018 12

Stochastic gradient descent (SGD) remains the method of choice for deep learning, despite the limitations arising for ill-behaved objective functions. In cases where it could be estimated, the natural gradient has proven very effective at mitigating the catastrophic effects of pathological curvature in the objective function, but little is known theoretically about its convergence properties, and it has yet to find a practical implementation that would scale to very deep and large networks. Here, we derive an exact expression for the natural gradient in deep linear networks, which exhibit pathological curvature similar to the nonlinear case. We provide for the first time an analytical solution for its convergence rate, showing that the loss decreases exponentially to the global minimum in parameter space. Our expression for the natural gradient is surprisingly simple, computationally tractable, and explains why some approximations proposed previously work well in practice. This opens new avenues for approximating the natural gradient in the nonlinear case, and we show in preliminary experiments that our online natural gradient descent outperforms SGD on MNIST autoencoding while sharing its computational simplicity.
Memory Replay GANs: Learning to Generate New Categories without Forgetting
Authors: Chenshen Wu, Luis Herranz, Xialei Liu, Yaxing Wang, Joost Van de Weijer, Bogdan Raducanu
Date: 2018-12-01 00:00:00
Proceeding: NeurIPS 2018 12

Previous works on sequential learning address the problem of forgetting in discriminative models. In this paper we consider the case of generative models. In particular, we investigate generative adversarial networks (GANs) in the task of learning new categories in a sequential fashion. We first show that sequential fine tuning renders the network unable to properly generate images from previous categories (i.e. forgetting). Addressing this problem, we propose Memory Replay GANs (MeRGANs), a conditional GAN framework that integrates a memory replay generator. We study two methods to prevent forgetting by leveraging these replays, namely joint training with replay and replay alignment. Qualitative and quantitative experimental results in MNIST, SVHN and LSUN datasets show that our memory replay approach can generate competitive images while significantly mitigating the forgetting of previous categories.
Automating Bayesian optimization with Bayesian optimization
Authors: Gustavo Malkomes, Roman Garnett
Date: 2018-12-01 00:00:00
Proceeding: NeurIPS 2018 12
Tasks: Bayesian Optimization, Decision Making, global-optimization

Bayesian optimization is a powerful tool for global optimization of expensive functions. One of its key components is the underlying probabilistic model used for the objective function f. In practice, however, it is often unclear how one should appropriately choose a model, especially when gathering data is expensive. In this work, we introduce a novel automated Bayesian optimization approach that dynamically selects promising models for explaining the observed data using Bayesian Optimization in the model space. Crucially, we account for the uncertainty in the choice of model; our method is capable of using multiple models to represent its current belief about f and subsequently using this information for decision making. We argue, and demonstrate empirically, that our approach automatically finds suitable models for the objective function, which ultimately results in more-efficient optimization.
Stacked Semantics-Guided Attention Model for Fine-Grained Zero-Shot Learning
Authors: Yunlong Yu, Zhong Ji, Yanwei Fu, Jichang Guo, Yanwei Pang, Zhongfei (Mark) Zhang
Date: 2018-12-01 00:00:00
Proceeding: NeurIPS 2018 12
Tasks: General Classification, Multi-class Classification, Retrieval, zero-shot-classification, Zero-Shot Learning

Zero-Shot Learning (ZSL) is generally achieved via aligning the semantic relationships between the visual features and the corresponding class semantic descriptions. However, using the global features to represent fine-grained images may lead to sub-optimal results since they neglect the discriminative differences of local regions. Besides, different regions contain distinct discriminative information. The important regions should contribute more to the prediction. To this end, we propose a novel stacked semantics-guided attention (S2GA) model to obtain semantic relevant features by using individual class semantic features to progressively guide the visual features to generate an attention map for weighting the importance of different local regions. Feeding both the integrated visual features and the class semantic features into a multi-class classification architecture, the proposed framework can be trained end-to-end. Extensive experimental results on CUB and NABird datasets show that the proposed approach has a consistent improvement on both fine-grained zero-shot classification and retrieval tasks.