pwc-archive/papers-with-abstracts huggingface dataset:
Partial Identification of Counterfactual Distributions
Authors: Junzhe Zhang, Elias Bareinboim, Jin Tian
Date: 2021-05-21 00:00:00
Proceeding: NeurIPS 2021 12
Tasks: counterfactual

This paper investigates the problem of bounding counterfactual queries from a combination of observational data and qualitative assumptions about the underlying data-generating model. These assumptions are usually represented in the form of a causal diagram (Pearl, 1995). We show that all counterfactual distributions (over finite observed variables) in an arbitrary causal diagram could be generated by a special family of structural causal models (SCMs), compatible with the same causal diagram, where unobserved (exogenous) variables are discrete, taking values in a finite domain.  This entails a reduction in which the space where the original, arbitrary SCM lives can be mapped to a dual, more well-behaved space where the exogenous variables are discrete, and more easily parametrizable. Using this reduction, we translate the bounding problem in the original space into an equivalent optimization program in the new space. Solving such programs leads to optimal bounds over unknown counterfactuals. Finally, we develop effective Monte Carlo algorithms to approximate these optimal bounds from a finite number of observational data. Our algorithms are validated extensively on synthetic datasets.
Distributed Learning with Strategic Users: A Repeated Game Approach
Authors: Abdullah Basar Akbay, Junshan Zhang
Date: 2021-05-21 00:00:00
Proceeding: NeurIPS 2021 12
Tasks: Action Classification

We consider a distributed learning setting where strategic users are incentivized, by a cost-sensitive fusion center, to train a learning model based on local data. The users are not obliged to provide their true gradient updates and the fusion center is not capable of validating the authenticity of reported updates. Thus motivated, we formulate the interactions between the fusion center and the users as repeated games, manifesting an under-explored interplay between machine learning and game theory. We then develop an incentive mechanism for the fusion center based on a joint gradient estimation and user action classification scheme, and study its impact on the convergence performance of distributed learning. Further, we devise an adaptive zero-determinant (ZD) strategy, thereby generalizing the celebrated ZD strategy to the repeated games with time-varying stochastic errors. Theoretical and empirical analysis show that the fusion center can incentivize the strategic users to cooperate and report informative gradient updates, thus ensuring the convergence.
Reinforcement learning for instance segmentation with high-level priors
Authors: Paul Hilt, Edgar Kaziakhmedov, Sourabh Bhide, Maria Leptin, Constantin Pape, Anna Kreshuk
Date: 2021-05-21 00:00:00
Proceeding: NeurIPS 2021 12
Tasks: graph partitioning, Instance Segmentation, reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL), Segmentation, Semantic Segmentation, Vocal Bursts Intensity Prediction

Instance segmentation is an important computer vision problem which remains challenging despite impressive recent advances due to deep learning-based methods. Given sufficient training data, fully supervised methods can yield excellent performance, but annotation of ground-truth data remains a major bottleneck, especially for biomedical applications where it has to be performed by domain experts. The amount of labels required can be drastically reduced by using rules derived from prior knowledge to guide the segmentation. However, these rules are in general not differentiable and thus cannot be used with existing methods. Here, we relax this requirement by using stateless actor critic reinforcement learning, which enables non-differentiable rewards. We formulate the instance segmentation problem as graph partitioning and the actor critic predicts the edge weights driven by the rewards, which are based on the conformity of segmented instances to high-level priors on object shape, position or size. The experiments on toy and real datasets demonstrate that we can achieve excellent performance without any direct supervision based only on a rich set of priors.
Is Heterophily A Real Nightmare For Graph Neural Networks Performing Node Classification?
Authors: Sitao Luan, Chenqing Hua, Qincheng Lu, Jiaqi Zhu, Mingde Zhao, Shuyuan Zhang, Xiao-Wen Chang, Doina Precup
Date: 2021-05-21 00:00:00
Proceeding: NeurIPS 2021 12
Tasks: Inductive Bias, Node Classification

Graph Neural Networks (GNNs) extend basic Neural Networks (NNs) by using the graph structures based on the relational inductive bias (homophily assumption). Though GNNs are believed to outperform NNs in real-world tasks, performance advantages of GNNs over graph-agnostic NNs seem not generally satisfactory. Heterophily has been considered as a main cause and numerous works have been put forward to address it. In this paper, we first show that not all cases of heterophily are harmful for GNNs with aggregation operation. Then, we propose new metrics based on a similarity matrix which considers the influence of graph structure and input features on GNNs. The metrics demonstrate advantages over the commonly used homophily metrics by tests on synthetic graphs. From the metrics and the observations, we find some cases of harmful heterophily can be addressed by diversification operation. With this fact and knowledge of filterbanks, we propose the Adaptive Channel Mixing (ACM) framework to adaptively exploit aggregation, diversification and identity operations in each GNN layer to address harmful heterophily. We validate the ACM-augmented baselines with 11 real-world node classification tasks. They consistently achieve significant performance gain and exceed the state-of-the-art GNNs on most of the tasks without incurring significant computational burden.
Test-Time Adaptation to Distribution Shifts by Confidence Maximization and Input Transformation
Authors: Chaithanya Kumar Mummadi, Robin Hutmacher, Kilian Rambach, Evgeny Levinkov, Thomas Brox, Jan Hendrik Metzen
Date: 2021-05-21 00:00:00
Proceeding: NeurIPS 2021 12
Tasks: Test-time Adaptation

Deep neural networks often exhibit poor performance on data that is unlikely under the train-time data distribution, for instance data affected by corruptions. Previous works demonstrate that test-time adaptation to data shift, for instance using entropy minimization, effectively improves performance on such shifted distributions. This paper focuses on the fully test-time adaptation setting, where only unlabeled data from the target distribution is required. This allows adapting arbitrary pretrained networks. Specifically, we propose a novel loss that improves test-time adaptation by addressing both premature convergence and instability of entropy minimization. This is achieved by replacing the entropy by a non-saturating surrogate and adding a diversity regularizer based on batch-wise entropy maximization that prevents convergence to trivial collapsed solutions. Moreover, we propose to prepend an input transformation module to the network that can partially undo test-time distribution shifts. Surprisingly, this preprocessing can be learned solely using the fully test-time adaptation loss in an end-to-end fashion without any target domain labels or source domain data. We show that our approach outperforms previous work in improving the robustness of publicly available pretrained image classifiers to common corruptions on such challenging benchmarks as ImageNet-C.
Impossibility results for fair representation
Authors: Tosca Lechner, Nivasini Ananthakrishnan, Sushant Agarwal, Shai Ben-David
Date: 2021-05-21 00:00:00
Proceeding: NeurIPS 2021 12
Tasks: Fairness

With the growing awareness to fairness in machine learning and the realization of the central role that data representation has in data processing tasks, there is an obvious interest in notions of fair data representations. We provide a formal framework for examining the fairness of data representations through the lens of their effect on decisions (mainly classification) made based on data represented that way.  Using that framework, we prove that several desiderata for fair representations cannot be achieved. While some of our conclusions are intuitive, we formulate (and prove) crisp statements of such impossibilities, often contrasting impressions conveyed by many recent works on fair representations.
$\texttt{DoStoVoQ}$: Doubly Stochastic Voronoi Vector Quantization SGD for Federated Learning
Authors: Louis Leconte, Aymeric Dieuleveut, Edouard Oyallon, Eric Moulines, Gilles Pages
Date: 2021-05-21 00:00:00
Proceeding: NeurIPS 2021 12
Tasks: Federated Learning, Quantization

The growing size of models and datasets have made distributed implementation of stochastic gradient descent (SGD) an active field of research. However the high bandwidth cost of communicating gradient updates between nodes remains a bottleneck;  lossy compression is a way to alleviate this problem. We propose a new  $\textit{unbiased}$ Vector Quantizer (VQ), named $\texttt{StoVoQ}$, to perform gradient quantization. This approach relies on introducing randomness within the quantization process, that is based on the use of unitarily invariant random codebooks and on a straightforward  bias compensation method. The distortion of $\texttt{StoVoQ}$  significantly improves upon existing quantization algorithms. Next, we explain how to combine this quantization scheme within a Federated Learning framework for complex high-dimensional model (dimension $>10^6$), introducing $\texttt{DoStoVoQ}$. We provide theoretical guarantees on the quadratic error  and (absence of) bias of the compressor, that allow to leverage strong theoretical results of convergence, e.g., with heterogeneous workers or variance reduction. Finally, we show that training on convex and non-convex deep learning problems, our method leads to significant reduction of bandwidth use while preserving model accuracy.
A Probabilistic Representation for Deep Learning: Delving into The Information Bottleneck Principle
Authors: Xinjie Lan, Kenneth Barner
Date: 2021-05-21 00:00:00
Proceeding: NeurIPS 2021 12

The Information Bottleneck (IB) principle has recently attracted great attention to explaining Deep Neural Networks (DNNs), and the key is to accurately estimate the mutual information between a hidden layer and dataset. However, some unsettled limitations weaken the validity of the IB explanation for DNNs. To address these limitations and fully explain deep learning in an information theoretic fashion, we propose a probabilistic representation for deep learning that allows the framework to estimate the mutual information, more accurately than existing non-parametric models, and also quantify how the components of a hidden layer affect the mutual information. Leveraging the probabilistic representation, we take into account the back-propagation training and derive two novel Markov chains to characterize the information flow in DNNs. We show that different hidden layers achieve different IB trade-offs depending on the architecture and the position of the layers in DNNs, whereas a DNN satisfies the IB principle no matter the architecture of the DNN.
ActCooLR – High-Level Learning Rate Schedules using Activation Pattern Temperature
Authors: David Hartmann, Sebastian Brodehl, Michael Wand
Date: 2021-05-21 00:00:00
Proceeding: NeurIPS 2021 12
Tasks: image-classification, Image Classification, Scheduling, Vocal Bursts Intensity Prediction

We consider the aspect of learning rate (LR-)scheduling in neural networks, which often significantly affects achievable training time and generalization performance. Although schedules such as 1-cycle offer substantial gains over base-line methods, the effect of LR-curves on the training process is not very well understood. In order to gain more insight into the training process, we combine information theoretic ideas and probabilistic optimization, namely simulated annealing. In more detail, we introduce the activation pattern temperature, which (i) captures changes in the non-linear behavior of ReLU networks and (ii) is free of hyperparameters and thus is more interpretable. Examining the training process, 1-cycle simply yields a linear decrease in temperature, reminiscent of successful cooling strategies in simulated annealing. In order to test a causal connection, we devise ActCooLR, an automatic LR-scheduler that produces declining temperature profiles. In experiments with various CNN architectures and different image classification data sets, we obtain results that perform favorably or exceed the performance of hand-tuned schedules.
How Gradient Descent Separates Data with Neural Collapse: A Layer-Peeled Perspective
Authors: Wenlong Ji, Yiping Lu, Yiliang Zhang, Zhun Deng, Weijie J Su
Date: 2021-05-21 00:00:00
Proceeding: NeurIPS 2021 12
Tasks: Inductive Bias

In this paper, we derive a landscape analysis to the surrogate model to study the inductive bias of the neural features and parameters from neural networks with cross-entropy. We show that once the training cross-entropy loss decreases below a certain threshold, the features and classifiers in the last layer of the neural network will converge to a certain geometry structure, which is known as neural collapse\citep{papyan2020prevalence,fang2021layer}, \emph{i.e.} cross-example within-class variability of last-layer feature collapses to zero and the class-means converge to a Simplex Equiangular Tight Frame (ETF). We illustrate that the cross-entropy loss enjoys a benign global landscape where all the critical points are strict saddles whose Hessian exhibit negative curvature directions except the only global minimizers which exhibit neural collapse phenomenon.
Metropolis-CVAE: Bootstrapping Labels for Bayesian Inference via Semi-Supervised Conditional Variational Autoencoders
Authors: Jonathan Doucette, Christian Kames, Alexander Rauscher
Date: 2021-05-21 00:00:00
Proceeding: NeurIPS 2021 12
Tasks: Bayesian Inference, parameter estimation

In Bayesian parameter estimation, models make simplifying assumptions to make parameter inference feasible. If learned inference methods are trained using data simulated by models, however, distributional differences between simulated and observed data may lead to biased inference results on the observed data. In this work, we introduce a semi-supervised learned Bayesian inference method which makes use of both simulated data -- for which the underlying parameters are known by construction -- and unlabeled data, which may depend on nuissance parameters not captured by the simulation procedure. A conditional variational autoencoder (CVAE) is trained to perform approximate inference simultaneously on the sets of labeled simulated data and unlabeled data, where the unlabeled data is initialized with arbitrary pseudo labels. At each training iteration, new candidate pseudo labels are drawn from the CVAE posterior and the pseudo labels are updated using the Metropolis-Hastings algorithm. This process results in a Markov chain of bootstrapped pseudo labels for each unlabeled datum, effectively performing online Markov chain Monte Carlo (MCMC) inference wherein the proposal distribution is a CVAE informed by labeled simulated data, producing proposals which are increasingly likely to be accepted as training proceeds. The resulting CVAE is able to efficiently produce samples from the posterior distributions of both the simulated and unlabeled data, implicitly marginalizing over nuissance parameters in the unlabeled data. We demonstrate the effectiveness of this method in magnetic resonance imaging (MRI) where MCMC is computationally impractical to due the (3+1)D nature of the images, showing improvement against traditional MCMC inference in both speed and posterior quality.
What Breaks The Curse of Dimensionality in Deep Learning?
Authors: Lechao Xiao, Jeffrey Pennington
Date: 2021-05-21 00:00:00
Proceeding: NeurIPS 2021 12
Tasks: Deep Learning, Open-Ended Question Answering

Although learning in high dimensions is commonly believed to suffer from the curse of dimensionality, modern machine learning methods often exhibit an astonishing power to tackle a wide range of challenging real-world learning problems without using abundant amounts of data. How exactly these methods break this curse remains a fundamental open question in the theory of deep learning. While previous efforts have investigated this question by studying the data (D), model (M), and inference algorithm (I) as independent modules, in this paper we analyzes the triple (D, M, I) as an integrated system. We examine the basic symmetries of such systems associated to four of the main architectures in deep learning: fully-connected networks (FCN), locally-connected networks (LCN), and convolutional networks with and without pooling (GAP/VEC). By computing an eigen-decomposition of the infinite-width limits (aka Neural Kernels) of these architectures, we characterize how inductive biases (locality, weight-sharing, pooling, etc) and the breaking of spurious symmetries can affect the performance of these learning systems. Our theoretical analysis shows that for many real-world tasks it is locality rather than symmetry that provides the first-order remedy to the curse of dimensionality. Empirical results on state-of-the-art models on ImageNet corroborate our results.
Revisiting Design Choices in Offline Model Based Reinforcement Learning
Authors: Cong Lu, Philip Ball, Jack Parker-Holder, Michael Osborne, S Roberts
Date: 2021-05-21 00:00:00
Proceeding: NeurIPS 2021 12
Tasks: Bayesian Optimization, Model-based Reinforcement Learning, Offline RL, reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

Offline reinforcement learning enables agents to make use of large pre-collected datasets of environment transitions and learn control policies without the need for potentially expensive or unsafe online data collection. Recently, significant progress has been made in offline RL, with the dominant approach becoming methods which leverage a learned dynamics model. This typically involves constructing a probabilistic model, and using it to penalize rewards in regions of high uncertainty, solving for a pessimistic MDP that lower bounds the true MDP. Recent work, however, exhibits a breakdown between theory and practice, whereby pessimistic return ought to be bounded by the total variation distance of the model from the true dynamics, but is instead implemented through a penalty based on estimated model uncertainty. This has spawned a variety of uncertainty heuristics, with little to no comparison between differing approaches. In this paper, we show these heuristics have significant interactions with other design choices, such as the number of models in the ensemble, the model rollout length and the penalty weight. Furthermore, we compare these uncertainty heuristics under a new evaluation protocol that, for the first time, captures the specific covariate shift induced by model-based RL. This allows us to accurately assess the calibration of different proposed penalties. Finally, with these insights, we show that selecting these key hyperparameters using Bayesian Optimization produces drastically stronger performance than existing hand-tuned methods.
Meta Reinforcement Learning for Fast Adaptation of Hierarchical Policies
Authors: David Kuric, Herke van Hoof
Date: 2021-05-21 00:00:00
Proceeding: NeurIPS 2021 12
Tasks: Meta-Learning, Meta Reinforcement Learning, reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

Hierarchical methods have the potential to allow reinforcement learning to scale to larger environments. Decomposing a task into transferable components, however, remains a challenging problem. In this paper, we propose a meta-learning approach for learning such a decomposition within the options framework. We formulate the objective as a bi-level optimization problem in which sub-policies and their terminations should facilitate fast learning on a family of tasks. Once such a set of options is obtained, it can then be used in new tasks where only the sequencing of options needs to be chosen. Our formalism tends to result in options where fewer decisions are needed to solve such new tasks. Experimentally, we show that our method is able to learn transferable components which accelerate learning and performs better than existing methods developed for this setting in the challenging ant maze locomotion task.
Gradient Clipping Helps in Non-Smooth Stochastic Optimization with Heavy-Tailed Noise
Authors: Eduard Gorbunov, Marina Danilova, Innokentiy Andreevich Shibaev, Pavel Dvurechensky, Alexander Gasnikov
Date: 2021-05-21 00:00:00
Proceeding: NeurIPS 2021 12
Tasks: Stochastic Optimization

Thanks to their practical efficiency and random nature of the data, stochastic first-order methods are standard for training large-scale machine learning models. Random behavior may cause a particular run of an algorithm to result in a highly suboptimal objective value, whereas theoretical guarantees are usually proved for the expectation of the objective value. Thus, it is essential to theoretically guarantee that algorithms provide small objective residual with high probability. Existing methods for non-smooth stochastic convex optimization have complexity bounds with the dependence on the confidence level that is either negative-power or logarithmic but under an additional assumption of sub-Gaussian (light-tailed) noise distribution that may not hold in practice, e.g., in several NLP tasks. In our paper, we resolve this issue and derive the first high-probability convergence results with logarithmical dependence on the confidence level for non-smooth convex stochastic optimization problems with non-sub-Gaussian (heavy-tailed) noise. To derive our results, we propose novel stepsize rules for two stochastic methods with gradient clipping. Moreover, our analysis works for generalized smooth objectives with Holder-continuous gradients, and for both methods, we provide an extension for strongly convex problems. Finally, our results imply that the first (accelerated) method we consider also has optimal iteration and oracle complexity in all the regimes, and the second one is optimal in the non-smooth setting.
Hierarchical Prototype Network for Continual Graph Representation Learning
Authors: Xikun Zhang, Dongjin Song, DaCheng Tao
Date: 2021-05-21 00:00:00
Proceeding: NeurIPS 2021 12
Tasks: Attribute, Continual Learning, Graph Representation Learning, Representation Learning

Despite significant advances in graph representation learning, little attention has been paid to graph data in which new categories of nodes (e.g., new research areas in citation networks or new types of products in co-purchasing networks) and their associated edges are continuously emerging. The key challenge is to incorporate the feature and topological information of new nodes in a continuous and effective manner such that performance over existing nodes is uninterrupted. To this end, we present Hierarchical Prototype Networks (HPNs) which can adaptively extract different levels of abstract knowledge in the form of prototypes to represent continually expanded graphs. Specifically, we first leverage a set of Atomic Feature Extractors (AFEs) to generate basic features which can
encode both the elemental attribute information and the topological structure of the target node. Next, we develop HPNs by adaptively selecting relevant AFEs and represent each node with three-levels of prototypes, i.e., atomic-level, node-level, and class-level. In this way, whenever a new category of nodes is given, only the relevant AFEs and prototypes at each level will be activated and refined, while others remain uninterrupted. Finally, we provide the theoretical analysis on memory consumption bound and the continual learning capability of HPNs. Extensive empirical studies on eight different public datasets justify that HPNs are memory efficient and can achieve state-of-the-art performance on different continual graph representation learning tasks.