pwc-archive/papers-with-abstracts huggingface dataset:
Prior-Free Dynamic Auctions with Low Regret Buyers
Authors: Yuan Deng, Jon Schneider, Balasubramanian Sivan
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12

We study the problem of how to repeatedly sell to a buyer running a no-regret, mean-based algorithm. Previous work [Braverman et al., 2018] shows that it is possible to design effective mechanisms in such a setting that extract almost all of the economic surplus, but these mechanisms require the buyer's values each round to be drawn independently and identically from a fixed distribution. In this work, we do away with this assumption and consider the prior-free setting where the buyer's value each round is chosen adversarially (possibly adaptively). 

We show that even in this prior-free setting, it is possible to extract a $(1-\varepsilon)$-approximation of the full economic surplus for any $\varepsilon > 0$. The number of options offered to a buyer in any round scales independently of the number of rounds $T$ and polynomially in $\varepsilon$. We show that this is optimal up to a polynomial factor; any mechanism achieving this approximation factor, even when values are drawn stochastically, requires at least $\Omega(1/\varepsilon)$ options.

Finally, we examine what is possible when we constrain our mechanism to a natural auction format where overbidding is dominated. Braverman et al. [2018] show that even when values are drawn from a known stochastic distribution supported on $[1/H, 1]$, it is impossible in general to extract more than $O(\log\log H / \log H)$ of the economic surplus. We show how to achieve the same approximation factor in the prior-independent setting (where the distribution is unknown to the seller), and an approximation factor of $O(1 / \log H)$ in the prior-free setting (where the values are chosen adversarially).
Spectral Modification of Graphs for Improved Spectral Clustering
Authors: Ioannis Koutis, Huong Le
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12
Tasks: Clustering, graph partitioning

Spectral clustering algorithms provide approximate solutions to  hard optimization problems that formulate graph partitioning  in terms of the graph conductance. It is well understood that  the quality of these approximate solutions is negatively affected  by a possibly significant gap between the conductance and the second eigenvalue  of the graph.  In this paper we show that for \textbf{any} graph $G$,  there exists a `spectral maximizer' graph $H$ which is cut-similar to $G$,    but has eigenvalues that are near the theoretical limit  implied by the cut structure of $G$. Applying then spectral clustering  on $H$ has the potential to produce improved  cuts that also exist in $G$ due to  the cut similarity.   This leads to the second contribution of this  work: we describe a practical spectral modification algorithm that   raises the eigenvalues of the input graph, while preserving its  cuts. Combined with spectral clustering on the modified  graph, this yields demonstrably improved cuts.
Cost Effective Active Search
Authors: Shali Jiang, Roman Garnett, Benjamin Moseley
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12
Tasks: Active Learning

We study a special paradigm of active learning, called cost effective active search, where the goal is to find a given number of positive points from a large unlabeled pool with minimum labeling cost. Most existing methods solve this problem heuristically, and few theoretical results have been established. We adopt a principled Bayesian approach for the first time. We first derive the Bayesian optimal policy and establish a strong hardness result: the optimal policy is hard to approximate, with the best-possible approximation ratio lower bounded by $\Omega(n^{0.16})$. We then propose an efficient and nonmyopic policy using the negative Poisson binomial distribution. We propose simple and fast approximations for computing its expectation, which serves as an essential role in our proposed policy. We conduct comprehensive experiments on various domains such as drug and materials discovery, and demonstrate that our proposed search procedure is superior to the widely used greedy baseline.
Exploration Bonus for Regret Minimization in Discrete and Continuous Average Reward MDPs
Authors: Jian Qian, Ronan Fruit, Matteo Pirotta, Alessandro Lazaric
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12

The exploration bonus is an effective approach to manage the exploration-exploitation trade-off in Markov Decision Processes (MDPs).
While it has been analyzed in infinite-horizon discounted and finite-horizon problems, we focus on designing and analysing the exploration bonus in the more challenging infinite-horizon undiscounted setting.
We first introduce SCAL+, a variant of SCAL (Fruit et al. 2018), that uses a suitable exploration bonus to solve any discrete unknown weakly-communicating MDP for which an upper bound $c$ on the span of the optimal bias function is known. We prove that SCAL+ enjoys the same regret guarantees as SCAL, which relies on the less efficient extended value iteration approach.
Furthermore, we leverage the flexibility provided by the exploration bonus scheme to generalize SCAL+ to smooth MDPs with continuous state space and discrete actions. We show that the resulting algorithm (SCCAL+) achieves the same regret bound as UCCRL (Ortner and Ryabko, 2012) while being the first implementable algorithm for this setting.
Hybrid 8-bit Floating Point (HFP8) Training and Inference for Deep Neural Networks
Authors: Xiao Sun, Jungwook Choi, Chia-Yu Chen, Naigang Wang, Swagath Venkataramani, Vijayalakshmi (Viji) Srinivasan, Xiaodong Cui, Wei zhang, Kailash Gopalakrishnan
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12
Tasks: image-classification, Image Classification, object-detection, Object Detection

Reducing the numerical precision of data and computation is extremely effective in accelerating deep learning training workloads. Towards this end, 8-bit floating point representations (FP8) were recently proposed for DNN training. However, its applicability was demonstrated on a few selected models only and significant degradation is observed when popular networks such as MobileNet and Transformer are trained using FP8. This degradation is due to the inherent precision requirement difference in the forward and backward passes of DNN training. Using theoretical insights, we propose a hybrid FP8 (HFP8) format and DNN end-to-end distributed training procedure. We demonstrate, using HFP8, the successful training of deep learning models across a whole spectrum of applications including Image Classification, Object Detection, Language and Speech without accuracy degradation. Finally, we demonstrate that, by using the new 8 bit format, we can directly quantize a pre-trained model down to 8-bits without losing accuracy by simply fine-tuning batch normalization statistics. These novel techniques enable a new generations of 8-bit hardware that are robust for building and deploying neural network models.
Breaking the Glass Ceiling for Embedding-Based Classifiers for Large Output Spaces
Authors: Chuan Guo, Ali Mousavi, Xiang Wu, Daniel N. Holtmann-Rice, Satyen Kale, Sashank Reddi, Sanjiv Kumar
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12
Tasks: Attribute, Classification, Data Augmentation, General Classification

In extreme classification settings, embedding-based neural network models are currently not competitive with sparse linear and tree-based methods in terms of accuracy. Most prior works attribute this poor performance to the low-dimensional bottleneck in embedding-based methods. In this paper, we demonstrate that theoretically there is no limitation to using low-dimensional embedding-based methods, and provide experimental evidence that overfitting is the root cause of the poor performance of embedding-based methods. These findings motivate us to investigate novel data augmentation and regularization techniques to mitigate overfitting. To this end, we propose GLaS, a new regularizer for embedding-based neural network approaches. It is a natural generalization from the graph Laplacian and spread-out regularizers, and empirically it addresses the drawback of each regularizer alone when applied to the extreme classification setup. With the proposed techniques, we attain or improve upon the state-of-the-art on most widely tested public extreme classification datasets with hundreds of thousands of labels.
Deep imitation learning for molecular inverse problems
Authors: Eric Jonas
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12
Tasks: Active Learning, Graph Generation, Imitation Learning, Structured Prediction

Many measurement modalities arise from well-understood physical processes and result in information-rich but difficult-to-interpret data. Much of this data still requires laborious human interpretation. This is the case in nuclear magnetic resonance (NMR) spectroscopy, where the observed spectrum of a molecule provides a distinguishing fingerprint of its bond structure. Here we solve the resulting inverse problem: given a molecular formula and a spectrum, can we infer the chemical structure? We show for a wide variety of molecules we can quickly compute the correct molecular structure, and can detect with reasonable certainty when our method cannot. We treat this as a problem of graph-structured prediction, where armed with per-vertex information on a subset of the vertices, we infer the edges and edge types. We frame the problem as a Markov decision process (MDP) and incrementally construct molecules one bond at a time, training a deep neural network via imitation learning, where we learn to imitate a subisomorphic oracle which knows which remaining bonds are correct. Our method is fast, accurate, and is the first among recent chemical-graph generation approaches to exploit per-vertex information and generate graphs with vertex constraints. Our method points the way towards automation of molecular structure identification and potentially active learning for spectroscopy.
Multivariate Triangular Quantile Maps for Novelty Detection
Authors: Jingjing Wang, Sun Sun, Yao-Liang Yu
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12
Tasks: Density Estimation, Novelty Detection

Novelty detection, a fundamental task in machine learning, has  drawn a lot of recent attention due to its wide-ranging applications and the rise of neural approaches. In this work, we present a general framework for neural novelty detection that centers around a multivariate extension of the univariate quantile function. Our framework unifies and extends many classical and recent novelty detection algorithms, and opens the way to exploit recent advances in flow-based neural density estimation. We adapt the multiple gradient descent algorithm to obtain the first efficient end-to-end implementation of our framework that is free of tuning hyperparameters. Extensive experiments over a number of real datasets confirm the efficacy of our proposed method against state-of-the-art alternatives.
Mutually Regressive Point Processes
Authors: Ifigeneia Apostolopoulou, Scott Linderman, Kyle Miller, Artur Dubrawski
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12
Tasks: Bayesian Inference, Point Processes

Many real-world data represent sequences of interdependent events unfolding over
 time. They can be modeled naturally as realizations of a point process. Despite many potential applications, existing point process models are limited in their
ability to capture complex patterns of interaction. Hawkes processes admit many
efficient inference algorithms, but are limited to mutually excitatory effects. Non-
linear Hawkes processes allow for more complex influence patterns, but for their
estimation it is typically necessary to resort to discrete-time approximations that may yield poor generative models. In this paper, we introduce the first general
class of Bayesian point process models extended with a nonlinear component that
allows both excitatory and inhibitory relationships in continuous time. We derive a fully Bayesian inference algorithm for these processes using Polya-Gamma augmentation and Poisson thinning. We evaluate the proposed model on single
and multi-neuronal spike train recordings. Results demonstrate that the proposed
model, unlike existing point process models, can generate biologically-plausible
spike trains, while still achieving competitive predictive likelihoods.
ANODEV2: A Coupled Neural ODE Framework
Authors: Tianjun Zhang, Zhewei Yao, Amir Gholami, Joseph E. Gonzalez, Kurt Keutzer, Michael W. Mahoney, George Biros
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12

It has been observed that residual networks can be viewed as the explicit Euler discretization of an Ordinary Differential Equation (ODE). This observation motivated the introduction of so-called Neural ODEs, in which other discretization schemes and/or adaptive time stepping techniques can be used to improve the performance of residual networks. Here, we propose \OURS, which extends this approach by introducing a framework that allows ODE-based evolution for both the weights and the activations, in a coupled formulation. Such an approach provides more modeling flexibility, and it can help with generalization performance. We present the formulation of \OURS, derive optimality conditions, and implement the coupled framework in PyTorch. We present empirical results using several different configurations of \OURS, testing them on the CIFAR-10 dataset. We report results showing that our coupled ODE-based framework is indeed trainable, and that it achieves higher accuracy, compared to the baseline ResNet network and the recently-proposed Neural ODE approach.
Learning in Generalized Linear Contextual Bandits with Stochastic Delays
Authors: Zhengyuan Zhou, Renyuan Xu, Jose Blanchet
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12
Tasks: Multi-Armed Bandits

In this paper, we consider online learning in generalized linear contextual bandits where rewards are not immediately observed. Instead, rewards are available to the decision maker only after some delay, which is unknown and stochastic, even though a decision must be made at each time step for an incoming set of contexts. We study the performance of upper confidence bound (UCB) based algorithms adapted to this delayed setting. In particular, we design a delay-adaptive algorithm, which we call Delayed UCB, for generalized linear contextual bandits using UCB-style exploration and establish regret bounds under various delay assumptions. In the important special case of linear contextual bandits, we further modify this algorithm and establish a tighter regret bound under the same delay assumptions. 
Our results contribute to the broad landscape of contextual bandits literature by establishing that UCB algorithms, which are widely deployed in modern recommendation engines, can be made robust to delays.
Face Reconstruction from Voice using Generative Adversarial Networks
Authors: Yandong Wen, Bhiksha Raj, Rita Singh
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12
Tasks: Face Reconstruction

Voice profiling aims at inferring various human parameters from their speech, e.g. gender, age, etc. In this paper, we address the challenge posed by a subtask of voice profiling - reconstructing someone's face from their voice. The task is designed to answer the question: given an audio clip spoken by an unseen person, can we picture a face that has as many common elements, or associations as possible with the speaker, in terms of identity?

To address this problem, we propose a simple but effective computational framework based on generative adversarial networks (GANs). The network learns to generate faces from voices by matching the identities of generated faces to those of the speakers, on a training set. We evaluate the performance of the network by leveraging a closely related task - cross-modal matching. The results show that our model is able to generate faces that match several biometric characteristics of the speaker, and results in matching accuracies that are much better than chance. The code is publicly available in https://github.com/cmu-mlsp/reconstructing_faces_from_voices
Balancing Efficiency and Fairness in On-Demand Ridesourcing
Authors: Nixie S. Lesmana, Xuan Zhang, Xiaohui Bei
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12
Tasks: Fairness

We investigate the problem of assigning trip requests to available vehicles in on-demand ridesourcing. Much of the literature has focused on maximizing the total value of served requests, achieving efficiency on the passengers’ side. However, such solutions may result in some drivers being assigned to insufficient or undesired trips, therefore losing fairness from the drivers’ perspective.

In this paper, we focus on both the system efficiency and the fairness among drivers and quantitatively analyze the trade-offs between these two objectives. In particular, we give an explicit answer to the question of whether there always exists an assignment that achieves any target efficiency and fairness. We also propose a simple reassignment algorithm that can achieve any selected trade-off. Finally, we demonstrate the effectiveness of the algorithms through extensive experiments on real-world datasets.
Latent Ordinary Differential Equations for Irregularly-Sampled Time Series
Authors: Yulia Rubanova, Tian Qi Chen, David K. Duvenaud
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12
Tasks: Time Series, Time Series Analysis

Time series with non-uniform intervals occur in many applications, and are difficult to model using standard recurrent neural networks (RNNs). We generalize RNNs to have continuous-time hidden dynamics defined by ordinary differential equations (ODEs), a model we call ODE-RNNs. Furthermore, we use ODE-RNNs to replace the recognition network of the recently-proposed Latent ODE model. Both ODE-RNNs and Latent ODEs can naturally handle arbitrary time gaps between observations, and can explicitly model the probability of observation times using Poisson processes. We show experimentally that these ODE-based models outperform their RNN-based counterparts on irregularly-sampled data.
Optimal Stochastic and Online Learning with Individual Iterates
Authors: Yunwen Lei, Peng Yang, Ke Tang, Ding-Xuan Zhou
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12
Tasks: Sparse Learning

Stochastic composite mirror descent (SCMD) is a simple and efficient method able to capture both geometric and composite structures of optimization problems in machine learning. Existing strategies require to take either an average or a random selection of iterates to achieve optimal convergence rates, which, however, can either destroy the sparsity of solutions or slow down the practical training speed. In this paper, we propose a theoretically sound strategy to select an individual iterate of the vanilla SCMD, which is able to achieve optimal rates for both convex and strongly convex problems in a non-smooth learning setting. This strategy of outputting an individual iterate can preserve the sparsity of solutions which is crucial for a proper interpretation in sparse learning problems. We report experimental comparisons with several baseline methods to show the effectiveness of our method in achieving a fast training speed as well as in outputting sparse solutions.
Regularized Gradient Boosting
Authors: Corinna Cortes, Mehryar Mohri, Dmitry Storcheus
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12
Tasks: Generalization Bounds

Gradient Boosting (\GB) is a popular and very successful ensemble method for binary trees. While various types of regularization of the base predictors are used with this algorithm, the theory that connects such regularizations with  generalization guarantees is poorly understood. We fill this gap by deriving data-dependent learning guarantees for \GB\ used with \emph{regularization}, expressed in terms of the Rademacher complexities of the constrained families of base predictors. We introduce a new algorithm, called \rgb\, that directly benefits from these generalization bounds and that, at every boosting round, applies the \emph{Structural Risk Minimization} principle to search for a base predictor with the best empirical fit versus complexity trade-off.
Inspired by \emph{Randomized Coordinate Descent} we provide a scalable implementation of our algorithm, able to search over large families of base predictors. Finally, we provide experimental results, demonstrating that our algorithm achieves significantly better out-of-sample performance on multiple datasets than the standard \GB\ algorithm used with its regularization.
Time-series Generative Adversarial Networks
Authors: Jinsung Yoon, Daniel Jarrett, M Van Der Schaar
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12
Tasks: Time Series, Time Series Analysis

A good generative model for time-series data should preserve temporal dynamics, in the sense that new sequences respect the original relationships between variables across time. Existing methods that bring generative adversarial networks (GANs) into the sequential setting do not adequately attend to the temporal correlations unique to time-series data. At the same time, supervised models for sequence prediction - which allow finer control over network dynamics - are inherently deterministic. We propose a novel framework for generating realistic time-series data that combines the flexibility of the unsupervised paradigm with the control afforded by supervised training. Through a learned embedding space jointly optimized with both supervised and adversarial objectives, we encourage the network to adhere to the dynamics of the training data during sampling. Empirically, we evaluate the ability of our method to generate realistic samples using a variety of real and synthetic time-series datasets. Qualitatively and quantitatively, we find that the proposed framework consistently and significantly outperforms state-of-the-art benchmarks with respect to measures of similarity and predictive ability.
A Refined Margin Distribution Analysis for Forest Representation Learning
Authors: Shen-Huan Lyu, Liang Yang, Zhi-Hua Zhou
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12
Tasks: Representation Learning

In this paper, we formulate the forest representation learning approach called \textsc{CasDF} as an additive model which boosts the augmented feature instead of the prediction. We substantially improve the upper bound of the generalization gap from $\mathcal{O}(\sqrt{\ln m/m})$ to $\mathcal{O}(\ln m/m)$, while the margin ratio of the margin standard deviation to the margin mean is sufficiently small. This tighter upper bound inspires us to optimize the ratio. Therefore, we design a margin distribution reweighting approach for deep forest to achieve a small margin ratio by boosting the augmented feature. Experiments confirm the correlation between the margin distribution and generalization performance. We remark that this study offers a novel understanding of \textsc{CasDF} from the perspective of the margin theory and further guides the layer-by-layer forest representation learning.