pwc-archive/papers-with-abstracts huggingface dataset:
Bridging the Gap Between f-GANs and Wasserstein GANs
Authors: Jiaming Song, Stefano Ermon
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: Density Ratio Estimation, Image Generation, Reinforcement Learning (RL)

Generative adversarial networks (GANs) variants approximately minimize divergences between the model and the data distribution using a discriminator. Wasserstein GANs (WGANs) enjoy superior empirical performance, however, unlike in f-GANs, the discriminator does not provide an estimate for the ratio between model and data densities, which is useful in applications such as inverse reinforcement learning. To overcome this limitation, we propose an new training objective where we additionally optimize over a set of importance weights over the generated samples. By suitably constraining the feasible set of importance weights, we obtain a family of objectives which includes and generalizes the original f-GAN and WGAN objectives. We show that a natural extension outperforms WGANs while providing density ratios as in f-GAN, and demonstrate empirical success on distribution modeling, density ratio estimation and image generation, where we achieve state-of-the-art FID scores on CIFAR10 generation.
Deep Reinforcement Learning with Smooth Policy
Authors: Qianli Shen, Yan Li, Haoming Jiang, Zhaoran Wang, Tuo Zhao
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: Deep Reinforcement Learning, reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

Deep neural networks have been widely adopted in modern reinforcement learning (RL) algorithms with great empirical successes in various domains. 
However, the large search space of training a neural network requires a significant amount of data, which makes the current RL algorithms not sample efficient. Motivated by the fact that many environments with continuous state space have smooth transitions, we propose to learn a smooth policy that behaves smoothly with respect to the state. In contrast to policy parameterized by linear/reproducing kernel functions, where simple regularization techniques suffice to control smoothness, for neural network based reinforcement learning algorithms, there is no readily available solution to learn a smooth policy. In this paper, we develop a new training framework --- \textbf{S}mooth \textbf{R}egularized \textbf{R}einforcement \textbf{L}earning ($\textbf{SR}^2\textbf{L}$), where the policy is trained with smoothness-inducing regularization. Such regularization effectively constrains the search space of the learning algorithms and enforces smoothness in the learned policy. We apply the proposed framework to both on-policy (TRPO) and off-policy algorithm (DDPG). Through extensive experiments, we demonstrate that our method achieves improved sample efficiency.
Differentiable Product Quantization for Learning Compact Embedding Layers
Authors: Ting Chen, Lala Li, Yizhou Sun
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: Quantization

Embedding layers are commonly used to map discrete symbols into continuous embedding vectors that reflect their semantic meanings. Despite their effectiveness, the number of parameters in an embedding layer increases linearly with the number of symbols and poses a critical challenge on memory and storage constraints.
In this work, we propose a generic and end-to-end learnable compression framework termed differentiable product quantization (DPQ). We present two instantiations of DPQ that leverage different approximation techniques to enable differentiability in end-to-end learning. Our method can readily serve as a drop-in alternative for any existing embedding layer. Empirically, DPQ offers significant compression ratios (14-238x) at negligible or no performance cost on 10 datasets across three different language tasks.
Estimating Q(s,s') with Deterministic Dynamics Gradients
Authors: Ashley Edwards, Himanshu Sahni, Rosanne Liu, Jane Hung, Ankit Jain, Rui Wang, Adrien Ecoffet, Thomas Miconi, Charles Isbell, Jason Yosinski
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: Transfer Learning

In this paper, we introduce a novel form of a value function, $Q(s, s')$, that expresses the utility of transitioning from a state $s$ to a neighboring state $s'$ and then acting optimally thereafter. In order to derive an optimal policy, we develop a novel forward dynamics model that learns to make next-state predictions that maximize $Q(s,s')$. This formulation decouples actions from values while still learning off-policy. We highlight the benefits of this approach in terms of value function transfer, learning within redundant action spaces, and learning off-policy from state observations generated by sub-optimal or completely random policies.
Fast Deterministic CUR Matrix Decomposition with Accuracy Assurance
Authors: Yasutoshi Ida, Sekitoshi Kanai, Yasuhiro Fujiwara, Tomoharu Iwata, Koh Takeuchi, Hisashi Kashima
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1

The deterministic CUR matrix decomposition is a low-rank approximation method to analyze a data matrix.
It has attracted considerable attention due to its high interpretability, which results from the fact that the decomposed matrices consist of subsets of the original columns and rows of the data matrix.
The subset is obtained by optimizing an objective function with sparsity-inducing norms via coordinate descent.
However, the existing algorithms for optimization incur high computation costs.
This is because coordinate descent iteratively updates all the parameters in the objective until convergence.
This paper proposes a fast deterministic CUR matrix decomposition.
Our algorithm safely skips unnecessary updates by efficiently evaluating the optimality conditions for the parameters to be zeros.
In addition, we preferentially update the parameters that must be nonzeros.
Theoretically, our approach guarantees the same result as the original approach.
Experiments demonstrate that our algorithm speeds up the deterministic CUR while achieving the same accuracy.
Improved Bounds on Minimax Regret under Logarithmic Loss via Self-Concordance
Authors: Blair Bilodeau, Dylan Foster, Daniel Roy
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1

We study the classical problem of forecasting under logarithmic loss while competing against an arbitrary class of experts. We present a novel approach to bounding the minimax regret that exploits the self-concordance property of logarithmic loss. Our regret bound depends on the metric entropy of the expert class and matches previous best known results for arbitrary expert classes. We improve the dependence on the time horizon for classes with metric entropy under the supremum norm of order $\Omega(\gamma^{-p})$ when $p>1$, which includes, for example, Lipschitz functions of dimension greater than 1.
Improved Sleeping Bandits with Stochastic Action Sets and Adversarial Rewards
Authors: Aadirupa Saha, Pierre Gaillard, Michal Valko
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1

In this paper, we consider the problem of sleeping bandits with stochastic action sets and adversarial rewards. In this setting, in contrast to most work in bandits, the actions may not be available at all times. For instance, some products might be out of stock in item recommendation. The best existing efficient (i.e., polynomial-time) algorithms for this problem only guarantee a $O(T^{2/3})$ upper-bound on the regret. Yet, inefficient algorithms based on EXP4 can achieve $O(\sqrt{T})$.  In this paper, we provide a new computationally efficient algorithm inspired by EXP3 satisfying a regret of order  $O(\sqrt{T})$ when the availabilities of each action $i \in \cA$ are independent. We then study the most general version of the problem where at each round available sets are generated from some unknown arbitrary distribution (i.e., without the independence assumption) and propose an efficient algorithm with $O(\sqrt {2^K T})$ regret guarantee. Our theoretical results are corroborated with experimental evaluations.
Improving Transformer Optimization Through Better Initialization
Authors: Xiao Shi Huang, Felipe Perez, Jimmy Ba, Maksims Volkovs
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: Decoder, Language Modeling, Language Modelling, Machine Translation, Translation

The Transformer architecture has achieved considerable success in areas such as language modeling and machine translation. The key component of the Transformer is the attention layer that enables the model to focus on important regions within the input sequence. Gradient optimization with attention layers can be notoriously difficult requiring tricks such as learning rate warmup to prevent divergence.  As Transformer models are becoming larger and more expensive to train, recent research has focused on understanding and improving optimization in these models. In this work our contributions are two-fold. We first investigate and empirically validate the source of optimization problems in encoder-decoder Transformer architecture.We then propose a new weight initialization scheme with theoretical justification, which enables training without warmup or layer normalization. Empirical results on public machine translation benchmarks show that our approach achieves leading accuracy, allowing to train deep Transformer models with 200 layers without difficulty. Full code for this work will be released with the final version of this draft.
Learning Attentive Meta-Transfer
Authors: Jaesik Yoon, Gautam Singh, Sungjin Ahn
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: Meta-Learning, Transfer Learning

Meta-transfer learning seeks to improve the efficiency of learning a new task via both meta-learning and transfer-learning in a setting with a stream of evolving tasks. While standard attention has been effective in a variety of settings, we question its effectiveness in improving meta-transfer learning since the tasks being learned are dynamic, and the amount of context information can be substantially small. In this paper, using a recently proposed meta-transfer learning model, Sequential Neural Processes (SNP), we first empirically show that it suffers a similar underfitting problem observed in the functions inferred by Neural Processes. However, we further demonstrate that unlike the meta-learning setting, standard attention mechanisms are ineffective in meta-transfer learning.~To resolve, we propose a new attention mechanism, Recurrent Memory Reconstruction (RMR), and demonstrate that providing an imaginary context that is recurrently updated and reconstructed with interaction is crucial in achieving effective attention for meta-transfer learning. Furthermore, incorporating RMR into SNP, we propose Attentive Sequential Neural Processes (ASNP) and demonstrate in various tasks that ASNP significantly outperforms the baselines.
Learning Selection Strategies in Buchberger’s Algorithm
Authors: Dylan Peifer, Michael Stillman, Daniel Halpern-Leistner
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1

Studying the set of exact solutions of a system of polynomial equations largely depends on a single iterative algorithm, known as Buchberger’s algorithm. Optimized versions of this algorithm are crucial for many computer algebra systems (e.g., Mathematica, Maple, Sage). We introduce a new approach to Buchberger’s algorithm that uses reinforcement learning agents to perform S-pair selection, a key step in the algorithm. We then study how the difficulty of the problem depends on the choices of domain and distribution of polynomials, about which little is known. Finally, we train a policy model using proximal policy optimization (PPO) to learn S-pair selection strategies for random systems of binomial equations. In certain domains, the trained model outperforms state-of-the-art selection heuristics both in number of iterations of the algorithm and total number of polynomial additions performed. These results provide a proof-of-concept that recent developments in machine learning have the potential to improve performance of algorithms in symbolic computation.
Learning the Valuations of a $k$-demand Agent
Authors: Hanrui Zhang, Vincent Conitzer
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: Active Learning

We study problems where a learner aims to learn the valuations of an agent by observing which goods he buys under varying price vectors.  More specifically, we consider the case of a $k$-demand agent, whose valuation over the goods is additive when receiving up to $k$ goods, but who has no interest in receiving more than $k$ goods.  We settle the query complexity for the active-learning (preference elicitation) version, where the learner chooses the prices to post, by giving a {\em biased binary search} algorithm, generalizing the classical binary search procedure.
We complement our query complexity upper bounds by lower bounds that match up to lower-order terms.  We also study the passive-learning version in which the learner does not control the prices, and instead they are sampled from some distribution.  We show that in the PAC model for passive learning, any {\em empirical risk minimizer} has a sample complexity that is optimal up to a factor of $\widetilde{O}(k)$.
Lower Complexity Bounds for Finite-Sum Convex-Concave Minimax Optimization Problems
Authors: Guangzeng Xie, Luo Luo, Yijiang Lian, Zhihua Zhang
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1

This paper studies the lower bound complexity for minimax optimization problem whose objective function is the average of $n$ individual smooth convex-concave functions. We consider the algorithm which gets access to gradient and proximal oracle for each individual component. For the strongly-convex-strongly-concave case, we prove such an algorithm can not reach an $\varepsilon$-suboptimal point in fewer than $\Omega\left((n+\kappa)\log(1/\varepsilon)\right)$ iterations, where $\kappa$ is the condition number of the objective function. This lower bound matches the upper bound of the existing incremental first-order oracle algorithm stochastic variance-reduced extragradient. We develop a novel construction to show the above result, which partitions the tridiagonal matrix of classical examples into $n$ groups. This construction is friendly to the analysis of incremental gradient and proximal oracle and we also extend the analysis to general convex-concave cases.
Meta Variance Transfer: Learning to Augment from the Others
Authors: Seong-Jin Park, Seungju Han, Ji-won Baek, Insoo Kim, Juhwan Song, Hae Beom Lee, Jae-Joon Han, Sung Ju Hwang
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: Face Recognition, Meta-Learning, Transfer Learning

Humans have the ability to robustly recognize objects with various factors of variations such as nonrigid transformation, background noise, and change in lighting conditions. However, deep learning frameworks generally require huge amount of data with instances under diverse variations, to train a robust model. To alleviate the need of collecting large data and better learn from scarce samples, we propose a novel meta-learning method which learns to transfer factors of variations from one class to another, such that it can improve the classification performance on unseen examples. Transferred variations generate virtual samples that augment the feature space of the target class during training, simulating upcoming query samples with similar variations. By sharing factors of variations across different classes, the model becomes more robust to variations in the unseen examples and tasks using small number of examples per class. We validate our model on multiple benchmark datasets for few-shot classification and face recognition, on which our model significantly improves the performance of the base model, outperforming relevant baselines.
Model-Agnostic Characterization of Fairness Trade-offs
Authors: Joon Kim, Jiahao Chen, Ameet Talwalkar
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: Diagnostic, Fairness, model

There exist several inherent trade-offs while designing a fair model, such as those between the model’s predictive accuracy and fairness, or even among different  notions of fairness. In practice, exploring these trade-offs requires significant human and computational resources. 
We propose a diagnostic to enable practitioners to explore these trade-offs without training a single model. Our work hinges on the observation that many widely-used fairness definitions can be expressed via the fairness-confusion tensor, an object obtained by splitting the traditional confusion matrix according to protected data attributes. Our diagnostic optimizes accuracy and fairness objectives directly over the elements in this tensor in a data-dependent, yet model-agnostic fashion. We further leverage our tensor-based perspective to generalize existing theoretical impossibility results to a wider range of fairness definitions. Finally, we demonstrate the usefulness of the proposed diagnostic on synthetic and real datasets.
Multi-Task Learning with User Preferences: Gradient Descent with Controlled Ascent in Pareto Optimization
Authors: Debabrata Mahapatra, Vaibhav Rajan
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: Multi-Task Learning

Multi-Task Learning (MTL) is a well established learning paradigm for jointly learning models for multiple correlated tasks. Often the tasks conflict requiring trade-offs between them during optimization. Recent advances in multi-objective optimization based MTL  have enabled us to use large-scale deep networks to find one or more Pareto optimal solutions. However, they cannot be used to find exact Pareto optimal solutions satisfying user-specified preferences with respect to task-specific losses, that is not only a common requirement in applications but also a useful way to explore the infinite set of Pareto optimal solutions. We develop the first gradient-based multi-objective MTL algorithm to address this problem. Our unique approach combines multiple gradient descent with carefully controlled ascent, that enables it to trace the Pareto front in a principled manner and makes it robust to initialization. Assuming only differentiability of the task-specific loss functions, we provide theoretical guarantees for convergence. We empirically demonstrate the superiority of our algorithm over state-of-the-art methods.
On a projective ensemble approach to two sample test for equality of distributions
Authors: Zhimei Li, Yaowu Zhang
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1

In this work, we propose a robust test for the multivariate two-sample problem through projective ensemble, which is a generalization of the Cramer-von Mises statistic. The proposed test statistic has a simple closed-form expression without any tuning parameters involved, it is easy to implement can be computed in quadratic time. Moreover, our test is insensitive to the dimension and consistent against all fixed alternatives, it does not require the moment assumption and is robust to the presence of outliers. We study the asymptotic behaviors of the test statistic under the null and two kinds of alternative hypotheses. We also suggest a permutation procedure to approximate critical values and employ its consistency. We demonstrate the effectiveness of our test through extensive simulation studies and a real data application.
On Breaking Deep Generative Model-based Defenses and Beyond
Authors: Yanzhi Chen, Renjie Xie, Zhanxing Zhu
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1

Deep neural networks have been proven to be vulnerable to the so-called adversarial attacks. Recently there have been efforts to defend such attacks with deep generative models. These defenses often involve an inversion phase that they first seek the latent representation that best matches with the input, then use this representation for prediction. Such defenses are often difficult to attack due to the non-analytical gradients. In this work, we develop a new gradient approximation attack to break these defenses. The idea is to view the inversion phase as a dynamical system, through which we extract the gradient with respect to the input by tracing its recent trajectory. An amortized strategy is further developed to accelerate the attack. Experiments show that our attack outperforms state-of-the-art approaches (e.g Backward Pass Differential Approximation) with unprecedented low distortions. Additionally, our empirical results reveal a key defect of current deep generative model-based defenses that it may not realize the on-manifold conjecture expectedly.
Online Learning with Dependent Stochastic Feedback Graphs
Authors: Corinna Cortes, Giulia Desalvo, Claudio Gentile, Mehryar Mohri, Ningshan Zhang
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1

A general framework for online learning with partial information is one where feedback graphs specify which losses can be observed by the learner. We study a
challenging scenario where feedback graphs vary stochastically with time and, more importantly, where graphs and losses are dependent. This scenario
appears in several real-world applications that we describe where the outcome of actions are correlated. We devise a new algorithm for this setting that exploits
the stochastic properties of the graphs and that benefits from favorable regret guarantees. We present a detailed theoretical analysis of this algorithm, and also report the results of a series of experiments on real-world datasets, which show that our algorithm outperforms standard baselines for online learning with feedback graphs.
Optimal Statistical Guaratees for Adversarially Robust Gaussian Classification
Authors: Chen Dan, Yuting Wei, Pradeep Ravikumar
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: Adversarial Robustness, Classification, General Classification, Robust classification

Adversarial robustness has become a fundamental requirement in modern machine learning applications. Yet, there has been surprisingly little statistical understanding so far. In this paper, we provide the first result of the \emph{optimal} minimax guarantees for the excess risk for adversarially robust classification, under Gaussian mixture model proposed by \cite{schmidt2018adversarially}. The results are stated in terms of the \emph{Adversarial Signal-to-Noise Ratio (AdvSNR)}, which
generalizes a similar notion for standard linear classification to the adversarial setting. For the Gaussian mixtures with AdvSNR value of $r$, we prove an excess risk lower bound of order $\Theta(e^{-(\frac{1}{2}+o(1)) r^2} \frac{d}{n})$ and design a computationally efficient estimator that achieves this optimal rate. Our results built upon minimal assumptions while cover a wide spectrum of adversarial perturbations including $\ell_p$ balls for any $p \ge 1$.
Optimizing Dynamic Structures with Bayesian Generative Search
Authors: Minh Hoang, Carleton Kingsford
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: Heuristic Search

Kernel selection for kernel-based methods is prohibitively expensive due to the NP-hard nature of discrete optimization. Since gradient-based optimizers are not applicable due to the lack of a differentiable objective function, many state-of-the-art solutions resort to heuristic search or gradient-free optimization. These approaches, however, require imposing restrictive assumptions on the explorable space of structures such as limiting the active candidate pool, thus depending heavily on the intuition of domain experts. This paper instead proposes \textbf{DTERGENS}, a novel generative search framework that constructs and optimizes a high-performance composite kernel expressions generator. \textbf{DTERGENS} does not restrict the space of candidate kernels and is capable of obtaining flexible length expressions by jointly optimizing a generative termination criterion. We demonstrate that our framework explores more diverse kernels and obtains better performance than state-of-the-art approaches on many real-world predictive tasks.