pwc-archive/papers-with-abstracts huggingface dataset:
First order expansion of convex regularized estimators
Authors: Pierre Bellec, Arun Kuchibhotla
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12
Tasks: Form, regression

We consider first order expansions of convex penalized estimators in
high-dimensional regression problems with random designs. Our setting includes
linear regression and logistic regression as special cases.  For a given
penalty function $h$ and the corresponding penalized estimator $\hbeta$, we
construct a quantity $\eta$, the first order expansion of $\hbeta$, such that
the distance between $\hbeta$ and $\eta$ is an order of magnitude smaller than
the estimation error $\|\hat{\beta} - \beta^*\|$.  In this sense, the first
order expansion $\eta$ can be thought of as a generalization of influence
functions from the mathematical statistics literature to regularized estimators
in high-dimensions.  Such first order expansion implies that the risk of
$\hat{\beta}$ is asymptotically the same as the risk of $\eta$ which leads to a
precise characterization of the MSE of $\hbeta$; this characterization takes a
particularly simple form for isotropic design.  Such first order expansion also
leads to inference results based on $\hat{\beta}$.  We provide sufficient
conditions for the existence of such first order expansion for three
regularizers: the Lasso in its constrained form, the lasso in its penalized
form, and the Group-Lasso.  The results apply to general loss functions under
some conditions and those conditions are satisfied for the squared loss in
linear regression and for the logistic loss in the logistic model.
Practical Differentially Private Top-k Selection with Pay-what-you-get Composition
Authors: David Durfee, Ryan M. Rogers
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12
Tasks: Sensitivity

We study the problem of top-k selection over a large domain universe subject to user-level differential privacy.  Typically, the exponential mechanism or report noisy max are the algorithms used to solve this problem.  However, these algorithms require querying the database for the count of each domain element.  We focus on the setting where the data domain is unknown, which is different than the setting of frequent itemsets where an apriori type algorithm can help prune the space of domain elements to query.  We design algorithms that ensures (approximate) differential privacy and only needs access to the true top-k' elements from the data for any chosen k' ≥ k.  This is a highly desirable feature for making differential privacy practical, since the algorithms require no knowledge of the domain.  We consider both the setting where a user's data can modify an arbitrary number of counts by at most 1, i.e. unrestricted sensitivity, and the setting where a user's data can modify at most some small, fixed number of counts by at most 1, i.e. restricted sensitivity.  Additionally, we provide a pay-what-you-get privacy composition bound for our algorithms.  That is, our algorithms might return fewer than k elements when the top-k elements are queried, but the overall privacy budget only decreases by the size of the outcome set.
Implicit Generation and Modeling with Energy Based Models
Authors: Yilun Du, Igor Mordatch
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12
Tasks: General Classification, Image Generation, Image Reconstruction, Robust classification

Energy based models (EBMs) are appealing due to their generality and simplicity in likelihood modeling, but have been traditionally difficult to train. We present techniques to scale MCMC based EBM training on continuous neural networks, and we show its success on the high-dimensional data domains of ImageNet32x32, ImageNet128x128, CIFAR-10, and robotic hand trajectories, achieving better samples than other likelihood models and nearing the performance of contemporary GAN approaches, while covering all modes of the data. We highlight some unique capabilities of implicit generation such as compositionality and corrupt image reconstruction and inpainting. Finally, we show that EBMs are useful models across a wide variety of tasks, achieving state-of-the-art out-of-distribution classification, adversarially robust classification, state-of-the-art continual online class learning, and coherent long term predicted trajectory rollouts.
Adaptive GNN for Image Analysis and Editing
Authors: Lingyu Liang, Lianwen Jin, Yong Xu
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12
Tasks: Graph Neural Network, Image Enhancement, Low-Light Image Enhancement

Graph neural network (GNN) has powerful representation ability, but optimal configurations of GNN are non-trivial to obtain due to diversity of graph structure and cascaded nonlinearities. This paper aims to understand some properties of GNN from a computer vision (CV) perspective. In mathematical analysis, we propose an adaptive GNN model by recursive definition, and derive its relation with two basic operations in CV: filtering and propagation operations. The proposed GNN model is formulated as a label propagation system with guided map, graph Laplacian and node weight. It reveals that 1) the guided map and node weight determine whether a GNN leads to filtering or propagation diffusion, and 2) the kernel of graph Laplacian controls diffusion pattern. In practical verification, we design a new regularization structure with guided feature to produce GNN-based filtering and propagation diffusion to tackle the ill-posed inverse problems of quotient image analysis (QIA), which recovers the reflectance ratio as a signature for image analysis or adjustment. A flexible QIA-GNN framework is constructed to achieve various image-based editing tasks, like face illumination synthesis and low-light image enhancement. Experiments show the effectiveness of the QIA-GNN, and provide new insights of GNN for image analysis and editing.
Ultra Fast Medoid Identification via Correlated Sequential Halving
Authors: Tavor Baharav, David Tse
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12

The medoid of a set of n points is the point in the set that minimizes the sum of distances to other points. It can be determined exactly in O(n^2) time by computing the distances between all pairs of points. Previous works show that one can significantly reduce the number of distance computations needed by adaptively querying distances. The resulting randomized algorithm is obtained by a direct conversion of the computation problem to a multi-armed bandit statistical inference problem. In this work, we show that we can better exploit the structure of the underlying computation problem by modifying the traditional bandit sampling strategy and using it in conjunction with a suitably chosen multi-armed bandit algorithm. Four to five orders of magnitude gains over exact computation are obtained on real data, in terms of both number of distance computations needed and wall clock time. Theoretical results are obtained to quantify such gains in terms of data parameters. Our code is publicly available online at https://github.com/TavorB/Correlated-Sequential-Halving.
Coda: An End-to-End Neural Program Decompiler
Authors: Cheng Fu, Huili Chen, Haolan Liu, Xinyun Chen, Yuandong Tian, Farinaz Koushanfar, Jishen Zhao
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12
Tasks: Computer Security, Malware Detection

Reverse engineering of binary executables is a critical problem in the computer security domain. On the one hand, malicious parties may recover interpretable source codes from the software products to gain commercial advantages. On the other hand, binary decompilation can be leveraged for code vulnerability analysis and malware detection. However, efficient binary decompilation is challenging. Conventional decompilers have the following major limitations: (i) they are only applicable to specific source-target language pair, hence incurs undesired development cost for new language tasks; (ii) their output high-level code cannot effectively preserve the correct functionality of the input binary; (iii) their output program does not capture the semantics of the input and the reversed program is hard to interpret. To address the above problems, we propose Coda1, the first end-to-end neural-based framework for code decompilation. Coda decomposes the decompilation task into of two key phases: First, Coda employs an instruction type-aware encoder and a tree decoder for generating an abstract syntax tree (AST) with attention feeding during the code sketch generation stage. Second, Coda then updates the code sketch using an iterative error correction machine guided by an ensembled neural error predictor. By finding a good approximate candidate and then fixing it towards perfect, Coda achieves superior with performance compared to baseline approaches. We assess Coda’s performance with extensive experiments on various benchmarks. Evaluation results show that Coda achieves an average of 82% program recovery accuracy on unseen binary samples, where the state-of-the-art decompilers yield 0% accuracy. Furthermore, Coda outperforms the sequence-to-sequence model with attention by a margin of 70% program accuracy. Our work reveals the vulnerability of binary executables and imposes a new threat to the protection of Intellectual Property (IP) for software development.
Bat-G net: Bat-inspired High-Resolution 3D Image Reconstruction using Ultrasonic Echoes
Authors: Gunpil Hwang, Seohyeon Kim, Hyeon-Min Bae
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12
Tasks: 3D Reconstruction, Decoder, Image Reconstruction

In this paper, a bat-inspired high-resolution ultrasound 3D imaging system is presented. Live bats demonstrate that the properly used ultrasound can be used to perceive 3D space. With this in mind, a neural network referred to as a Bat-G network is implemented to reconstruct the 3D representation of target objects from the hyperbolic FM (HFM) chirped ultrasonic echoes. The Bat-G network consists of an encoder emulating a bat's central auditory pathway, and a 3D graphical visualization decoder. For the acquisition of the ultrasound data, a custom-made Bat-I sensor module is used. The Bat-G network shows the uniform 3D reconstruction results and achieves precision, recall, and F1-score of 0.896, 0.899 and 0.895, respectively. The experimental results demonstrate the implementation feasibility of a high-resolution non-optical sound-based imaging system being used by live bats. The project web page (https://sites.google.com/view/batgnet) contains additional content summarizing our research.
Privacy-Preserving Classification of Personal Text Messages with Secure Multi-Party Computation
Authors: Devin Reich, Ariel Todoki, Rafael Dowsley, Martine De Cock, Anderson Nascimento
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12
Tasks: Classification, General Classification, Privacy Preserving, text-classification, Text Classification

Classification of personal text messages has many useful applications in surveillance, e-commerce, and mental health care, to name a few. Giving applications access to personal texts can easily lead to (un)intentional privacy violations. We propose the first privacy-preserving solution for text classification that is provably secure. Our method, which is based on Secure Multiparty Computation (SMC), encompasses both feature extraction from texts, and subsequent classification with logistic regression and tree ensembles. We prove that when using our secure text classification method, the application does not learn anything about the text, and the author of the text does not learn anything about the text classification model used by the application beyond what is given by the classification result itself. We perform end-to-end experiments with an application for detecting hate speech against women and immigrants, demonstrating excellent runtime results without loss of accuracy.
Learning Representations for Time Series Clustering
Authors: Qianli Ma, Jiawei Zheng, Sen Li, Gary W. Cottrell
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12
Tasks: Anomaly Detection, Clustering, Open-Ended Question Answering, Representation Learning, Time Series, Time Series Analysis, Time Series Clustering

Time series clustering is an essential unsupervised technique in cases when category information is not available. It has been widely applied to genome data, anomaly detection, and in general, in any domain where pattern detection is important. Although feature-based time series clustering methods are robust to noise and outliers, and can reduce the  dimensionality of the data, they typically rely on domain knowledge to manually construct high-quality features. Sequence to sequence (seq2seq) models can learn representations from sequence data in an unsupervised manner by designing appropriate learning objectives, such as reconstruction and context prediction. When applying seq2seq to time series clustering, obtaining a representation that effectively represents the temporal dynamics of the sequence, multi-scale features, and good clustering properties remains a challenge. How to best improve the ability of the encoder is still an open question. Here we propose a novel unsupervised temporal representation learning model, named Deep Temporal Clustering Representation (DTCR), which integrates the temporal reconstruction and K-means objective into the seq2seq model. This approach leads to improved cluster structures and thus obtains cluster-specific temporal representations. Also, to enhance the ability of encoder, we propose a fake-sample generation strategy and auxiliary classification task. Experiments conducted on extensive time series datasets show that DTCR is state-of-the-art compared to existing methods. The visualization analysis not only shows the effectiveness of cluster-specific representation but also shows the learning process is robust, even if K-means makes mistakes.
A Normative Theory for Causal Inference and Bayes Factor Computation in Neural Circuits
Authors: Wenhao Zhang, Si Wu, Brent Doiron, Tai Sing Lee
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12
Tasks: Causal Inference, Model Selection

This study provides a normative theory for how Bayesian causal inference can be implemented in neural circuits. In both cognitive processes such as causal reasoning and perceptual inference such as cue integration, the nervous systems need to choose different models representing the underlying causal structures when making inferences on external stimuli. In multisensory processing, for example, the nervous system has to choose whether to integrate or segregate inputs from different sensory modalities to infer the sensory stimuli, based on whether the inputs are from the same or different sources. Making this choice is a model selection problem requiring the computation of Bayes factor, the ratio of likelihoods between the integration and the segregation models. In this paper, we consider the causal inference in multisensory processing and propose a novel generative model based on neural population code that takes into account both stimulus feature and stimulus reliability in the inference. In the case of circular variables such as heading direction, our normative theory yields an analytical solution for computing the Bayes factor, with a clear geometric interpretation, which can be implemented by simple additive mechanisms with neural population code. Numerical simulation shows that the tunings of the neurons computing Bayes factor are consistent with the "opposite neurons" discovered in dorsal medial superior temporal (MSTd) and the ventral intraparietal (VIP) areas for visual-vestibular processing. This study illuminates a potential neural mechanism for causal inference in the brain.
Stochastic Gradient Hamiltonian Monte Carlo Methods with Recursive Variance Reduction
Authors: Difan Zou, Pan Xu, Quanquan Gu
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12

Stochastic Gradient Hamiltonian Monte Carlo (SGHMC) algorithms have received increasing attention in both theory and practice. In this paper, we  propose a Stochastic Recursive Variance-Reduced gradient HMC (SRVR-HMC) algorithm. It makes use of a semi-stochastic gradient estimator that recursively accumulates the gradient information to reduce the variance of the stochastic gradient. We provide a convergence analysis of SRVR-HMC for sampling from a class of non-log-concave distributions and show that SRVR-HMC converges faster than all existing HMC-type algorithms based on underdamped Langevin dynamics. Thorough experiments on synthetic and real-world datasets validate our theory and demonstrate the superiority of SRVR-HMC.
Domes to Drones: Self-Supervised Active Triangulation for 3D Human Pose Reconstruction
Authors: Aleksis Pirinen, Erik Gärtner, Cristian Sminchisescu
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12
Tasks: 2D Pose Estimation, 3D Pose Estimation, 3D Reconstruction, Deep Reinforcement Learning, Pose Estimation, Reinforcement Learning

Existing state-of-the-art estimation systems can detect 2d poses of multiple people in images quite reliably. In contrast, 3d pose estimation from a single image is ill-posed due to occlusion and depth ambiguities. Assuming access to multiple cameras, or given an active system able to position itself to observe the scene from multiple viewpoints, reconstructing 3d pose from 2d measurements becomes well-posed within the framework of standard multi-view geometry. Less clear is what is an informative set of viewpoints for accurate 3d reconstruction, particularly in complex scenes, where people are occluded by others or by scene objects. In order to address the view selection problem in a principled way, we here introduce ACTOR, an active triangulation agent for 3d human pose reconstruction. Our fully trainable agent consists of a 2d pose estimation network (any of which would work) and a deep reinforcement learning-based policy for camera viewpoint selection. The policy predicts observation viewpoints, the number of which varies adaptively depending on scene content, and the associated images are fed to an underlying pose estimator. Importantly, training the policy requires no annotations - given a 2d pose estimator, ACTOR is trained in a self-supervised manner. In extensive evaluations on complex multi-people scenes filmed in a Panoptic dome, under multiple viewpoints, we compare our active triangulation agent to strong multi-view baselines, and show that ACTOR produces significantly more accurate 3d pose reconstructions. We also provide a proof-of-concept experiment indicating the potential of connecting our view selection policy to a physical drone observer.
MetaQuant: Learning to Quantize by Learning to Penetrate Non-differentiable Quantization
Authors: Shangyu Chen, Wenya Wang, Sinno Jialin Pan
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12
Tasks: Quantization

Tremendous amount of parameters make deep neural networks impractical to be deployed for edge-device-based real-world applications due to the limit of computational power and storage space. Existing studies have made progress on learning quantized deep models to reduce model size and energy consumption, i.e. converting full-precision weights ($r$'s) into discrete values ($q$'s) in a supervised training manner. However, the training process for quantization is non-differentiable, which leads to either infinite or zero gradients ($g_r$) w.r.t. $r$. To address this problem, most training-based quantization methods use the gradient w.r.t. $q$ ($g_q$) with clipping to approximate $g_r$ by Straight-Through-Estimator (STE) or manually design their computation. However, these methods only heuristically make training-based quantization applicable, without further analysis on how the approximated gradients can assist training of a quantized network. In this paper, we propose to learn $g_r$ by a neural network. Specifically, a meta network is trained using $g_q$ and $r$ as inputs, and outputs $g_r$ for subsequent weight updates. The meta network is updated together with the original quantized network. Our proposed method alleviates the problem of non-differentiability, and can be trained in an end-to-end manner. Extensive experiments are conducted with CIFAR10/100 and ImageNet on various deep networks to demonstrate the advantage of our proposed method in terms of a faster convergence rate and better performance. Codes are released at: \texttt{https://github.com/csyhhu/MetaQuant}
A First-Order Algorithmic Framework for Distributionally Robust Logistic Regression
Authors: Jiajin Li, Sen Huang, Anthony Man-Cho So
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12
Tasks: regression

Wasserstein distance-based distributionally robust optimization (DRO) has received much attention lately due to its ability to provide a robustness interpretation of various learning models. Moreover, many of the DRO problems that arise in the learning context admits exact convex reformulations and hence can be tackled by off-the-shelf solvers. Nevertheless, the use of such solvers severely limits the applicability of DRO in large-scale learning problems, as they often rely on general purpose interior-point algorithms. On the other hand, there are very few works that attempt to develop fast iterative methods to solve these DRO problems, which typically possess complicated structures. In this paper, we take a first step towards resolving the above difficulty by developing a first-order algorithmic framework for tackling a class of Wasserstein distance-based distributionally robust logistic regression (DRLR) problem. Specifically, we propose a novel linearized proximal ADMM to solve the DRLR problem, whose objective is convex but consists of a smooth term plus two non-separable non-smooth terms. We prove that our method enjoys a sublinear convergence rate. Furthermore, we conduct three different experiments to show its superb performance on both synthetic and real-world datasets. In particular, our method can achieve the same accuracy up to 800+ times faster than the standard off-the-shelf solver.
Learning Generalizable Device Placement Algorithms for Distributed Machine Learning
Authors: Ravichandra Addanki, Shaileshh Bojja Venkatakrishnan, Shreyan Gupta, Hongzi Mao, Mohammad Alizadeh
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12
Tasks: BIG-bench Machine Learning, Reinforcement Learning, Reinforcement Learning (RL)

We present Placeto, a reinforcement learning (RL) approach to
efficiently find device placements for distributed neural network training.

Unlike prior approaches that only find a device placement for a specific computation graph, Placeto can learn generalizable device placement policies that can be applied to any graph.

We propose two key ideas in our approach:
(1) we represent the policy as performing iterative placement improvements, rather than outputting a placement in one shot;
(2) we use graph embeddings to capture relevant information about the  structure of the computation graph, without relying on node labels for indexing.

These ideas allow Placeto to train efficiently and generalize
to unseen graphs.

Our experiments show that Placeto requires up to 6.1x
fewer training steps to find placements that are on par with or
better than the best placements found by prior approaches.
Moreover, Placeto is able to learn a generalizable placement policy for any given family of graphs that can be used without any re-training to predict optimized placements for unseen graphs from the same family. 

This eliminates the huge overhead incurred by the prior RL approaches whose lack of generalizability necessitates re-training from scratch every time a new graph is to be placed.