pwc-archive/papers-with-abstracts huggingface dataset:
R2D2: Reliable and Repeatable Detector and Descriptor
Authors: Jerome Revaud, Cesar De Souza, Martin Humenberger, Philippe Weinzaepfel
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12
Tasks: Atari Games, Camera Localization, Image Matching, Interest Point Detection, Keypoint Detection, Metric Learning

Interest point detection and local feature description are fundamental steps in many computer vision applications. Classical approaches are based on a detect-then-describe paradigm where separate handcrafted methods are used to first identify repeatable keypoints and then represent them with a local descriptor. Neural networks trained with metric learning losses have recently caught up with these techniques, focusing on learning repeatable saliency maps for keypoint detection or learning descriptors at the detected keypoint locations. In this work, we argue that repeatable regions are not necessarily discriminative and can therefore lead to select suboptimal keypoints. Furthermore, we claim that descriptors should be learned only in regions for which matching can be performed with high confidence. 
We thus propose to jointly learn keypoint detection and description together with a predictor of the local descriptor discriminativeness. This allows to avoid ambiguous areas, thus leading to reliable keypoint detection and description. Our detection-and-description approach simultaneously outputs sparse, repeatable and reliable keypoints that outperforms state-of-the-art detectors and descriptors on the HPatches dataset and on the recent Aachen Day-Night localization benchmark.
Selective Sampling-based Scalable Sparse Subspace Clustering
Authors: Shin Matsushima, Maria Brbic
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12
Tasks: Clustering, Representation Learning

Sparse subspace clustering (SSC) represents each data point as a sparse linear combination of other data points in the dataset. In the representation learning step SSC finds a lower dimensional representation of data points, while in the spectral clustering step data points are clustered according to the underlying subspaces. However, both steps suffer from high computational and memory complexity, preventing the application of SSC to large-scale datasets. To overcome this limitation, we introduce Selective Sampling-based Scalable Sparse Subspace Clustering (S5C) algorithm which selects subsamples based on the approximated subgradients and linearly scales with the number of data points in terms of time and memory requirements. Along with the computational advantages, we derive theoretical guarantees for the correctness of S5C. Our theoretical result presents novel contribution for SSC in the case of limited number of subsamples. Extensive experimental results demonstrate effectiveness of our approach.
Distribution Learning of a Random Spatial Field with a Location-Unaware Mobile Sensor
Authors: Meera Pai, Animesh Kumar
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12

Measurement of spatial fields is of interest in environment monitoring. Recently mobile sensing has been proposed for spatial field reconstruction, which requires a smaller number of sensors when compared to the traditional paradigm of sensing with static sensors. A challenge in mobile sensing is to overcome the location uncertainty of its sensors. While GPS or other localization methods can reduce this uncertainty, we address a more fundamental question: can a location-unaware mobile sensor, recording samples on a directed non-uniform random walk, learn the statistical distribution (as a function of space) of an underlying random process (spatial field)? The answer is in the affirmative for Lipschitz continuous fields, where the accuracy of our distribution-learning method increases with the number of observed field samples (sampling rate). To validate our distribution-learning method, we have created a dataset with 43 experimental trials by measuring sound-level along a fixed path using a location-unaware mobile sound-level meter.
Selecting causal brain features with a single conditional independence test per feature
Authors: Atalanti Mastakouri, Bernhard Schölkopf, Dominik Janzing
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12
Tasks: feature selection

We propose a constraint-based causal feature selection method for identifying causes of a given target variable, selecting from a set of candidate variables, while there can also be hidden variables acting as common causes with the target. We prove that if we observe a cause for each candidate cause, then a single conditional independence test with one conditioning variable is sufficient to decide whether a candidate associated with the target is indeed causing it. We thus improve upon existing methods by significantly simplifying statistical testing and requiring a weaker version of causal faithfulness. Our main assumption is inspired by neuroscience paradigms where the activity of a single neuron is considered to be also caused by its own previous state. We demonstrate successful application of our method to simulated, as well as encephalographic data of twenty-one participants,  recorded in Max Planck Institute for intelligent Systems. The detected causes of motor performance are in accordance with the latest consensus about the neurophysiological pathways, and can provide new insights into personalised brain stimulation.
Curriculum-guided Hindsight Experience Replay
Authors: Meng Fang, Tianyi Zhou, Yali Du, Lei Han, Zhengyou Zhang
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12
Tasks: Deep Reinforcement Learning, Diversity, Reinforcement Learning

In off-policy deep reinforcement learning, it is usually hard to collect sufficient successful experiences with sparse rewards to learn from. Hindsight experience replay (HER) enables an agent to learn from failures by treating the achieved state of a failed experience as a pseudo goal. However, not all the failed experiences are equally useful to different learning stages, so it is not efficient to replay all of them or uniform samples of them. In this paper, we propose to 1) adaptively select the failed experiences for replay according to the proximity to the true goals and the curiosity of exploration over diverse pseudo goals, and 2) gradually change the proportion of the goal-proximity and the diversity-based curiosity in the selection criteria: we adopt a human-like learning strategy that enforces more curiosity in earlier stages and changes to larger goal-proximity later. This ``Goal-and-Curiosity-driven Curriculum Learning'' leads to ``Curriculum-guided HER (CHER)'', which adaptively and dynamically controls the exploration-exploitation trade-off during the learning process via hindsight experience selection. We show that CHER improves the state of the art in challenging robotics environments.
MetaInit: Initializing learning by learning to initialize
Authors: Yann N. Dauphin, Samuel Schoenholz
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12
Tasks: Meta-Learning

Deep learning models frequently trade handcrafted features for deep features learned with much less human intervention using gradient descent. While this paradigm has been enormously successful, deep networks are often difficult to train and performance can depend crucially on the initial choice of parameters. In this work, we introduce an algorithm called MetaInit as a step towards automating the search for good initializations using meta-learning. Our approach is based on a hypothesis that good initializations make gradient descent easier by starting in regions that look locally linear with minimal second order effects. We formalize this notion via a quantity that we call the gradient quotient, which can be computed with any architecture or dataset. MetaInit minimizes this quantity efficiently by using gradient descent to tune the norms of the initial weight matrices. We conduct experiments on plain and residual networks and show that the algorithm can automatically recover from a class of bad initializations. MetaInit allows us to train networks and achieve performance competitive with the state-of-the-art without batch normalization or residual connections. In particular, we find that this approach outperforms normalization for networks without skip connections on CIFAR-10 and can scale to Resnet-50 models on Imagenet.
Scalable Deep Generative Relational Model with High-Order Node Dependence
Authors: Xuhui Fan, Bin Li, Caoyuan Li, Scott Sisson, Ling Chen
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12
Tasks: Data Augmentation, Link Prediction, Vocal Bursts Intensity Prediction

In this work, we propose a probabilistic framework for relational data modelling and latent structure exploring. Given the possible feature information for the nodes in a network, our model builds up a deep architecture that can approximate to the possible nonlinear mappings between the nodes' feature information and latent representations. For each node, we incorporate all its neighborhoods' high-order structure information to generate latent representation, such that these latent representations are ``smooth'' in terms of the network. Since the latent representations are generated from Dirichlet distributions, we further develop a data augmentation trick to enable efficient Gibbs sampling for Ber-Poisson likelihood with Dirichlet random variables. Our model can be ready to apply to large sparse network as its computations cost scales to the number of positive links in the networks. The superior performance of our model is demonstrated through improved link prediction performance on a range of real-world datasets.
Random Path Selection for Continual Learning
Authors: Jathushan Rajasegaran, Munawar Hayat, Salman H. Khan, Fahad Shahbaz Khan, Ling Shao
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12
Tasks: Continual Learning, Incremental Learning, Knowledge Distillation, Reinforcement Learning

Incremental life-long learning is a main challenge towards the long-standing goal of Artificial General Intelligence. In real-life settings, learning tasks arrive in a sequence and machine learning models must continually learn to increment already acquired knowledge. The existing incremental learning approaches fall well below the state-of-the-art cumulative models that use all training classes at once. In this paper, we propose a random path selection algorithm, called RPS-Net, that progressively chooses optimal paths for the new tasks while encouraging parameter sharing and reuse. Our approach avoids the overhead introduced by computationally expensive evolutionary and reinforcement learning based path selection strategies  while achieving considerable performance gains. As an added novelty, the proposed model integrates knowledge distillation and retrospection along with the path selection strategy to overcome catastrophic forgetting. In order to maintain an equilibrium between previous and newly acquired knowledge, we propose a simple controller to dynamically balance the model plasticity.  Through extensive experiments, we demonstrate that the proposed method surpasses the state-of-the-art performance on incremental learning and by utilizing parallel computation this method can run in constant time with nearly the same efficiency as a conventional deep convolutional neural network.
Regret Bounds for Learning State Representations in Reinforcement Learning
Authors: Ronald Ortner, Matteo Pirotta, Alessandro Lazaric, Ronan Fruit, Odalric-Ambrym Maillard
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12
Tasks: reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

We consider the problem of online reinforcement learning when several state representations (mapping histories to a discrete state space) are available to the learning agent. At least one of these representations is assumed to induce a Markov decision process (MDP), and the performance of the agent is measured in terms of cumulative regret against the optimal policy giving the highest average reward in this MDP representation. We propose an algorithm (UCB-MS) with O(sqrt(T)) regret in any communicating Markov decision process. The regret bound shows that UCB-MS automatically adapts to the Markov model. This improves over the currently known best results in the literature that gave regret bounds of order O(T^(2/3)).
Sparse High-Dimensional Isotonic Regression
Authors: David Gamarnik, Julia Gaudio
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12
Tasks: Cancer Classification, regression, Vocal Bursts Intensity Prediction

We consider the problem of estimating an unknown coordinate-wise monotone function given noisy measurements, known as the isotonic regression problem. Often, only a small subset of the features affects the output. This motivates the sparse isotonic regression setting, which we consider here. We provide an upper bound on the expected VC entropy of the space of sparse coordinate-wise monotone functions, and identify the regime of statistical consistency of our estimator. We also propose a linear program to recover the active coordinates, and provide theoretical recovery guarantees. We close with experiments on cancer classification, and show that our method significantly outperforms several standard methods.
Triad Constraints for Learning Causal Structure of Latent Variables
Authors: Ruichu Cai, Feng Xie, Clark Glymour, Zhifeng Hao, Kun Zhang
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12

Learning causal structure from observational data has attracted much attention, and it is notoriously challenging to find the underlying structure in the presence of confounders (hidden direct common causes of two variables). In this paper, by properly leveraging the non-Gaussianity of the data, we propose to estimate the structure over latent variables with the so-called Triad constraints: we design a form of "pseudo-residual" from three variables, and show that when causal relations are linear and noise terms are non-Gaussian, the causal direction between the latent variables for the three observed variables is identifiable by checking a certain kind of independence relationship. In other words, the Triad constraints help us to locate latent confounders and determine the causal direction between them. This goes far beyond the Tetrad constraints and reveals more information about the underlying structure from non-Gaussian data. Finally, based on the Triad constraints, we develop a two-step algorithm to learn the causal structure corresponding to measurement models. Experimental results on both synthetic and real data demonstrate the effectiveness and reliability of our method.
Shallow RNN: Accurate Time-series Classification on Resource Constrained Devices
Authors: Don Dennis, Durmus Alp Emre Acar, Vikram Mandikal, Vinu Sankar Sadasivan, Venkatesh Saligrama, Harsha Vardhan Simhadri, Prateek Jain
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12
Tasks: Classification, General Classification, Time Series, Time Series Analysis, Time Series Classification

Recurrent Neural Networks (RNNs) capture long dependencies and context, and
2 hence are the key component of typical sequential data based tasks. However, the
sequential nature of RNNs dictates a large inference cost for long sequences even if
the hardware supports parallelization. To induce long-term dependencies, and yet
admit parallelization, we introduce novel shallow RNNs. In this architecture, the
first layer splits the input sequence and runs several independent RNNs. The second
layer consumes the output of the first layer using a second RNN thus capturing
long dependencies. We provide theoretical justification for our architecture under
weak assumptions that we verify on real-world benchmarks. Furthermore, we show
that for time-series classification, our technique leads to substantially improved
inference time over standard RNNs without compromising accuracy. For example,
we can deploy audio-keyword classification on tiny Cortex M4 devices (100MHz
processor, 256KB RAM, no DSP available) which was not possible using standard
RNN models. Similarly, using SRNN in the popular Listen-Attend-Spell (LAS)
architecture for phoneme classification [4], we can reduce the lag inphoneme
classification by 10-12x while maintaining state-of-the-art accuracy.
REM: From Structural Entropy to Community Structure Deception
Authors: Yiwei Liu, Jiamou Liu, Zijian Zhang, Liehuang Zhu, Angsheng Li
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12
Tasks: Community Detection

This paper focuses on the privacy risks of disclosing the community structure in an online social network. By exploiting the community affiliations of user accounts, an attacker may infer sensitive user attributes. This raises the problem of community structure deception (CSD), which asks for ways to minimally modify the network so that a given community structure maximally hides itself from community detection algorithms. We investigate CSD through an information-theoretic lens. To this end, we propose a community-based structural entropy to express the amount of information revealed by a community structure. This notion allows us to devise residual entropy minimization (REM) as an efficient procedure to solve CSD. Experimental results over 9 real-world networks and 6 community detection algorithms show that REM is very effective in obfuscating the community structure as compared to other benchmark methods.
Stochastic Continuous Greedy ++: When Upper and Lower Bounds Match
Authors: Amin Karbasi, Hamed Hassani, Aryan Mokhtari, Zebang Shen
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12

In this paper, we develop \scg~(\text{SCG}{$++$}), the first efficient variant of a conditional gradient method for maximizing a  continuous submodular function subject to a convex constraint. Concretely, for a monotone and continuous DR-submodular function, \SCGPP achieves a tight  $[(1-1/e)\OPT -\epsilon]$ solution while using $O(1/\epsilon^2)$ stochastic gradients and $O(1/\epsilon)$ calls to the linear optimization oracle. The best previously known algorithms either achieve a suboptimal $[(1/2)\OPT -\epsilon]$ solution with $O(1/\epsilon^2)$ stochastic gradients or the tight $[(1-1/e)\OPT -\epsilon]$ solution  with suboptimal $O(1/\epsilon^3)$ stochastic gradients. We further provide an information-theoretic lower bound to showcase the necessity of $\OM({1}/{\epsilon^2})$ stochastic oracle queries in order to achieve $[(1-1/e)\OPT -\epsilon]$ for monotone and DR-submodular functions. This result shows that our proposed \SCGPP enjoys optimality in terms of both approximation guarantee, i.e., $(1-1/e)$ approximation factor, and stochastic gradient evaluations, i.e., $O(1/\epsilon^2)$ calls to the stochastic oracle. By using stochastic
continuous optimization as an interface, we also show that it is possible to obtain the $[(1-1/e)\OPT-\epsilon]$ tight approximation guarantee for maximizing a monotone
but stochastic submodular set function subject to a general matroid constraint after at most 
$\mathcal{O}(n^2/\epsilon^2)$ calls to the stochastic function value, where $n$ is the number of elements in the ground set.
Online-Within-Online Meta-Learning
Authors: Giulia Denevi, Dimitris Stamos, Carlo Ciliberto, Massimiliano Pontil
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12
Tasks: Meta-Learning

We study the problem of learning a series of tasks in a fully online Meta-Learning
setting. The goal is to exploit similarities among the tasks to incrementally adapt
an inner online algorithm in order to incur a low averaged cumulative error over
the tasks. We focus on a family of inner algorithms based on a parametrized
variant of online Mirror Descent. The inner algorithm is incrementally adapted
by an online Mirror Descent meta-algorithm using the corresponding within-task
minimum regularized empirical risk as the meta-loss. In order to keep the process
fully online, we approximate the meta-subgradients by the online inner algorithm.
An upper bound on the approximation error allows us to derive a cumulative
error bound for the proposed method. Our analysis can also be converted to the
statistical setting by online-to-batch arguments. We instantiate two examples of the
framework in which the meta-parameter is either a common bias vector or feature
map. Finally, preliminary numerical experiments confirm our theoretical findings.
Outlier-robust estimation of a sparse linear model using \ell_1-penalized Huber's M-estimator
Authors: Arnak Dalalyan, Philip Thompson
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12

We study the problem of estimating a $p$-dimensional 
$s$-sparse vector in a linear model with Gaussian design. 
In the case where the labels are contaminated by at most 
$o$ adversarial outliers, we prove that the $\ell_1$-penalized 
Huber's $M$-estimator based on $n$ samples attains the 
optimal rate of convergence $(s/n)^{1/2} + (o/n)$, up to a 
logarithmic factor. For more general design matrices, our results 
highlight the importance of two properties: the transfer principle
and the incoherence property. These properties with suitable 
constants are shown to yield the optimal rates of robust 
estimation with adversarial contamination.
Variance Reduction in Bipartite Experiments through Correlation Clustering
Authors: Jean Pouget-Abadie, Kevin Aydin, Warren Schudy, Kay Brodersen, Vahab Mirrokni
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12
Tasks: Causal Inference, Clustering

Causal inference in randomized experiments typically assumes that the units of randomization and the units of analysis are one and the same. In some applications, however, these two roles are played by distinct entities linked by a bipartite graph. The key challenge in such bipartite settings is how to avoid interference bias, which would typically arise if we simply randomized the treatment at the level of analysis units. One effective way of minimizing interference bias in standard experiments is through cluster randomization, but this design has not been studied in the bipartite setting where conventional clustering schemes can lead to poorly powered experiments. This paper introduces a novel clustering objective and a corresponding algorithm that partitions a bipartite graph so as to maximize the statistical power of a bipartite experiment on that graph. Whereas previous work relied on balanced partitioning, our formulation suggests the use of a correlation clustering objective. We use a publicly-available graph of Amazon user-item reviews to validate our solution and illustrate how it substantially increases the statistical power in bipartite experiments.
On Differentially Private Graph Sparsification and Applications
Authors: Raman Arora, Jalaj Upadhyay
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12

In this paper, we study private sparsification of graphs. In particular, we give an algorithm that given an input graph, returns a sparse graph which approximates the spectrum of the input graph while ensuring differential privacy. This allows one to solve many graph problems privately yet efficiently and accurately. This is exemplified with application of the proposed meta-algorithm to graph algorithms for privately answering cut-queries, as well as practical algorithms for computing {\scshape MAX-CUT} and {\scshape SPARSEST-CUT} with better accuracy than previously known. We also give the first efficient private algorithm to learn Laplacian eigenmap on a graph.