pwc-archive/papers-with-abstracts huggingface dataset:
“Other-Play” for Zero-Shot Coordination
Authors: Hengyuan Hu, Alexander Peysakhovich, Adam Lerer, Jakob Foerster
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: Multi-agent Reinforcement Learning, Reinforcement Learning (RL)

We consider the problem of zero-shot coordination - constructing AI agents that can coordinate with novel partners they have not seen before (e.g.humans). Standard Multi-Agent Reinforcement Learning (MARL) methods typically focus on the self-play (SP) setting where agents construct strategies by playing the game with themselves repeatedly. Unfortunately, applying SP naively to the zero-shot coordination problem can produce agents that establish highly specialized conventions that do not carry over to novel partners they have not been trained with. We introduce a novel learning algorithm called other-play (OP), that enhances self-play by looking for more robust strategies. We characterize OP theoretically as well as experimentally. We study the cooperative card game Hanabi and show that OP agents achieve higher scores when paired with independently trained agents as well as with human players than SP agents.
Robust Graph Representation Learning via Neural Sparsification
Authors: Cheng Zheng, Bo Zong, Wei Cheng, Dongjin Song, Jingchao Ni, Wenchao Yu, Haifeng Chen, Wei Wang
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: Fraud Detection, Graph Representation Learning, Node Classification, Product Recommendation, Representation Learning

Graph representation learning serves as the core of important prediction tasks, ranging from product recommendation to fraud detection. Real-life graphs usually have complex information in the local neighborhood, where each node is described by a rich set of features and connects to dozens or even hundreds of neighbors. Despite the success of neighborhood aggregation in graph neural networks, task-irrelevant information is mixed into nodes' neighborhood, making learned models suffer from sub-optimal generalization performance. In this paper, we present NeuralSparse, a supervised graph sparsification technique that improves generalization power by learning to remove potentially task-irrelevant edges from input graphs. Our method takes both structural and non-structural information as input, utilizes deep neural networks to parameterize sparsification processes, and optimizes the parameters by feedback signals from downstream tasks. Under the NeuralSparse framework, supervised graph sparsification could seamlessly connect with existing graph neural networks for more robust performance. Experimental results on both benchmark and private datasets show that NeuralSparse can yield up to 7.2% improvement in testing accuracy when working with existing graph neural networks on node classification tasks.
Acceleration for Compressed Gradient Descent in Distributed Optimization
Authors: Zhize Li, Dmitry Kovalev, Xun Qian, Peter Richtarik
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: Distributed Optimization, Federated Learning, Quantization

Due to the high communication cost in distributed and federated learning problems, methods relying on sparsification or quantization of communicated messages are becoming increasingly popular. While in other contexts the best performing gradient-type  methods invariably rely on some form of acceleration to reduce the number of iterations, there are no methods which combine the benefits of both  gradient compression and acceleration. In this paper, we remedy this situation and propose the first {\em accelerated compressed gradient descent (ACGD)} methods. In the single machine regime, we prove that ACGD enjoys the rate $O((1+\omega)\sqrt{\nicefrac{L}{\mu}}\log \nicefrac{1}{\epsilon})$ for $\mu$-strongly convex problems and $O((1+\omega)\sqrt{\nicefrac{L}{\epsilon}})$ for convex problems, respectively, where $L$ is the smoothness constant and $\omega$ is the variance parameter of an unbiased compression operator. Our results improve upon the existing non-accelerated rates $O\left((1+\omega)\nicefrac{L}{\mu}\log \nicefrac{1}{\epsilon}\right)$ and $O\left((1+\omega)\nicefrac{L}{\epsilon}\right)$, respectively, and recover the best known rates of accelerated gradient descent as a special case when no compression ($\omega=0$) is applied. We further propose a distributed variant  of ACGD and establish the rate $\tilde{O}\left(\omega+\sqrt{\nicefrac{L}{\mu}} +\sqrt{(\nicefrac{\omega}{n}+\sqrt{\nicefrac{\omega}{n}})\nicefrac{\omega L}{\mu}}\right)$, where $n$ is the number of machines and $\tilde{O}$ hides the logarithmic factor $\log \nicefrac{1}{\epsilon}$ . This improves upon the previous best result $\tilde{O}\left(\omega + \nicefrac{L}{\mu}+\nicefrac{\omega L}{n\mu} \right)$ achieved by the DIANA method. Finally, we conduct several experiments on real-world datasets which corroborate  our theoretical results and confirm the practical superiority of our methods.
Adaptive Sketching for Fast and Convergent Canonical Polyadic Decomposition
Authors: Kareem Aggour, Bülent Yener
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1

This work considers the canonical polyadic decomposition (CPD) of
tensors using proximally regularized sketched alternating least squares algorithms. First, it establishes a sublinear rate of convergence for proximally regularized sketched CPD algorithms under two natural conditions that
are known to be satisfied by many popular forms of sketching. Second, it demonstrates that the iterative nature of CPD algorithms
can be exploited algorithmically to choose more performant sketching rates. This is
accomplished by introducing CPD-MWU, a proximally-regularized sketched alternating least squares algorithm that adaptively selects the sketching rate at each iteration. On both synthetic and real data we observe that
for noisy tensors CPD-MWU produces decompositions of comparable accuracy to the standard CPD decomposition in less time, often half the time; for ill-conditioned tensors, given the same time budget, CPD-MWU produces decompositions with an order-of-magnitude lower relative error. For a representative real-
world dataset CPD-MWU produces residual errors on average 20% lower than CPRAND-MIX and 44% lower than SPALS, two recent sketched CPD algorithms.
Adversarial Nonnegative Matrix Factorization
Authors: lei luo, yanfu Zhang, Heng Huang
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: Bilevel Optimization

Nonnegative Matrix Factorization (NMF) has become an increasingly important research topic in machine learning. It targets at searching for two non-negative matrices (\textit{i.e.}, feature matrix \textbf{A} and weight matrix \textbf{X}) whose product can well approximate the original matrix \textbf{Y}. Despite all the practical success, most of existing NMF models are still vulnerable to adversarial attacks. To overcome this limitation, we propose a novel Adversarial NMF (ANMF) approach in which an adversary can exercise some control over the perturbed data generation process. Different from the traditional NMF models which focus on either the regular input or certain types of noise, our model considers potential test adversaries that are beyond the pre-defined constraints, which can cope with various noises (or perturbations). We formulate the proposed model as a bilevel optimization problem and use Alternating Direction Method of Multipliers (ADMM) to solve it with convergence analysis. Theoretically, the robustness analysis of ANMF is established under mild conditions dedicating asymptotically unbiased prediction. Extensive experiments verify that ANMF is robust to a broad categories of perturbations, and achieves state-of-the-art performances on distinct real-world benchmark datasets.
CoMic: Co-Training and Mimicry for Reusable Skills
Authors: Leonard Hasenclever, Fabio Pardo, Raia Hadsell, Nicolas Heess, Josh Merel
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: continuous-control, Continuous Control, Reinforcement Learning (RL)

Learning to control complex bodies and reuse learned behaviors is a longstanding challenge in continuous control. We study the problem of learning reusable humanoid skills by imitating motion capture data and co-training with complementary tasks. We show that it is possible to learn reusable skills through reinforcement learning on 50 times more motion capture data than prior work. We systematically compare a variety of different network architectures across different data regimes both in terms of imitation performance as well as transfer to challenging locomotion tasks. Finally we show that it is possible to interleave the motion capture tracking with training on complementary tasks, enriching the resulting skill space, and enabling the reuse of skills not well covered by the motion capture data such as getting up from the ground or catching a ball.
Curvature-corrected learning dynamics in deep neural networks
Authors: Dongsung Huh
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: Second-order methods

Deep neural networks exhibit highly non-convex loss landscape, which results in complex learning dynamics under steepest gradient descent. Second order optimization methods, such as natural gradient descent, can facilitate learning by compensating for ill-conditioned curvature. However, the exact nature of such curvature-corrected learning process remains largely unknown. Here, we derive exact solutions to curvature-corrected learning rules for the restricted case of deep linear neural networks. Our analysis reveals that natural gradient descent follows the same path as gradient descent, only adjusting the temporal dynamics along the path. This preserves the implicit bias of gradient-based learning, such as weight balance across layers. However, block-diagonal approximations of natural gradient, which are widely used in most second order methods (e.g. K-FAC), significantly distort the dynamics to follow highly divergent paths, destroying weight balance across layers. We introduce partially curvature-corrected learning rule, which provides most of the benefit of full curvature correction in terms of convergence speed with superior numerical stability while preserving the core property of gradient descent under block-diagonal approximations.
Estimating Model Uncertainty of Neural Network in Sparse Information Form
Authors: Jongseok Lee, Matthias Humt, Jianxiang Feng, Rudolph Triebel
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: Dimensionality Reduction, Form

We present a sparse representation of model uncertainty for Deep Neural Networks (DNNs) where the parameter posterior is approximated with an inverse formulation of the Multivariate Normal Distribution (MND), also known as the information form. The key insight of our work is that the information matrix, i.e. the inverse of the covariance matrix tends to be sparse in its spectrum. Therefore, dimensionality reduction techniques such as low rank approximations can be effectively exploited. To achieve this, we develop a novel sparsification algorithm and derive a cost-effective analytical sampler. As a result, we show that the information form of MND can be scalably applied to represent model uncertainty in MND. Our exhaustive theoretical analysis and empirical evaluations on various benchmarks show the competitiveness of our approach over the current methods.
Inductive Bias-driven Reinforcement Learning For Efficient Schedules in Heterogeneous Clusters
Authors: Subho Banerjee, Saurabh Jha, Zbigniew Kalbarczyk, Ravishankar Iyer
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: Heuristic Search, Inductive Bias, reinforcement-learning, Reinforcement Learning (RL), Scheduling

The problem of scheduling of workloads onto heterogeneous processors (e.g., CPUs, GPUs, FPGAs) is of fundamental importance in modern datacenters.
Current system schedulers rely on application/system-specific heuristics that have to be built on a case-by-case basis.
Recent work has demonstrated ML techniques to automate this heuristic search using black box approaches which require significant training data and time, which make them challenging to use in practice.
This paper addresses the challenge in two ways: 
(i) a domain-driven Bayesian reinforcement learning (RL) model for scheduling, which inherently models the resource dependencies identified from the  system architecture; and
(ii) a sampling-based technique which allows the computation of gradients of a Bayesian model without performing full probabilistic inference.
Together, these techniques reduce both the amount of training-data and -time required to produce scheduling policies that significantly outperform black box approaches by up to 2.2$\times$.
Scalable Differential Privacy with Certified Robustness in Adversarial Learning
Authors: Hai Phan, My T. Thai, Han Hu, Ruoming Jin, Tong Sun, Dejing Dou
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1

In this paper, we aim to develop a scalable algorithm to preserve differential privacy (DP) in adversarial learning for deep neural networks (DNNs), with certified robustness to adversarial examples. By leveraging the sequential composition theory in DP, we randomize both input and latent spaces to strengthen our certified robustness bounds. To address the trade-off among model utility, privacy loss, and robustness, we design an original adversarial objective function, based on the post-processing property in DP, to tighten the sensitivity of our model. A new stochastic batch training is proposed to apply our mechanism on large DNNs and datasets, by bypassing the vanilla iterative batch-by-batch training in DP DNNs. An end-to-end theoretical analysis and evaluations show that our mechanism notably improves the robustness and scalability of DP DNNs.
Too Relaxed to Be Fair
Authors: Michael Lohaus, Michaël Perrot, Ulrike Von Luxburg
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: Fairness

We address the problem of classification under fairness constraints. Given a notion of fairness, the goal is to learn a classifier that is not discriminatory against a group of individuals. In the literature, this problem is often formulated as a constrained optimization problem and solved using relaxations of the fairness constraints. We show that many existing relaxations are unsatisfactory: even if a model satisfies the relaxed constraint, it can be surprisingly unfair. We propose a principled framework to solve this problem. This new approach uses a strongly convex formulation and comes with theoretical guarantees on the fairness of its solution. In practice, we show that this method gives promising results on real data.
Transformation of ReLU-based recurrent neural networks from discrete-time to continuous-time
Authors: Zahra Monfared, Daniel Durstewitz
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: BIG-bench Machine Learning, Numerical Integration, Time Series, Time Series Analysis, Time Series Prediction, Translation

Recurrent neural networks (RNN) as used in machine learning are commonly formulated in discrete time, i.e. as recursive maps. This brings a lot of advantages for training models on data, e.g. for the purpose of time series prediction or dynamical systems identification, as powerful and efficient inference algorithms exist for discrete time systems and numerical integration of differential equations is not necessary. On the other hand, mathematical analysis of dynamical systems inferred from data is often more convenient and enables additional insights if these are formulated in continuous time, i.e. as systems of ordinary (or partial) differential equations (ODE). Here we show how to perform such a translation from discrete to continuous time for a particular class of ReLU-based RNN. We prove three theorems on the mathematical equivalence between the discrete and continuous time formulations under a variety of conditions, and illustrate how to use our mathematical results on different machine learning and nonlinear dynamical systems examples.
Unique Properties of Wide Minima in Deep Networks
Authors: Rotem Mulayoff, Tomer Michaeli
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1

It is well known that (stochastic) gradient descent has an implicit bias towards wide minima. In deep neural network training, this mechanism serves to screen out minima. However, the precise effect that this has on the trained network is not yet fully understood. In this paper, we characterize the wide minima in linear neural networks trained with a quadratic loss. First, we show that linear ResNets with zero initialization necessarily converge to the widest of all minima. We then prove that these minima correspond to nearly balanced networks whereby the gain from the input to any intermediate representation does not change drastically from one layer to the next. Finally, we show that consecutive layers in wide minima solutions are coupled. That is, one of the left singular vectors of each weight matrix, equals one of the right singular vectors of the next matrix. This forms a distinct path from input to output, that, as we show, is dedicated to the signal that experiences the largest gain end-to-end. Experiments indicate that these properties are characteristic of both linear and nonlinear models trained in practice.
Augmenting Continuous Time Bayesian Networks with Clocks
Authors: Nicolai Engelmann, Dominik Linzner, Heinz Koeppl
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1

Structured stochastic processes evolving in continuous time present a widely adopted framework to model phenomena occurring in nature and engineering. However, such models are often chosen to satisfy the Markov property to maintain tractability. One of the more popular of such memoryless models is Continuous Time Bayesian Networks (CTBNs). In this work, we lift its restriction to exponential survival times to arbitrary distributions. Current extensions achieve this via auxiliary states, which hinder tractability. To avoid that, we introduce a set of node-wise clocks to construct a collection of graph-coupled semi-Markov chains. We provide algorithms for parameter and structure inference, which make use of local dependencies and conduct experiments on synthetic data and data-sets generated through a benchmark tool for gene regulatory networks. In doing so, we point out advantages compared to current CTBN extensions.
Estimating the Error of Randomized Newton Methods: A Bootstrap Approach
Authors: Miles Lopes, Jessie X.T. Chen
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: Distributed Optimization, valid

Randomized Newton methods have recently become the focus of intense research activity in large-scale and distributed optimization. Generally, these methods are based on a "computation-accuracy trade-off", which allows the user to gain scalability in exchange for error in the solution. However, the user does not know how much error is created by the randomization, which can be detrimental in two ways: On one hand, the user may try to manage the unknown error with theoretical worst-case error bounds, but this approach is impractical when the bounds involve unknown constants, and it typically leads to excessive computation. On the other hand, the user may select tuning parameters or stopping criteria in a heuristic manner, but this is generally unreliable. Motivated by these difficulties, we develop a bootstrap method for directly estimating the unknown error, which avoids excessive computation and offers greater reliability. Also, we provide non-asymptotic theoretical guarantees to show that the error estimates are valid for several error metrics and algorithms (including GIANT and Newton Sketch). Lastly, we show that the proposed method adds relatively little cost to existing randomized Newton methods, and that it performs well in a range of experimental conditions.
Fast Adaptation to New Environments via Policy-Dynamics Value Functions
Authors: Roberta Raileanu, Max Goldstein, Arthur Szlam, Facebook Rob Fergus
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: MuJoCo

Standard RL algorithms assume fixed environment dynamics and require a significant amount of interaction to adapt to new environments. We introduce Policy-Dynamics Value Functions (PD-VF), a novel approach for rapidly adapting to dynamics different from those previously seen in training. PD-VF explicitly estimates the cumulative reward in a space of policies and environments. An ensemble of conventional RL policies is used to gather experience on training environments, from which embeddings of both policies and environments can be learned. Then, a value function conditioned on both embeddings is trained. At test time, a few actions are sufficient to infer the environment embedding, enabling a policy to be selected by maximizing the learned value function (which requires no additional environment interaction). We show that our method can rapidly adapt to new dynamics on a set of MuJoCo domains.
Growing Adaptive Multi-hyperplane Machines
Authors: Nemanja Djuric, Zhuang Wang, Slobodan Vucetic
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1

Adaptive Multi-hyperplane Machine (AMM) is an online algorithm for learning Multi-hyperplane Machine (MM), a classification model which allows multiple hyperplanes per class. AMM is based on Stochastic Gradient Descent (SGD), with training time comparable to linear Support Vector Machine (SVM) and significantly higher accuracy. On the other hand, empirical results indicate there is a large accuracy gap between AMM and non-linear SVMs. In this paper we show that this performance gap is not due to limited representability of MM model, as it can represent arbitrary concepts. We set to explain a connection between AMM and LVQ, and introduce a novel Growing AMM (GAMM) algorithm motivated by Growing LVQ, that imputes duplicate hyperplanes into MM model during SGD training. We provide theoretical results showing that GAMM has favorable convergence properties, and analyze the generalization bound of MM models. Experiments indicate that GAMM achieves significantly improved accuracy on non-linear problems with only slightly slower training compared to AMM. On some tasks GAMM is even more accurate than non-linear SVM and other popular classifiers such as Neural Networks and Random Forests.
Involutive MCMC: One Way to Derive Them All
Authors: Kirill Neklyudov, Max Welling, Evgenii Egorov, Dmitry Vetrov
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: All

Markov Chain Monte Carlo (MCMC) is a computational approach to fundamental problems such as inference, integration, optimization, and simulation. The field has developed a broad spectrum of algorithms, varying in the way they are motivated, the way they are applied and how efficiently they sample. Despite all the differences, many of them share the same core principle, which we unify as the Involutive MCMC (iMCMC) framework. Building upon this, we describe a wide range of MCMC algorithms in terms of iMCMC, and formulate a number of "tricks" which one can use as design principles for developing new MCMC algorithms. Thus, iMCMC provides a unified view of many known MCMC algorithms, which facilitates the derivation of powerful extensions. We demonstrate the latter with two examples where we transform known reversible MCMC algorithms into more efficient irreversible ones.