pwc-archive/papers-with-abstracts huggingface dataset:
Online Convex Optimization Over Erdos-Renyi Random Networks
Authors: Jinlong Lei, Peng Yi, Yiguang Hong, Jie Chen, Guodong Shi
Date: 2020-12-01 00:00:00
Proceeding: NeurIPS 2020 12

The work studies how node-to-node communications over an  Erd\H{o}s-R\'enyi random network influence distributed  online convex optimization, which  is vital in solving large-scale machine learning in antagonistic or changing environments. At per step, each node (computing unit) makes a local decision,  experiences a loss evaluated with a convex function, and  communicates the decision with other nodes over a network. The node-to-node communications are described by the Erd\H{o}s-R\'enyi rule, where independently  each link takes place with a probability $p$ over a prescribed connected graph.  The objective is to
minimize the system-wide loss accumulated over a finite time horizon.
We consider standard distributed gradient descents with full gradients, one-point bandits and two-points bandits for convex  and strongly convex losses, respectively. We  establish how the regret bounds scale  with respect to time horizon $T$, network size $N$, decision dimension $d$, and  an algebraic  network connectivity. The regret bounds scaling with respect to $T$
match those obtained by state-of-the-art algorithms and fundamental limits in
the corresponding centralized online optimization problems, e.g.,
 $\mathcal{O}(\sqrt{T}) $ and $\mathcal{O}(\ln(T)) $  regrets are established  for  convex  and strongly convex losses with full gradient feedback and two-points information, respectively. For classical Erd\H{o}s-R\'enyi  networks over all-to-all possible node communications, the regret scalings with respect to the probability $p$ are analytically  established, based on which the tradeoff between the communication overhead and computation accuracy is clearly demonstrated. Numerical studies have validated the theoretical findings.
Collapsing Bandits and Their Application to Public Health Intervention
Authors: Aditya Mate, Jackson Killian, Haifeng Xu, Andrew Perrault, Milind Tambe
Date: 2020-12-01 00:00:00
Proceeding: NeurIPS 2020 12

We propose and study Collapsing Bandits,  a new restless multi-armed bandit (RMAB) setting in which each arm follows a binary-state Markovian process with a special structure: when an arm is played, the state is fully observed, thus“collapsing” any uncertainty, but when an arm is passive, no observation is made, thus allowing uncertainty to evolve. The goal is to keep as many arms in the “good” state as possible by planning a limited budget of actions per round. Such CollapsingBandits are natural models for many healthcare domains in which health workers must simultaneously monitor patients and deliver interventions in a  way that maximizes the health of their patient cohort. Our main contributions are as follows: (i) Building on the Whittle index technique for RMABs, we derive conditions under which the Collapsing Bandits problem is indexable. Our derivation hinges on novel conditions that characterize when the optimal policies may take the form of either“forward” or “reverse” threshold policies. (ii) We exploit the optimality of threshold policies to build fast algorithms for computing the Whittle index, including a closed-form. (iii) We evaluate our algorithm on several data distributions including data from a real-world healthcare task in which a worker must monitor and deliver interventions to maximize their patients’ adherence to tuberculosis medication. Our algorithm achieves a 3-order-of-magnitude speedup compared to state-of-the-art RMAB techniques, while achieving similar performance. The code is available at:https://github.com/AdityaMate/collapsing_bandits
Learning efficient task-dependent representations with synaptic plasticity
Authors: Colin Bredenberg, Eero Simoncelli, Cristina Savin
Date: 2020-12-01 00:00:00
Proceeding: NeurIPS 2020 12

Neural populations encode the sensory world imperfectly: their capacity is limited by the number of neurons, availability of metabolic and other biophysical resources, and intrinsic noise. The brain is presumably shaped by these limitations, improving efficiency by discarding some aspects of incoming sensory streams, while preferentially preserving commonly occurring, behaviorally-relevant information. Here we construct a stochastic recurrent neural circuit model that can learn efficient, task-specific sensory codes using a novel form of reward-modulated Hebbian synaptic plasticity. We illustrate the flexibility of the model by training an initially unstructured neural network to solve two different tasks: stimulus estimation, and stimulus discrimination. The network achieves high performance in both tasks by appropriately allocating resources and using its recurrent circuitry to best compensate for different levels of noise. We also show how the interaction between stimulus priors and task structure dictates the emergent network representations.
Disentangling Human Error from Ground Truth in Segmentation of Medical Images
Authors: Le Zhang, Ryutaro Tanno, MouCheng Xu, Chen Jin, Joseph Jacob, Olga Cicarrelli, Frederik Barkhof, Daniel Alexander
Date: 2020-12-01 00:00:00
Proceeding: NeurIPS 2020 12
Tasks: Medical Image Segmentation, Segmentation

Recent years have seen increasing use of supervised learning methods for segmentation tasks. However, the predictive performance of these algorithms depends on the quality of labels. This problem is particularly pertinent in the medical image domain, where both the annotation cost and inter-observer variability are high. In a typical label acquisition process, different human experts provide their estimates of the ``true'' segmentation labels under the influence of their own biases and competence levels. Treating these noisy labels blindly as the ground truth limits the performance that automatic segmentation algorithms can achieve. In this work, we present a method for jointly learning, from purely noisy observations alone, the reliability of individual annotators and the true segmentation label distributions, using two coupled CNNs. The separation of the two is achieved by encouraging the estimated annotators to be maximally unreliable while achieving high fidelity with the noisy training data. We first define a toy segmentation dataset based on MNIST and study the properties of the proposed algorithm. We then demonstrate the utility of the method on three public medical imaging segmentation datasets with simulated (when necessary) and real diverse annotations: 1) MSLSC (multiple-sclerosis lesions); 2) BraTS (brain tumours); 3) LIDC-IDRI (lung abnormalities). In all cases, our method outperforms competing methods and relevant baselines particularly in cases where the number of annotations is small and the amount of disagreement is large. The experiments also show strong ability to capture the complex spatial characteristics of annotators' mistakes. Our code is available at \url{https://github.com/moucheng2017/LearnNoisyLabelsMedicalImages}.
Hitting the High Notes: Subset Selection for Maximizing Expected Order Statistics
Authors: Aranyak Mehta, Uri Nadav, Alexandros Psomas, Aviad Rubinstein
Date: 2020-12-01 00:00:00
Proceeding: NeurIPS 2020 12
Tasks: Retrieval, Vocal Bursts Intensity Prediction

We consider the fundamental problem of selecting $k$ out of $n$ random variables in a way that the expected highest or second-highest value is maximized. This question captures several applications where we have uncertainty about the quality of candidates (e.g. auction bids, search results) and have the capacity to explore only a small subset due to an exogenous constraint. For example, consider a second price auction where system constraints (e.g., costly retrieval or model computation) allow the participation of only $k$ out of $n$ bidders, and the goal is to optimize the expected efficiency (highest bid) or expected revenue (second highest bid).


We study the case where we are given an explicit description of each random variable. We give a PTAS for the problem of maximizing the expected highest value. For the second-highest value, we prove a hardness result: assuming the Planted Clique Hypothesis, there is no constant factor approximation algorithm that runs in polynomial time. Surprisingly, under the assumption that each random variable has monotone hazard rate (MHR), a simple score-based algorithm, namely picking the $k$ random variables with the largest $1/\sqrt{k}$ top quantile value,  is a constant approximation to the expected highest and second highest value, \emph{simultaneously}.
Towards Scale-Invariant Graph-related Problem Solving by Iterative Homogeneous GNNs
Authors: Hao Tang, Zhiao Huang, Jiayuan Gu, Bao-liang Lu, Hao Su
Date: 2020-12-01 00:00:00
Proceeding: NeurIPS 2020 12

Current graph neural networks (GNNs) lack generalizability with respect to scales (graph sizes, graph diameters, edge weights, etc..) when solving many graph analysis problems. Taking the perspective of synthesizing graph theory programs, we propose several extensions to address the issue. First, inspired by the dependency of iteration number of common  graph theory algorithms on graph size, we learn to terminate the message passing process in GNNs adaptively according to the computation progress. Second, inspired by the fact that many graph theory algorithms are homogeneous with respect to graph weights, we introduce homogeneous transformation layers that are universal homogeneous function approximators, to convert ordinary GNNs to be homogeneous. Experimentally, we show that our GNN can be trained from small-scale graphs but generalize well to large-scale graphs for a number of basic graph theory problems. It also shows generalizability for applications of multi-body physical simulation and image-based navigation problems.
Non-Crossing Quantile Regression for Distributional Reinforcement Learning
Authors: Fan Zhou, Jianing Wang, Xingdong Feng
Date: 2020-12-01 00:00:00
Proceeding: NeurIPS 2020 12
Tasks: Atari Games, Distributional Reinforcement Learning, quantile regression, regression, reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

Distributional reinforcement learning (DRL) estimates the distribution over future returns instead of the mean to more efficiently capture the intrinsic uncertainty of MDPs. However, batch-based DRL algorithms cannot guarantee the non-decreasing property of learned quantile curves especially at the early training stage, leading to abnormal distribution estimates and reduced model interpretability. To address these issues, we introduce a general DRL framework by using non-crossing quantile regression to ensure the monotonicity constraint within each sampled batch, which can be incorporated with any well-known DRL algorithm. We demonstrate the validity of our method from both the theory and model implementation perspectives. Experiments on Atari 2600 Games show that some state-of-art DRL algorithms with the non-crossing modification can significantly outperform their baselines in terms of faster convergence speeds and better testing performance. In particular, our method can effectively recover the distribution information and thus dramatically increase the exploration efficiency when the reward space is extremely sparse.
PLLay: Efficient Topological Layer based on Persistent Landscapes
Authors: Kwangho Kim, Jisu Kim, Manzil Zaheer, Joon Kim, Frederic Chazal, Larry Wasserman
Date: 2020-12-01 00:00:00
Proceeding: NeurIPS 2020 12

We propose PLLay, a novel topological layer for general deep learning models based on persistence landscapes, in which we can efficiently exploit the underlying topological features of the input data structure. In this work, we show differentiability with respect to layer inputs, for a general persistent homology with arbitrary filtration. Thus, our proposed layer can be placed anywhere in the network and feed critical information on the topological features of input data into subsequent layers to improve the learnability of the networks toward a given task. A task-optimal structure of PLLay is learned during training via backpropagation, without requiring any input featurization or data preprocessing. We provide a novel adaptation for the DTM function-based filtration, and show that the proposed layer is robust against noise and outliers through a stability analysis. We demonstrate the effectiveness of our approach by classification experiments on various datasets.
Decentralized Langevin Dynamics for Bayesian Learning
Authors: Anjaly Parayil, He Bai, Jemin George, Prudhvi Gurram
Date: 2020-12-01 00:00:00
Proceeding: NeurIPS 2020 12
Tasks: BIG-bench Machine Learning

Motivated by decentralized approaches to machine learning, we propose a collaborative Bayesian learning algorithm taking the form of decentralized Langevin dynamics in a non-convex setting. Our analysis show that the initial KL-divergence between the Markov Chain and the target posterior distribution is exponentially decreasing while the error contributions to the overall KL-divergence from the additive noise is decreasing in polynomial time. We further show that the polynomial-term experiences speed-up with number of agents and provide sufficient conditions on the time-varying step-sizes to guarantee convergence to the desired distribution. The performance of the proposed algorithm is evaluated on a wide variety of machine learning tasks. The empirical results show that the performance of individual agents with locally available data is on par with the centralized setting with considerable improvement in the convergence rate.
The Diversified Ensemble Neural Network
Authors: Shaofeng Zhang, Meng Liu, Junchi Yan
Date: 2020-12-01 00:00:00
Proceeding: NeurIPS 2020 12

Ensemble is a general way of improving the accuracy and stability of learning models, especially for the generalization ability on small datasets. Compared with tree-based methods, relatively less works have been devoted to an in-depth study on effective ensemble design for neural networks. In this paper, we propose a principled ensemble technique by constructing the so-called diversified ensemble layer to combine multiple networks as individual modules. We theoretically show that each individual model in our ensemble layer corresponds to weights in the ensemble layer optimized in different directions. Meanwhile, the devised ensemble layer can be readily integrated into popular neural architectures, including CNNs, RNNs, and GCNs. Extensive experiments are conducted on public tabular datasets, images, and texts. By adopting weight sharing approach, the results show our method can notably improve the accuracy and stability of the original neural networks with ignorable extra time and space overhead.
Inductive Quantum Embedding
Authors: Santosh Kumar Srivastava, Dinesh Khandelwal, Dhiraj Madan, Dinesh Garg, Hima Karanam, L Venkata Subramaniam
Date: 2020-12-01 00:00:00
Proceeding: NeurIPS 2020 12

Quantum logic inspired embedding (aka Quantum Embedding (QE)) of a Knowledge-Base (KB) was proposed recently by Garg:2019. It is claimed that the QE preserves the logical structure of the input KB given in the form of unary and binary predicates hierarchy. Such structure preservation allows one to perform Boolean logic style deductive reasoning directly over these embedding vectors. The original QE idea, however, is limited to the transductive (not inductive) setting. Moreover, the original QE scheme runs quite slow on real applications involving millions of entities. This paper alleviates both of these key limitations. We start by reformulating the original QE problem to allow for the induction. On the way, we also underscore some interesting analytic and geometric properties of the solution and leverage them to design a faster training scheme. As an application, we show that one can achieve state-of-the-art performance on the well-known NLP task of fine-grained entity type classification by using the inductive QE approach. Our training runs 9-times faster than the original QE scheme on this task.
Batched Coarse Ranking in Multi-Armed Bandits
Authors: Nikolai Karpov, Qin Zhang
Date: 2020-12-01 00:00:00
Proceeding: NeurIPS 2020 12
Tasks: Multi-Armed Bandits

We study the problem of coarse ranking in the multi-armed bandits (MAB) setting, where we have a set of arms each of which is associated with an unknown distribution.  The task is to partition the arms into clusters of predefined sizes, such that the mean of any arm in the $i$-th cluster is larger than that of any arm in the $j$-th cluster for any $j > i$.  Coarse ranking  generalizes a number of basic problems in MAB (e.g., best arm identification) and has many real-world applications.  We initiate the study of the problem in the batched model where we can only have a small number of policy changes.  We study both the fixed budget and fixed confidence variants in MAB, and propose algorithms and prove impossibility results which together give almost tight tradeoffs between the total number of arms pulls and the number of policy changes.  We have tested our algorithms in both real and synthetic data; our experimental results have demonstrated the efficiency of the proposed methods.
Coded Sequential Matrix Multiplication For Straggler Mitigation
Authors: Nikhil Krishnan Muralee Krishnan, Seyederfan Hosseini, Ashish Khisti
Date: 2020-12-01 00:00:00
Proceeding: NeurIPS 2020 12

 In this work, we consider a sequence of $J$ matrix multiplication jobs which needs to be distributed by a master across multiple worker nodes. For $i\in \{1,2,\ldots,J\}$, job-$i$ begins in round-$i$ and has to be completed by round-$(i+T)$. Previous works consider only the special case of $T=0$ and focus on coding across workers. We propose here two schemes with $T>0$, which feature coding across workers as well as the dimension of time. Our first scheme is a modification of the polynomial coding scheme introduced by Yu et al. and places no assumptions on the straggler model. Exploitation of the temporal dimension helps the scheme handle a larger set of straggler patterns than the polynomial coding scheme, for a given computational load per worker per round.  The second scheme assumes a particular straggler model to further improve performance (in terms of encoding/decoding complexity).   We develop theoretical results establishing (i) optimality of our proposed schemes for a certain class of straggler patterns and (ii) improved performance for the case of i.i.d. stragglers. These are further validated by experiments, where we implement our schemes to train neural networks.
Domain Generalization via Entropy Regularization
Authors: Shanshan Zhao, Mingming Gong, Tongliang Liu, Huan Fu, DaCheng Tao
Date: 2020-12-01 00:00:00
Proceeding: NeurIPS 2020 12
Tasks: Domain Generalization

Domain generalization aims to learn from multiple source domains a predictive model that can generalize to unseen target domains. One essential problem in domain generalization is to learn discriminative domain-invariant features. To arrive at this, some methods introduce a domain discriminator through adversarial learning to match the feature distributions in multiple source domains. However, adversarial training can only guarantee that the learned features have invariant marginal distributions, while the invariance of conditional distributions is more important for prediction in new domains. To ensure the conditional invariance of learned features, we propose an entropy regularization term that measures the dependency between the learned features and the class labels. Combined with the typical task-related loss, e.g., cross-entropy loss for classification, and adversarial loss for domain discrimination, our overall objective is guaranteed to learn conditional-invariant features across all source domains and thus can learn classifiers with better generalization capabilities. 
We demonstrate the effectiveness of our method through comparison with state-of-the-art methods on both simulated and real-world datasets. Code is available at: https://github.com/sshan-zhao/DGviaER.
Online Bayesian Persuasion
Authors: Matteo Castiglioni, Andrea Celli, Alberto Marchesi, Nicola Gatti
Date: 2020-12-01 00:00:00
Proceeding: NeurIPS 2020 12

In Bayesian persuasion, an informed sender has to design a signaling scheme that discloses the right amount of information so as to influence the behavior of a self-interested receiver. This kind of strategic interaction is ubiquitous in real economic scenarios. However, the original model by Kamenica and Gentzkow makes some stringent assumptions which limit its applicability in practice. One of the most limiting assumptions is arguably that, in order to compute an optimal signaling scheme, the sender is usually required to know the receiver's utility function. In this paper, we relax this assumption through an online learning framework in which the sender faces a receiver with unknown type. At each round, the receiver's type is chosen adversarially from a finite set of possible types. We are interested in no-regret algorithms prescribing a signaling scheme at each round of the repeated interaction with performances close to that of the best-in-hindsight signaling scheme. First, we prove a hardness result on the per-iteration running time required to achieve the no-regret property. Then, we provide algorithms for the full and partial information model which exhibit regret sublinear in the number of rounds and polynomial in the parameters of the game.
Random Walk Graph Neural Networks
Authors: Giannis Nikolentzos, Michalis Vazirgiannis
Date: 2020-12-01 00:00:00
Proceeding: NeurIPS 2020 12
Tasks: Graph Classification, Graph Neural Network

In recent years, graph neural networks (GNNs) have become the de facto tool for performing machine learning tasks on graphs. Most GNNs belong to the family of message passing neural networks (MPNNs). These models employ an iterative neighborhood aggregation scheme to update vertex representations. Then, to compute vector representations of graphs, they aggregate the representations of the vertices using some permutation invariant function. One would expect the hidden layers of a GNN to be composed of parameters that take the form of graphs. However, this is not the case for MPNNs since their update procedure is parameterized by fully-connected layers. In this paper, we propose a more intuitive and transparent architecture for graph-structured data, so-called Random Walk Graph Neural Network (RWNN). The first layer of the model consists of a number of trainable ``hidden graphs'' which are compared against the input graphs using a random walk kernel to produce graph representations. These representations are then passed on to a fully-connected neural network which produces the output. The employed random walk kernel is differentiable, and therefore, the proposed model is end-to-end trainable. We demonstrate the model's transparency on synthetic datasets. Furthermore, we empirically evaluate the model on graph classification datasets and show that it achieves competitive performance.