pwc-archive/papers-with-abstracts huggingface dataset:
Learning Interpretable Models with Causal Guarantees
Authors: Carolyn Kim, Osbert Bastani
Date: 2019-01-24 00:00:00
Tasks: BIG-bench Machine Learning, Decision Making

Machine learning has shown much promise in helping improve the quality of medical, legal, and financial decision-making. In these applications, machine learning models must satisfy two important criteria: (i) they must be causal, since the goal is typically to predict individual treatment effects, and (ii) they must be interpretable, so that human decision makers can validate and trust the model predictions. There has recently been much progress along each direction independently, yet the state-of-the-art approaches are fundamentally incompatible. We propose a framework for learning interpretable models from observational data that can be used to predict individual treatment effects (ITEs). In particular, our framework converts any supervised learning algorithm into an algorithm for estimating ITEs. Furthermore, we prove an error bound on the treatment effects predicted by our model. Finally, in an experiment on real-world data, we show that the models trained using our framework significantly outperform a number of baselines.
Theoretically Principled Trade-off between Robustness and Accuracy
Authors: Hongyang Zhang, Yaodong Yu, Jiantao Jiao, Eric P. Xing, Laurent El Ghaoui, Michael. I. Jordan
Date: 2019-01-24 00:00:00
Tasks: Adversarial Attack, Adversarial Defense, Adversarial Robustness, General Classification

We identify a trade-off between robustness and accuracy that serves as a guiding principle in the design of defenses against adversarial examples. Although this problem has been widely studied empirically, much remains unknown concerning the theory underlying this trade-off. In this work, we decompose the prediction error for adversarial examples (robust error) as the sum of the natural (classification) error and boundary error, and provide a differentiable upper bound using the theory of classification-calibrated loss, which is shown to be the tightest possible upper bound uniform over all probability distributions and measurable predictors. Inspired by our theoretical analysis, we also design a new defense method, TRADES, to trade adversarial robustness off against accuracy. Our proposed algorithm performs well experimentally in real-world datasets. The methodology is the foundation of our entry to the NeurIPS 2018 Adversarial Vision Challenge in which we won the 1st place out of ~2,000 submissions, surpassing the runner-up approach by $11.41\%$ in terms of mean $\ell_2$ perturbation distance.
Nonparametric Inference under B-bits Quantization
Authors: Kexuan Li, Ruiqi Liu, Ganggang Xu, Zuofeng Shang
Date: 2019-01-24 00:00:00
Tasks: Quantization

Statistical inference based on lossy or incomplete samples is often needed in research areas such as signal/image processing, medical image storage, remote sensing, signal transmission. In this paper, we propose a nonparametric testing procedure based on samples quantized to $B$ bits through a computationally efficient algorithm. Under mild technical conditions, we establish the asymptotic properties of the proposed test statistic and investigate how the testing power changes as $B$ increases. In particular, we show that if $B$ exceeds a certain threshold, the proposed nonparametric testing procedure achieves the classical minimax rate of testing (Shang and Cheng, 2015) for spline models. We further extend our theoretical investigations to a nonparametric linearity test and an adaptive nonparametric test, expanding the applicability of the proposed methods. Extensive simulation studies {together with a real-data analysis} are used to demonstrate the validity and effectiveness of the proposed tests.
Width Provably Matters in Optimization for Deep Linear Neural Networks
Authors: Simon S. Du, Wei Hu
Date: 2019-01-24 00:00:00

We prove that for an $L$-layer fully-connected linear neural network, if the width of every hidden layer is $\tilde\Omega (L \cdot r \cdot d_{\mathrm{out}} \cdot \kappa^3 )$, where $r$ and $\kappa$ are the rank and the condition number of the input data, and $d_{\mathrm{out}}$ is the output dimension, then gradient descent with Gaussian random initialization converges to a global minimum at a linear rate. The number of iterations to find an $\epsilon$-suboptimal solution is $O(\kappa \log(\frac{1}{\epsilon}))$. Our polynomial upper bound on the total running time for wide deep linear networks and the $\exp\left(\Omega\left(L\right)\right)$ lower bound for narrow deep linear neural networks [Shamir, 2018] together demonstrate that wide layers are necessary for optimizing deep models.
End-to-End Optimized Transmission over Dispersive Intensity-Modulated Channels Using Bidirectional Recurrent Neural Networks
Authors: Boris Karanov, Domaniç Lavery, Polina Bayvel, Laurent Schmalen
Date: 2019-01-24 00:00:00

We propose an autoencoding sequence-based transceiver for communication over
dispersive channels with intensity modulation and direct detection (IM/DD),
designed as a bidirectional deep recurrent neural network (BRNN). The receiver
uses a sliding window technique to allow for efficient data stream estimation.
We find that this sliding window BRNN (SBRNN), based on end-to-end deep
learning of the communication system, achieves a significant bit-error-rate
reduction at all examined distances in comparison to previous block-based
autoencoders implemented as feed-forward neural networks (FFNNs), leading to an
increase of the transmission distance. We also compare the end-to-end SBRNN
with a state-of-the-art IM/DD solution based on two level pulse amplitude
modulation with an FFNN receiver, simultaneously processing multiple received
symbols and approximating nonlinear Volterra equalization. Our results show
that the SBRNN outperforms such systems at both 42 and 84\,Gb/s, while training
fewer parameters. Our novel SBRNN design aims at tailoring the end-to-end deep
learning-based systems for communication over nonlinear channels with memory,
such as the optical IM/DD fiber channel.
Algorithms for Fairness in Sequential Decision Making
Authors: Min Wen, Osbert Bastani, Ufuk Topcu
Date: 2019-01-24 00:00:00
Tasks: Decision Making, Fairness, Reinforcement Learning, Sequential Decision Making

It has recently been shown that if feedback effects of decisions are ignored, then imposing fairness constraints such as demographic parity or equality of opportunity can actually exacerbate unfairness. We propose to address this challenge by modeling feedback effects as Markov decision processes (MDPs). First, we propose analogs of fairness properties for the MDP setting. Second, we propose algorithms for learning fair decision-making policies for MDPs. Finally, we demonstrate the need to account for dynamical effects using simulations on a loan applicant MDP.
Learning Neurosymbolic Generative Models via Program Synthesis
Authors: Halley Young, Osbert Bastani, Mayur Naik
Date: 2019-01-24 00:00:00
Proceeding: ICLR Workshop drlStructPred 2019 5
Tasks: Program Synthesis

Significant strides have been made toward designing better generative models
in recent years. Despite this progress, however, state-of-the-art approaches
are still largely unable to capture complex global structure in data. For
example, images of buildings typically contain spatial patterns such as windows
repeating at regular intervals; state-of-the-art generative methods can't
easily reproduce these structures. We propose to address this problem by
incorporating programs representing global structure into the generative
model---e.g., a 2D for-loop may represent a configuration of windows.
Furthermore, we propose a framework for learning these models by leveraging
program synthesis to generate training data. On both synthetic and real-world
data, we demonstrate that our approach is substantially better than the
state-of-the-art at both generating and completing images that contain global
structure.
Sample Complexity of Estimating the Policy Gradient for Nearly Deterministic Dynamical Systems
Authors: Osbert Bastani
Date: 2019-01-24 00:00:00
Tasks: reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

Reinforcement learning is a promising approach to learning robotics controllers. It has recently been shown that algorithms based on finite-difference estimates of the policy gradient are competitive with algorithms based on the policy gradient theorem. We propose a theoretical framework for understanding this phenomenon. Our key insight is that many dynamical systems (especially those of interest in robotics control tasks) are nearly deterministic -- i.e., they can be modeled as a deterministic system with a small stochastic perturbation. We show that for such systems, finite-difference estimates of the policy gradient can have substantially lower variance than estimates based on the policy gradient theorem. Finally, we empirically evaluate our insights in an experiment on the inverted pendulum.
Semi-Unsupervised Learning: Clustering and Classifying using Ultra-Sparse Labels
Authors: Matthew Willetts, Stephen J. Roberts, Christopher C. Holmes
Date: 2019-01-24 00:00:00
Tasks: Clustering

In semi-supervised learning for classification, it is assumed that every ground truth class of data is present in the small labelled dataset. Many real-world sparsely-labelled datasets are plausibly not of this type. It could easily be the case that some classes of data are found only in the unlabelled dataset -- perhaps the labelling process was biased -- so we do not have any labelled examples to train on for some classes. We call this learning regime $\textit{semi-unsupervised learning}$, an extreme case of semi-supervised learning, where some classes have no labelled exemplars in the training set. First, we outline the pitfalls associated with trying to apply deep generative model (DGM)-based semi-supervised learning algorithms to datasets of this type. We then show how a combination of clustering and semi-supervised learning, using DGMs, can be brought to bear on this problem. We study several different datasets, showing how one can still learn effectively when half of the ground truth classes are entirely unlabelled and the other half are sparsely labelled.
General Supervision via Probabilistic Transformations
Authors: Santiago Mazuelas, Aritz Perez
Date: 2019-01-24 00:00:00
Tasks: Classification, General Classification

Different types of training data have led to numerous schemes for supervised
classification. Current learning techniques are tailored to one specific scheme
and cannot handle general ensembles of training data. This paper presents a
unifying framework for supervised classification with general ensembles of
training data, and proposes the learning methodology of generalized robust risk
minimization (GRRM). The paper shows how current and novel supervision schemes
can be addressed under the proposed framework by representing the relationship
between examples at test and training via probabilistic transformations. The
results show that GRRM can handle different types of training data in a unified
manner, and enable new supervision schemes that aggregate general ensembles of
training data.
Learning Space Partitions for Nearest Neighbor Search
Authors: Yihe Dong, Piotr Indyk, Ilya Razenshteyn, Tal Wagner
Date: 2019-01-24 00:00:00
Proceeding: ICLR 2020 1
Tasks: General Classification, graph partitioning, Quantization

Space partitions of $\mathbb{R}^d$ underlie a vast and important class of fast nearest neighbor search (NNS) algorithms. Inspired by recent theoretical work on NNS for general metric spaces [Andoni, Naor, Nikolov, Razenshteyn, Waingarten STOC 2018, FOCS 2018], we develop a new framework for building space partitions reducing the problem to balanced graph partitioning followed by supervised classification. We instantiate this general approach with the KaHIP graph partitioner [Sanders, Schulz SEA 2013] and neural networks, respectively, to obtain a new partitioning procedure called Neural Locality-Sensitive Hashing (Neural LSH). On several standard benchmarks for NNS, our experiments show that the partitions obtained by Neural LSH consistently outperform partitions found by quantization-based and tree-based methods as well as classic, data-oblivious LSH.
Causal Mediation Analysis Leveraging Multiple Types of Summary Statistics Data
Authors: Yongjin Park, Abhishek Sarkar, Khoi Nguyen, Manolis Kellis
Date: 2019-01-24 00:00:00
Tasks: Causal Inference

Summary statistics of genome-wide association studies (GWAS) teach causal
relationship between millions of genetic markers and tens and thousands of
phenotypes. However, underlying biological mechanisms are yet to be elucidated.
We can achieve necessary interpretation of GWAS in a causal mediation
framework, looking to establish a sparse set of mediators between genetic and
downstream variables, but there are several challenges. Unlike existing methods
rely on strong and unrealistic assumptions, we tackle practical challenges
within a principled summary-based causal inference framework. We analyzed the
proposed methods in extensive simulations generated from real-world genetic
data. We demonstrated only our approach can accurately redeem causal genes,
even without knowing actual individual-level data, despite the presence of
competing non-causal trails.
Learning Disentangled Representations with Reference-Based Variational Autoencoders
Authors: Adria Ruiz, Oriol Martinez, Xavier Binefa, Jakob Verbeek
Date: 2019-01-24 00:00:00
Tasks: Attribute, Conditional Image Generation, Image Generation

Learning disentangled representations from visual data, where different
high-level generative factors are independently encoded, is of importance for
many computer vision tasks. Solving this problem, however, typically requires
to explicitly label all the factors of interest in training images. To
alleviate the annotation cost, we introduce a learning setting which we refer
to as "reference-based disentangling". Given a pool of unlabeled images, the
goal is to learn a representation where a set of target factors are
disentangled from others. The only supervision comes from an auxiliary
"reference set" containing images where the factors of interest are constant.
In order to address this problem, we propose reference-based variational
autoencoders, a novel deep generative model designed to exploit the
weak-supervision provided by the reference set. By addressing tasks such as
feature learning, conditional image generation or attribute transfer, we
validate the ability of the proposed model to learn disentangled
representations from this minimal form of supervision.
Curvature-Exploiting Acceleration of Elastic Net Computations
Authors: Vien V. Mai, Mikael Johansson
Date: 2019-01-24 00:00:00

This paper introduces an efficient second-order method for solving the
elastic net problem. Its key innovation is a computationally efficient
technique for injecting curvature information in the optimization process which
admits a strong theoretical performance guarantee. In particular, we show
improved run time over popular first-order methods and quantify the speed-up in
terms of statistical measures of the data matrix. The improved time complexity
is the result of an extensive exploitation of the problem structure and a
careful combination of second-order information, variance reduction techniques,
and momentum acceleration. Beside theoretical speed-up, experimental results
demonstrate great practical performance benefits of curvature information,
especially for ill-conditioned data sets.
Learning from Multiple Cities: A Meta-Learning Approach for Spatial-Temporal Prediction
Authors: Huaxiu Yao, Yiding Liu, Ying WEI, Xianfeng Tang, Zhenhui Li
Date: 2019-01-24 00:00:00
Tasks: Meta-Learning, Prediction, Transfer Learning

Spatial-temporal prediction is a fundamental problem for constructing smart city, which is useful for tasks such as traffic control, taxi dispatching, and environmental policy making. Due to data collection mechanism, it is common to see data collection with unbalanced spatial distributions. For example, some cities may release taxi data for multiple years while others only release a few days of data; some regions may have constant water quality data monitored by sensors whereas some regions only have a small collection of water samples. In this paper, we tackle the problem of spatial-temporal prediction for the cities with only a short period of data collection. We aim to utilize the long-period data from other cities via transfer learning. Different from previous studies that transfer knowledge from one single source city to a target city, we are the first to leverage information from multiple cities to increase the stability of transfer. Specifically, our proposed model is designed as a spatial-temporal network with a meta-learning paradigm. The meta-learning paradigm learns a well-generalized initialization of the spatial-temporal network, which can be effectively adapted to target cities. In addition, a pattern-based spatial-temporal memory is designed to distill long-term temporal information (i.e., periodicity). We conduct extensive experiments on two tasks: traffic (taxi and bike) prediction and water quality prediction. The experiments demonstrate the effectiveness of our proposed model over several competitive baseline models.
A Unified Analysis of Extra-gradient and Optimistic Gradient Methods for Saddle Point Problems: Proximal Point Approach
Authors: Aryan Mokhtari, Asuman Ozdaglar, Sarath Pattathil
Date: 2019-01-24 00:00:00

In this paper we consider solving saddle point problems using two variants of Gradient Descent-Ascent algorithms, Extra-gradient (EG) and Optimistic Gradient Descent Ascent (OGDA) methods. We show that both of these algorithms admit a unified analysis as approximations of the classical proximal point method for solving saddle point problems. This viewpoint enables us to develop a new framework for analyzing EG and OGDA for bilinear and strongly convex-strongly concave settings. Moreover, we use the proximal point approximation interpretation to generalize the results for OGDA for a wide range of parameters.
Maximum Entropy Generators for Energy-Based Models
Authors: Rithesh Kumar, Sherjil Ozair, Anirudh Goyal, Aaron Courville, Yoshua Bengio
Date: 2019-01-24 00:00:00
Tasks: Anomaly Detection

Maximum likelihood estimation of energy-based models is a challenging problem due to the intractability of the log-likelihood gradient. In this work, we propose learning both the energy function and an amortized approximate sampling mechanism using a neural generator network, which provides an efficient approximation of the log-likelihood gradient. The resulting objective requires maximizing entropy of the generated samples, which we perform using recently proposed nonparametric mutual information estimators. Finally, to stabilize the resulting adversarial game, we use a zero-centered gradient penalty derived as a necessary condition from the score matching literature. The proposed technique can generate sharp images with Inception and FID scores competitive with recent GAN techniques, does not suffer from mode collapse, and is competitive with state-of-the-art anomaly detection techniques.
Never Forget: Balancing Exploration and Exploitation via Learning Optical Flow
Authors: Hsuan-Kung Yang, Po-Han Chiang, Kuan-Wei Ho, Min-Fong Hong, Chun-Yi Lee
Date: 2019-01-24 00:00:00
Tasks: Deep Reinforcement Learning, Optical Flow Estimation, Reinforcement Learning

Exploration bonus derived from the novelty of the states in an environment
has become a popular approach to motivate exploration for deep reinforcement
learning agents in the past few years. Recent methods such as curiosity-driven
exploration usually estimate the novelty of new observations by the prediction
errors of their system dynamics models. Due to the capacity limitation of the
models and difficulty of performing next-frame prediction, however, these
methods typically fail to balance between exploration and exploitation in
high-dimensional observation tasks, resulting in the agents forgetting the
visited paths and exploring those states repeatedly. Such inefficient
exploration behavior causes significant performance drops, especially in large
environments with sparse reward signals. In this paper, we propose to introduce
the concept of optical flow estimation from the field of computer vision to
deal with the above issue. We propose to employ optical flow estimation errors
to examine the novelty of new observations, such that agents are able to
memorize and understand the visited states in a more comprehensive fashion. We
compare our method against the previous approaches in a number of experimental
experiments. Our results indicate that the proposed method appears to deliver
superior and long-lasting performance than the previous methods. We further
provide a set of comprehensive ablative analysis of the proposed method, and
investigate the impact of optical flow estimation on the learning curves of the
DRL agents.
On the Transformation of Latent Space in Autoencoders
Authors: Jaehoon Cha, Kyeong Soo Kim, Sanghyuk Lee
Date: 2019-01-24 00:00:00
Tasks: Denoising

Noting the importance of the latent variables in inference and learning, we propose a novel framework for autoencoders based on the homeomorphic transformation of latent variables, which could reduce the distance between vectors in the transformed space, while preserving the topological properties of the original space, and investigate the effect of the latent space transformation on learning generative models and denoising corrupted data. The experimental results demonstrate that our generative and denoising models based on the proposed framework can provide better performance than conventional variational and denoising autoencoders due to the transformation, where we evaluate the performance of generative and denoising models in terms of the Hausdorff distance between the sets of training and processed i.e., either generated or denoised images, which can objectively measure their differences, as well as through direct comparison of the visual characteristics of the processed images.
Deep Generative Learning via Variational Gradient Flow
Authors: Yuan Gao, Yuling Jiao, Yang Wang, Yao Wang, Can Yang, Shunkang Zhang
Date: 2019-01-24 00:00:00
Tasks: Binary Classification

We propose a general framework to learn deep generative models via \textbf{V}ariational \textbf{Gr}adient Fl\textbf{ow} (VGrow) on probability spaces. The evolving distribution that asymptotically converges to the target distribution is governed by a vector field, which is the negative gradient of the first variation of the $f$-divergence between them. We prove that the evolving distribution coincides with the pushforward distribution through the infinitesimal time composition of residual maps that are perturbations of the identity map along the vector field. The vector field depends on the density ratio of the pushforward distribution and the target distribution, which can be consistently learned from a binary classification problem. Connections of our proposed VGrow method with other popular methods, such as VAE, GAN and flow-based methods, have been established in this framework, gaining new insights of deep generative learning. We also evaluated several commonly used divergences, including Kullback-Leibler, Jensen-Shannon, Jeffrey divergences as well as our newly discovered `logD' divergence which serves as the objective function of the logD-trick GAN. Experimental results on benchmark datasets demonstrate that VGrow can generate high-fidelity images in a stable and efficient manner, achieving competitive performance with state-of-the-art GANs.