pwc-archive/papers-with-abstracts huggingface dataset:
Simple and Scalable Epistemic Uncertainty Estimation Using a Single Deep Deterministic Neural Network
Authors: Joost van Amersfoort, Lewis Smith, Yee Whye Teh, Yarin Gal
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: Uncertainty Quantification

We propose a method for training a deterministic deep model that can find and reject out of distribution data points at test time with a single forward pass. Our approach, deterministic uncertainty quantification (DUQ), builds upon ideas of RBF networks. We scale training in these with a novel loss function and centroid updating scheme. By enforcing detectability of changes in the input using a gradient penalty, we are able to reliably detect out of distribution data. Our uncertainty quantification scales well to large datasets, and using a single model, we improve upon Deep Ensembles on notable difficult dataset pairs such as FashionMNIST vs. MNIST, and CIFAR-10 vs. SVHN, while maintaining competitive accuracy.
Temporal Logic Point Processes
Authors: Shuang Li, Lu Wang, Ruizhi Zhang, xiaofu Chang, Xuqin Liu, Yao Xie, Yuan Qi, Le Song
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: Point Processes

We propose a modeling framework for event data, which excels in small data regime with the ability to incorporate domain knowledge. Our framework will model the intensities of the event starts and ends via a set of first-order temporal logic rules. Using softened representation of temporal relations, and a weighted combination of logic rules, our framework can also deal with uncertainty in event data. Furthermore, many existing point process models can be interpreted as special cases of our framework given simple temporal logic rules. We derive a maximum likelihood estimation procedure for our model, and show that it can lead to accurate predictions when data are sparse and domain knowledge is critical.
Compressive sensing with un-trained neural networks: Gradient descent finds a smooth approximation
Authors: Reinhard Heckel, Mahdi Soltanolkotabi
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: Compressive Sensing, Denoising

Un-trained convolutional neural networks have emerged as highly successful tools for image recovery and restoration. They are capable of solving standard inverse problems such as denoising and compressive sensing with excellent results by simply fitting a neural network model to measurements from a single image or signal without the need for any additional training data. For some applications, this critically requires additional regularization in the form of early stopping the optimization. For signal recovery from a few measurements, however, un-trained convolutional networks have an intriguing self-regularizing property: Even though the network can perfectly fit any image, the network recovers a natural image from few measurements when trained with gradient descent until convergence. In this paper, we demonstrate this property numerically and study it theoretically. We show that---without any further regularization---an un-trained convolutional neural network can approximately reconstruct signals and images that are sufficiently structured, from a near minimal number of random measurements.
On the Iteration Complexity of Hypergradient Computations
Authors: Riccardo Grazzi, Saverio Salzo, Massimiliano Pontil, Luca Franceschi
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: Bilevel Optimization, Computational Efficiency, Meta-Learning

We study a general class of bilevel optimization problems, in which the upper-level objective is defined via the solution of a fixed point equation. Important instances arising in machine learning include hyper-parameter optimization, meta-learning, graph and recurrent neural networks. Typically the gradient of the upper-level objective is not known explicitly or is hard to compute exactly, which has raised the interest in approximation methods. We investigate two popular approaches to compute the hypergradient, based on reverse mode iterative differentiation and approximate implicit differentiation. We present a unified analysis which allows for the first time to quantitatively compare these methods, providing explicit bounds for their iteration complexity. This analysis suggests a hierarchy in terms of computational efficiency among the above methods, with approximate implicit differentiation based on conjugate gradient performing best. We present an extensive experimental comparison among the methods which confirm the theoretical findings.
Optimal Estimator for Unlabeled Linear Regression
Authors: Hang Zhang, Ping Li
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: regression

Unlabeled linear regression, or ``linear regression with an  unknown permutation'',  has attracted increasing  attentions due to its applications in linkage record and
de-anonymization.  However, its computation proves to be cumbersome and
all existing algorithms require considerable time in the  high dimensional regime. 
This paper proposes a one-step estimator which  are optimal from both the computational and statistical  sense.  From the computational perspective, our estimator  exhibits the same order of computational time  as that of the oracle case, where the covariates are known in advance and only the permutation 
needs recovery.  From the statistical  perspective, when comparing with the necessary conditions for permutation recovery,  our requirement on \emph{signal-to-noise ratio} ($\snr$) agrees up to $O\bracket{\log \log n}$ difference  in certain regimes.  Numerical experiments have also been provided to  corroborate the above claims.
OPtions as REsponses: Grounding behavioural hierarchies in multi-agent reinforcement learning
Authors: Alexander Vezhnevets, Yuhuai Wu, Maria Eckstein, Rémi Leblond, Joel Z. Leibo
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: Deep Reinforcement Learning, Multi-agent Reinforcement Learning, reinforcement-learning, Reinforcement Learning (RL)

This paper investigates generalisation in multi-agent games, where the generality of the agent can be evaluated by playing against opponents it hasn't seen during training. We propose two new games with concealed information and complex, non-transitive reward structure (think rock-paper-scissors). It turns out that most current deep reinforcement learning methods fail to efficiently explore the strategy space, thus learning policies that generalise poorly to unseen opponents. We then propose a novel hierarchical agent architecture, where the hierarchy is grounded in the game-theoretic structure of the game -- the top level chooses strategic responses to opponents, while the low level implements them into policy over primitive actions. This grounding facilitates credit assignment across the levels of hierarchy. Our experiments show that the proposed hierarchical agent is capable of generalisation to unseen opponents, while conventional baselines fail to generalise whatsoever.
Simple and sharp analysis of k-means||
Authors: Vaclav Rozhon
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1

We present a truly simple analysis of k-means|| (Bahmani et al., PVLDB 2012) -- a distributed variant of the k-means++ algorithm (Arthur and Vassilvitskii, SODA 2007) -- and improve its round complexity from O(log (Var X)), where Var X is the variance of the input data set, to O(log (Var X) / log log (Var X)), which we show to be tight.
Why Are Learned Indexes So Effective?
Authors: Paolo Ferragina, Fabrizio Lillo, Giorgio Vinciguerra
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1

A recent trend in algorithm design consists of augmenting classic data structures with machine learning models, which are better suited to reveal and exploit patterns and trends in the input data so to achieve outstanding practical improvements in space occupancy and time efficiency.  
This is especially known in the context of indexing data structures where, despite few attempts in evaluating their asymptotic efficiency, theoretical results are yet missing in showing that learned indexes are provably better than classic indexes, such as B+ trees and their variants.
In this paper, we present the first mathematically-grounded answer to this open problem. We obtain this result by discovering and exploiting a link between the original problem and a mean exit time problem over a proper stochastic process which, we show, is related to the space and time occupancy of those learned indexes. Our general result is then specialised to five well-known distributions: Uniform, Lognormal, Pareto, Exponential, and Gamma; and it is corroborated in precision and robustness by a large set of experiments.
Double Reinforcement Learning for Efficient and Robust Off-Policy Evaluation
Authors: Nathan Kallus, Masatoshi Uehara
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: Off-policy evaluation, reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

Off-policy evaluation (OPE) in reinforcement learning allows one to evaluate novel decision policies without needing to conduct exploration, which is often costly or otherwise infeasible. We consider for the first time the semiparametric efficiency limits of OPE in Markov decision processes (MDPs), where actions, rewards, and states are memoryless. We show existing OPE estimators may fail to be efficient in this setting. We develop a new estimator based on cross-fold estimation of $q$-functions and marginalized density ratios, which we term double reinforcement learning (DRL). We show that DRL is efficient when both components are estimated at fourth-root rates and is also doubly robust when only one component is consistent.
We investigate these properties empirically and demonstrate the performance benefits due to harnessing memorylessness.
Understanding and Estimating the Adaptability of Domain-Invariant Representations
Authors: Ching-Yao Chuang, Antonio Torralba, Stefanie Jegelka
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: Domain Adaptation, Model Selection, Unsupervised Domain Adaptation

Learning domain-invariant representations is a popular approach to unsupervised domain adaptation, i.e., generalizing from a source domain with labels to an unlabeled target domain. In this work, we aim to better understand and estimate the effect of domain-invariant representations on generalization to the target. In particular, we study the effect of the complexity of the latent, domain-invariant representation, and find that it has a significant influence on the target risk. Based on these findings, we propose a general approach for addressing this complexity tradeoff in neural networks. We also propose a method for estimating how well a model based on domain-invariant representations will perform on the target domain, without having seen any target labels. Applications of our results include model selection, deciding early stopping, and predicting the adaptability of a model between domains.
Accelerating the diffusion-based ensemble sampling by non-reversible dynamics
Authors: Futoshi Futami, Issei Sato, Masashi Sugiyama
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: Bayesian Inference

Posterior distribution approximation is a central task in Bayesian inference. Stochastic gradient Langevin dynamics (SGLD) and its extensions have been widely used practically and studied theoretically. While SGLD updates a single particle at a time, ensemble methods that update multiple particles simultaneously have been recently gathering attention. Compared with the naive parallel-chain SGLD that updates multiple particles independently, ensemble methods update particles with their interactions. Thus, these methods are expected to be more particle-efficient than the naive parallel-chain SGLD because particles can be aware of other particles’ behavior through their interactions. Although ensemble methods demonstrated their superior performance numerically, no theoretical guarantee exists to assure such particle-efficiency and it is unclear whether those ensemble methods are really superior to the naive parallel-chain SGLD in the non-asymptotic settings. To cope with this problem, we propose a novel ensemble method that uses a non-reversible Markov chain for the interaction, and we present a non-asymptotic theoretical analysis for our method. Our analysis shows that, for the first time, the interaction causes a faster convergence rate than the naive parallel-chain SGLD in the non-asymptotic setting if the discretization error is appropriately controlled. Numerical experiments show that we can control the discretization error by tuning the interaction appropriately.
Learning with Feature and Distribution Evolvable Streams
Authors: Zhen-Yu Zhang, Peng Zhao, Yuan Jiang, Zhi-Hua Zhou
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1

In many real-world applications, data are often collected in the form of a stream, and thus the feature space of streaming data can evolve over time. For example, in the environmental monitoring task, features can be dynamically vanished or augmented due to the existence of expired old sensors and deployed new sensors. Besides the feature space evolving, it is noteworthy that the data distribution often changes in streaming data. When both feature space and data distribution are evolvable, it is quite challenging to design algorithms with guarantees, particularly the theoretical understanding of generalization ability. To address this difficulty, we propose a novel discrepancy measure for evolving feature space and data distribution named the evolving discrepancy, based on which we provide the generalization error analysis. The theory motivates the design of a learning algorithm, which is further implemented by deep neural networks. We present empirical studies on synthetic data to verify the rationale of the proposed discrepancy measure. Extensive experiments on real-world tasks validate the effectiveness of our algorithm.
dS^2LBI: Exploring Structural Sparsity on Deep Network via Differential Inclusion Paths
Authors: Yanwei Fu, Chen Liu, Donghao Li, Xinwei Sun, Jinshan Zeng, Yuan YAO
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1

Over-parameterization is ubiquitous nowadays in training neural networks to benefit both optimization in seeking global optima and generalization in reducing prediction error. However, compressive networks are desired in many real world applications
and direct training of small networks may be trapped in local optima. In this paper, instead of pruning or distilling over-parameterized models to compressive ones, we propose a new approach based on differential inclusions of inverse scale spaces. Specifically, it generates a family of models from simple to complex ones that couples a pair of parameters to simultaneously train over-parameterized deep models and structural sparsity of which on weights of fully connected (fc) and convolutional layers. Such a differential inclusion scheme has a simple discretization, proposed as deep Structural Splitting Linearized Bregman Iteration (dS^2LBI), whose global convergence analysis in deep learning is established that from any initializations, algorithmic iterations converge to a critical point of empirical risks. Experimental evidence shows that gS^2LBI achieve comparable and even better performance than the competitive optimizers in exploring the structural sparsity of several widely used backbones on the benchmark datasets. Remarkably, with early stopping, gS2LBI unveils “winning tickets”, i.e., the effective sparse structure with comparable test accuracy to over-parameterized models after retraining.
Adaptive Droplet Routing in Digital Microfluidic Biochips Using Deep Reinforcement Learning
Authors: Tung-Che Liang, Zhanwei Zhong, Yaas Bigdeli, Tsung-Yi Ho, Richard Fair, Krishnendu Chakrabarty
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: Deep Reinforcement Learning, OpenAI Gym, reinforcement-learning, Reinforcement Learning (RL)

We present and investigate a novel application domain for deep reinforcement learning (RL): droplet routing on digital microfluidic biochips (DMFBs). A DMFB, composed of a two-dimensional electrode array, manipulates discrete fluid droplets to automatically execute biochemical protocols such as high-throughput DNA sequencing and point-of-care clinical diagnosis. However, a major concern associated with the use of DMFBs is that electrodes in a biochip can degrade over time. Droplet-transportation operations associated with the degraded electrodes can fail, thereby compromising the integrity of the bioassay outcome. While it is not feasible to detect the degradation of an electrode by simply examining its appearance, we show that casting droplet transportation as an RL problem enables the training of deep network policies to capture the underlying health conditions of electrodes and to provide reliable fluidic operations. We propose a new RL-based droplet-routing flow that can be used for various sizes of DMFBs, and demonstrate reliable execution of an epigenetic bioassay with the RL droplet router on a fabricated DMFB. To facilitate further research, we also present a simulation environment based on the OpenAI Gym Interface for RL-guided droplet-routing problems on DMFBs.
An Optimistic Perspective on Offline Deep Reinforcement Learning
Authors: Rishabh Agarwal, Dale Schuurmans, Mohammad Norouzi
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: Atari Games, Deep Reinforcement Learning, Diversity, DQN Replay Dataset, Offline RL, Q-Learning, reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

Off-policy reinforcement learning (RL) using a fixed offline dataset of logged interactions is an important consideration in real world applications. This paper studies offline RL using the DQN replay dataset comprising the entire replay experience of a DQN agent on 60 Atari 2600 games. We demonstrate that recent off-policy deep RL algorithms, even when trained solely on this fixed dataset, outperform the fully trained DQN agent. To enhance generalization in the offline setting, we present Random Ensemble Mixture (REM), a robust Q-learning algorithm that enforces optimal Bellman consistency on random convex combinations of multiple Q-value estimates. Offline REM trained on the DQN replay dataset surpasses strong RL baselines. Ablation studies highlight the role of offline dataset size and diversity as well as the algorithm choice in our positive results. Overall, the results here present an optimistic view that robust RL algorithms trained on sufficiently large and diverse offline datasets can lead to high quality policies. The DQN replay dataset can serve as an offline RL benchmark and is open-sourced.
Can Stochastic Zeroth-Order Frank-Wolfe Method Converge Faster for Non-Convex Problems?
Authors: Hongchang Gao, Heng Huang
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1

Frank-Wolfe algorithm is an efficient method for optimizing  non-convex constrained problems. However, most of existing methods focus on the first-order case. In real-world applications, the gradient is not always available. To address the problem  of lacking gradient in many applications, we propose two new stochastic zeroth-order Frank-Wolfe algorithms and theoretically proved that they have a faster convergence rate than existing methods for non-convex problems. Specifically, the function queries oracle of the proposed faster zeroth-order Frank-Wolfe (FZFW) method is $O(\frac{n^{1/2}d}{\epsilon^2})$  which can match the iteration complexity of the first-order counterpart approximately. As for the proposed faster zeroth-order conditional gradient sliding (FZCGS) method, its function queries oracle is  improved to $O(\frac{n^{1/2}d}{\epsilon})$, indicating that its iteration complexity is even better than that of its first-order counterpart NCGS-VR. In other words, the iteration complelxity of the  accelerated first-order Frank-Wolfe method NCGS-VR is suboptimal. 
Then, we  proposed a new algorithm to improve its IFO (incremental first-order oracle) to $O(\frac{n^{1/2}}{\epsilon})$. At last, the empirical studies on benchmark datasets validate our theoretical results.
Causal Effect Identifiability under Partial-Observability
Authors: Sanghack Lee, Elias Bareinboim
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1

Causal effect identifiability is concerned with establishing the effect of intervening on a set of variables on another set of variables from observational or interventional distributions under causal assumptions that are usually encoded in the form of a causal graph. Most of the results of this literature implicitly assume that every variable modeled in the graph is measured in the available distributions. In practice, however, the data collections of the different studies considered do not measure the same variables, consistently. In this paper, we study the causal effect identifiability problem when the available distributions may be associated with different sets of variables, which we refer to as identification under partial-observability. We study a number of properties of the factors that comprise a causal effect under various levels of abstraction, and then characterize the relationship between them with respect to their status relative to the identification of a targeted intervention. We establish a sufficient graphical criterion for determining whether the effects are identifiable from partially-observed distributions. Finally, building on these graphical properties, we develop an algorithm that returns a formula for a causal effect in terms of the available distributions.
Complexity of Finding Stationary Points of Nonconvex Nonsmooth Functions
Authors: Jingzhao Zhang, Hongzhou Lin, Stefanie Jegelka, Suvrit Sra, Ali Jadbabaie
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1

We provide the first non-asymptotic analysis for finding stationary points of nonsmooth, nonconvex functions. In particular, we study the class of Hadamard semi-differentiable functions, perhaps the largest class of nonsmooth functions for
which the chain rule of calculus holds. This class contains important examples such as ReLU neural networks and others with non-differentiable activation functions. First, we show that finding an epsilon-stationary point with first-order methods is
impossible in finite time. Therefore, we introduce the notion of (delta, epsilon)-stationarity, a generalization that allows for a point to be within distance delta of an epsilon-stationary point and reduces to epsilon-stationarity for smooth functions. We propose a series of randomized first-order methods and analyze their complexity
of finding a (delta, epsilon)-stationary point. Furthermore, we provide a lower bound and show that our stochastic algorithm has min-max optimal dependence on delta. Empirically, our methods perform well for training ReLU neural networks.
Don't Waste Your Bits! Squeeze Activations and Gradients for Deep Neural Networks via TinyScript
Authors: Fangcheng Fu, Yuzheng Hu, Yihan He, Jiawei Jiang, Yingxia Shao, Ce Zhang, Bin Cui
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: Quantization

Recent years have witnessed intensive research interests on training deep neural networks (DNNs) more efficiently by quantization-based compression methods, which facilitate DNNs training in two ways: (1) activations are quantized to shrink the memory consumption, and (2) gradients are quantized to decrease the communication cost. However, existing methods mostly use a uniform mechanism that quantizes the values evenly. Such a scheme may cause a large quantization variance and slow down the convergence in practice.

In this work, we introduce TinyScript, which applies a non-uniform quantization algorithm to both activations and gradients. TinyScript models the original values by a family of Weibull distributions and searches for ''quantization knobs'' that minimize quantization variance. We also discuss the convergence of the non-uniform quantization algorithm on DNNs with varying depths, shedding light on the number of bits required for convergence. Experiments show that TinyScript always obtains lower quantization variance, and achieves comparable model qualities against full precision training using 1-2 bits less than the uniform-based counterpart.