pwc-archive/papers-with-abstracts huggingface dataset:
Model Based Reinforcement Learning for Atari
Authors: Łukasz Kaiser, Mohammad Babaeizadeh, Piotr Miłos, Błażej Osiński, Roy H. Campbell, Konrad Czechowski, Dumitru Erhan, Chelsea Finn, Piotr Kozakowski, Sergey Levine, Afroz Mohiuddin, Ryan Sepassi, George Tucker, Henryk Michalewski
Date: 2020-05-01 00:00:00
Proceeding: ICLR 2020 1
Tasks: Atari Games, model, Model-based Reinforcement Learning, reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL), Video Prediction

Model-free reinforcement learning (RL) can be used to learn effective policies for complex tasks, such as Atari games, even from image observations. However, this typically requires very large amounts of interaction -- substantially more, in fact, than a human would need to learn the same games. How can people learn so quickly? Part of the answer may be that people can learn how the game works and predict which actions will lead to desirable outcomes. In this paper, we explore how video prediction models can similarly enable agents to solve Atari games with fewer interactions than model-free methods. We describe Simulated Policy Learning (SimPLe), a complete model-based deep RL algorithm based on video prediction models and present a comparison of several model architectures, including a novel architecture that yields the best results in our setting. Our experiments evaluate SimPLe on a range of Atari games in low data regime of 100k interactions between the agent and the environment, which corresponds to two hours of real-time play. In most games SimPLe outperforms state-of-the-art model-free algorithms, in some games by over an order of magnitude.
Inductive and Unsupervised Representation Learning on Graph Structured Objects
Authors: Lichen Wang, Bo Zong, Qianqian Ma, Wei Cheng, Jingchao Ni, Wenchao Yu, Yanchi Liu, Dongjin Song, Haifeng Chen, Yun Fu
Date: 2020-05-01 00:00:00
Proceeding: ICLR 2020 1
Tasks: Graph Learning, Graph Similarity, Information Retrieval, Representation Learning, Retrieval

Inductive and unsupervised graph learning is a critical technique for predictive or information retrieval tasks where label information is difficult to obtain. It is also challenging to make graph learning inductive and unsupervised at the same time, as learning processes guided by reconstruction error based loss functions inevitably demand graph similarity evaluation that is usually computationally intractable. In this paper, we propose a general framework SEED (Sampling, Encoding, and Embedding Distributions) for inductive and unsupervised representation learning on graph structured objects. Instead of directly dealing with the computational challenges raised by graph similarity evaluation, given an input graph, the SEED framework samples a number of subgraphs whose reconstruction errors could be efficiently evaluated, encodes the subgraph samples into a collection of subgraph vectors, and employs the embedding of the subgraph vector distribution as the output vector representation for the input graph. By theoretical analysis, we demonstrate the close connection between SEED and graph isomorphism. Using public benchmark datasets, our empirical study suggests the proposed SEED framework is able to achieve up to 10% improvement, compared with competitive baseline methods.
Learning the Arrow of Time for Problems in Reinforcement Learning
Authors: Nasim Rahaman, Steffen Wolf, Anirudh Goyal, Roman Remme, Yoshua Bengio
Date: 2020-05-01 00:00:00
Proceeding: ICLR 2020 1
Tasks: reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

We humans have an innate understanding of the asymmetric progression of time, which we use to efficiently and safely perceive and manipulate our environment. Drawing inspiration from that, we approach the problem of learning an arrow of time in a Markov (Decision) Process. We illustrate how a learned arrow of time can capture salient information about the environment, which in turn can be used to measure reachability, detect side-effects and to obtain an intrinsic reward signal. Finally, we propose a simple yet effective algorithm to parameterize the problem at hand and learn an arrow of time with a function approximator (here, a deep neural network). Our empirical results span a selection of discrete and continuous environments, and demonstrate for a class of stochastic processes that the learned arrow of time agrees reasonably well with a well known notion of an arrow of time due to Jordan, Kinderlehrer and Otto (1998).
Gap-Aware Mitigation of Gradient Staleness
Authors: Saar Barkai, Ido Hakimi, Assaf Schuster
Date: 2020-05-01 00:00:00
Proceeding: ICLR 2020 1
Tasks: Cloud Computing

Cloud computing is becoming increasingly popular as a platform for distributed training of deep neural networks. Synchronous stochastic gradient descent (SSGD) suffers from substantial slowdowns due to stragglers if the environment is non-dedicated, as is common in cloud computing. Asynchronous SGD (ASGD) methods are immune to these slowdowns but are scarcely used due to gradient staleness, which encumbers the convergence process. Recent techniques have had limited success mitigating the gradient staleness when scaling up to many workers (computing nodes).  In this paper we define the Gap as a measure of gradient staleness and propose Gap-Aware (GA), a novel asynchronous-distributed method that penalizes stale gradients linearly to the Gap and performs well even when scaling to large numbers of workers. Our evaluation on the CIFAR, ImageNet, and WikiText-103 datasets shows that GA outperforms the currently acceptable gradient penalization method, in final test accuracy. We also provide convergence rate proof for GA. Despite prior beliefs, we show that if GA is applied, momentum becomes beneficial in asynchronous environments, even when the number of workers scales up.
Deep Symbolic Superoptimization Without Human Knowledge
Authors: Hui Shi, Yang Zhang, Xinyun Chen, Yuandong Tian, Jishen Zhao
Date: 2020-05-01 00:00:00
Proceeding: ICLR 2020 1
Tasks: Decoder, reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

Deep  symbolic superoptimization refers to the task of applying deep learning methods to simplify symbolic expressions.   Existing approaches either perform supervised training on human-constructed datasets that defines equivalent expression pairs, or apply reinforcement learning with human-defined equivalent trans-formation actions.  In short,  almost all existing methods rely on human knowledge to define equivalence, which suffers from large labeling cost and learning bias, because it is almost impossible to define and comprehensive equivalent set. We thus propose HISS, a reinforcement learning framework for symbolic super-optimization that keeps human outside the loop.  HISS introduces a tree-LSTM encoder-decoder network with attention to ensure tractable learning.   Our experiments show that HISS can discover more simplification rules than existing human-dependent methods, and can learn meaningful embeddings for symbolic expressions, which are indicative of equivalence.
Towards Verified Robustness under Text Deletion Interventions
Authors: Johannes Welbl, Po-Sen Huang, Robert Stanforth, Sven Gowal, Krishnamurthy (Dj) Dvijotham, Martin Szummer, Pushmeet Kohli
Date: 2020-05-01 00:00:00
Proceeding: ICLR 2020 1
Tasks: Natural Language Inference, Sensitivity

Neural networks are widely used in Natural Language Processing, yet despite their empirical successes, their behaviour is brittle: they are both over-sensitive to small input changes, and under-sensitive to deletions of large fractions of input text. This paper aims to tackle under-sensitivity in the context of natural language inference by ensuring that models do not become more confident in their predictions as arbitrary subsets of words from the input text are deleted. We develop a novel technique for formal verification of this specification for models based on the popular decomposable attention mechanism by employing the efficient yet effective interval bound propagation (IBP) approach. Using this method we can efficiently prove, given a model, whether a particular sample is free from the under-sensitivity problem. We compare different training methods to address under-sensitivity, and compare metrics to measure it. In our experiments on the SNLI and MNLI datasets, we observe that IBP training leads to a significantly improved verified accuracy. On the SNLI test set, we can verify 18.4% of samples, a substantial improvement over only 2.8% using standard training.
All in the (Exponential) Family: Information Geometry and Thermodynamic Variational Inference
Authors: Rob Brekelmans, Vaden Masrani, Frank Wood, Greg Ver Steeg, Aram Galstyan
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: All, Scheduling, Variational Inference

While the Evidence Lower Bound (ELBO) has become a ubiquitous objective for variational inference, the recently proposed Thermodynamic Variational Objective (TVO) leverages thermodynamic integration to provide a tighter and more general family of bounds.  In previous work, the tightness of these bounds was not known, grid search was used to choose a `schedule' of intermediate distributions, and model learning suffered with ostensibly tighter bounds. We interpret the geometric mixture curve common to TVO and related path sampling methods using the geometry of exponential families, which allows us to characterize the gap in TVO bounds as a sum of KL divergences along a given path.  Further, we propose a principled technique for choosing intermediate distributions using equal spacing in the moment parameters of our exponential family.  We demonstrate that this scheduling approach adapts to the shape of the integrand defining the TVO objective and improves overall performance. Additionally, we derive a reparameterized gradient estimator which empirically allows the TVO to benefit from additional, well chosen partitions. Finally, we provide a unified framework for understanding thermodynamic integration and the TVO in terms of Taylor series remainders.
Combinatorial Pure Exploration for Dueling Bandit
Authors: Wei Chen, Yihan Du, Longbo Huang, Haoyu Zhao
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: Position

In this paper, we study combinatorial pure exploration for dueling bandits (CPE-DB): we have multiple candidates for multiple positions as modeled by a bipartite graph, and in each round we sample a duel of two candidates on one position and observe who wins in the duel, with the goal of finding the best candidate-position matching with high probability after multiple rounds of samples. CPE-DB is an adaptation of the original combinatorial pure exploration for multi-armed bandit (CPE-MAB) problem to the dueling bandit setting. We consider both the Borda winner and the Condorcet winner cases. For Borda winner, we establish a reduction of the problem to the original CPE-MAB setting and design PAC and exact algorithms that achieve both the sample complexity similar to that in the CPE-MAB setting (which is nearly optimal for a subclass of problems)  and polynomial running time per round. For Condorcet winner, we first design a fully polynomial time approximation scheme (FPTAS) for the offline problem of finding the Condorcet winner with known winning probabilities, and then use the FPTAS as an oracle to design a novel pure exploration algorithm CAR-Cond with sample complexity analysis. CAR-Cond is the first algorithm with polynomial running time per round for identifying the Condorcet winner in CPE-DB.
Communication-Efficient Federated Learning with Sketching
Authors: Daniel Rothchild, Ashwinee Panda, Enayat Ullah, Nikita Ivkin, Vladimir Braverman, Joseph Gonzalez, Ion Stoica, Raman Arora
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: Federated Learning

Existing approaches to federated learning suffer from a communication bottleneck as well as convergence issues due to sparse client participation. In this paper we introduce a novel algorithm, called FedSketchedSGD, to overcome these challenges. FedSketchedSGD compresses model updates using a Count Sketch, and then takes advantage of the mergeability of sketches to combine model updates from many workers. A key insight in the design of FedSketchedSGD is that, because the Count Sketch is linear, momentum and error accumulation can both be carried out within the sketch. This allows the algorithm to move momentum and error accumulation from clients to the central aggregator, overcoming the challenges of sparse client participation while still achieving high compression rates. We prove that FedSketchedSGD has favorable convergence guarantees, and we demonstrate its empirical effectiveness by training two residual networks and a transformer model.
Deep Reasoning Networks for Unsupervised Pattern De-mixing with Constraint Reasoning
Authors: Di Chen, Yiwei Bai, Wenting Zhao, Sebastian Ament, John Gregoire, Carla Gomes
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1

We introduce Deep Reasoning Networks (DRNets), an end-to-end framework that combines deep learning with constraint reasoning for solving pattern de-mixing problems, typically in an unsupervised or very-weakly-supervised setting. DRNets exploit problem structure and prior knowledge by tightly combining constraint reasoning with stochastic-gradient-based neural network optimization. Our motivating task is from materials discovery and concerns inferring crystal structures of materials from X-ray diffraction data (Crystal-Structure-Phase-Mapping). Given the complexity of its underlying scientific domain, we start by introducing DRNets on an analogous but much simpler task: de-mixing overlapping hand-written Sudokus (Multi-MNIST-Sudoku). On Multi-MNIST-Sudoku, DRNets almost perfectly recovered the mixed Sudokus' digits, with 100\% digit accuracy, outperforming the supervised state-of-the-art MNIST de-mixing models. On Crystal-Structure-Phase-Mapping, DRNets significantly outperform the state of the art and experts' capabilities, recovering more precise and physically meaningful crystal structures.
Distance Metric Learning with Joint Representation Diversification
Authors: Xu Chu, Yang Lin, Xiting Wang, Xin Gao, Qi Tong, Hailong Yu, Yasha Wang
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: Metric Learning

Distance metric learning (DML) is to learn a representation space equipped with a metric, such that examples from the same class are closer than examples from different classes with respect to the metric. The recent success of deep neural networks motivates many DML losses that encourage the intra-class compactness and inter-class separability. However, overemphasizing intra-class compactness may potentially cause the neural networks to filter out information that contributes to discriminating examples from unseen classes, resulting in a less generalizable representation. In contrast, we propose not to penalize intra-class distances explicitly and use a Joint Representation Similarity (JRS) regularizer that focuses on penalizing inter-class distributional similarities in a DML framework. The proposed JRS regularizer diversifies the joint distributions of representations from different classes in multiple neural layers based on cross-covariance operators in Reproducing Kernel Hilbert Space (RKHS). Experiments on three well-known benchmark datasets (Cub-200-2011, Cars-196, and Stanford Online Products) demonstrate the effectiveness of the proposed approach.
Distributionally Robust Policy Evaluation and Learning in Offline Contextual Bandits
Authors: Nian Si, Fan Zhang, Zhengyuan Zhou, Jose Blanchet
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: Multi-Armed Bandits

Policy learning using historical observational data is an important problem that has found widespread applications. However, existing literature rests on the crucial assumption that the future environment where the learned policy will be deployed is the same as the past environment that has generated the data–an assumption that is often false or too coarse an approximation. In this paper, we lift this assumption and aim to learn a distributionally robust policy with bandit observational data. We propose a novel learning algorithm that is able to learn a robust policy to adversarial perturbations and unknown covariate shifts. We first present a policy evaluation procedure in the ambiguous environment and also give a heuristic algorithm to solve the distributionally robust policy learning problems efficiently. Additionally, we provide extensive simulations to demonstrate the robustness of our policy.
Expert Learning through Generalized Inverse Multiobjective Optimization: Models, Insights and Algorithms
Authors: Chaosheng Dong, Bo Zeng
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: Clustering, Decision Making, Multiobjective Optimization

We study a new unsupervised learning task of inferring objective functions or constraints of a multiobjective decision making model, based on a set of observed decisions. Specifically, we formulate such a learning problem as an inverse multiobjective optimization problem (IMOP) and propose its first sophisticated model with statistical guarantees. Then, we some fundamental connections between IMOP, K-means clustering and manifold learning. More precisely, we prove that every K-means clustering problem can be transformed equivalently into an IMOP, and every IMOP can be conversely interpreted as a constrained K-means clustering problem. In addition, we show that the Pareto optimal set is a piecewise continuous manifold with an intrinsic dimension of $ p-1 $ (where $ p $ is the number of objectives) under suitable conditions. Hence, IMOP can also be interpreted as a manifold learning problem. Leveraging these critical insights and connections, we propose two algorithms to solve IMOP through manifold learning and clustering. Numerical results confirm the effectiveness of our model and the computational efficacy of algorithms.
FedBoost: A Communication-Efficient Algorithm for Federated Learning
Authors: Jenny Hamer, Mehryar Mohri, Ananda Theertha Suresh
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: Density Estimation, Federated Learning, Language Modeling, Language Modelling, Model Compression

Communication cost is often a bottleneck in federated learning and other client-based distributed learning scenarios. To overcome this, several gradient compression and model compression algorithms have been proposed. In this work, we propose an alternative approach whereby an ensemble of pre-trained base predictors is trained via federated learning. This method allows for training a model which may otherwise surpass the communication bandwidth and storage capacity of the clients to be learned with on-device data through federated learning. Motivated by language modeling, we prove the optimality of ensemble methods for density estimation for standard empirical risk minimization and agnostic risk minimization. We provide communication-efficient ensemble algorithms for federated learning, where per-round communication cost is independent of the size of the ensemble. Furthermore, unlike works on gradient compression, our proposed approach reduces the communication cost of both server-to-client and client-to-server communication.
Generating Programmatic Referring Expressions via Program Synthesis
Authors: Jiani Huang, Calvin Smith, Osbert Bastani, Rishabh Singh, Aws Albarghouthi, Mayur Naik
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: Enumerative Search, Logical Reasoning, Program Synthesis

Incorporating symbolic reasoning into machine learning algorithms is a promising approach to improve performance on learning tasks that require logical reasoning. We study the problem of generating a programmatic variant of referring expressions that we call referring relational programs. In particular, given a symbolic representation of an image and a target object in that image, the goal is to generate a relational program that uniquely identifies the target object in terms of its attributes and its relations to other objects in the image. We propose a neurosymbolic program synthesis algorithm that combines a policy neural network with enumerative search to generate such relational programs. The policy neural network employs a program interpreter that provides immediate feedback on the consequences of the decisions made by the policy, and also takes into account the uncertainty in the symbolic representation of the image. We evaluate our algorithm on challenging benchmarks based on the CLEVR dataset, and demonstrate that our approach significantly outperforms several baselines.
Implicit Learning Dynamics in Stackelberg Games: Equilibria Characterization, Convergence Analysis, and Empirical Study
Authors: Tanner Fiez, Benjamin Chasnov, Lillian Ratliff
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: Decision Making

Contemporary work on learning in continuous games has commonly overlooked the hierarchical decision-making structure present in machine learning problems formulated as games, instead treating them as simultaneous play games and adopting the Nash equilibrium solution concept. We deviate from this paradigm and provide a comprehensive study of learning in Stackelberg games. This work provides insights into the optimization landscape of zero-sum games by establishing connections between Nash and Stackelberg equilibria along with the limit points of simultaneous gradient descent. We derive novel gradient-based learning dynamics emulating the natural structure of a Stackelberg game using the Implicit Function Theorem and provide convergence analysis for deterministic and stochastic updates for zero-sum and general-sum games. Notably, in zero-sum games using deterministic updates, we show the only critical points the dynamics converge to are Stackelberg equilibria and provide a local convergence rate. Empirically, the proposed learning dynamics mitigate rotational behavior and exhibit benefits for training Generative Adversarial Networks compared to gradient play.
(Individual) Fairness for k-Clustering
Authors: Sepideh Mahabadi, Ali Vakilian
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: Clustering, Fairness

We give a local search based algorithm for $k$-median ($k$-means) clustering from the perspective of individual fairness. 
More precisely, for a point $x$ in a point set $P$ of size $n$, let $r(x)$ be the minimum radius such that the ball of radius $r(x)$ centered at $x$ has at least $n/k$ points from $P$. Intuitively, if a set of $k$ random points are chosen from $P$ as centers, every point $x\in P$ expects to have a center within radius $r(x)$. An individually fair clustering provides such a guarantee for every point $x\in P$. This notion of fairness was introduced in [Jung et al., 2019] where they showed how to get an approximately feasible $k$-clustering with respect to this fairness condition.

In this work, we show how to get an approximately \emph{optimal} such fair $k$-clustering. The $k$-median ($k$-means) cost of our solution is within a constant factor of the cost of an optimal fair $k$-clustering, and our solution approximately satisfies the fairness condition (also within a constant factor).