pwc-archive/papers-with-abstracts huggingface dataset:
Interpolation between CNNs and ResNets
Authors: Zonghan Yang, Yang Liu, Chenglong Bao, Zuoqiang Shi
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: Adversarial Attack, image-classification, Image Classification

Although ordinary differential equations (ODEs) provide insights for designing networks architectures, its relationship with the non-residual convolutional neural networks (CNNs) is still unclear. In this paper, we present a novel ODE model by adding a damping term. It can be shown that the proposed model can recover both a ResNet and a CNN by adjusting an interpolation coefficient. Therefore, the damped ODE model provides a unified framework for the interpretation of CNNs and ResNets. The Lyapunov analysis reveals better stability of the proposed model, and thus yields robustness improvement of the learned networks. Experiments on a number of image classification benchmarks show that the proposed model substantially improves the accuracy of ResNet and ResNeXt over the perturbed inputs from both stochastic noise and adversarial attack methods. Moreover, the loss landscape analysis demonstrates the improved robustness of our method along the attack direction.
Learning and Simulation in Generative Structured World Models
Authors: Zhixuan Lin, Yi-Fu Wu, Skand Peri, Bofeng Fu, Jindong Jiang, Sungjin Ahn
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: object-detection, Object Detection

Despite several recent advances in object-oriented generative temporal models, there are a few key challenges. First, while many of these achievements are indispensable for a general world model, it is unclear how we can combine the benefits of each method into a unified model. Second, despite using generative model objectives, abilities for object detection and tracking are mainly investigated, leaving the crucial ability of generation largely under question. Third, a few key abilities for more faithful generation such as multi-modal uncertainty and situated behavior are missing. In this paper, we introduce Generative Structured World Models (G-SWM). The G-SWM not only unifies the key properties of previous models in a principled framework but also achieves two crucial new abilities, multi-modal uncertainty and situated behavior. By investigating the generation ability in comparison to the previous models, we demonstrate that G-SWM achieves the best or comparable performance for all experiment settings including a few complex settings that have not been tested before.
LTF: A Label Transformation Framework for Correcting Label Shift
Authors: Jiaxian Guo, Mingming Gong, Tongliang Liu, Kun Zhang, DaCheng Tao
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1

Distribution shift is a major obstacle to the deployment of current deep learning models on real-world problems. Let $Y$ be the class label and $X$ the features. We focus on one type of distribution shift, \textit{ label shift}, where the label marginal distribution $P_Y$ changes but the conditional distribution $P_{X|Y}$ does not. Most existing methods estimate the density ratio between the source- and target-domain label distributions by density matching. However, these methods are either computationally infeasible for large-scale data or restricted to shift correction for discrete labels. In this paper, we propose an end-to-end Label Transformation Framework (LTF) for correcting label shift, which implicitly models the shift of $P_Y$ and the conditional distribution $P_{X|Y}$ using neural networks. Thanks to the flexibility of deep networks, our framework can handle continuous, discrete, and even multi-dimensional labels in a unified way and is scalable to large data. Moreover, for high dimensional $X$, such as images, we find that the redundant information in $X$ severely degrades the estimation accuracy. To remedy this issue, we propose to match the distribution implied by our generative model and the target-domain distribution in a low-dimensional feature space that discards information irrelevant to $Y$. Both theoretical and empirical studies demonstrate the superiority of our method over previous approaches.
Manifold Identification for Ultimately Communication-Efficient Distributed Optimization
Authors: Yu-Sheng Li, Wei-Lin Chiang, Ching-pei Lee
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: Distributed Optimization

The expensive inter-machine communication is the bottleneck of
distributed optimization.
Existing study tackles this problem by shortening the communication
rounds, but the reduction of per-round communication cost is not
well-studied.
This work proposes a progressive manifold identification approach with 
sound theoretical justifications to greatly reduce both the
communication rounds and the bytes communicated per round for partly
smooth regularized problems, which include many large-scale machine
learning tasks such as the training of $\ell_1$- and
group-LASSO-regularized models.
Our method uses an inexact proximal quasi-Newton method to iteratively
identify a sequence of low-dimensional smooth manifolds in which the
final solution lies, and restricts the model update within the current
manifold to lower significantly the per-round communication cost.
After identifying the final manifold within which the problem is
smooth, we take superlinear-convergent truncated semismooth
Newton steps obtained through preconditioned conjugate gradient to
largely reduce the communication rounds.
Experiments show that when compared with the state of the art,
the communication cost of our method is significantly lower
and the running time is up to $10$ times faster.
Minimax Rate for Learning From Pairwise Comparisons in the BTL Model
Authors: Julien Hendrickx, Alex Olshevsky, Venkatesh Saligrama
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1

We consider the problem of learning the qualities w_1, ... , w_n of a collection of items by performing noisy comparisons among them. We assume there is a fixed ``comparison graph'' and every neighboring pair of items is compared k times. We will study the popular Bradley-Terry-Luce model,  where the probability that item i wins a  comparison against j equals w_i/(w_i + w_j).  We are interested in how the expected error in estimating the vector w = (w_1, ... , w_n) behaves in the regime when the number of comparisons k is large.

Our contribution is the determination of the minimax rate up to a constant factor. We   show that this rate is achieved by a simple algorithm based on weighted least squares, with weights determined from the empirical outcomes of the comparisons. This algorithm can be implemented  in nearly linear time in the total number of comparisons.
Min-Max Optimization without Gradients: Convergence and Applications to Black-Box Evasion and Poisoning Attacks
Authors: Sijia Liu, Songtao Lu, Xiangyi Chen, Yao Feng, Kaidi Xu, Abdullah Al-Dujaili, Mingyi Hong, Una-May O'Reilly
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1

In this paper, we study the problem of constrained min-max optimization in a black-box setting, where the desired optimizer cannot access the gradients of the objective function but may query its values. We present a principled optimization framework, integrating a zeroth-order (ZO) gradient estimator with an alternating projected stochastic gradient descent-ascent method, where the former only requires a small number of function queries and the later needs just one-step descent/ascent update. We show that the proposed framework, referred to as ZO-Min-Max, has a sub-linear convergence rate under mild conditions and scales gracefully with problem size. We also explore a promising connection between black-box min-max optimization and black-box evasion and poisoning attacks in adversarial machine learning (ML). Our empirical evaluations on these use cases demonstrate the effectiveness of our approach and its scalability to dimensions that prohibit using recent black-box solvers.
Mutual Transfer Learning for Massive Data
Authors: Ching-Wei Cheng, Xingye Qiao, Guang Cheng
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: Transfer Learning

In the transfer learning problem, the target and the source data domains are typically known. In this article, we study a new paradigm called mutual transfer learning where among many heterogeneous data domains, every data domain could potentially be the target of interest, and it could also be a useful source to help the learning in other data domains. However, it is important to note that given a target not every data domain can be a successful source; only data sets that are similar enough to be thought as from the same population can be useful sources for each other. Under this mutual learnability assumption, a confidence distribution fusion approach is proposed to recover the mutual learnability relation in the transfer learning regime. Our proposed method achieves the same oracle statistical inferential accuracy as if the true learnability structure were known. It can be implemented in an efficient parallel fashion to deal with large-scale data. Simulated and real examples are analyzed to illustrate the usefulness of the proposed method.
On Implicit Regularization in $\beta$-VAEs
Authors: Abhishek Kumar, Ben Poole
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: Variational Inference

While the impact of variational inference (VI) on posterior inference in a fixed generative model is well-characterized, its role in regularizing a learned generative model when used in variational autoencoders (VAEs) is poorly understood. We study the regularizing effects of variational distributions on learning in generative models from two perspectives. First, we analyze the role that the choice of variational family plays in imparting uniqueness to the learned model by restricting the set of optimal generative models. Second, we study the regularization effect of the variational family on the local geometry of the decoding model. This analysis uncovers the regularizer implicit in the $\beta$-VAE objective, and leads to an approximation consisting of a deterministic autoencoding objective plus analytic regularizers that depend on the Hessian or Jacobian of the decoding model, unifying VAEs with recent heuristics proposed for training regularized autoencoders. We empirically verify these findings, observing that the proposed deterministic objective indeed exhibits similar behavior to the $\beta$-VAE in terms of objective value and sample quality on CelebA and MNIST.
Reinforcement Learning with Differential Privacy
Authors: Giuseppe Vietri, Borja de Balle Pigem, Steven Wu, Akshay Krishnamurthy
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: Decision Making, Privacy Preserving, reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

Motivated by high-stakes decision-making domains like personalized
medicine where user information is inherently sensitive, we design
privacy preserving exploration policies for episodic reinforcement
learning (RL). We first provide a meaningful privacy formulation using
the notion of joint differential privacy (JDP)--a strong variant of
differential privacy for settings where each user receives their own
sets of output (e.g., policy recommendations). We then develop a
private optimism-based learning algorithm that simultaneously achieves
strong PAC and regret bounds, and enjoys a JDP guarantee. Our
algorithm only pays for a moderate privacy cost on exploration: in
comparison to the non-private bounds, the privacy parameter only
appears in lower-order terms.  Finally, we present lower bounds on
sample complexity and regret for reinforcement learning subject to
JDP.
Safe Deep Semi-Supervised Learning for Unseen-Class Unlabeled Data
Authors: Lan-Zhe Guo, Zhen-Yu Zhang, Yuan Jiang, Yufeng Li, Zhi-Hua Zhou
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1

Deep semi-supervised learning (SSL) has been shown very effectively. However, its performance is seriously hurt when the class distribution is mismatched, among which a common phenomenon is that unlabeled data contains the classes not seen in labeled data. Efforts on this aspect remain to be limited. This paper proposes a simple and effective safe deep SSL method to alleviate the performance harm caused by it. In theory, the result learned from the new method is never worse than learning from merely labeled data, and it is theoretically guaranteed that its generalization approaches the optimal in the order $O(\sqrt{d\ln(n)/n})$, even faster than the convergence rate in supervised learning associated with massive parameters. In the experiment of benchmark data, unlike the existing deep SSL methods which are no longer as good as supervised learning in 40\% of unseen-class unlabeled data, the new method can still achieve performance gain in more than 60\% of unseen-class unlabeled data. The proposal is suitable for any deep SSL algorithm and can be easily extended to handle other cases of class distribution mismatch.
Searching to Exploit Memorization Effect in Learning with Noisy Labels
Authors: QUANMING YAO, Hansi Yang, Bo Han, Gang Niu, James Kwok
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: AutoML, Learning with noisy labels, Memorization

Sample selection approaches are popular in robust learning from noisy labels. However, how to properly control the selection process so that deep networks can benefit from the memorization effect is a hard problem. In this paper, motivated by the success of automated machine learning (AutoML), we model this issue as a function approximation problem. 
Specifically, we design a domain-specific search space based on general patterns of the memorization effect and propose a novel Newton algorithm to solve the bi-level optimization problem efficiently.  We further provide a theoretical analysis of the algorithm, which ensures a good approximation to critical points. Experiments are performed on both benchmark and real-world data sets. Results demonstrate that the proposed method is much better than the state-of-the-art noisy-label-learning approaches, and also much more efficient than existing AutoML algorithms.
Self-concordant analysis of Frank-Wolfe algorithm
Authors: Mathias Staudigl, Pavel Dvurechenskii, Shimrit Shtern, Kamil Safin, Petr Ostroukhov
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: Quantum State Tomography

Projection-free optimization via different variants of the Frank-Wolfe (FW) method has become one of the cornerstones in optimization for machine learning since in many cases the linear minimization oracle is much cheaper to implement than projections and some sparsity needs to be preserved. In a number of applications, e.g. Poisson inverse problems or quantum state tomography, the loss is given by a
self-concordant (SC) function having unbounded curvature, implying absence of theoretical guaranteesfor the existing FW methods. We use the
theory of SC functions to provide a new adaptive step size for FW methods and prove global convergence rate O(1/k), k being the iteration counter. If the problem can be represented by a local linear minimization oracle, we are the first
to propose a FW method with linear convergence rate without assuming neither strong convexity nor a Lipschitz continuous gradient.
Semismooth Newton Algorithm for Efficient Projections onto $\ell_{1, \infty}$-norm Ball
Authors: Dejun Chu, Chang-Shui Zhang, Shiliang Sun, Qing Tao
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1

Structured sparsity-inducing $\ell_{1, \infty}$-norm, as a generalization of the classical $\ell_1$-norm, plays an important role in jointly sparse models which select or remove simultaneously all the variables forming a group. However, its resulting problem is more difficult to solve than the conventional $\ell_1$-norm constrained problem. In this paper, we propose an efficient algorithm for Euclidean projection onto $\ell_{1, \infty}$-norm ball. We tackle the projection problem via semismooth Newton algorithm to solve the system of semismooth equations. Meanwhile, exploiting the structure of Jacobian matrix via LU decomposition yields an equivalent algorithm which is proved to terminate after a finite number  of iterations. Empirical studies demonstrate that our proposed algorithm outperforms the existing state-of-the-art solver and is promising for the optimization of learning problems with $\ell_{1, \infty}$-norm ball constraint.
Streaming k-Submodular Maximization under Noise subject to Size Constraint
Authors: Lan N. Nguyen, My T. Thai
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1

Maximizing on k-submodular functions subject to size constraint has received extensive attention recently. In this paper, we investigate a more realistic scenario of this problem that (1) obtaining exact evaluation of an objective function is impractical, instead, its noisy version is acquired; and (2) algorithms are required to take only one single pass over dataset, producing solutions in a timely manner. We propose two novel streaming algorithms, namely DStream and RStream, with their theoretical performance guarantees. We further demonstrate the efficiency of our algorithms in two application, showing that our algorithms can return comparative results to state-of-the-art non-streaming methods while using a much fewer number of queries.
Streaming Submodular Maximization under a k-Set System Constraint
Authors: Ran Haba, Ehsan Kazemi, Moran Feldman, Amin Karbasi
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: Data Summarization, Movie Recommendation

In this paper, we propose a novel framework that converts streaming algorithms for monotone submodular maximization into streaming algorithms for non-monotone submodular maximization. This reduction readily leads to the currently tightest deterministic approximation ratio for submodular maximization subject to a $k$-matchoid constraint. Moreover, we propose the first streaming algorithms for monotone submodular maximization subject to $k$-extendible and $k$-system constraints. Together with our proposed reduction, we obtain $O(k\log k)$ and $O(k^2\log k)$ approximation ratio for submodular maximization subject to the above constraints, respectively. We extensively evaluate the empirical performance of our algorithm against the existing work in a series of experiments including finding the maximum independent set in randomly generated graphs, maximizing linear functions over social networks, movie recommendation, Yelp location summarization, and Twitter data summarization.
Student Specialization in Deep Rectified Networks With Finite Width and Input Dimension
Authors: Yuandong Tian
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: Inductive Bias

We consider a deep ReLU / Leaky ReLU student network trained from the output of a fixed teacher network of the same depth, with Stochastic Gradient Descent (SGD). The student network is \emph{over-realized}: at each layer $l$, the number $n_l$ of student nodes is more than that ($m_l$) of teacher. Under mild conditions on dataset and teacher network, we prove that when the gradient is small at every data sample, each teacher node is \emph{specialized} by at least one student node \emph{at the lowest layer}. For two-layer network, such specialization can be achieved by training on any dataset of \emph{polynomial} size $\cO( K^{5/2} d^3 \epsilon^{-1})$ (sample size including augmentation) until the gradient magnitude drops to $\cO(\epsilon/K^{3/2}\sqrt{d})$, where $d$ is the input dimension, $K = m_1 + n_1$ is the total number of neurons in the lowest layer of teacher and student. To our best knowledge, we are the first to give polynomial sample complexity for student specialization of training two-layer (Leaky) ReLU networks with finite depth and width in teacher-student setting, and finite complexity for the lowest layer specialization in multi-layer case, without parametric assumption of the input (like Gaussian). Our theory suggests that teacher nodes with large fan-out weights get specialized first when the gradient is still large, while others are specialized with small gradient, which suggests inductive bias in training. This shapes the stage of training as empirically observed in multiple previous works. Experiments on synthetic and CIFAR10 verify our findings.
Batch Reinforcement Learning with Hyperparameter Gradients
Authors: Byung-Jun Lee, Jongmin Lee, Peter Vrancx, Dongho Kim, Kee-Eung Kim
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: continuous-control, Continuous Control, reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

We consider the batch reinforcement learning problem where the agent needs to learn only from a fixed batch of data, without further interaction with the environment. In such a scenario, we want to prevent the optimized policy from deviating too much from the data collection policy since the estimation becomes highly unstable otherwise due to the off-policy nature of the problem. However, imposing this requirement too strongly will result in a policy that merely follows the data collection policy. Unlike prior work where this trade-off is controlled by hand-tuned hyperparameters, we propose a novel batch reinforcement learning approach, batch optimization of policy and hyperparameter (BOPAH), that uses a gradient-based optimization of the hyperparameter using held-out data. We show that BOPAH outperforms other batch reinforcement learning algorithms in tabular and continuous control tasks, by finding a good balance to the trade-off between adhering to the data collection policy and pursuing the possible policy improvement.
Detecting Out-of-Distribution Examples with Gram Matrices
Authors: Chandramouli Shama Sastry, Sageev Oore
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1
Tasks: Out of Distribution (OOD) Detection

When presented with Out-of-Distribution (OOD) examples, deep neural networks yield confident, incorrect predictions. Detecting OOD examples is challenging, and the potential risks are high. In this paper, we propose to detect OOD examples by identifying inconsistencies between activity patterns and predicted class. We find that characterizing activity patterns by Gram matrices and identifying anomalies in Gram matrix values can yield high OOD detection rates. We identify anomalies in the Gram matrices by simply comparing each value with its respective range observed over the training data. Unlike many approaches, this can be used with any pre-trained softmax classifier and neither requires access to OOD data for fine-tuning hyperparameters, nor does it require OOD access for inferring parameters. We empirically demonstrate applicability across a variety of architectures and vision datasets and, for the important and surprisingly hard task of detecting far out-of-distribution examples, it generally performs better than or equal to state-of-the-art OOD detection methods (including those that do assume access to OOD examples).
Distributed Online Optimization over a Heterogeneous Network
Authors: Nima Eshraghi, Ben Liang
Date: 2020-01-01 00:00:00
Proceeding: ICML 2020 1

In distributed online optimization over a computing network with heterogeneous nodes, slow nodes can adversely affect the progress of fast nodes, leading to drastic slowdown of the overall convergence process. To address this issue, we consider a new algorithm termed Distributed Any-Batch Mirror Descent (DABMD), which is based on distributed Mirror Descent but uses a fixed per-round computing time to limit the waiting by fast nodes to receive information updates from slow nodes. DABMD is characterized by varying minibatch sizes across nodes. It is applicable to a broader range of problems compared with existing distributed online optimization methods such as those based on dual averaging, and it accommodates time-varying network topology. We study two versions of DABMD, depending on whether the computing nodes average their primal variables via single or multiple consensus iterations. We show that both versions provide strong theoretical performance guarantee, by deriving upperbounds on their expected dynamic regret, which capture the variability in minibatch sizes. Our experimental results show substantial reduction in cost and acceleration in convergence compared with the known best alternative.