pwc-archive/papers-with-abstracts huggingface dataset:
Efficient Identification in Linear Structural Causal Models with Auxiliary Cutsets
Authors: Daniel Kumor, Carlos Cinelli, Elias Bareinboim
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1

We develop a a new polynomial-time algorithm for identification in linear Structural Causal Models that subsumes previous non-exponential identification methods when applied to direct effects, and unifies several disparate approaches to identification in linear systems. Leveraging these new results and  understanding, we develop a procedure for identifying total causal effects.
Evolving Machine Learning Algorithms From Scratch
Authors: Esteban Real, Chen Liang, David So, Quoc Le
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: AutoML, BIG-bench Machine Learning

Machine learning research has advanced in multiple aspects, including model structures and learning methods. The effort to automate such research, known as AutoML, has also made significant progress. However, this progress has largely focused on the architecture of neural networks, where it has relied on sophisticated expert-designed layers as building blocks---or similarly restrictive search spaces. Our goal is to show that AutoML can go further: it is possible today to automatically discover complete machine learning algorithms just using basic mathematical operations as building blocks. We demonstrate this by introducing a novel framework that significantly reduces human bias through a generic search space. Despite the vastness of this space, evolutionary search can still discover two-layer neural networks trained by backpropagation. These simple neural networks can then be surpassed by evolving directly on tasks of interest, e.g. CIFAR-10 variants, where modern techniques emerge in the top algorithms, such as bilinear interactions, normalized gradients, and weight averaging. Moreover, evolution adapts algorithms to different task types: e.g., dropout-like techniques appear when little data is available. We believe these preliminary successes in discovering machine learning algorithms from scratch indicate a promising new direction for the field.
Finite-Time Convergence in Continuous-Time Optimization
Authors: Orlando Romero, Mouhacine Benosman
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1

In this paper, we investigate a Lyapunov-like differential inequality that allows us to establish finite-time stability of a continuous-time state-space dynamical system represented via a multivariate ordinary differential equation or differential inclusion. Equipped with this condition, we successfully synthesize first and second-order dynamical systems that achieve finite-time convergence to the minima of a given sufficiently regular cost function. As a byproduct, we show that the p-rescaled gradient flow (p-RGF) proposed by Wibisono et al. (2016) is indeed finite-time convergent, provided the cost function is gradient dominated of order q in (1,p). Thus, we effectively bridge a gap between the p-RGF and the normalized gradient flow (NGF) (p=\infty) proposed by Cortes (2006) in his seminal paper in the context of multi-agent systems. We discuss strategies to discretize our proposed flows and conclude by conducting some numerical experiments to illustrate our results.
Generative Adversarial Imitation Learning with Neural Network Parameterization: Global Optimality and Convergence Rate
Authors: Yufeng Zhang, Qi Cai, Zhuoran Yang, Zhaoran Wang
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: Imitation Learning, reinforcement-learning, Reinforcement Learning (RL)

Generative adversarial imitation learning (GAIL) demonstrates tremendous success in practice, especially when combined with neural networks. Different from reinforcement learning, GAIL learns both policy and reward function from expert (human) demonstration. Despite its empirical success, it remains unclear whether GAIL with neural networks converges to the globally optimal solution. The major difﬁculty comes from the nonconvex-nonconcave minimax optimization structure. To bridge the gap between practice and theory, we analyze a gradient-based algorithm with alternating updates and establish its sublinear convergence to the globally optimal solution. To the best of our knowledge, our analysis establishes the global optimality and convergence rate of GAIL with neural networks for the ﬁrst time.
Learning Adversarial Markov Decision Processes with Bandit Feedback and Unknown Transition
Authors: Chi Jin, Tiancheng Jin, Haipeng Luo, Suvrit Sra, Tiancheng Yu
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1

We consider the task of learning in episodic finite-horizon Markov decision processes with an unknown transition function, bandit feedback, and adversarial losses. We propose an efficient algorithm that achieves  O(√L|X|AT ) regret with high probability, where L is the horizon, |X| the number of states, |A| the number of actions, and T the number of episodes. To our knowledge, our algorithm is the first to ensure O(√T) regret in this challenging setting; in fact, it achieves the same regret as (Rosenberg & Mansour, 2019a) who consider the easier setting with full-information. Our key contributions are two-fold: a tighter confidence set for the transition function; and an optimistic loss estimator that is inversely weighted by an "upper occupancy bound".
Learning Fair Policies in Multi-Objective (Deep) Reinforcement Learning with Average and Discounted Rewards
Authors: Umer Siddique, Paul Weng, Matthieu Zimmer
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: Deep Reinforcement Learning, Fairness, Reinforcement Learning (RL)

As the operations of autonomous systems generally affect simultaneously several users, it is crucial that their designs account for fairness considerations. In contrast to standard (deep) reinforcement learning (RL), we investigate the problem of learning a policy that treats its users equitably. In this paper, we formulate this novel RL problem, in which an objective function (generalized Gini index of utility vectors), which encodes a notion of fairness that we formally define, is optimized.
For this problem, we provide a theoretical discussion where we examine the case of discounted rewards and that of average rewards. During this analysis, we notably derive a new result in the standard RL setting, which is of independent interest: it states a novel bound on the approximation error with respect to the optimal average reward of that of a policy optimal for the discounted reward.
Since learning with discounted rewards is generally easier, this discussion further justifies finding a fair policy for the average reward by learning a fair policy for the discounted reward. Thus, we describe how several classic deep RL algorithms can be adapted to our fair optimization problem. Finally, we validate our approach with extensive experiments in three different domains.
Near-optimal sample complexity bounds for learning Latent $k-$polytopes and applications to Ad-Mixtures
Authors: Chiranjib Bhattacharyya, Ravindran Kannan
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1

Recently near-optimal bounds on sample complexity of Mixture of Gaussians was shown in the seminal paper \cite{HSNCAY18}.
No such results are known for Ad-mixtures.
In this paper we show that $O^*(dk/m)$ samples are sufficient to learn each of
$k-$ topic vectors of LDA, a popular Ad-mixture model, with vocabulary size $d$
and $m\in \Omega(1)$ words per document, to any constant error in $L_1$ norm.

This is a corollary of the major contribution of the current paper: the first sample complexity upper bound for the problem (introduced in \cite{BK20})
of learning the vertices of a Latent $k-$ Polytope in ${\bf R}^d$, given perturbed points from it.
The bound,  $O^*(dk/\beta)$, is optimal and applies to many stochastic models including LDA, Mixed Membership block Models(MMBM),Dirichlet Simplex Nest,  and large class of Ad-mixtures.
The parameter, $\beta$ depends on the probability laws governing individual models and in many cases can be expressed very succintly, e.g. it is equal to the average degree of
each node for MMBM, and equal to $m$ in LDA.
The tightness is proved by a nearly matching lower of $\Omega^*(dk/\beta)$ by a combinatorial construction based on a code-design.
Our upper bound proof combines two novel methods. The first is {\it vertex set certification} which, for any $k-$polytope $K$ gives convex geometry based sufficient conditions for a set of $k$ points from a larger candidate set
to be close in Hausdorff distance to the set of $k$ vertices of the polytope.
The second is {\it subset averaging} which uses $\beta$ to prove that the set of averages of all large subsets of data is a good candidate set.
Parameterized Rate-Distortion Stochastic Encoder
Authors: Quan Hoang, Trung Le, Dinh Phung
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1

We propose a novel gradient-based tractable approach for the Blahut-Arimoto (BA) algorithm to compute the rate-distortion function where the BA algorithm is fully parameterized. This results in a rich and flexible framework to learn a new class of stochastic encoders, termed PArameterized RAte-DIstortion Stochastic Encoder (PARADISE). The framework can be applied to a wide range of settings from semi-supervised, multi-task to supervised and robust learning. We show that the training objective of PARADISE can be seen as a form of regularization that helps improve generalization. With an emphasis on robust learning we further develop a novel posterior matching objective to encourage smoothness on the loss function and show that PARADISE can significantly improve interpretability as well as robustness to adversarial attacks on the CIFAR-10 and ImageNet datasets. In particular, on the CIFAR-10 dataset, our model reduces standard and adversarial error rates in comparison to the state-of-the-art by 50% and 41%, respectively without the expensive computational cost of adversarial training.
Strategyproof Mean Estimation from Multiple-Choice Questions
Authors: Anson Kahng, Gregory Kehne, Ariel Procaccia
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: Multiple-choice

Given n values possessed by n agents, we study the problem of estimating the mean by truthfully eliciting agents' answers to multiple-choice questions about their values. We consider two natural candidates for estimation error: mean squared error (MSE) and mean absolute error (MAE). We design a randomized estimator which is asymptotically optimal for both measures in the worst case. In the case where prior distributions over the agents' values are known, we give an optimal, polynomial-time algorithm for MSE, and show that the task of computing an optimal estimate for MAE is #P-hard. Finally, we demonstrate empirically that knowledge of prior distributions gives a significant edge.
Uncertainty-Aware Lookahead Factor Models for Improved Quantitative Investing
Authors: Lakshay Chauhan, John Alberg, Zachary Lipton
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1

On a periodic basis, publicly traded companies are required to report fundamentals: financial data such as revenue, earnings, debt, etc., providing insight into the company’s financial health. Quantitative finance research has identified several factors—computed features of the reported data—that have been demonstrated in retrospective analysis to outperform market averages. In this paper, we first show through simulation that if we could (clairvoyantly) select stocks using factors calculated on future fundamentals (via oracle), then our portfolios would far outperform a standard factor approach.  Motivated by this analysis, we train MLP and LSTM neural networks to forecast future fundamentals based on a trailing window of five years. We propose lookahead factor models to act upon these predictions,  plugging the predicted future fundamentals into traditional factors. Finally, we incorporate uncertainty estimates from both neural heteroscedastic regression and a dropout-based heuristic, demonstrating gains from adjusting our portfolios to avert risk.  In a retrospective analysis using an industry-grade stock portfolio simulator (backtester), we show simultaneous improvement in annualized return and Sharpe ratio (a common measure of risk-adjusted returns).  Specifically, the simulated annualized return for the uncertainty-aware model is 17.7% (vs 14.0% for a standard factor model) and the Sharpe ratio is 0.84 (vs 0.52).
A Chance-Constrained Generative Framework for Sequence Optimization
Authors: Xianggen Liu, Jian Peng, Qiang Liu, Sen Song 
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: valid

Deep generative modeling has achieved many successes for continuous data generation, such as producing realistic images and controlling their properties (e.g., styles). However, the development of generative modeling techniques for optimizing discrete data, such as sequences or strings, still lags behind largely due to the challenges in modeling complex and long-range constraints, including both syntax and semantics, in discrete structures. For example, to generate a string representing a molecule structure or a mathematical expression with a  desired quantitative property, we need to both ensure the validity of the generated string subject to a grammar and model the string representation so that it is predictive of the property.  In this paper, we formulate the sequence optimization task as a chance-constrained sampling problem. The key idea is to enforce a high probability of generating valid sequences and also optimizes the property of interest. We propose a novel minmax algorithm based a tightening of the chance constraint, by jointly tightening a bound of the valid chance and optimizing the expected property. Extensive experimental results in three domains, including arithmetic expressions, Python programs, and SMILES strings for molecules, demonstrate the superiority of our approach over the existing sequence optimization methods. In particular, it is able to achieve the state-of-the-art performance in the molecule optimization task where the current best methods are graph-based.
A Markov Decision Process Model for Socio-Economic Systems Impacted by Climate Change
Authors: Salman Sadiq Shuvo, Yasin Yilmaz, Alan Bush, Mark Hafen
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: Deep Reinforcement Learning

Coastal communities are at high risk of natural hazards due to unremitting global warming and sea level rise. Both the catastrophic impacts, e.g., tidal flooding and storm surges, and the long-term impacts, e.g., beach erosion, inundation of low lying areas, and saltwater intrusion into aquifers, cause economic, social, and ecological losses. Creating policies through appropriate modeling of the responses of stakeholders, such as government, businesses, and residents, to climate change and sea level rise scenarios can help to reduce these losses. In this work, we propose a Markov decision process (MDP) formulation for an agent (government) which interacts with the environment (nature and residents) to deal with the impacts of climate change, in particular sea level rise. Through theoretical analysis we show that a reasonable government's policy on infrastructure development ought to be proactive and based on detected sea levels in order to minimize the expected total cost, as opposed to a straightforward government that reacts to observed costs from nature. We also provide a deep reinforcement learning-based scenario planning tool considering different government and resident types in terms of cooperation, and different sea level rise projections by the National Oceanic and Atmospheric Administration (NOAA).
Context Aware Local Differential Privacy
Authors: Jayadev Acharya, Kallista Bonawitz, Peter Kairouz, Daniel Ramage, Ziteng Sun
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1

Local differential privacy (LDP) is a strong notion of privacy that often leads to a significant drop in utility. The original definition of LDP assumes that all the elements in the data domain are equally sensitive. However, in many real-life applications, some elements are more sensitive than others. We propose a context-aware framework for LDP that allows the privacy level to vary across the data domain, enabling system designers to place privacy constraints where they matter without paying the cost where they do not. For binary data domains, we provide a universally optimal privatization scheme and highlight its connections to Warner’s randomized response and Mangat’s improved response. Motivated by geo-location and web search applications, for k-ary data domains, we consider two special cases of context-aware LDP: block-structured LDP and high-low LDP. We study minimax discrete distribution estimation under both cases and provide communication-efficient, sample-optimal schemes, and information-theoretic lower bounds. We show, using worst-case analyses and experiments on Gowalla’s 3.6 million check-ins to 43,750 locations, that context-aware LDP achieves a far better accuracy under the same number of samples.
Designing Optimal Dynamic Treatment Regimes: A Causal Reinforcement Learning Approach
Authors: Junzhe Zhang
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: Decision Making, reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

A dynamic treatment regime (DTR) consists of a sequence of decision rules, one per stage of intervention, that dictates how to determine the treatment assignment to patients based on evolving treatments and covariates' history. These regimes are particularly effective for managing chronic disorders and is arguably one of the critical ingredients underlying more personalized decision-making systems. All reinforcement learning algorithms for finding the optimal DTR in online settings will suffer O(\sqrt{|D_{X, S}|T}) regret on some environments, where T is the number of experiments, and D_{X, S} is the domains of treatments X and covariates S. This implies T = O (|D_{X, S}|) trials to generate an optimal DTR. In many applications, domains of X and S could be so enormous that the time required to ensure appropriate learning may be unattainable. We show that, if the causal diagram of the underlying environment is provided, one could achieve regret that is exponentially smaller than D_{X, S}. In particular, we develop two online algorithms that satisfy such regret bounds by exploiting the causal structure underlying the DTR; one is based on the principle of optimism in the face of uncertainty (OFU-DTR), and the other uses the posterior sampling learning (PS-DTR). Finally, we introduce efficient methods to accelerate these online learning procedures by leveraging the abundant, yet biased observational (non-experimental) data.
Dispersed EM-VAEs for Interpretable Text Generation
Authors: Wenxian Shi, Hao Zhou, Ning Miao, Lei LI
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: Text Generation

Interpretability is important in text generation for guiding the generation with interpretable attributes.
Variational auto-encoder (VAE) with Gaussian distribution as prior has been successfully applied in text generation, but it is hard to interpret the meaning of the latent variable.
To enhance the controllability and interpretability, one can replace the Gaussian prior with a mixture of Gaussian distributions (GM-VAE), whose mixture components could be related to some latent attributes of data.
Unfortunately, straightforward variational training of GM-VAE leads the mode-collapse problem.
In this paper, we find that mode-collapse is a general problem for VAEs with exponential family mixture priors. 
We propose DEM-VAE, which introduces an extra dispersion term to induce a well-structured latent space.
Experimental results show that our approach does obtain a well structured latent space, with which our method outperforms strong baselines in interpretable text generation benchmarks.
Fast OSCAR and OWL with Safe Screening Rules
Authors: Runxue Bao, Bin Gu, Heng Huang
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: regression

Ordered Weight $L_{1}$-Norms (OWL) is a new family of regularizers for high-dimensional sparse regression. However, due to the non-separable penalty, existing algorithms are either invalid or inefficient when either the size of the feature or sample is large. To address this challenge, we propose the first safe screening rule for the OWL regularized regression, which effectively avoids the updates of the parameters whose coefficients must be zeros. Moreover, we prove the proposed screening rule can be safely applied to the standard proximal gradient methods. More importantly, our screening rule can also be safely applied to stochastic proximal gradient methods in large-scale learning, which is the first safe screening rule in the stochastic setting. Experimental results on a variety of datasets show that the screening rule leads to a significant computation gain without any loss of accuracy, compared to exiting competitive algorithms.
Hierarchically Decoupled Morphological Transfer
Authors: Donald Hejna, Lerrel Pinto, Pieter Abbeel
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1

Learning long-range behaviors on complex high-dimensional agents is a fundamental problem in robot learning. For such tasks, we argue that transferring learned information from a morphologically simpler agent can massively improve the sample efficiency of a more complex one. To this end, we propose a hierarchical decoupling of policies into two parts: an independently learned low-level policy and a transferable high-level policy. To remedy poor transfer performance due to mismatch in morphologies, we contribute two key ideas. First, we show that incentivizing a complex agent's low-level to imitate a simpler agent's low-level significantly improves zero-shot high-level transfer. Second, we show that KL-regularized training of the high level stabilizes learning and prevents mode-collapse. Finally, on a suite of navigation and manipulation environments, we demonstrate the applicability of hierarchical transfer on long-range tasks across morphologies.
Learning Compound Tasks without Task-specific Knowledge via Imitation and Self-supervised Learning
Authors: Sang-Hyun Lee, Seung-Woo Seo
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: Imitation Learning, Self-Supervised Learning

Most real-world tasks are compound tasks that consist of multiple simpler sub-tasks. The main challenge of learning compound tasks is that we have no explicit supervision to learn the hierarchical structure of compound tasks. To address this challenge, previous imitation learning methods exploit task-specific knowledge, e.g., labeling demonstrations manually or specifying termination conditions for each sub-task. However, the need for task-specific knowledge makes it difficult to scale imitation learning to real-world tasks. In this paper, we propose an imitation learning method that can learn compound tasks without task-specific knowledge. The key idea behind our method is to leverage a self-supervised learning framework to learn the hierarchical structure of compound tasks. Our work also proposes a task-agnostic regularization technique to prevent unstable switching between sub-tasks, which has been a common degenerate case in previous works. We evaluate our method against several baselines on compound tasks. The results show that our method achieves state-of-the-art performance on compound tasks, outperforming prior imitation learning methods.