pwc-archive/papers-with-abstracts huggingface dataset:
Graph Stochastic Neural Networks for Semi-supervised Learning
Authors: Haibo Wang, Chuan Zhou, Xin Chen, Jia Wu, Shirui Pan, Jilong Wang
Date: 2020-12-01 00:00:00
Proceeding: NeurIPS 2020 12
Tasks: Classification, General Classification, Graph Neural Network, Missing Labels, Node Classification, Variational Inference

Graph Neural Networks (GNNs) have achieved remarkable performance in the task of the semi-supervised node classification. However, most existing models learn a deterministic classification function, which lack sufficient flexibility to explore better choices in the presence of  kinds of imperfect observed data such as the scarce labeled nodes and noisy graph structure. To improve the  rigidness and inflexibility of deterministic classification functions, this paper proposes a novel framework named Graph Stochastic Neural Networks (GSNN), which aims to model the uncertainty of the classification function by simultaneously learning a family of  functions, i.e., a stochastic function. Specifically,  we introduce a learnable graph neural network coupled with a high-dimensional latent variable to model the distribution of the classification function, and further adopt the amortised variational inference to approximate the intractable joint posterior for missing labels and the latent variable. By maximizing the lower-bound of the likelihood for observed node labels, the instantiated models can be trained in an end-to-end manner effectively. Extensive experiments on three real-world datasets show that GSNN achieves substantial performance gain in different scenarios compared with stat-of-the-art baselines.
Compositional Zero-Shot Learning via Fine-Grained Dense Feature Composition
Authors: Dat Huynh, Ehsan Elhamifar
Date: 2020-12-01 00:00:00
Proceeding: NeurIPS 2020 12
Tasks: Attribute, Compositional Zero-Shot Learning, Diversity, Zero-Shot Learning

We develop a novel generative model for zero-shot learning to recognize fine-grained unseen classes without training samples. Our observation is that generating holistic features of unseen classes fails to capture every attribute needed to distinguish small differences among classes. We propose a feature composition framework that learns to extract attribute-based features from training samples and combines them to construct fine-grained features for unseen classes. Feature composition allows us to not only selectively compose features of unseen classes from only relevant training samples, but also obtain diversity among composed features via changing samples used for composition. In addition, instead of building a global feature of an unseen class, we use all attribute-based features to form a dense representation consisting of fine-grained attribute details. To recognize unseen classes, we propose a novel training scheme that uses a discriminative model to construct features that are subsequently used to train itself. Therefore, we directly train the discriminative model on composed features without learning separate generative models. We conduct experiments on four popular datasets of DeepFashion, AWA2, CUB, and SUN, showing that our method significantly improves the state of the art.
Graduated Assignment for Joint Multi-Graph Matching and Clustering with Application to Unsupervised Graph Matching Network Learning
Authors: Runzhong Wang, Junchi Yan, Xiaokang Yang
Date: 2020-12-01 00:00:00
Proceeding: NeurIPS 2020 12
Tasks: Clustering, Graph Matching

This paper considers the setting of jointly matching and clustering multiple graphs belonging to different groups, which naturally rises in many realistic problems. Both graph matching and clustering are challenging (NP-hard) and a joint solution is appealing due to the natural connection of the two tasks. In this paper, we resort to a graduated assignment procedure for soft matching and clustering over iterations, whereby the two-way constraint and clustering confidence are modulated by two separate annealing parameters, respectively. Our technique can be further utilized for end-to-end learning whose loss refers to the cross-entropy between two lines of matching pipelines, as such the keypoint feature extraction CNNs can be learned without ground-truth supervision. Experimental results on real-world benchmarks show our method outperforms learning-free algorithms and performs comparatively against two-graph based supervised graph matching approaches.
Adversarial Bandits with Corruptions: Regret Lower Bound and No-regret Algorithm
Authors: Lin Yang, Mohammad Hajiesmaili, Mohammad Sadegh Talebi, John C. S. Lui, Wing Shing Wong
Date: 2020-12-01 00:00:00
Proceeding: NeurIPS 2020 12

This paper studies adversarial bandits with corruptions. In the basic adversarial bandit setting, the reward of arms is predetermined by an adversary who is oblivious to the learner’s policy. In this paper, we consider an extended setting in which an attacker sits in-between the environment and the learner, and is endowed with a limited budget to corrupt the reward of the selected arm. We have two main results. First, we derive a lower bound on the regret of any bandit algorithm that is aware of the budget of the attacker. Also, for budget-agnostic algorithms, we characterize an impossibility result demonstrating that even when the attacker has a sublinear budget, i.e., a budget growing sublinearly with time horizon T, they fail to achieve a sublinear regret.
Second, we propose ExpRb, a bandit algorithm that incorporates a biased estimator and a robustness parameter to deal with corruption. We characterize the regret of ExpRb as a function of the corruption budget and show that for the case of a known corruption budget, the regret of ExpRb is tight.
OrganITE: Optimal transplant donor organ offering using an individual treatment effect
Authors: Jeroen Berrevoets, James Jordon, Ioana Bica, alexander gimson, Mihaela van der Schaar
Date: 2020-12-01 00:00:00
Proceeding: NeurIPS 2020 12

Transplant-organs are a scarce medical resource. The uniqueness of each organ and the patients' heterogeneous responses to the organs present a unique and challenging machine learning problem. In this problem there are two key challenges: (i) assigning each organ "optimally" to a patient in the queue; (ii) accurately estimating the potential outcomes associated with each patient and each possible organ. In this paper, we introduce OrganITE, an organ-to-patient assignment methodology that assigns organs based not only on its own estimates of the potential outcomes but also on organ scarcity. By modelling and accounting for organ scarcity we significantly increase total life years across the population, compared to the existing greedy approaches that simply optimise life years for the current organ available. Moreover, we propose an individualised treatment effect model capable of addressing the high dimensionality of the organ space. We test our method on real and simulated data, resulting in as much as an additional year of life expectancy as compared to existing organ-to-patient policies.
On the universality of deep learning
Authors: Emmanuel Abbe, Colin Sandon
Date: 2020-12-01 00:00:00
Proceeding: NeurIPS 2020 12
Tasks: Deep Learning

This paper shows that deep learning, i.e., neural networks trained by SGD, can learn in polytime any function class that can be learned in polytime by some algorithm, including parities. This universal result is further shown to be robust, i.e., it holds under possibly poly-noise on the gradients, which gives a separation between deep learning and statistical query algorithms, as the latter are not comparably universal due to cases like parities. This also shows that SGD-based deep learning does not suffer from the limitations of the perceptron discussed by Minsky-Papert '69. The paper further complement this result with a lower-bound on the generalization error of descent algorithms, which implies in particular that the robust universality breaks down if the gradients are averaged over large enough batches of samples as in full-GD, rather than fewer samples as in SGD.
Improving Sparse Vector Technique with Renyi Differential Privacy
Authors: Yuqing Zhu, Yu-Xiang Wang
Date: 2020-12-01 00:00:00
Proceeding: NeurIPS 2020 12

The Sparse Vector Technique (SVT) is one of the most fundamental algorithmic tools in differential privacy (DP). It also plays a central role in the state-of-the-art algorithms for adaptive data analysis and model-agnostic private learning. In this paper, we revisit SVT from the lens of Renyi differential privacy, which results in new privacy bounds, new theoretical insight and new variants of SVT algorithms. A notable example is a Gaussian mechanism version of SVT, which provides better utility over the standard (Laplace-mechanism-based) version thanks to its more concentrated noise and tighter composition. Extensive empirical evaluation demonstrates the merits of Gaussian SVT over the Laplace SVT and other alternatives, which encouragingly suggests that using Gaussian SVT as a drop-in replacement could make SVT-based algorithms practical in downstream tasks.
Consistent Plug-in Classifiers for Complex Objectives and Constraints
Authors: Shiv Kumar Tavker, Harish Guruprasad Ramaswamy, Harikrishna Narasimhan
Date: 2020-12-01 00:00:00
Proceeding: NeurIPS 2020 12

We present a statistically consistent algorithm for constrained classification problems where the objective (e.g. F-measure, G-mean) and the constraints (e.g. demographic parity, coverage) are defined by general functions of the confusion matrix. The key idea is to reduce the problem into a sequence of plug-in classifier learning problems, which is done by formulating an optimization problem over the intersection of the set of achievable confusion matrices and the set of feasible matrices. For objective and constraints that are convex functions of the confusion matrix, our algorithm requires $O(1/\epsilon^2)$ calls to the plug-in routine, which improves on the $O(1/\epsilon^3)$ rate achieved by Narasimhan (2018). We demonstrate empirically that our algorithm performs at least as well as the state-of-the-art methods for these problems.
Agnostic Learning with Multiple Objectives
Authors: Corinna Cortes, Mehryar Mohri, Javier Gonzalvo, Dmitry Storcheus
Date: 2020-12-01 00:00:00
Proceeding: NeurIPS 2020 12

Most machine learning tasks are inherently multi-objective. This
  means that the learner has to come up with a model that performs
  well across a number of base objectives $\cL_{1}, \ldots, \cL_{p}$,
  as opposed to a single one. Since optimizing with respect to
  multiple objectives at the same time is often computationally
  expensive, the base objectives are often combined in an ensemble
  $\sum_{k=1}^{p}\lambda_{k}\cL_{k}$, thereby reducing the problem to
  scalar optimization. The mixture weights $\lambda_{k}$ are set to
  uniform or some other fixed distribution, based on the learner's
  preferences. We argue that learning with a fixed distribution on the
  mixture weights runs the risk of overfitting to some individual
  objectives and significantly harming others, despite
  performing well on an entire ensemble. Moreover, in reality, the true
  preferences of a learner across multiple objectives are often
  unknown or hard to express as a specific distribution. Instead, we
  propose a new framework of \emph{Agnostic Learning with Multiple
    Objectives} ($\almo$), where a model is optimized for \emph{any}
  weights in the mixture of base objectives. We present data-dependent
  Rademacher complexity guarantees for learning in the $\almo$
  framework, which are used to guide a scalable optimization
  algorithm and the corresponding regularization. We present
  convergence guarantees for this algorithm, assuming convexity of the
  loss functions and the underlying hypothesis space. We further
  implement the algorithm in a popular symbolic gradient computation
  framework and empirically demonstrate on a number of datasets the
  benefits of $\almo$ framework versus learning with a fixed mixture
  weights distribution.
Differentiable Top-k with Optimal Transport
Authors: Yujia Xie, Hanjun Dai, Minshuo Chen, Bo Dai, Tuo Zhao, Hongyuan Zha, Wei Wei, Tomas Pfister
Date: 2020-12-01 00:00:00
Proceeding: NeurIPS 2020 12
Tasks: Information Retrieval, Retrieval

Finding the k largest or smallest elements from a collection of scores, i.e., top-k operation, is an important model component widely used in information retrieval, machine learning, and data mining. However, if the top-k operation is implemented in an algorithmic way, e.g., using bubble algorithm, the resulted model cannot be trained in an end-to-end way using prevalent gradient descent algorithms. This is because these implementations typically involve swapping indices, whose gradient cannot be computed. Moreover, the corresponding mapping from the input scores to the indicator vector of whether this element belongs to the top-k set is essentially discontinuous. To address the issue, we propose a smoothed approximation, namely SOFT (Scalable Optimal transport-based diFferenTiable) top-k operator. Specifically, our SOFT top-k operator approximates the output of top-k operation as the solution of an Entropic Optimal Transport (EOT) problem. The gradient of the SOFT operator can then be efficiently approximated based on the optimality conditions of EOT problem.
We then apply the proposed operator to k-nearest neighbors algorithm and beam search algorithm. The numerical experiment demonstrates their achieve improved performance.
Learning from Failure: De-biasing Classifier from Biased Classifier
Authors: Junhyun Nam, Hyuntak Cha, Sung-Soo Ahn, Jaeho Lee, Jinwoo Shin
Date: 2020-12-01 00:00:00
Proceeding: NeurIPS 2020 12

Neural networks often learn to make predictions that overly rely on spurious corre- lation existing in the dataset, which causes the model to be biased. While previous work tackles this issue by using explicit labeling on the spuriously correlated attributes or presuming a particular bias type, we instead utilize a cheaper, yet generic form of human knowledge, which can be widely applicable to various types of bias. We first observe that neural networks learn to rely on the spurious correlation only when it is “easier” to learn than the desired knowledge, and such reliance is most prominent during the early phase of training. Based on the obser- vations, we propose a failure-based debiasing scheme by training a pair of neural networks simultaneously. Our main idea is twofold; (a) we intentionally train the first network to be biased by repeatedly amplifying its “prejudice”, and (b) we debias the training of the second network by focusing on samples that go against the prejudice of the biased network in (a). Extensive experiments demonstrate that our method significantly improves the training of network against various types of biases in both synthetic and real-world datasets. Surprisingly, our framework even occasionally outperforms the debiasing methods requiring explicit supervision of the spuriously correlated attributes.
Deep Diffusion-Invariant Wasserstein Distributional Classification
Authors: Sung Woo Park+, Dong Wook Shu, Junseok Kwon
Date: 2020-12-01 00:00:00
Proceeding: NeurIPS 2020 12
Tasks: Classification, General Classification

In this paper, we present a novel classification method called deep diffusion-invariant Wasserstein distributional classification (DeepWDC). DeepWDC represents input data and labels as probability measures to address severe perturbations in input data. It can output the optimal label measure in terms of diffusion invariance, where the label measure is  stationary over time and becomes equivalent to a Gaussian measure. Furthermore, DeepWDC minimizes the 2-Wasserstein distance between the optimal label measure and Gaussian measure, which reduces the Wasserstein uncertainty. Experimental results demonstrate that DeepWDC can substantially enhance the accuracy of several baseline deterministic classification methods and outperforms state-of-the-art-methods on 2D and 3D data containing various types of perturbations (e.g., rotations, impulse noise, and down-scaling).
Finding All $\epsilon$-Good Arms in Stochastic Bandits
Authors: Blake Mason, Lalit Jain, Ardhendu Tripathy, Robert Nowak
Date: 2020-12-01 00:00:00
Proceeding: NeurIPS 2020 12
Tasks: All, Multi-Armed Bandits

The pure-exploration problem in stochastic multi-armed bandits aims to find one or more arms with the largest (or near largest) means.  Examples include finding an $\epsilon$-good arm, best-arm identification, top-$k$ arm identification, and finding all arms with means above a specified threshold.  However, the problem of finding \emph{all} $\epsilon$-good arms has been overlooked in past work, although arguably this may be the most natural objective in many applications.  For example, a virologist may conduct preliminary laboratory experiments on a large candidate set of treatments and move all $\epsilon$-good treatments into more expensive clinical trials. Since the ultimate clinical efficacy is uncertain, it is important to identify all $\epsilon$-good candidates.  Mathematically, the all-$\epsilon$-good arm identification problem is presents significant new challenges and surprises that do not arise in the pure-exploration objectives studied in the past. We introduce two algorithms to overcome these and demonstrate their great empirical performance on a large-scale crowd-sourced dataset of $2.2$M ratings collected by the New Yorker Caption Contest  as well as a dataset testing hundreds of possible cancer drugs.
Adversarial Attacks on Deep Graph Matching
Authors: Zijie Zhang, Zeru Zhang, Yang Zhou, Yelong Shen, Ruoming Jin, Dejing Dou
Date: 2020-12-01 00:00:00
Proceeding: NeurIPS 2020 12
Tasks: Adversarial Attack, Density Estimation, Graph Learning, Graph Matching, Meta-Learning, Network Embedding, Node Classification

Despite achieving remarkable performance, deep graph learning models, such as node classification and network embedding, suffer from harassment caused by small adversarial perturbations. However, the vulnerability analysis of graph matching under adversarial attacks has not been fully investigated yet. This paper proposes an adversarial attack model with two novel attack techniques to perturb the graph structure and degrade the quality of deep graph matching: (1) a kernel density estimation approach is utilized to estimate and maximize node densities to derive imperceptible perturbations, by pushing attacked nodes to dense regions in two graphs, such that they are indistinguishable from many neighbors; and (2) a meta learning-based projected gradient descent method is developed to well choose attack starting points and to improve the search performance for producing effective perturbations. We evaluate the effectiveness of the attack model on real datasets and validate that the attacks can be transferable to other graph learning models.
Improving Online Rent-or-Buy Algorithms with Sequential Decision Making and ML Predictions
Authors: Soumya Banerjee
Date: 2020-12-01 00:00:00
Proceeding: NeurIPS 2020 12
Tasks: BIG-bench Machine Learning, Decision Making, Sequential Decision Making

In this work we study online rent-or-buy problems as a sequential decision making problem. We show how one can integrate predictions, typically coming from a machine learning (ML) setup, into this framework. Specifically, we consider the ski-rental problem and the dynamic TCP acknowledgment problem. We present new online algorithms and obtain explicit performance bounds in-terms of the accuracy of the prediction. Our algorithms are close to optimal with accurate predictions while hedging against less accurate predictions.
Escaping the Gravitational Pull of Softmax
Authors: Jincheng Mei, Chenjun Xiao, Bo Dai, Lihong Li, Csaba Szepesvari, Dale Schuurmans
Date: 2020-12-01 00:00:00
Proceeding: NeurIPS 2020 12

The softmax is the standard transformation used in machine learning to map real-valued vectors to categorical distributions. Unfortunately, this transform poses serious drawbacks for gradient descent (ascent) optimization. We reveal this difficulty by establishing two negative results: (1) optimizing any expectation with respect to the softmax must exhibit sensitivity to parameter initialization (softmax gravity well''), and (2) optimizing log-probabilities under the softmax must exhibit slow convergence (softmax damping''). Both findings are based on an analysis of convergence rates using the Non-uniform \L{}ojasiewicz (N\L{}) inequalities. To circumvent these shortcomings we investigate an alternative transformation, the \emph{escort} mapping, that demonstrates better optimization properties. The disadvantages of the softmax and the effectiveness of the escort transformation are further explained using the concept of N\L{} coefficient. In addition to proving bounds on convergence rates to firmly establish these results, we also provide experimental evidence for the superiority of the escort transformation.
Second Order Optimality in Decentralized Non-Convex Optimization via Perturbed Gradient Tracking
Authors: Isidoros Tziotis, Constantine Caramanis, Aryan Mokhtari
Date: 2020-12-01 00:00:00
Proceeding: NeurIPS 2020 12

In this paper we study the problem of escaping from saddle points and achieving second-order optimality in a decentralized setting where a group of agents collaborate to minimize their aggregate objective function. We provide a non-asymptotic (finite-time) analysis and show that by following the idea of perturbed gradient descent, it is possible to converge to a second-order stationary point in a number of iterations which depends linearly on dimension and polynomially on the accuracy of second-order stationary point. Doing this in a communication-efficient manner requires overcoming several challenges, from identifying (first order) stationary points in a distributed manner, to adapting the perturbed gradient framework without prohibitive communication complexity. Our proposed Perturbed Decentralized Gradient Tracking (PDGT) method consists of two major stages: (i) a gradient-based step to find a first-order stationary point and (ii) a perturbed gradient descent step to escape from a first-order stationary point, if it is a saddle point with sufficient curvature. As a side benefit of our result, in the case that all saddle points are non-degenerate (strict), the proposed PDGT method finds a local minimum of the considered decentralized optimization problem in a finite number of iterations.
Uncertainty-aware Self-training for Few-shot Text Classification
Authors: Subhabrata Mukherjee, Ahmed Awadallah
Date: 2020-12-01 00:00:00
Proceeding: NeurIPS 2020 12
Tasks: Classification, Few-Shot Text Classification, General Classification, text-classification, Text Classification

Recent success of pre-trained language models crucially hinges on fine-tuning them on large amounts of labeled data for the downstream task, that are typically expensive to acquire or difficult to access for many applications. We study self-training as one of the earliest semi-supervised learning approaches to reduce the annotation bottleneck by making use of large-scale unlabeled data for the target task. Standard self-training mechanism randomly samples instances from the unlabeled pool to generate pseudo-labels and augment labeled data. We propose an approach to improve self-training by incorporating uncertainty estimates of the underlying neural network leveraging recent advances in Bayesian deep learning. Specifically, we propose (i) acquisition functions to select instances from the unlabeled pool leveraging Monte Carlo (MC) Dropout, and (ii) learning mechanism leveraging model confidence for self-training. As an application, we focus on text classification with five benchmark datasets. We show our methods leveraging only 20-30 labeled samples per class for each task for training and for validation perform within 3% of fully supervised pre-trained language models fine-tuned on thousands of labels with an aggregate accuracy of 91% and improvement of up to 12% over baselines.