pwc-archive/papers-with-abstracts huggingface dataset:
Scaling the Poisson GLM to massive neural datasets through polynomial approximations
Authors: David Zoltowski, Jonathan W. Pillow
Date: 2018-12-01 00:00:00
Proceeding: NeurIPS 2018 12

Recent advances in recording technologies have allowed neuroscientists to record simultaneous spiking activity from hundreds to thousands of neurons in multiple brain regions. Such large-scale recordings pose a major challenge to existing statistical methods for neural data analysis. Here we develop highly scalable approximate inference methods for Poisson generalized linear models (GLMs) that require only a single pass over the data. Our approach relies on a recently proposed method for obtaining approximate sufficient statistics for GLMs using polynomial approximations [Huggins et al., 2017], which we adapt to the Poisson GLM setting. We focus on inference using quadratic approximations to nonlinear terms in the Poisson GLM log-likelihood with Gaussian priors, for which we derive closed-form solutions to the approximate maximum likelihood and MAP estimates, posterior distribution, and marginal likelihood. We introduce an adaptive procedure to select the polynomial approximation interval and show that the resulting method allows for efficient and accurate inference and regularization of high-dimensional parameters. We use the quadratic estimator to fit a fully-coupled Poisson GLM to spike train data recorded from 831 neurons across five regions of the mouse brain for a duration of 41 minutes, binned at 1 ms resolution. Across all neurons, this model is fit to over 2 billion spike count bins and identifies fine-timescale statistical dependencies between neurons within and across cortical and subcortical areas.
Multiplicative Weights Updates with Constant Step-Size in Graphical Constant-Sum Games
Authors: Yun Kuen Cheung
Date: 2018-12-01 00:00:00
Proceeding: NeurIPS 2018 12

Since Multiplicative Weights (MW) updates are the discrete analogue of the continuous Replicator Dynamics (RD), some researchers had expected their qualitative behaviours would be similar. We show that this is false in the context of graphical constant-sum games, which include two-person zero-sum games as special cases. In such games which have a fully-mixed Nash Equilibrium (NE), it was known that RD satisfy the permanence and Poincare recurrence properties, but we show that MW updates with any constant step-size eps > 0 converge to the boundary of the state space, and thus do not satisfy the two properties. Using this result, we show that MW updates have a regret lower bound of Omega( 1 / (eps T) ), while it was known that the regret of RD is upper bounded by O( 1 / T ).

Interestingly, the regret perspective can be useful for better understanding of the behaviours of MW updates. In a two-person zero-sum game, if it has a unique NE which is fully mixed, then we show, via regret, that for any sufficiently small eps, there exist at least two probability densities and a constant Z > 0, such that for any arbitrarily small z > 0, each of the two densities fluctuates above Z and below z infinitely often.
Modern Neural Networks Generalize on Small Data Sets
Authors: Matthew Olson, Abraham Wyner, Richard Berk
Date: 2018-12-01 00:00:00
Proceeding: NeurIPS 2018 12
Tasks: General Classification, image-classification, Image Classification, Small Data Image Classification

In this paper,  we  use a linear program to empirically decompose fitted neural networks into ensembles of low-bias sub-networks. We show that these sub-networks are relatively uncorrelated which leads to an  internal regularization process, very much like a random forest, which can explain why a neural network is surprisingly resistant to overfitting.  We then demonstrate this in practice by applying large neural networks, with hundreds of parameters per training observation, to a  collection of 116 real-world data sets from the UCI Machine Learning Repository.   This collection of data sets contains a much smaller number of training examples than the types of image classification tasks generally studied in the deep learning literature, as well as non-trivial label noise. We show  that even in this setting deep neural nets are capable of achieving superior classification accuracy without overfitting.
Optimal Subsampling with Influence Functions
Authors: Daniel Ting, Eric Brochu
Date: 2018-12-01 00:00:00
Proceeding: NeurIPS 2018 12
Tasks: regression

Subsampling is a common and often effective method to deal with the computational challenges of large datasets. However, for most statistical models, there is no well-motivated approach for drawing a non-uniform subsample. We show that the concept of an asymptotically linear estimator and the associated influence function leads to asymptotically optimal sampling probabilities for a wide class of popular models. This is the only tight optimality result for subsampling we are aware of as other methods only provide probabilistic error bounds or optimal rates. 
Furthermore, for linear regression models, which have well-studied procedures for non-uniform subsampling, we empirically show our optimal influence function based method outperforms previous approaches even when using approximations to the optimal probabilities.
A Bandit Approach to Sequential Experimental Design with False Discovery Control
Authors: Kevin G. Jamieson, Lalit Jain
Date: 2018-12-01 00:00:00
Proceeding: NeurIPS 2018 12
Tasks: Drug Discovery, Experimental Design, Multi-Armed Bandits

We propose a new adaptive sampling approach to multiple testing which aims to maximize statistical power while ensuring anytime false discovery control. We consider $n$ distributions whose means are partitioned by whether they are below or equal to a baseline (nulls), versus above the baseline (true positives). In addition, each distribution can be sequentially and repeatedly sampled. Using techniques from multi-armed bandits, we provide an algorithm that takes as few samples as possible to exceed a target true positive proportion (i.e. proportion of true positives discovered) while giving anytime control of the false discovery proportion (nulls predicted as true positives). Our sample complexity results match known information theoretic lower bounds and through simulations we show a substantial performance improvement over uniform sampling and an adaptive elimination style algorithm. Given the simplicity of the approach, and its sample efficiency, the method has promise for wide adoption in the biological sciences, clinical testing for drug discovery, and maximization of click through in A/B/n testing problems.
Equality of Opportunity in Classification: A Causal Approach
Authors: Junzhe Zhang, Elias Bareinboim
Date: 2018-12-01 00:00:00
Proceeding: NeurIPS 2018 12
Tasks: Classification, counterfactual, Fairness, General Classification

The Equalized Odds (for short, EO)  is one of the most popular measures of discrimination used in the supervised learning setting. It ascertains fairness through the balance of the misclassification rates (false positive and negative) across the protected groups -- e.g., in the context of law enforcement, an African-American defendant who would not commit a future crime will have an equal opportunity of being released, compared to a non-recidivating Caucasian defendant. Despite this noble goal, it has been acknowledged in the literature that statistical tests based on the EO are oblivious to the underlying causal mechanisms that generated the disparity in the first place (Hardt et al. 2016). This leads to a critical disconnect between statistical measures readable from the data and the meaning of discrimination in the legal system, where compelling evidence that the observed disparity is tied to a specific causal process deemed unfair by society is required to characterize discrimination. The goal of this paper is to develop a principled approach to connect the statistical disparities characterized by the EO  and the underlying, elusive, and frequently unobserved, causal mechanisms that generated such inequality. We start by introducing a new family of counterfactual measures that allows one to explain the misclassification disparities in terms of the underlying mechanisms in an arbitrary, non-parametric structural causal model. This will, in turn, allow legal and data analysts to interpret currently deployed classifiers through causal lens, linking the statistical disparities found in the data to the corresponding causal processes. Leveraging the new family of counterfactual measures, we develop a learning procedure to construct a classifier that is statistically efficient, interpretable, and compatible with the basic human intuition of fairness. We demonstrate our results through experiments in both real (COMPAS) and synthetic datasets.
Unsupervised Attention-guided Image-to-Image Translation
Authors: Youssef Alami Mejjati, Christian Richardt, James Tompkin, Darren Cosker, Kwang In Kim
Date: 2018-12-01 00:00:00
Proceeding: NeurIPS 2018 12
Tasks: Image-to-Image Translation, Translation, Unsupervised Image-To-Image Translation

Current unsupervised image-to-image translation techniques struggle to focus their attention on individual objects without altering the background or the way multiple objects interact within a scene. Motivated by the important role of attention in human perception, we tackle this limitation by introducing unsupervised attention mechanisms which are jointly adversarially trained with the generators and discriminators. We empirically demonstrate that our approach is able to attend to relevant regions in the image without requiring any additional supervision, and that by doing so it achieves more realistic mappings compared to recent approaches.
Inferring Networks From Random Walk-Based Node Similarities
Authors: Jeremy Hoskins, Cameron Musco, Christopher Musco, Babis Tsourakakis
Date: 2018-12-01 00:00:00
Proceeding: NeurIPS 2018 12
Tasks: Anomaly Detection, Clustering, Graph Clustering, Graph Learning, Graph Similarity

Digital presence in the world of online social media entails significant privacy risks. In this work we consider a privacy threat to a social network in which an attacker has access to a subset of random walk-based node similarities, such as effective resistances (i.e., commute times) or personalized PageRank scores. Using these similarities, the attacker seeks to infer as much information as possible about the network, including unknown pairwise node similarities and edges.

For the effective resistance metric, we show that with just a small subset of measurements, one  can learn a large fraction of edges in a social network. We also show that it is possible to  learn a graph which accurately matches the underlying network on all other effective resistances. This second observation is interesting from a data mining perspective, since it can be expensive to compute all effective resistances or other random walk-based similarities. As an alternative, our graphs learned from just a subset of effective resistances can be used as surrogates in a range of applications that use effective resistances to probe graph structure, including for graph clustering, node centrality evaluation, and anomaly detection. 

We obtain our results by formalizing the graph learning objective mathematically, using two optimization problems. One formulation is convex and can be solved provably in polynomial time. The other is not, but we solve it efficiently with projected gradient and coordinate descent. We demonstrate the effectiveness of these methods on a number of social networks obtained from Facebook. We also discuss how our methods can be generalized to other random walk-based similarities, such as personalized PageRank scores. Our code is available at https://github.com/cnmusco/graph-similarity-learning.
Variational PDEs for Acceleration on Manifolds and Application to Diffeomorphisms
Authors: Ganesh Sundaramoorthi, Anthony Yezzi
Date: 2018-12-01 00:00:00
Proceeding: NeurIPS 2018 12

We consider the optimization of cost functionals on manifolds and derive a variational approach to accelerated methods on manifolds. We demonstrate the methodology on the infinite-dimensional manifold of diffeomorphisms, motivated by registration problems in computer vision. We build on the variational approach to accelerated optimization by Wibisono, Wilson and Jordan, which applies in finite dimensions, and generalize that approach to infinite dimensional manifolds. We derive the continuum evolution equations, which are partial differential equations (PDE), and relate them to simple mechanical principles. Our approach can also be viewed as a generalization of the $L^2$ optimal mass transport problem. Our approach evolves an infinite number of particles endowed with mass, represented as a mass density. The density evolves with the optimization variable, and endows the particles with dynamics. This is different than current accelerated methods where only a single particle moves and hence the dynamics does not depend on the mass. We derive the theory, compute the PDEs for acceleration, and illustrate the behavior of this new accelerated optimization scheme.
Bayesian Inference of Temporal Task Specifications from Demonstrations
Authors: Ankit Shah, Pritish Kamath, Julie A. Shah, Shen Li
Date: 2018-12-01 00:00:00
Proceeding: NeurIPS 2018 12
Tasks: Bayesian Inference, Probabilistic Programming

When observing task demonstrations, human apprentices are able to identify whether a given task is executed correctly long before they gain expertise in actually performing that task. Prior research into learning from demonstrations (LfD) has failed to capture this notion of the acceptability of an execution; meanwhile, temporal logics provide a flexible language for expressing task specifications. Inspired by this, we present Bayesian specification inference, a probabilistic model for inferring task specification as a temporal logic formula. We incorporate methods from probabilistic programming to define our priors, along with a domain-independent likelihood function to enable sampling-based inference. We demonstrate the efficacy of our model for inferring true specifications with over 90% similarity between the inferred specification and the ground truth, both within a synthetic domain and a real-world table setting task.
Data center cooling using model-predictive control
Authors: Nevena Lazic, Craig Boutilier, Tyler Lu, Eehern Wong, Binz Roy, Mk Ryu, Greg Imwalle
Date: 2018-12-01 00:00:00
Proceeding: NeurIPS 2018 12
Tasks: model, Model Predictive Control, reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

Despite impressive recent advances in reinforcement learning (RL), its deployment in real-world physical systems is often complicated by unexpected events, limited data, and the potential for expensive failures. In this paper, we describe an application of RL “in the wild” to the task of regulating temperatures and airflow inside a large-scale data center (DC). Adopting a data-driven, model-based approach, we demonstrate that an RL agent with little prior knowledge is able to effectively and safely regulate conditions on a server floor after just a few hours of exploration, while improving operational efficiency relative to existing PID controllers.
Bipartite Stochastic Block Models with Tiny Clusters
Authors: Stefan Neumann
Date: 2018-12-01 00:00:00
Proceeding: NeurIPS 2018 12

We study the problem of finding clusters in random bipartite graphs. We present a simple two-step algorithm which provably finds even tiny clusters of size $O(n^\epsilon)$, where $n$ is the number of vertices in the graph and $\epsilon > 0$. Previous algorithms were only able to identify clusters of size $\Omega(\sqrt{n})$. We evaluate the algorithm on synthetic and on real-world data; the experiments show that the algorithm can find extremely small clusters even in presence of high destructive noise.
Faster Online Learning of Optimal Threshold for Consistent F-measure Optimization
Authors: Xiaoxuan Zhang, Mingrui Liu, Xun Zhou, Tianbao Yang
Date: 2018-12-01 00:00:00
Proceeding: NeurIPS 2018 12

In this paper, we consider online F-measure optimization (OFO). Unlike traditional performance metrics (e.g., classification error rate), F-measure is non-decomposable over training examples and is a non-convex function of model parameters, making it much more difficult to be optimized in an online fashion. Most existing results of OFO usually suffer from high memory/computational costs and/or lack  statistical consistency  guarantee for optimizing F-measure at the population level. To advance OFO, we propose an efficient online algorithm based on simultaneously learning a posterior probability of class and learning an optimal threshold by minimizing  a stochastic strongly convex function with unknown strong convexity parameter. A key component of the proposed method is  a novel stochastic algorithm with low memory and computational costs, which can enjoy a  convergence rate of $\widetilde O(1/\sqrt{n})$ for learning the optimal threshold under a mild condition on the convergence of the posterior probability,  where $n$ is the number of processed examples. It is provably  faster than its predecessor based on a heuristic for updating the threshold.   The experiments verify  the efficiency of the proposed algorithm in comparison with state-of-the-art OFO algorithms.
Stochastic Nested Variance Reduced Gradient Descent for Nonconvex Optimization
Authors: Dongruo Zhou, Pan Xu, Quanquan Gu
Date: 2018-12-01 00:00:00
Proceeding: NeurIPS 2018 12

We study finite-sum nonconvex optimization problems, where the objective function is an average of $n$ nonconvex functions. We propose a new stochastic gradient descent algorithm based on nested variance reduction. Compared with conventional stochastic variance reduced gradient (SVRG) algorithm that uses two reference points to construct a semi-stochastic gradient with diminishing variance in each epoch, our algorithm uses $K+1$ nested reference points to build an semi-stochastic gradient to further reduce its variance in each epoch. For smooth functions, the proposed algorithm converges to an approximate first order stationary point (i.e., $\|\nabla F(\xb)\|_2\leq \epsilon$) within $\tO(n\land \epsilon^{-2}+\epsilon^{-3}\land n^{1/2}\epsilon^{-2})$\footnote{$\tO(\cdot)$ hides the logarithmic factors} number of stochastic gradient evaluations, where $n$ is the number of component functions, and $\epsilon$ is the optimization error. This improves the best known gradient complexity of SVRG $O(n+n^{2/3}\epsilon^{-2})$ and the best gradient complexity of SCSG $O(\epsilon^{-5/3}\land n^{2/3}\epsilon^{-2})$. For gradient dominated functions, our algorithm achieves $\tO(n\land \tau\epsilon^{-1}+\tau\cdot (n^{1/2}\land (\tau\epsilon^{-1})^{1/2})$ gradient complexity, which again beats the existing best gradient complexity $\tO(n\land \tau\epsilon^{-1}+\tau\cdot (n^{1/2}\land (\tau\epsilon^{-1})^{2/3})$ achieved by SCSG. Thorough experimental results on different nonconvex optimization problems back up our theory.
Faster Neural Networks Straight from JPEG
Authors: Lionel Gueguen, Alex Sergeev, Ben Kadlec, Rosanne Liu, Jason Yosinski
Date: 2018-12-01 00:00:00
Proceeding: NeurIPS 2018 12
Tasks: CPU, GPU

The simple, elegant approach of training convolutional neural
  networks (CNNs) directly from RGB pixels has enjoyed overwhelming
  empirical success. But can more performance be squeezed out of
  networks by using different input representations?  In this paper we
  propose and explore a simple idea: train CNNs directly on the
  blockwise discrete cosine transform (DCT) coefficients computed and
  available in the middle of the JPEG codec. Intuitively, when
  processing JPEG images using CNNs, it seems unnecessary to
  decompress a blockwise frequency representation to an expanded pixel
  representation, shuffle it from CPU to GPU, and then process it with
  a CNN that will learn something similar to a transform back to
  frequency representation in its first layers. Why not skip both
  steps and feed the frequency domain into the network directly?  In
  this paper we modify \libjpeg to produce DCT coefficients directly,
  modify a ResNet-50 network to accommodate the differently sized and
  strided input, and evaluate performance on ImageNet. We find
  networks that are both faster and more accurate, as well as networks
  with about the same accuracy but 1.77x faster than ResNet-50.
Learning from discriminative feature feedback
Authors: Sanjoy Dasgupta, Akansha Dey, Nicholas Roberts, Sivan Sabato
Date: 2018-12-01 00:00:00
Proceeding: NeurIPS 2018 12

We consider the problem of learning a multi-class classifier from labels as well as simple explanations that we call "discriminative features". We show that such explanations can be provided whenever the target concept is a decision tree, or more generally belongs to a particular subclass of DNF formulas. We present an efficient online algorithm for learning from such feedback and we give tight bounds on the number of mistakes made during the learning process. These bounds depend only on the size of the target concept and not on the overall number of available features, which could be infinite. We also demonstrate the learning procedure experimentally.
Solving Non-smooth Constrained Programs with Lower Complexity than \mathcal{O}(1/\varepsilon): A Primal-Dual Homotopy Smoothing Approach
Authors: Xiaohan Wei, Hao Yu, Qing Ling, Michael Neely
Date: 2018-12-01 00:00:00
Proceeding: NeurIPS 2018 12
Tasks: Distributed Optimization

We propose a new primal-dual homotopy smoothing algorithm for a linearly constrained convex program, where neither the primal nor the dual function has to be smooth or strongly convex. The best known iteration complexity solving such a non-smooth problem is $\mathcal{O}(\varepsilon^{-1})$. In this paper, 
we show that by leveraging a local error bound condition on the dual function, the proposed algorithm can achieve a better primal convergence time of  $\mathcal{O}\l(\varepsilon^{-2/(2+\beta)}\log_2(\varepsilon^{-1})\r)$, where $\beta\in(0,1]$ is a local error bound parameter. 
As an example application, we show that the distributed geometric median problem, which can be formulated as a constrained convex program, has its dual function non-smooth but satisfying the aforementioned local error bound condition with $\beta=1/2$, therefore enjoying a convergence time of $\mathcal{O}\l(\varepsilon^{-4/5}\log_2(\varepsilon^{-1})\r)$. This result improves upon the $\mathcal{O}(\varepsilon^{-1})$ convergence time bound achieved by existing distributed optimization algorithms. Simulation experiments also demonstrate the performance of our proposed algorithm.
Probabilistic Neural Programmed Networks for Scene Generation
Authors: Zhiwei Deng, Jiacheng Chen, Yifang Fu, Greg Mori
Date: 2018-12-01 00:00:00
Proceeding: NeurIPS 2018 12
Tasks: Image Generation, Scene Generation

In this paper we address the text to scene image generation problem. Generative models that capture the variability in complicated scenes containing rich semantics is a grand goal of image generation. Complicated scene images contain rich visual elements, compositional visual concepts, and complicated relations between objects. Generative models, as an analysis-by-synthesis process, should encompass the following three core components: 1) the generation process that composes the scene; 2) what are the primitive visual elements and how are they composed; 3) the rendering of abstract concepts into their pixel-level realizations.  We propose PNP-Net, a variational auto-encoder framework that addresses these three challenges: it flexibly composes images with a dynamic network structure, learns a set of distribution transformers that can compose distributions based on semantics, and decodes samples from these distributions into realistic images.