pwc-archive/papers-with-abstracts huggingface dataset:
Revisiting the Stability of Stochastic Gradient Descent: A Tightness Analysis
Authors: Yikai Zhang, Samuel Bald, Wenjia Zhang, Vamsi Pritham Pingali, Chao Chen, Mayank Goswami
Date: 2021-01-01 00:00:00
Tasks: Exponential degradation

The technique of algorithmic stability has been used to capture the generalization power of several learning models, especially those trained with stochastic gradient descent (SGD). This paper investigates the tightness of the algorithmic stability bounds for SGD given by~\cite{hardt2016train}. We show that the analysis of~\cite{hardt2016train} is tight for convex objective functions, but loose for non-convex objective functions. In the non-convex case we provide a tighter upper bound on the stability (and hence generalization error), and provide evidence that it is asymptotically tight up to a constant factor. 
However, deep neural networks trained with SGD exhibit much better stability and generalization in practice than what is suggested by these (tight) bounds,
namely, linear or exponential degradation with time for SGD with constant step size. We aim towards characterizing deep learning loss functions with good generalization guarantees, despite being trained using SGD with constant step size.
 We propose the Hessian Contractive (HC) condition, which specifies the contractivity of regions containing local minima in the neural network loss landscape. We provide empirical evidence that this condition holds for several loss functions, and provide theoretical evidence that the known tight SGD stability bounds for convex and non-convex loss functions can be circumvented by HC loss functions, thus partially explaining the generalization of deep neural networks.
The Card Shuffling Hypotheses: Building a Time and Memory Efficient Graph Convolutional Network
Authors: Yawei Li, He Chen, Zhaopeng Cui, Radu Timofte, Marc Pollefeys, Gregory Chirikjian, Luc van Gool
Date: 2021-01-01 00:00:00
Tasks: 3D Classification, Point Cloud Classification, Segmentation, Semantic Segmentation

This paper investigates the design of time and memory efficient graph convolutional networks (GCNs). State-of-the-art GCNs adopt $K$-nearest neighbor (KNN) searches for local feature aggregation and feature extraction operations from layer to layer. Based on the mathematical analysis of existing graph convolution operations, we articulate the following two card shuffling hypotheses. (1) Shuffling the nearest neighbor selection for KNN searches in a multi-layered GCN approximately preserves the local geometric structures of 3D representations. (2) Shuffling the order of local feature aggregation and feature extraction leads to equivalent or similar composite operations for GCNs. The two hypotheses shed light on two possible directions of accelerating modern GCNs. That is, reasonable shuffling of the cards (neighbor selection or local feature operations) can significantly improve time and memory efficiency. A series of experiments show that the network architectures designed based on the proposed card shuffling hypotheses decrease both the time and memory consumption significantly (e.g., about 50% for point cloud classification and semantic segmentation), while maintaining comparable accuracy, on several important tasks in 3D deep learning, i.e., 3D classification, part segmentation, semantic segmentation, and mesh generation.
Fooling a Complete Neural Network Verifier
Authors: Dániel Zombori, Balázs Bánhelyi, Tibor Csendes, István Megyeri, Márk Jelasity
Date: 2021-01-01 00:00:00
Proceeding: ICLR 2021 1
Tasks: valid

The efficient and accurate characterization of the robustness of neural networks to input perturbation is an important open problem. Many approaches exist including heuristic and exact (or complete) methods. Complete methods are expensive but their mathematical formulation guarantees that they provide exact robustness metrics. However, this guarantee is valid only if we assume that the verified network applies arbitrary-precision arithmetic and the verifier is reliable. In practice, however, both the networks and the verifiers apply limited-precision floating point arithmetic. In this paper, we show that numerical roundoff errors can be exploited to craft adversarial networks, in which the actual robustness and the robustness computed by a state-of-the-art complete verifier radically differ. We also show that such adversarial networks can be used to insert a backdoor into any network in such a way that the backdoor is completely missed by the verifier. The attack is easy to detect in its naive form but, as we show, the adversarial network can be transformed to make its detection less trivial. We offer a simple defense against our particular attack based on adding a very small perturbation to the network weights. However, our conjecture is that other numerical attacks are possible, and exact verification has to take into account all the details of the computation executed by the verified networks, which makes the problem significantly harder.
UMEC: Unified model and embedding compression for efficient recommendation systems
Authors: Jiayi Shen, Haotao Wang, Shupeng Gui, Jianchao Tan, Zhangyang Wang, Ji Liu
Date: 2021-01-01 00:00:00
Proceeding: ICLR 2021 1
Tasks: Efficient Neural Network, feature selection, Neural Network Compression, Recommendation Systems, Retrieval

The recommendation system (RS) plays an important role in the content recommendation and retrieval scenarios. The core part of the system is the Ranking neural network, which is usually a bottleneck of whole system performance during online inference.  In this work, we propose a unified model and embedding compression (UMEC) framework to hammer an efficient neural network-based recommendation system.  Our framework jointly learns input feature selection and neural network compression together, and solve them as an end-to-end resource-constrained optimization problem using ADMM.  Our method outperforms other baselines in terms of neural network Flops, sparse embedding feature size and the number of sparse embedding features.  We evaluate our method on the public benchmark of DLRM, trained over the Kaggle Criteo dataset.
Learning One-hidden-layer Neural Networks on Gaussian Mixture Models with Guaranteed Generalizability
Authors: Hongkang Li, Shuai Zhang, Meng Wang
Date: 2021-01-01 00:00:00
Tasks: Binary Classification

We analyze the learning problem of fully connected neural networks with the sigmoid activation function for binary classification from the setup of model estimation. The outputs are assumed to be generated by a ground-truth neural network with the unknown parameters, and the learning objective is to estimate the ground-truth model parameters by minimizing a non-convex cross-entropy loss function of the training data. Instead of following the conventional and restrictive assumption in the literature that the input features follow the standard Gaussian distribution, this paper, for the first time, analyzes a more general and practical scenario that the input features follow a Gaussian mixture model of a finite number of Gaussian distributions of various mean and variance. We propose a gradient descent algorithm with a tensor initialization approach and show that our algorithm converges linearly to a critical point that has a  diminishing distance to the ground-truth model with guaranteed generalizability. We characterize the required number of samples for successful convergence, referred to as the sample complexity,  as a function of the parameters of the Gaussian mixture model. We prove analytically that when any mean or variance in the mixture model is large, or when all variances are close to zero, the sample complexity increases, and the convergence slows down, indicating a more challenging learning problem. Although focusing on one-hidden-layer neural networks, this paper provides the first theoretical analyses of the impact of the parameters of the input distributions on the learning performance.
Fairness guarantee in analysis of incomplete data
Authors: Yiliang Zhang, Qi Long
Date: 2021-01-01 00:00:00
Tasks: Fairness, Missing Values

Missing data are prevalent and present daunting challenges in real data analysis. While there is a growing body of literature on fairness in analysis of fully observed data, there has been little work on investigating fairness in analysis of incomplete data when the goal is to develop a fair algorithm in the complete data domain where there are no missing values. In practice, a popular analytical approach for dealing with missing data is to use only the set of complete cases, i.e., observations with all features fully observed, as a representation of complete data in learning. However, depending on the missing data mechanism,  the complete case domain and the complete data domain may have different data distributions and a fair algorithm in the complete case domain may show disproportionate bias towards some marginalized groups in the complete data domain. To fill this significant gap, we studying the problem of estimating fairness in the complete data domain for a model trained using observed data and evaluated in the complete case domain. We provide upper and lower bounds on the fairness estimation error and conduct numerical experiments to assess our theoretical results. Our work provides the first known results on fairness guarantee in analysis of incomplete data.
Understanding Adversarial Attacks on Autoencoders
Authors: Elsa Riachi, Frank Rudzicz
Date: 2021-01-01 00:00:00
Tasks: Compressive Sensing, Knowledge Distillation

Adversarial  vulnerability  is  a  fundamental  limitation  of  deep  neural  networks which remains poorly understood.  Recent work suggests that adversarial attacks on  deep  neural  network  classifiers  exploit  the  fact  that  non-robust  models  rely on superficial statistics to form predictions. While such features are semantically meaningless, they are strongly predictive of the input’s label, allowing non-robust networks to achieve good generalization on unperturbed test inputs. However, this hypothesis fails to explain why autoencoders are also vulnerable to adversarial attacks, despite achieving low reconstruction error on clean inputs.  We show that training an autoencoder on adversarial input-target pairs leads to low reconstruction error on the standard test set, suggesting that adversarial attacks on autoencoders are predictive.  In this work, we study the predictive power of adversarial examples on autoencoders through the lens of compressive sensing. We characterize the relationship between adversarial perturbations and target inputs and reveal that training autoencoders on adversarial input-target pairs is a form of knowledge distillation, achieved by learning to attenuate structured noise.
Importance-based Multimodal Autoencoder
Authors: Sayan Ghosh, Eugene Laksana, Louis-Philippe Morency, Stefan Scherer
Date: 2021-01-01 00:00:00

Integrating information from multiple modalities (e.g.,  verbal,  acoustic and visual data) into meaningful representations has seen great progress in recent years. However, two challenges are not sufficiently addressed by current approaches: (1) computationally efficient training of multimodal autoencoder networks which are robust in the absence of modalities, and (2) unsupervised learning of important subspaces in each modality which are correlated with other modalities.   In this paper we propose the IMA (Importance-based Multimodal Autoencoder) model, a scalable model that learns modality importances and robust multimodal representations through a novel cross-covariance based loss function.  We conduct experiments on MNIST-TIDIGITS a multimodal dataset of spoken and image digits,and on IEMOCAP, a multimodal emotion corpus. The IMA model is able to distinguish  digits  from  uncorrelated  noise,  and  word-level  importances  learnt  that correspond to the separation between function and emotional words.  The multimodal representations learnt by IMA are also competitive with state-of-the-art baseline approaches on downstream tasks.
Communication in Multi-Agent Reinforcement Learning: Intention Sharing
Authors: Woojun Kim, Jongeui Park, Youngchul Sung
Date: 2021-01-01 00:00:00
Proceeding: ICLR 2021 1
Tasks: Multi-agent Reinforcement Learning, reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

Communication is one of the core components for learning coordinated behavior in multi-agent systems.
In this paper, we propose a new communication scheme named  Intention Sharing (IS) for multi-agent reinforcement learning in order to enhance the coordination among agents. In the proposed IS scheme, each agent generates an imagined trajectory by modeling the environment dynamics and other agents' actions. The imagined trajectory is the simulated future trajectory of each agent based on the learned model of the environment dynamics and other agents and represents each agent's future action plan. Each agent compresses this imagined trajectory capturing its future action plan to generate its intention message for communication by applying an attention mechanism to learn the relative importance of the components in the imagined trajectory based on the received message from other agents. Numeral results show that the proposed IS scheme outperforms other communication schemes in multi-agent reinforcement learning.
Anomaly detection in dynamical systems from measured time series
Authors: Andrei Ivanov, Anna Golovkina
Date: 2021-01-01 00:00:00
Tasks: Anomaly Detection, Benchmarking, Time Series, Time Series Analysis, Time Series Anomaly Detection

The paper addresses a problem of abnormalities detection in nonlinear processes represented by measured time series. Anomaly detection problem is usually formulated as finding outlier data points relative to some usual signals such as unexpected spikes, drops, or trend changes. In nonlinear dynamical systems, there are cases where a time series does not contain statistical outliers while the process corresponds to an abnormal configuration of the dynamical system. Since the polynomial neural architecture has a strong connection with the theory of differential equations, we use it for the feature extraction that describes the dynamical system itself. The paper discusses in both simulations and a practical example with real measurements the applicability of the proposed approach and it's benchmarking with existing methods.
Improving Generalizability of Protein Sequence Models via Data Augmentations
Authors: Hongyu Shen, Layne C. Price, Mohammad Taha Bahadori, Franziska Seeger
Date: 2021-01-01 00:00:00
Tasks: BIG-bench Machine Learning, Contrastive Learning, Data Augmentation, Representation Learning

While protein sequence data is an emerging application domain for machine learning methods, small modifications to protein sequences can result in difficult-to-predict changes to the protein's function. Consequently, protein machine learning models typically do not use randomized data augmentation procedures analogous to those used in computer vision or natural language, e.g., cropping or synonym substitution. In this paper, we empirically explore a set of simple string manipulations, which we use to augment protein sequence data when fine-tuning semi-supervised protein models. We provide 276 different comparisons to the Tasks Assessing Protein Embeddings (TAPE) baseline models, with Transformer-based models and training datasets that vary from the baseline methods only in the data augmentations and representation learning procedure. For each TAPE validation task, we demonstrate improvements to the baseline scores when the learned protein representation is fixed between tasks.  We also show that contrastive learning fine-tuning methods typically outperform masked-token prediction in these models, with increasing amounts of data augmentation generally improving performance for contrastive learning protein methods.  We find the most consistent results across TAPE tasks when using domain-motivated transformations, such as amino acid replacement, as well as restricting the Transformer attention to randomly sampled sub-regions of the protein sequence.  In rarer cases, we even find that information-destroying augmentations, such as randomly shuffling entire protein sequences, can improve downstream performance.
Tight Frame Contractions in Deep Networks
Authors: John Zarka, Florentin Guth, Stéphane Mallat
Date: 2021-01-01 00:00:00
Proceeding: ICLR 2021 1

Numerical experiments demonstrate that deep neural networks classifiers progressively separate class distributions around their mean, achieving linear separability. To explain this mechanism, we introduce structured deep network architectures that can be analyzed mathematically and have high classification accuracies on complex image databases. They iterate over tight frame contractions, which apply a pointwise contraction on decomposition coefficients in a tight frame. Tight frame contractions can reduce within-class variabilities while preserving class mean separations and hence improve the Fisher discriminant ratio. Variance reduction bounds are proved for soft-thresholding contractions with Gaussian mixture models. Iterating on tight frame contractions defines deep convolutional network without bias parameters in hidden layers. We show that spatial filters do not need to be learned, and can be defined from wavelet frames. Learning frame contractions along the resulting wavelet scattering channels is sufficient to nearly reach the classification accuracies of VGG-11 and ResNet-18 on ImageNet, with no learned bias.
Variance Reduction in Hierarchical Variational Autoencoders
Authors: Adeel Pervez, Efstratios Gavves
Date: 2021-01-01 00:00:00

Variational autoencoders with deep hierarchies of stochastic layers have been known to suffer from the problem of posterior collapse, where the top layers fall back to the prior and become independent of input.
We suggest that the hierarchical VAE objective explicitly includes the variance of the function parameterizing the mean and variance of the latent Gaussian distribution which itself is often a high variance function.
Building on this we generalize VAE neural networks by incorporating a smoothing parameter motivated by Gaussian analysis to reduce variance in parameterizing functions and show that this can help to solve the problem of posterior collapse.
We further show that under such smoothing the VAE loss exhibits a phase transition, where the top layer KL divergence sharply drops to zero at a critical value of the smoothing parameter.
We validate the phenomenon across model configurations and datasets.
GANMEX: Class-Targeted One-vs-One Attributions using GAN-based Model Explainability
Authors: Sheng-Min Shih, Pin-Ju Tien, Zohar Karnin
Date: 2021-01-01 00:00:00

Attribution methods have been shown as promising approaches for identifying key features that led to learned model predictions. While most existing attribution methods rely on a baseline input for performing feature perturbations, limited research has been conducted to address the baseline selection issues. Poor choices of baselines can lead to unfair attributions as well as limited ability of one-vs-one explanations for multi-class classifiers, which means explaining why the input belongs to its original class but not the other specified target class. Achieving one-vs-one explanation is crucial when certain classes are more similar than others, e.g. two bird types among multiple animals. One-vs-one explanations focus on key differentiating features rather than features shared across the original and the target classes. In this paper, we present GANMEX, a novel algorithm applying Generative Adversarial Networks (GAN) by incorporating the to-be-explained classifier as part of the adversarial networks. Our approach effectively selects the baseline as the closest realistic sample belong to the target class, which allows attribution methods to provide true one-vs-one explanations. We showed that GANMEX baselines improved the saliency maps visually and led to stronger performance on perturbation-based evaluation metrics over the existing baselines. Attribution results with the existing baselines are known to be insensitive to model randomization, and we demonstrated that GANMEX baselines led to better outcome under the randomization sanity checks.
Transferable Unsupervised Robust Representation Learning
Authors: De-An Huang, Zhiding Yu, Anima Anandkumar
Date: 2021-01-01 00:00:00
Tasks: Data Augmentation, Representation Learning, Transfer Learning

Robustness is an important, and yet, under-explored aspect of unsupervised representation learning, which has seen a lot of recent developments. In this work, we address this gap by developing a novel framework: Unsupervised Robust Representation Learning (URRL), which combines unsupervised representation learning's pretext task and robust supervised learning (e.g., AugMix).  Moreover, it is commonly assumed that there needs to be a trade-off between natural accuracy (on clean data) and robust accuracy (on corrupted data). We upend this view and show that URRL improves both the natural accuracy of unsupervised representation learning and its robustness to corruptions and adversarial noise. A further challenge is that the robustness of a representation might not be preserved in the transfer learning process after fine-tuning on downstream tasks. We develop transferable robustness by proposing a task-agnostic similarity regularization during the fine-tuning process. We show that this improves the robustness of the resulting model without the need for any adversarial training or further data augmentation during fine-tuning.
Differentiable Learning of Graph-like Logical Rules from Knowledge Graphs
Authors: Hongzhi Shi, Quanming Yao, Yong Li
Date: 2021-01-01 00:00:00
Tasks: Knowledge Graphs

Logical rules inside a knowledge graph (KG) are essential for reasoning, logical inference, and rule mining. However, existing works can only handle simple, i.e., chain-like and tree-like, rules and cannot capture KG's complex semantics, which can be better captured by graph-like rules. Besides, learning graph-like rules is very difficult because the graph structure exhibits a huge discrete search space. To address these issues, observing the plausibility of logical rules can be explained by how frequently it appears in a KG, we propose a score function that represents graph-like rules with learnable parameters. The score also helps relax the discrete space into a continuous one and can be uniformly transformed into matrix form by the Einstein summation convention. Thus, it allows us to learn graph-like rules in an efficient, differentiable, and end-to-end training manner. We conduct extensive experiments on real-world and synthetic datasets to show that our method outperforms previous works due to logical rules' better expressive ability. Furthermore, we demonstrate that our method can learn high-quality and interpretable graph-like logical rules.