pwc-archive/papers-with-abstracts huggingface dataset:
Efficient Clustering Based On A Unified View Of $K$-means And Ratio-cut
Authors: Shenfei Pei, Feiping Nie, Rong Wang, Xuelong Li
Date: 2020-12-01 00:00:00
Proceeding: NeurIPS 2020 12
Tasks: Clustering

Spectral clustering and $k$-means, both as two major traditional clustering methods, are still attracting a lot of attention, although a variety of novel clustering algorithms have been proposed in recent years.
Firstly, a unified framework of $k$-means and ratio-cut is revisited,  and a novel and efficient clustering algorithm is then proposed based on this framework. 
The time and space complexity of our method are both linear with respect to the number of samples, and are independent of the number of clusters to construct, more importantly.
These properties mean that it is easily scalable and applicable to large practical problems.
Extensive experiments on 12 real-world benchmark and 8 facial datasets validate the advantages of the proposed algorithms compared to the state-of-the-art clustering algorithms. 
In particular, over 15x and 7x speed-up can be obtained with respect to $k$-means on the synthetic dataset of 1 million samples and the benchmark dataset (CelebA) of 200k samples, respectively [GitHub].
Recurrent Switching Dynamical Systems Models for Multiple Interacting Neural Populations
Authors: Joshua Glaser, Matthew Whiteway, John P. Cunningham, Liam Paninski, Scott Linderman
Date: 2020-12-01 00:00:00
Proceeding: NeurIPS 2020 12

Modern recording techniques can generate large-scale measurements of multiple neural populations over extended time periods. However, it remains a challenge to model non-stationary interactions between high-dimensional populations of neurons. To tackle this challenge, we develop recurrent switching linear dynamical systems models for multiple populations. Here, each high-dimensional neural population is represented by a unique set of latent variables, which evolve dynamically in time. Populations interact with each other through this low-dimensional space. We allow the nature of these interactions to change over time by using a discrete set of dynamical states. Additionally, we parameterize these discrete state transition rules to capture which neural populations are responsible for switching between interaction states. To fit the model, we use variational expectation-maximization with a structured mean-field approximation. After validating the model on simulations, we apply it to two different neural datasets: spiking activity from motor areas in a non-human primate, and calcium imaging from neurons in the nematode \textit{C. elegans}. In both datasets, the model reveals behaviorally-relevant discrete states with unique inter-population interactions and different populations that predict transitioning between these states.
Understanding and Exploring the Network with Stochastic Architectures
Authors: Zhijie Deng, Yinpeng Dong, Shifeng Zhang, Jun Zhu
Date: 2020-12-01 00:00:00
Proceeding: NeurIPS 2020 12
Tasks: Neural Architecture Search

There is an emerging trend to train a network with stochastic architectures to enable various architectures to be plugged and played during inference. However, the existing investigation is highly entangled with neural architecture search (NAS), limiting its widespread use across scenarios. In this work, we decouple the training of a network with stochastic architectures (NSA) from NAS and provide a first systematical investigation on it as a stand-alone problem. We first uncover the characteristics of NSA in various aspects ranging from training stability, convergence, predictive behaviour, to generalization capacity to unseen architectures. We identify various issues of the vanilla NSA, such as training/test disparity and function mode collapse, and further propose the solutions to these issues with theoretical and empirical insights. We believe that these results could also serve as good heuristics for NAS. Given these understandings, we further apply the NSA with our improvements into diverse scenarios to fully exploit its promise of inference-time architecture stochasticity, including model ensemble, uncertainty estimation and semi-supervised learning. Remarkable performance (e.g., 2.75% error rate and 0.0032 expected calibration error on CIFAR-10) validate the effectiveness of such a model, providing new perspectives of exploring the potential of the network with stochastic architectures, beyond NAS.
Analytical Probability Distributions and Exact Expectation-Maximization for Deep Generative Networks
Authors: Randall Balestriero, Sebastien Paris, Richard Baraniuk
Date: 2020-12-01 00:00:00
Proceeding: NeurIPS 2020 12
Tasks: Anomaly Detection, Imputation, Variational Inference

Deep Generative Networks (DGNs) with probabilistic modeling of their output
and latent space are currently trained via Variational Autoencoders
(VAEs).
In the absence of a known analytical form for the posterior and
likelihood expectation, VAEs resort to approximations, including
(Amortized) Variational Inference (AVI) 
and Monte-Carlo
sampling.
We exploit the Continuous Piecewise Affine
property
of modern DGNs to derive their posterior and marginal
distributions as well as the latter's first two moments. 
These findings enable us 
to derive an analytical Expectation-Maximization (EM) algorithm for gradient-free DGN learning.
We demonstrate empirically that EM training of DGNs produces greater
likelihood than VAE training.
Our new framework will guide the design of new VAE AVI that better approximates the true posterior and open new avenues to apply standard statistical tools for model comparison, anomaly detection, and missing data imputation.
Bayesian Pseudocoresets
Authors: Dionysis Manousakas, Zuheng Xu, Cecilia Mascolo, Trevor Campbell
Date: 2020-12-01 00:00:00
Proceeding: NeurIPS 2020 12
Tasks: Bayesian Inference

Standard Bayesian inference algorithms are prohibitively expensive in the regime of modern large-scale data. Recent work has found that a small, weighted subset of data (a coreset) may be used in place of the full dataset during inference, taking advantage of data redundancy to reduce computational cost. However, this approach has limitations in the increasingly common setting of sensitive, high-dimensional data.  Indeed, we prove that there are situations in which the Kullback-Leibler divergence between the optimal coreset  and the true posterior grows with data dimension; and as coresets include a subset of the original data, they cannot be constructed in a manner that preserves individual privacy. We address both of these issues with a single unified solution, Bayesian pseudocoresets --- a small weighted collection of synthetic "pseudodata"---along with a variational optimization method to select both pseudodata and weights. The use of pseudodata (as opposed to the original datapoints) enables both the summarization of high-dimensional data and the  differentially private summarization of sensitive data. Real and synthetic experiments on high-dimensional data demonstrate that Bayesian  pseudocoresets achieve significant improvements in posterior approximation error compared to traditional coresets, and that pseudocoresets provide privacy without a significant loss in approximation quality.
Learning Feature Sparse Principal Subspace
Authors: Lai Tian, Feiping Nie, Rong Wang, Xuelong Li
Date: 2020-12-01 00:00:00
Proceeding: NeurIPS 2020 12
Tasks: Dimensionality Reduction, feature selection

This paper presents new algorithms to solve the feature-sparsity constrained PCA problem (FSPCA), which performs feature selection and PCA simultaneously. Existing optimization methods for FSPCA require data distribution assumptions and are lack of global convergence guarantee. Though the general FSPCA problem is NP-hard, we show that, for a low-rank covariance, FSPCA can be solved globally (Algorithm 1). Then, we propose another strategy (Algorithm 2) to solve FSPCA for the general covariance by iteratively building a carefully designed proxy. We prove (data-dependent) approximation bound and convergence guarantees for the new algorithms. For the spectrum of covariance with exponential/Zipf's distribution, we provide exponential/posynomial approximation bound. Experimental results show the promising performance and efficiency of the new algorithms compared with the state-of-the-arts on both synthetic and real-world datasets.
Learning to Select Best Forecast Tasks for Clinical Outcome Prediction
Authors: Yuan Xue, Nan Du, Anne Mottram, Martin Seneviratne, Andrew M. Dai
Date: 2020-12-01 00:00:00
Proceeding: NeurIPS 2020 12
Tasks: Meta-Learning

The paradigm of pretraining' from a set of relevant auxiliary tasks and thenfinetuning' on a target task has been successfully applied in many different domains. However, when the auxiliary tasks are abundant, with complex relationships to the target task, using domain knowledge or searching over all possible pretraining setups are inefficient strategies. To address this challenge, we propose a method to automatically select from a large set of auxiliary tasks which yield a representation most useful to the target task. In particular, we develop an efficient algorithm that uses automatic auxiliary task selection within a nested-loop meta-learning process. We have applied this algorithm to the task of clinical outcome predictions in electronic medical records, learning from a large number of self-supervised tasks related to forecasting patient trajectories. Experiments on a real clinical dataset demonstrate the superior predictive performance of our method compared to direct supervised learning, naive pretraining and multitask learning, in particular in low-data scenarios when the primary task has very few examples. With detailed ablation analysis, we further show that the selection rules are interpretable and able to generalize to unseen target tasks with new data.
The Autoencoding Variational Autoencoder
Authors: Taylan Cemgil, Sumedh Ghaisas, Krishnamurthy Dvijotham, Sven Gowal, Pushmeet Kohli
Date: 2020-12-01 00:00:00
Proceeding: NeurIPS 2020 12
Tasks: Decoder

Does a Variational AutoEncoder (VAE) consistently encode typical samples generated from its decoder? This paper shows that the perhaps surprising answer to this question is `No'; a (nominally trained) VAE does not necessarily amortize inference for typical samples that it is capable of generating. We study the implications of this behaviour on the learned representations and also the consequences of fixing it by introducing a notion of self consistency. 
Our approach hinges on an alternative construction of the variational approximation distribution to the true posterior of an extended VAE model with a Markov chain alternating between the encoder and the decoder. The method can be used to train a VAE model from scratch or given an already trained VAE, it can be run as a post processing step in an entirely self supervised way without access to the original training data. 
Our experimental analysis reveals that encoders trained with our self-consistency approach lead to representations that are robust (insensitive) to perturbations in the input introduced by adversarial attacks.
We provide experimental results on the ColorMnist and CelebA benchmark datasets that quantify the properties of the learned representations and compare the approach with a baseline that is specifically trained for the desired property.
A Fair Classifier Using Kernel Density Estimation
Authors: Jaewoong Cho, Gyeongjo Hwang, Changho Suh
Date: 2020-12-01 00:00:00
Proceeding: NeurIPS 2020 12
Tasks: BIG-bench Machine Learning, Binary Classification, Density Estimation, Fairness

As machine learning becomes prevalent in a widening array of sensitive applications such as job hiring and criminal justice, one critical aspect that machine learning classifiers should respect is to ensure fairness: guaranteeing the irrelevancy of a prediction output to sensitive attributes such as gender and race. In this work, we develop a kernel density estimation trick to quantify fairness measures that capture the degree of the irrelevancy. A key feature of our approach is that quantified fairness measures can be expressed as differentiable functions w.r.t. classifier model parameters. This then allows us to enjoy prominent gradient descent to readily solve an interested optimization problem that fully respects fairness constraints. We focus on a binary classification setting and two well-known definitions of group fairness: Demographic Parity (DP) and Equalized Odds (EO). Our experiments both on synthetic and benchmark real datasets demonstrate that our algorithm outperforms prior fair classifiers in accuracy-fairness tradeoff performance both w.r.t. DP and EO.
Sharp uniform convergence bounds through empirical centralization
Authors: Cyrus Cousins, Matteo Riondato
Date: 2020-12-01 00:00:00
Proceeding: NeurIPS 2020 12

We introduce the use of empirical centralization to derive novel practical, probabilistic, sample-dependent bounds to the Supremum Deviation (SD) of empirical means of functions in a family from their expectations.
Our bounds have optimal dependence on the maximum (i.e., wimpy) variance
and the function ranges, and the same dependence on the number of samples as existing SD bounds.
To compute the SD bounds in practice, we develop tightly-concentrated
Monte Carlo estimators of the empirical Rademacher average of the empirically-centralized family, and we show novel concentration results for the empirical wimpy variance.
Our experimental evaluation shows that our bounds greatly outperform non-centralized bounds and are extremely practical
even at small sample sizes.
Almost Optimal Model-Free Reinforcement Learningvia Reference-Advantage Decomposition
Authors: Zihan Zhang, Yuan Zhou, Xiangyang Ji
Date: 2020-12-01 00:00:00
Proceeding: NeurIPS 2020 12
Tasks: reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

We  study  the  reinforcement  learning  problem  in  the  setting  of  finite-horizon1episodic Markov Decision Processes (MDPs) with S states, A actions, and episode length H. We propose a model-free algorithm UCB-ADVANTAGE and prove that it achieves  \tilde{O}(\sqrt{H^2 SAT}) regret where T=KH and K is the number of episodes to play.  Our regret bound improves upon the results of [Jin et al., 2018] and matches the best known model-based algorithms as well as the information theoretic lower bound up to logarithmic factors. We also show that UCB-ADVANTAGE achieves low local switching cost and applies to concurrent reinforcement learning, improving upon the recent results of [Bai et al., 2019].
Exploiting MMD and Sinkhorn Divergences for Fair and Transferable Representation Learning
Authors: Luca Oneto, Michele Donini, Giulia Luise, Carlo Ciliberto, Andreas Maurer, Massimiliano Pontil
Date: 2020-12-01 00:00:00
Proceeding: NeurIPS 2020 12
Tasks: Fairness, Representation Learning

Developing learning methods which do not discriminate subgroups in the population is a central goal of algorithmic fairness. One way to reach this goal is by modifying the data representation in order to meet certain fairness constraints. In this work we measure fairness according to demographic parity. This requires the probability of the possible model decisions to be independent of the sensitive information.
We argue that the goal of imposing demographic parity can be substantially facilitated within a multitask learning setting. We present a method for learning a shared fair representation across multiple tasks, by means of different new constraints based on MMD and Sinkhorn Divergences. We derive learning bounds establishing that the learned representation transfers well to novel tasks. We present experiments on three real world datasets, showing that the proposed method outperforms state-of-the-art approaches by a significant margin.
Deep Rao-Blackwellised Particle Filters for Time Series Forecasting
Authors: Richard Kurle, Syama Sundar Rangapuram, Emmanuel de Bézenac, Stephan Günnemann, Jan Gasthaus
Date: 2020-12-01 00:00:00
Proceeding: NeurIPS 2020 12
Tasks: Decoder, Time Series, Time Series Analysis, Time Series Forecasting

This work addresses efficient inference and learning in switching Gaussian linear dynamical systems using a Rao-Blackwellised particle filter and a corresponding Monte Carlo objective. To improve the forecasting capabilities, we extend this classical model by conditionally linear state-to-switch dynamics, while leaving the partial tractability of the conditional Gaussian linear part intact. Furthermore, we use an auxiliary variable approach with a decoder-type neural network that allows for more complex non-linear emission models and multivariate observations. We propose a Monte Carlo objective that leverages the conditional linearity by computing the corresponding conditional expectations in closed-form and a suitable proposal distribution that is factorised similarly to the optimal proposal distribution. We evaluate our approach on several popular time series forecasting datasets as well as image streams of simulated physical systems. Our results show improved forecasting performance compared to other deep state-space model approaches.
Robust Sequence Submodular Maximization
Authors: Gamal Sallam, Zizhan Zheng, Jie Wu, Bo Ji
Date: 2020-12-01 00:00:00
Proceeding: NeurIPS 2020 12

Submodularity is an important property of set functions and has been extensively studied in the literature. It models set functions that exhibit a diminishing returns property, where the marginal value of adding an element to a set decreases as the set expands. This notion has been generalized to considering sequence functions, where the order of adding elements plays a crucial role and determines the function value; the generalized notion is called sequence (or string) submodularity. In this paper, we study a new problem of robust sequence submodular maximization with cardinality constraints. The robustness is against the removal of a subset of elements in the selected sequence (e.g., due to malfunctions or adversarial attacks). Compared to robust submodular maximization for set function, new challenges arise when sequence functions are concerned. Specifically, there are multiple definitions of submodularity for sequence functions, which exhibit subtle yet critical differences. Another challenge comes from two directions of monotonicity: forward monotonicity and backward monotonicity, both of which are important to proving performance guarantees. To address these unique challenges, we design two robust greedy algorithms: while one algorithm achieves a constant approximation ratio but is robust only against the removal of a subset of contiguous elements, the other is robust against the removal of an arbitrary subset of the selected elements but requires a stronger assumption and achieves an approximation ratio that depends on the number of the removed elements. Finally, we generalize the analyses to considering sequence functions under weaker assumptions based on approximate versions of sequence submodularity and backward monotonicity.
System Identification with Biophysical Constraints: A Circuit Model of the Inner Retina
Authors: Cornelius Schröder, David Klindt, Sarah Strauss, Katrin Franke, Matthias Bethge, Thomas Euler, Philipp Berens
Date: 2020-12-01 00:00:00
Proceeding: NeurIPS 2020 12
Tasks: Blocking

Visual processing in the retina has been studied in great detail at all levels such that a comprehensive picture of the retina's cell types and the many neural circuits they form is emerging. However, the currently best performing models of retinal function are black-box CNN models which are agnostic to such biological knowledge. In particular, these models typically neglect the role of the many inhibitory circuits involving amacrine cells and the biophysical mechanisms underlying synaptic release. Here, we present a computational model of temporal processing in the inner retina, including inhibitory feedback circuits and realistic synaptic release mechanisms. Fit to the responses of bipolar cells, the model generalized well to new stimuli including natural movie sequences, performing on par with or better than a benchmark black-box model. In pharmacology experiments, the model replicated in silico the effect of blocking specific amacrine cell populations with high fidelity, indicating that it had learned key circuit functions. Also, more in depth comparisons showed that connectivity patterns learned by the model were well matched to connectivity patterns extracted from connectomics data. Thus, our model provides a biologically interpretable data-driven account of temporal processing in the inner retina, filling the gap between purely black-box and detailed biophysical modeling.
A Unified Switching System Perspective and Convergence Analysis of Q-Learning Algorithms
Authors: Donghwan Lee, Niao He
Date: 2020-12-01 00:00:00
Proceeding: NeurIPS 2020 12
Tasks: Q-Learning

This paper develops a novel and unified framework to analyze the convergence of a large family of Q-learning algorithms from the switching system perspective. We show that the  nonlinear  ODE  models  associated  with Q-learning and many of its variants can be naturally formulated as affine switching systems.  Building on their asymptotic stability, we obtain a number of interesting results: (i) we provide a simple ODE analysis for the convergence of asynchronous  Q-learning under relatively weak assumptions; (ii) we establish the first convergence analysis of the averaging Q-learning algorithm; and (iii) we  derive a new sufficient condition for the convergence of Q-learning with linear function approximation.
Calibrating CNNs for Lifelong Learning
Authors: Pravendra Singh, Vinay Kumar Verma, Pratik Mazumder, Lawrence Carin, Piyush Rai
Date: 2020-12-01 00:00:00
Proceeding: NeurIPS 2020 12
Tasks: Continual Learning, Lifelong learning

We present an approach for lifelong/continual learning of convolutional neural networks (CNN) that does not suffer from the problem of catastrophic forgetting when moving from one task to the other. We show that the activation maps generated by the CNN trained on the old task can be calibrated using very few calibration parameters, to become relevant to the new task. Based on this, we calibrate the activation maps produced by each network layer using spatial and channel-wise calibration modules and train only these calibration parameters for each new task in order to perform lifelong learning. Our calibration modules introduce significantly less computation and parameters as compared to the approaches that dynamically expand the network. Our approach is immune to catastrophic forgetting since we store the task-adaptive calibration parameters, which contain all the task-specific knowledge and is exclusive to each task. Further, our approach does not require storing data samples from the old tasks, which is done by many replay based methods. We perform extensive experiments on multiple benchmark datasets (SVHN, CIFAR, ImageNet, and MS-Celeb), all of which show substantial improvements over state-of-the-art methods (e.g., a 29% absolute increase in accuracy on CIFAR-100 with 10 classes at a time). On large-scale datasets, our approach yields 23.8% and 9.7% absolute increase in accuracy on ImageNet-100 and MS-Celeb-10K datasets, respectively, by employing very few (0.51% and 0.35% of model parameters) task-adaptive calibration parameters.