pwc-archive/papers-with-abstracts huggingface dataset:
Near-Optimal Reinforcement Learning in Dynamic Treatment Regimes
Authors: Junzhe Zhang, Elias Bareinboim
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12
Tasks: Decision Making, reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

A dynamic treatment regime (DTR) consists of a sequence of decision rules, one per stage of intervention, that dictates how to determine the treatment assignment to patients based on evolving treatments and covariates' history. These regimes are particularly effective for managing chronic disorders and is arguably one of the key aspects towards more personalized decision-making. In this paper, we investigate the online reinforcement learning (RL) problem for selecting optimal DTRs provided that observational data is available. We develop the first adaptive algorithm that achieves near-optimal regret in DTRs in online settings, without any access to historical data. We further derive informative bounds on the system dynamics of the underlying DTR from confounded, observational data. Finally, we combine these results and develop a novel RL algorithm that efficiently learns the optimal DTR while leveraging the abundant, yet imperfect confounded observations.
ODE2VAE: Deep generative second order ODEs with Bayesian neural networks
Authors: Cagatay Yildiz, Markus Heinonen, Harri Lahdesmaki
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12
Tasks: Imputation, motion prediction, Position, Time Series, Time Series Analysis

We present Ordinary Differential Equation Variational Auto-Encoder (ODE2VAE), a latent second order ODE model for high-dimensional sequential data. Leveraging the advances in deep generative models, ODE2VAE can simultaneously learn the embedding of high dimensional trajectories and infer arbitrarily complex continuous-time latent dynamics. Our model explicitly decomposes the latent space into momentum and position components and solves a second order ODE system, which is in contrast to recurrent neural network (RNN) based time series models and recently proposed black-box ODE techniques. In order to account for uncertainty, we propose probabilistic latent ODE dynamics parameterized by deep Bayesian neural networks. We demonstrate our approach on motion capture, image rotation, and bouncing balls datasets. We achieve state-of-the-art performance in long term motion prediction and imputation tasks.
Optimal Sampling and Clustering in the Stochastic Block Model
Authors: Se-Young Yun, Alexandre Proutiere
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12
Tasks: Clustering, Stochastic Block Model

This paper investigates the design of joint adaptive sampling and clustering algorithms in networks whose structure follows the celebrated Stochastic Block Model (SBM). To extract hidden clusters, the interaction between edges (pairs of nodes) may be sampled sequentially, in an adaptive manner. After gathering samples, the learner returns cluster estimates. We derive information-theoretical upper bounds on the cluster recovery rate. These bounds actually reveal the optimal sequential edge sampling strategy, and interestingly, the latter does not depend on the sampling budget, but on the parameters of the SBM only. We devise a joint sampling and clustering algorithm matching the recovery rate upper bounds. The algorithm initially uses a fraction of the sampling budget to estimate the SBM parameters, and to learn the optimal sampling strategy. This strategy then guides the remaining sampling process, which confers the optimality of the algorithm. We show both analytically and numerically that adaptive edge sampling yields important improvements over random sampling (traditionally used in the SBM analysis). For example, we prove that adaptive sampling significantly enlarges the region of the SBM parameters where asymptotically exact cluster recovery is feasible.
Globally Optimal Learning for Structured Elliptical Losses
Authors: Yoav Wald, Nofar Noy, Gal Elidan, Ami Wiesel
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12
Tasks: regression

Heavy tailed and contaminated data are common in various applications of machine learning. A standard technique to handle regression tasks that involve such data, is to use robust losses, e.g., the popular Huber’s loss.

In structured problems, however, where there are multiple labels and structural constraints on the labels are imposed (or learned), robust optimization is challenging, and more often than not the loss used is simply the negative log-likelihood of a Gaussian Markov random field.
Heavy tailed and contaminated data are common in various applications of machine learning. A standard technique to handle regression tasks that involve such data, is to use robust losses, e.g., the popular Huber’s loss.
In structured problems, however, where there are multiple labels and structural constraints on the labels are imposed (or learned), robust optimization is challenging, and more often than not the loss used is simply the negative log-likelihood of a Gaussian Markov random field. In this work, we analyze robust alternatives. Theoretical understanding of such problems is quite limited, with guarantees on optimization given only for special cases and non-structured settings. The core of the difficulty is the non-convexity of the objective function, implying that standard optimization algorithms may converge to sub-optimal critical points. Our analysis focuses on loss functions that arise from elliptical distributions, which appealingly include most loss functions proposed in the literature as special cases. We show that, even though these problems are non-convex, they can be optimized efficiently. Concretely, we prove that at the limit of infinite training data, due to algebraic properties of the problem, all stationary points are globally optimal. Finally, we demonstrate the empirical appeal of using these losses for regression on synthetic and real-life data.
Specific and Shared Causal Relation Modeling and Mechanism-Based Clustering
Authors: Biwei Huang, Kun Zhang, Pengtao Xie, Mingming Gong, Eric P. Xing, Clark Glymour
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12
Tasks: Causal Discovery, Clustering, Relation

State-of-the-art approaches to causal discovery usually assume a fixed underlying causal model. However, it is often the case that causal models vary across domains or subjects, due to possibly omitted factors that affect the quantitative causal effects. As a typical example, causal connectivity in the brain network has been reported to vary across individuals, with significant differences across groups of people, such as autistics and typical controls. In this paper, we develop a unified framework for causal discovery and mechanism-based group identification. In particular, we propose a specific and shared causal model (SSCM), which takes into account the variabilities of causal relations across individuals/groups and leverages their commonalities to achieve statistically reliable estimation. The learned SSCM gives the specific causal knowledge for each individual as well as the general trend over the population. In addition, the estimated model directly provides the group information of each individual. Experimental results on synthetic and real-world data demonstrate the efficacy of the proposed method.
Communication trade-offs for Local-SGD with large step size
Authors: Aymeric Dieuleveut, Kumar Kshitij Patel
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12

Synchronous mini-batch SGD is state-of-the-art for large-scale distributed machine learning. However, in practice, its convergence is bottlenecked by slow communication rounds between worker nodes. A natural solution to reduce communication is to use the \emph{``local-SGD''}  model in which the workers train their model independently and synchronize every once in a while. This algorithm improves the computation-communication trade-off but its convergence is not understood very well. We propose a non-asymptotic error analysis, which enables comparison to \emph{one-shot averaging} i.e., a single communication round among independent workers, and \emph{mini-batch averaging} i.e., communicating at every step. We also provide adaptive lower bounds on the communication frequency for large step-sizes ($ t^{-\alpha} $, $ \alpha\in (1/2 , 1 ) $) and show that \emph{Local-SGD} reduces communication by a factor of $O\Big(\frac{\sqrt{T}}{P^{3/2}}\Big)$, with $T$ the total number of gradients and $P$ machines.
AutoPrune: Automatic Network Pruning by Regularizing Auxiliary Parameters
Authors: Xia Xiao, Zigeng Wang, Sanguthevar Rajasekaran
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12
Tasks: Network Pruning

Reducing the model redundancy is an important task to deploy complex deep learning models to resource-limited or time-sensitive devices. Directly regularizing or modifying weight values makes pruning procedure less robust and sensitive to the choice of hyperparameters, and it also requires prior knowledge to tune different hyperparameters for different models. To build a better generalized and easy-to-use pruning method, we propose AutoPrune, which prunes the network through optimizing a set of trainable auxiliary parameters instead of original weights. The instability and noise during training on auxiliary parameters will not directly affect weight values, which makes pruning process more robust to noise and less sensitive to hyperparameters. Moreover, we design gradient update rules for auxiliary parameters to keep them consistent with pruning tasks. Our method can automatically eliminate network redundancy with recoverability, relieving the complicated prior knowledge required to design thresholding functions, and reducing the time for trial and error. We evaluate our method with LeNet and VGG-like on MNIST and CIFAR-10 datasets, and with AlexNet, ResNet and MobileNet on ImageNet to establish the scalability of our work. Results show that our model achieves state-of-the-art sparsity, e.g. 7%, 23% FLOPs and 310x, 75x compression ratio for LeNet5 and VGG-like structure without accuracy drop, and 200M and 100M FLOPs for MobileNet V2 with accuracy 73.32% and 66.83% respectively.
Towards Hardware-Aware Tractable Learning of Probabilistic Models
Authors: Laura I. Galindez Olascoaga, Wannes Meert, Nimish Shah, Marian Verhelst, Guy Van Den Broeck
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12
Tasks: Activity Recognition, Edge-computing, Small Data Image Classification

Smart portable applications increasingly rely on edge computing due to privacy and latency concerns. But guaranteeing always-on functionality comes with two major challenges: heavily resource-constrained hardware; and dynamic application conditions. Probabilistic models present an ideal solution to these challenges: they are robust to missing data, allow for joint predictions and have small data needs. In addition, ongoing efforts in field of tractable learning have resulted in probabilistic models with strict inference efficiency guarantees. However, the current notions of tractability are often limited to model complexity, disregarding the hardware's specifications and constraints.  We propose a novel resource-aware cost metric that takes into consideration the hardware's properties in determining whether the inference task can be efficiently deployed. We use this metric to evaluate the performance versus resource trade-off relevant to the application of interest, and we propose a strategy that selects the device-settings that can optimally meet users' requirements. We showcase our framework on a mobile activity recognition scenario, and on a variety of benchmark datasets representative of the field of tractable learning and of the applications of interest.
Rand-NSG: Fast Accurate Billion-point Nearest Neighbor Search on a Single Node
Authors: Suhas Jayaram Subramanya, Fnu Devvrit, Harsha Vardhan Simhadri, Ravishankar Krishnawamy, Rohan Kadekodi
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12

Current state-of-the-art approximate nearest neighbor search (ANNS) algorithms
generate indices that must be stored in main memory for fast high-recall search.
This makes them expensive and limits the size of the dataset. We present a
new graph-based indexing and search system called DiskANN that can index,
store, and search a billion point database on a single workstation with just 64GB
RAM and an inexpensive solid-state drive (SSD). Contrary to current wisdom,
we demonstrate that the SSD-based indices built by DiskANN can meet all three
desiderata for large-scale ANNS: high-recall, low query latency and high density
(points indexed per node). On the billion point SIFT1B bigann dataset, DiskANN
serves > 5000 queries a second with < 3ms mean latency and 95%+ 1-recall@1
on a 16 core machine, where state-of-the-art billion-point ANNS algorithms with
similar memory footprint like FAISS and IVFOADC+G+P plateau at
around 50% 1-recall@1. Alternately, in the high recall regime, DiskANN can
index and serve 5 − 10x more points per node compared to state-of-the-art graph-
based methods such as HNSW and NSG. Finally, as part of our overall
DiskANN system, we introduce Vamana, a new graph-based ANNS index that is
more versatile than the graph indices even for in-memory indices.
MonoForest framework for tree ensemble analysis
Authors: Igor Kuralenok, Vasilii Ershov, Igor Labutin
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12
Tasks: Form, Translation

In this work, we introduce a new decision tree ensemble representation framework: instead of using a graph model we transform each tree into a well-known polynomial form. We apply the new representation to three tasks: theoretical analysis, model reduction, and interpretation. The polynomial form of a tree ensemble allows a straightforward interpretation of the original model. In our experiments, it shows comparable results with state-of-the-art interpretation techniques. Another application of the framework is the ensemble-wise pruning: we can drop monomials from the polynomial, based on train data statistics. This way we reduce the model size up to 3 times without loss of its quality. It is possible to show the equivalence of tree shape classes that share the same polynomial. This fact gives us the ability to train a model in one tree's shape and exploit it in another, which is easier for computation or interpretation. We formulate a problem statement for optimal tree ensemble translation from one form to another and build a greedy solution to this problem.
Primal-Dual Block Generalized Frank-Wolfe
Authors: Qi Lei, Jiacheng Zhuo, Constantine Caramanis, Inderjit S. Dhillon, Alexandros G. Dimakis
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12
Tasks: Multi-class Classification, Retrieval

We propose a generalized variant of Frank-Wolfe algorithm for solving a class of sparse/low-rank optimization problems. Our formulation includes Elastic Net, regularized SVMs and phase retrieval as special cases. The proposed Primal-Dual Block Generalized Frank-Wolfe algorithm reduces the per-iteration cost while maintaining linear convergence rate.
The per iteration cost of our method depends on the structural complexity of the solution (i.e. sparsity/low-rank) instead of the ambient dimension.
We empirically show that our algorithm outperforms the state-of-the-art methods on (multi-class) classification tasks.
User-Specified Local Differential Privacy in Unconstrained Adaptive Online Learning
Authors: Dirk van der Hoeven
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12

Local differential privacy is a strong notion of privacy in which the provider of the data guarantees privacy by perturbing the data with random noise. In the standard application of local differential differential privacy the distribution of the noise is constant and known by the learner. In this paper we generalize this approach by allowing the provider of the data to choose the distribution of the noise without disclosing any parameters of the distribution to the learner, under the constraint that the distribution is symmetrical. We consider this problem in the unconstrained Online Convex Optimization setting with noisy feedback. In this setting the learner receives the subgradient of a loss function, perturbed by noise, and aims to achieve sublinear regret with respect to some competitor, without constraints on the norm of the competitor. We derive the first algorithms that have adaptive regret bounds in this setting, i.e. our algorithms adapt to the unknown competitor norm, unknown noise, and unknown sum of the norms of the subgradients, matching state of the art bounds in all cases.
Learning Positive Functions with Pseudo Mirror Descent
Authors: Yingxiang Yang, Haoxiang Wang, Negar Kiyavash, Niao He
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12
Tasks: Computational Efficiency, Point Processes

The nonparametric learning of positive-valued functions appears widely in machine learning, especially in the context of estimating intensity functions of point processes. Yet, existing approaches either require computing expensive projections or semidefinite relaxations, or lack convexity and theoretical guarantees after introducing nonlinear link functions. In this paper, we propose a novel algorithm, pseudo mirror descent, that performs efficient estimation of positive functions within a Hilbert space without expensive projections. The algorithm guarantees positivity by performing mirror descent with an appropriately selected Bregman divergence, and a pseudo-gradient is adopted to speed up the gradient evaluation procedure in practice. We analyze both asymptotic and nonasymptotic convergence of the algorithm. Through simulations, we show that pseudo mirror descent outperforms the state-of-the-art benchmarks for learning intensities of Poisson and multivariate Hawkes processes, in terms of both computational efficiency and accuracy.
A Similarity-preserving Network Trained on Transformed Images Recapitulates Salient Features of the Fly Motion Detection Circuit
Authors: Yanis Bahroun, Dmitri Chklovskii, Anirvan Sengupta
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12
Tasks: Image Reconstruction, Motion Detection

Learning to detect content-independent transformations from data is one of the central problems in biological and artificial intelligence. An example of such problem is unsupervised learning of a visual motion detector from pairs of consecutive video frames. Rao and Ruderman formulated this problem in terms of learning infinitesimal transformation operators (Lie group generators) via  minimizing image reconstruction error. Unfortunately, it is difficult to map their model onto a biologically plausible neural network (NN) with local learning rules. Here we propose a biologically plausible model of motion detection. We also adopt the transformation-operator approach but, instead of reconstruction-error minimization, start with a similarity-preserving objective function. An online algorithm that optimizes such an objective function naturally maps onto an NN with biologically plausible learning rules. The trained NN recapitulates major features of the well-studied motion detector in the fly. In particular, it is consistent with the experimental observation that local motion detectors combine information from at least three adjacent pixels, something that contradicts the celebrated Hassenstein-Reichardt model.
Differentially Private Covariance Estimation
Authors: Kareem Amin, Travis Dick, Alex Kulesza, Andres Munoz, Sergei Vassilvitskii
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12

The covariance matrix of a dataset is a fundamental statistic that can be used for calculating optimum regression weights as well as in many other learning and data analysis settings. For datasets containing private user information, we often want to estimate the covariance matrix in a way that preserves differential privacy. While there are known methods for privately computing the covariance matrix, they all have one of two major shortcomings. Some, like the Gaussian mechanism, only guarantee (epsilon, delta)-differential privacy, leaving a non-trivial probability of privacy failure. Others give strong epsilon-differential privacy guarantees, but are impractical, requiring complicated sampling schemes, and tend to perform poorly on real data. 

In this work we propose a new epsilon-differentially private algorithm for computing the covariance matrix of a dataset that addresses both of these limitations. We show that it has lower error than existing state-of-the-art approaches, both analytically and empirically. In addition, the algorithm is significantly less complicated than other methods and can be efficiently implemented with rejection sampling.
Outlier Detection and Robust PCA Using a Convex Measure of Innovation
Authors: Mostafa Rahmani, Ping Li
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12
Tasks: Outlier Detection

This paper presents a provable  and strong algorithm, termed Innovation Search (iSearch), to robust Principal Component Analysis (PCA) and outlier detection.  An outlier by definition is a data point which  does not participate in forming a low dimensional structure with a large number of data points in the data.  In other word, an outlier carries some innovation with respect to most of the other data points. iSearch ranks the data points based on their values of innovation. A convex optimization problem is proposed whose optimal value is used as our measure of  innovation.  We derive analytical performance guarantees for the proposed robust PCA method  under different models for the distribution of the outliers including randomly distributed outliers, clustered outliers, and linearly dependent outliers.  Moreover, it is shown that iSearch provably recovers the span of the inliers when the inliers lie in a union of subspaces.  In the challenging scenarios in which the outliers are close to each other or they are close to the span of the inliers, iSearch is shown to  outperform most of the existing methods.
Constraint-based Causal Structure Learning with Consistent Separating Sets
Authors: Honghao Li, Vincent Cabeli, Nadir Sella, Herve Isambert
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12
Tasks: Tree Decomposition

We consider constraint-based methods for causal structure learning, such as the PC algorithm or any PC-derived algorithms whose ﬁrst step consists in pruning a complete graph to obtain an undirected graph skeleton, which is subsequently oriented. All constraint-based methods perform this ﬁrst step of removing dispensable edges, iteratively, whenever a separating set and corresponding conditional independence can be found. Yet, constraint-based methods lack robustness over sampling noise and are prone to uncover spurious conditional independences in ﬁnite datasets. In particular, there is no guarantee that the separating sets identiﬁed during the iterative pruning step remain consistent with the ﬁnal graph. In this paper, we propose a simple modiﬁcation of PC and PC-derived algorithms so as to ensure that all separating sets identiﬁed to remove dispensable edges are consistent with the ﬁnal graph,thus enhancing the explainability of constraint-basedmethods. It is achieved by repeating the constraint-based causal structure learning scheme, iteratively, while searching for separating sets that are consistent with the graph obtained at the previous iteration. Ensuring the consistency of separating sets can be done at a limited complexity cost, through the use of block-cut tree decomposition of graph skeletons, and is found to increase their validity in terms of actual d-separation. It also signiﬁcantly improves the sensitivity of constraint-based methods while retaining good overall structure learning performance. Finally and foremost, ensuring sepset consistency improves the interpretability of constraint-based models for real-life applications.