mtybilly/Instruct2DS huggingface dataset:
A Spectral View of Adversarially Robust Features
Authors: Vatsal Sharan, Brian Zhang, Gregory Valiant Shivam Garg
Published in: Advances in Neural Information Processing Systems 31  (NeurIPS 2018) (Main Conference Track), 2018

Abstract: Given the apparent difficulty of learning models that are robust to adversarial perturbations, we propose tackling the simpler problem of developing adversarially robust features.  Specifically, given a dataset and metric of interest, the goal is to return a function (or multiple functions) that 1) is robust to adversarial perturbations, and 2) has significant variation across the datapoints.  We establish strong connections between adversarially robust features and a natural spectral property of the geometry of the dataset and metric of interest.  This connection can be leveraged to provide both robust features, and a lower bound on the robustness of any function that has significant variance across the dataset.  Finally, we provide empirical evidence that the adversarially robust features given by this spectral approach can be fruitfully leveraged to learn a robust (and accurate) model.
Dimensionality Reduction has Quantifiable Imperfections: Two Geometric Bounds
Authors: Gavin Weiguang Ding, Ruitong Huang, Robert McCann Kry Lui
Published in: Advances in Neural Information Processing Systems 31  (NeurIPS 2018) (Main Conference Track), 2018

Abstract: In this paper, we investigate Dimensionality reduction (DR) maps in an information retrieval setting from a quantitative topology point of view. In particular, we show that no DR maps can achieve perfect precision and perfect recall simultaneously. Thus a continuous DR map must have imperfect precision. We further prove an upper bound on the precision of Lipschitz continuous DR maps. While precision is a natural measure in an information retrieval setting, it does not measure `how' wrong the retrieved data is. We therefore propose a new measure based on Wasserstein distance that comes with similar theoretical guarantee. A key technical step in our proofs is a particular optimization problem of the $L_2$-Wasserstein distance over a constrained set of distributions. We provide a complete solution to this optimization problem, which can be of independent interest on the technical side.
Learning SMaLL Predictors
Authors: Ofer Dekel, Lin Xiao Vikas Garg
Published in: Advances in Neural Information Processing Systems 31  (NeurIPS 2018) (Main Conference Track), 2018

Abstract: We introduce a new framework for learning in severely resource-constrained settings. Our technique delicately amalgamates the representational richness of multiple linear predictors with the sparsity of Boolean relaxations, and thereby yields classifiers that are compact, interpretable, and accurate. We provide a rigorous formalism of the learning problem, and establish fast convergence of the ensuing algorithm via relaxation to a minimax saddle point objective. We supplement the theoretical foundations of our work with an extensive empirical evaluation.
ResNet with one-neuron hidden layers is a Universal Approximator
Authors: Stefanie Jegelka Hongzhou Lin
Published in: Advances in Neural Information Processing Systems 31  (NeurIPS 2018) (Main Conference Track), 2018

Abstract: We demonstrate that a very deep ResNet with stacked modules that have one neuron per hidden layer and ReLU activation functions can uniformly approximate any Lebesgue integrable function in d dimensions, i.e. \ell_1(R^d). Due to the identity mapping inherent to ResNets, our network has alternating layers of dimension one and d. This stands in sharp contrast to fully connected networks, which are not universal approximators if their width is the input dimension d [21,11]. Hence, our result implies an increase in representational power for narrow deep networks by the ResNet architecture.
How Many Samples are Needed to Estimate a Convolutional Neural Network?
Authors: Yining Wang, Xiyu Zhai, Sivaraman Balakrishnan, Ruslan Salakhutdinov, Aarti Singh Simon S Du
Published in: Advances in Neural Information Processing Systems 31  (NeurIPS 2018) (Main Conference Track), 2018

Abstract: A widespread folklore for explaining the success of Convolutional Neural Networks (CNNs) is that CNNs use a more compact representation than the Fully-connected Neural Network (FNN) and thus require fewer training samples to accurately estimate their parameters. We initiate the study of rigorously characterizing the sample complexity of estimating CNNs. We show that for an $m$-dimensional convolutional filter with linear activation acting on a $d$-dimensional input, the sample complexity of achieving population prediction error of $\epsilon$ is $\widetilde{O(m/\epsilon^2)$, whereas the sample-complexity for its FNN counterpart is lower bounded by $\Omega(d/\epsilon^2)$ samples. Since, in typical settings $m \ll d$, this result demonstrates the advantage of using a CNN. We further consider the sample complexity of estimating a one-hidden-layer CNN with linear activation where both the $m$-dimensional convolutional filter and the $r$-dimensional output weights are unknown. For this model, we show that the sample complexity is $\widetilde{O}\left((m+r)/\epsilon^2\right)$ when the ratio between the stride size and the filter size is a constant. For both models, we also present lower bounds showing our sample complexities are tight up to logarithmic factors. Our main tools for deriving these results are a localized empirical process analysis and a new lemma characterizing the convolutional structure. We believe that these tools may inspire further developments in understanding CNNs.
Objective and efficient inference for couplings in neuronal networks
Authors: Tomoyuki Obuchi, Takuya Isomura, Yoshiyuki Kabashima Yu Terada
Published in: Advances in Neural Information Processing Systems 31  (NeurIPS 2018) (Main Conference Track), 2018

Abstract: Inferring directional couplings from the spike data of networks is desired in various scientific fields such as neuroscience. Here, we apply a recently proposed objective procedure to the spike data obtained from the Hodgkin-Huxley type models and in vitro neuronal networks cultured in a circular structure. As a result, we succeed in reconstructing synaptic connections accurately from the evoked activity as well as the spontaneous one. To obtain the results, we invent an analytic formula approximately implementing a method of screening relevant couplings. This significantly reduces the computational cost of the screening method employed in the proposed objective procedure, making it possible to treat large-size systems as in this study.
Unsupervised Adversarial Invariance
Authors: Rex Yue Wu, Wael Abd-Almageed, Prem Natarajan Ayush Jaiswal
Published in: Advances in Neural Information Processing Systems 31  (NeurIPS 2018) (Main Conference Track), 2018

Abstract: Data representations that contain all the information about target variables but are invariant to nuisance factors benefit supervised learning algorithms by preventing them from learning associations between these factors and the targets, thus reducing overfitting. We present a novel unsupervised invariance induction framework for neural networks that learns a split representation of data through competitive training between the prediction task and a reconstruction task coupled with disentanglement, without needing any labeled information about nuisance factors or domain knowledge. We describe an adversarial instantiation of this framework and provide analysis of its working. Our unsupervised model outperforms state-of-the-art methods, which are supervised, at inducing invariance to inherent nuisance factors, effectively using synthetic data augmentation to learn invariance, and domain adaptation. Our method can be applied to any prediction task, eg., binary/multi-class classification or regression, without loss of generality.
Critical initialisation for deep signal propagation in noisy rectifier neural networks
Authors: Elan van Biljon, Steve Kroon, Herman Kamper Arnu Pretorius
Published in: Advances in Neural Information Processing Systems 31  (NeurIPS 2018) (Main Conference Track), 2018

Abstract: Stochastic regularisation is an important weapon in the arsenal of a deep learning practitioner. However, despite recent theoretical advances, our understanding of how noise influences signal propagation in deep neural networks remains limited. By extending recent work based on mean field theory, we develop a new framework for signal propagation in stochastic regularised neural networks. Our \textit{noisy signal propagation} theory can incorporate several common noise distributions, including additive and multiplicative Gaussian noise as well as dropout. We use this framework to investigate initialisation strategies for noisy ReLU networks. We show that no critical initialisation strategy exists using additive noise, with signal propagation exploding regardless of the selected noise distribution. For multiplicative noise (e.g.\ dropout), we identify alternative critical initialisation strategies that depend on the second moment of the noise distribution.  Simulations and experiments on real-world data confirm that our proposed initialisation is able to stably propagate signals in deep networks, while using an initialisation disregarding noise fails to do so. Furthermore, we analyse correlation dynamics between inputs. Stronger noise regularisation is shown to reduce the depth to which discriminatory information about the inputs to a noisy ReLU network is able to propagate, even when initialised at criticality. We support our theoretical predictions for these trainable depths with simulations, as well as with experiments on MNIST and CIFAR-10.
Learning sparse neural networks via sensitivity-driven regularization
Authors: Skjalg Lepsøy, Attilio Fiandrotti, Gianluca Francini Enzo Tartaglione
Published in: Advances in Neural Information Processing Systems 31  (NeurIPS 2018) (Main Conference Track), 2018

Abstract: The ever-increasing number of parameters in deep neural networks poses challenges for memory-limited applications. Regularize-and-prune methods aim at meeting these challenges by sparsifying the network weights. In this context we quantify the output sensitivity to the parameters (i.e. their relevance to the network output) and introduce a regularization term that gradually lowers the absolute value of parameters with low sensitivity.  Thus, a very large fraction of the parameters approach zero and are eventually set to zero by simple thresholding. Our method surpasses most of the recent techniques both in terms of sparsity and error rates. In some cases, the method reaches twice the sparsity obtained by other techniques at equal error rates.
Cooperative neural networks (CoNN): Exploiting prior independence structure for improved classification
Authors: Eugene Bart, Bob Price, Hanjun Dai, Bo Dai, Srinivas Aluru Harsh Shrivastava
Published in: Advances in Neural Information Processing Systems 31  (NeurIPS 2018) (Main Conference Track), 2018

Abstract: We propose a new approach, called cooperative neural networks (CoNN), which use a set of cooperatively trained neural networks to capture latent representations that exploit prior given independence structure. The model is more flexible than traditional graphical models based on exponential family distributions, but incorporates more domain specific prior structure than traditional deep networks or variational autoencoders. The framework is very general and can be used to exploit the independence structure of any graphical model. We illustrate the technique by showing that we can transfer the independence structure of the popular Latent Dirichlet Allocation (LDA) model to a cooperative neural network, CoNN-sLDA. Empirical evaluation of CoNN-sLDA on supervised text classification tasks demonstrate that the theoretical advantages of prior independence structure can be realized in practice - we demonstrate a 23 percent reduction in error on the challenging MultiSent data set compared to state-of-the-art.
Data center cooling using model-predictive control
Authors: Craig Boutilier, Tyler Lu, Eehern Wong, Binz Roy, MK Ryu, Greg Imwalle Nevena Lazic
Published in: Advances in Neural Information Processing Systems 31  (NeurIPS 2018) (Main Conference Track), 2018

Abstract: 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.
Generalization Bounds for Uniformly Stable Algorithms
Authors: Jan Vondrak Vitaly Feldman
Published in: Advances in Neural Information Processing Systems 31  (NeurIPS 2018) (Main Conference Track), 2018

Abstract: Uniform stability of a learning algorithm is a classical notion of algorithmic stability introduced to derive high-probability bounds on the generalization error (Bousquet and Elisseeff, 2002).  Specifically, for a loss function with range bounded in $[0,1]$, the generalization error of $\gamma$-uniformly stable learning algorithm on $n$ samples is known to be at most $O((\gamma +1/n) \sqrt{n \log(1/\delta)})$ with probability at least $1-\delta$. Unfortunately, this bound does not lead to meaningful generalization bounds in many common settings where $\gamma \geq 1/\sqrt{n}$. At the same time the bound is known to be tight only when $\gamma = O(1/n)$.
  Here we prove substantially stronger generalization bounds for uniformly stable algorithms without any additional assumptions. First, we show that the generalization error in this setting is at most $O(\sqrt{(\gamma + 1/n) \log(1/\delta)})$ with probability at least $1-\delta$. In addition, we prove a tight bound of $O(\gamma^2 + 1/n)$ on the second moment of the generalization error. The best previous bound on the second moment of the generalization error is $O(\gamma + 1/n)$. Our proofs are based on new analysis techniques and our results imply substantially stronger generalization guarantees for several well-studied algorithms.
COLA: Decentralized Linear Learning
Authors: An Bian, Martin Jaggi Lie He
Published in: Advances in Neural Information Processing Systems 31  (NeurIPS 2018) (Main Conference Track), 2018

Abstract: Decentralized machine learning is a promising emerging paradigm in view of global challenges of data ownership and privacy. We consider learning of linear classification and regression models, in the setting where the training data is decentralized over many user devices, and the learning algorithm must run on-device, on an arbitrary communication network, without a central coordinator.
We propose COLA, a new decentralized training algorithm with strong theoretical guarantees and superior practical performance. Our framework overcomes many limitations of existing methods, and achieves communication efficiency, scalability, elasticity as well as resilience to changes in data and allows for unreliable and heterogeneous participating devices.
Leveraging the Exact Likelihood of Deep Latent Variable Models
Authors: Jes Frellsen Pierre-Alexandre Mattei
Published in: Advances in Neural Information Processing Systems 31  (NeurIPS 2018) (Main Conference Track), 2018

Abstract: Deep latent variable models (DLVMs) combine the approximation abilities of deep neural networks and the statistical foundations of generative models. Variational methods are commonly used for inference; however, the exact likelihood of these models has been largely overlooked. The purpose of this work is to study the general properties of this quantity and to show how they can be leveraged in practice. We focus on important inferential problems that rely on the likelihood: estimation and missing data imputation. First, we investigate maximum likelihood estimation for DLVMs: in particular, we show that most unconstrained models used for continuous data have an unbounded likelihood function. This problematic behaviour is demonstrated to be a source of mode collapse. We also show how to ensure the existence of maximum likelihood estimates, and draw useful connections with nonparametric mixture models. Finally, we describe an algorithm for missing data imputation using the exact conditional likelihood of a DLVM. On several data sets, our algorithm consistently and significantly outperforms the usual imputation scheme used for DLVMs.
A General Method for Amortizing Variational Filtering
Authors: Milan Cvitkovic, Yisong Yue Joseph Marino
Published in: Advances in Neural Information Processing Systems 31  (NeurIPS 2018) (Main Conference Track), 2018

Abstract: We introduce the variational filtering EM algorithm, a simple, general-purpose method for performing variational inference in dynamical latent variable models using information from only past and present variables, i.e. filtering. The algorithm is derived from the variational objective in the filtering setting and consists of an optimization procedure at each time step. By performing each inference optimization procedure with an iterative amortized inference model, we obtain a computationally efficient implementation of the algorithm, which we call amortized variational filtering. We present experiments demonstrating that this general-purpose method improves inference performance across several recent deep dynamical latent variable models.
One-Shot Unsupervised Cross Domain Translation
Authors: Lior Wolf Sagie Benaim
Published in: Advances in Neural Information Processing Systems 31  (NeurIPS 2018) (Main Conference Track), 2018

Abstract: Given a single image $x$ from domain $A$ and a set of images from domain $B$, our task is to generate the analogous of $x$ in $B$. We argue that this task could be a key AI capability that underlines the ability of cognitive agents to act in the world and present empirical evidence that the existing unsupervised domain translation methods fail on this task. Our method follows a two step process. First, a variational autoencoder for domain $B$ is trained. Then, given the new sample $x$, we create a variational autoencoder for domain $A$ by adapting the layers that are close to the image in order to directly fit $x$, and only indirectly adapt the other layers. Our experiments indicate that the new method does as well, when trained on one sample $x$, as the existing domain transfer methods, when these enjoy a multitude of training samples from domain $A$. Our code is made publicly available at https://github.com/sagiebenaim/OneShotTranslation
Query K-means Clustering and the Double Dixie Cup Problem
Authors: Chao Pan, Olgica Milenkovic I Chien
Published in: Advances in Neural Information Processing Systems 31  (NeurIPS 2018) (Main Conference Track), 2018

Abstract: We consider the problem of approximate $K$-means clustering with outliers and side information provided by same-cluster queries and possibly noisy answers. Our solution shows that, under some mild assumptions on the smallest cluster size, one can obtain an $(1+\epsilon)$-approximation for the optimal potential with probability at least $1-\delta$, where $\epsilon>0$ and $\delta\in(0,1)$, using an expected number of $O(\frac{K^3}{\epsilon \delta})$ noiseless same-cluster queries and comparison-based clustering of complexity $O(ndK + \frac{K^3}{\epsilon \delta})$; here, $n$ denotes the number of points and $d$ the dimension of space. Compared to a handful of other known approaches that perform importance sampling to account for small cluster sizes, the proposed query technique reduces the number of queries by a factor of roughly $O(\frac{K^6}{\epsilon^3})$, at the cost of possibly missing very small clusters. We extend this settings to the case where some queries to the oracle produce erroneous information, and where certain points, termed outliers, do not belong to any clusters. Our proof techniques differ from previous methods used for $K$-means clustering analysis, as they rely on estimating the sizes of the clusters and the number of points needed for accurate centroid estimation and subsequent nontrivial generalizations of the double Dixie cup problem. We illustrate the performance of the proposed algorithm both on synthetic and real datasets, including MNIST and CIFAR $10$.
Probabilistic Neural Programmed Networks for Scene Generation
Authors: Jiacheng Chen, YIFANG FU, Greg Mori Zhiwei Deng
Published in: Advances in Neural Information Processing Systems 31  (NeurIPS 2018) (Main Conference Track), 2018

Abstract: 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.
Escaping Saddle Points in Constrained Optimization
Authors: Asuman Ozdaglar, Ali Jadbabaie Aryan Mokhtari
Published in: Advances in Neural Information Processing Systems 31  (NeurIPS 2018) (Main Conference Track), 2018

Abstract: In this paper, we study the problem of escaping from saddle points in smooth
nonconvex optimization problems subject to a convex set $\mathcal{C}$. We propose a generic framework that yields convergence to a second-order stationary point of the problem, if the convex set $\mathcal{C}$ is simple for a quadratic objective function. Specifically, our results hold if one can find a $\rho$-approximate solution of a quadratic program subject to $\mathcal{C}$ in polynomial time, where $\rho<1$ is a positive constant that depends on the structure of the set $\mathcal{C}$. Under this condition, we show that the sequence of iterates generated by the proposed framework reaches an $(\epsilon,\gamma)$-second order stationary point (SOSP) in at most $\mathcal{O}(\max\{\epsilon^{-2},\rho^{-3}\gamma^{-3}\})$ iterations.  We further characterize the overall complexity of reaching an SOSP when the convex set $\mathcal{C}$ can be written as a set of quadratic constraints and the objective function Hessian
has a specific structure over the convex $\mathcal{C}$. Finally, we extend our results to the stochastic setting and characterize the number of stochastic gradient and Hessian evaluations to reach an $(\epsilon,\gamma)$-SOSP.
Adversarial Text Generation via Feature-Mover's Distance
Authors: Shuyang Dai, Chenyang Tao, Haichao Zhang, Zhe Gan, Dinghan Shen, Yizhe Zhang, Guoyin Wang, Ruiyi Zhang, Lawrence Carin Liqun Chen
Published in: Advances in Neural Information Processing Systems 31  (NeurIPS 2018) (Main Conference Track), 2018

Abstract: Generative adversarial networks (GANs) have achieved significant success in generating real-valued data. However, the discrete nature of text hinders the application of GAN to text-generation tasks. Instead of using the standard GAN objective, we propose to improve text-generation GAN via a novel approach inspired by optimal transport. Specifically, we consider matching the latent feature distributions of real and synthetic sentences using a novel metric, termed the feature-mover's distance (FMD). This formulation leads to a highly discriminative critic and easy-to-optimize objective, overcoming the mode-collapsing and brittle-training problems in existing methods. Extensive experiments are conducted on a variety of tasks to evaluate the proposed model empirically, including unconditional text generation, style transfer from non-parallel text, and unsupervised cipher cracking. The proposed model yields superior performance, demonstrating wide applicability and effectiveness.
On gradient regularizers for MMD GANs
Authors: Danica J. Sutherland, Mikołaj Bińkowski, Arthur Gretton Michael Arbel
Published in: Advances in Neural Information Processing Systems 31  (NeurIPS 2018) (Main Conference Track), 2018

Abstract: We propose a principled method for gradient-based regularization of the critic of GAN-like models trained by adversarially optimizing the kernel of a Maximum Mean Discrepancy (MMD). We show that controlling the gradient of the critic is vital to having a sensible loss function, and devise a method to enforce exact, analytical gradient constraints at no additional cost compared to existing approximate techniques based on additive regularizers. The new loss function is provably continuous, and experiments show that it stabilizes and accelerates training, giving image generation models that outperform state-of-the art methods on $160 \times 160$ CelebA and $64 \times 64$ unconditional ImageNet.
Differentially Private Bayesian Inference for Exponential Families
Authors: Daniel R. Sheldon Garrett Bernstein
Published in: Advances in Neural Information Processing Systems 31  (NeurIPS 2018) (Main Conference Track), 2018

Abstract: The study of private inference has been sparked by growing concern regarding the analysis of data when it stems from sensitive sources. We present the first method for private Bayesian inference in exponential families that properly accounts for noise introduced by the privacy mechanism. It is efficient because it works only with sufficient statistics and not individual data. Unlike other methods, it gives properly calibrated posterior beliefs in the non-asymptotic data regime.
Stochastic Primal-Dual Method for Empirical Risk Minimization with O(1) Per-Iteration Complexity
Authors: Tong Zhang, Shiqian Ma, Ji Liu Conghui Tan
Published in: Advances in Neural Information Processing Systems 31  (NeurIPS 2018) (Main Conference Track), 2018

Abstract: Regularized empirical risk minimization problem with linear predictor appears frequently in machine learning. In this paper, we propose a new stochastic primal-dual method to solve this class of problems. Different from existing methods, our proposed methods only require O(1) operations in each iteration. We also develop a variance-reduction variant of the algorithm that converges linearly. Numerical experiments suggest that our methods are faster than existing ones such as proximal SGD, SVRG and SAGA on high-dimensional problems.
Answerer in Questioner's Mind: Information Theoretic Approach to Goal-Oriented Visual Dialog
Authors: Yu-Jung Heo, Byoung-Tak Zhang Sang-Woo Lee
Published in: Advances in Neural Information Processing Systems 31  (NeurIPS 2018) (Main Conference Track), 2018

Abstract: Goal-oriented dialog has been given attention due to its numerous applications in artificial intelligence.
Goal-oriented dialogue tasks occur when a questioner asks an action-oriented question and an answerer responds with the intent of letting the questioner know a correct action to take. 
To ask the adequate question, deep learning and reinforcement learning have been recently applied. 
However, these approaches struggle to find a competent recurrent neural questioner, owing to the complexity of learning a series of sentences.
Motivated by theory of mind, we propose "Answerer in Questioner's Mind" (AQM), a novel information theoretic algorithm for goal-oriented dialog. 
With AQM, a questioner asks and infers based on an approximated probabilistic model of the answerer.
The questioner figures out the answerer’s intention via selecting a plausible question by explicitly calculating the information gain of the candidate intentions and possible answers to each question.
We test our framework on two goal-oriented visual dialog tasks: "MNIST Counting Dialog" and "GuessWhat?!".
In our experiments, AQM outperforms comparative algorithms by a large margin.
Learning Plannable Representations with Causal InfoGAN
Authors: Aviv Tamar, Ge Yang, Stuart Russell, Pieter Abbeel Thanard Kurutach
Published in: Advances in Neural Information Processing Systems 31  (NeurIPS 2018) (Main Conference Track), 2018

Abstract: In recent years, deep generative models have been shown to 'imagine' convincing high-dimensional observations such as images, audio, and even video, learning directly from raw data. In this work, we ask how to imagine goal-directed visual plans -- a plausible sequence of observations that transition a dynamical system from its current configuration to a desired goal state, which can later be used as a reference trajectory for control. We focus on systems with high-dimensional observations, such as images, and propose an approach that naturally combines representation learning and planning. Our framework learns a generative model of sequential observations, where the generative process is induced by a transition in a low-dimensional planning model, and an additional noise. By maximizing the mutual information between the generated observations and the transition in the planning model, we obtain a low-dimensional representation that best explains the causal nature of the data. We structure the planning model to be compatible with efficient planning algorithms, and we propose several such models based on either discrete or continuous states. Finally, to generate a visual plan, we project the current and goal observations onto their respective states in the planning model, plan a trajectory, and then use the generative model to transform the trajectory to a sequence of observations. We demonstrate our method on imagining plausible visual plans of rope manipulation.
Interactive Structure Learning with Structural Query-by-Committee
Authors: Sanjoy Dasgupta Christopher Tosh
Published in: Advances in Neural Information Processing Systems 31  (NeurIPS 2018) (Main Conference Track), 2018

Abstract: In this work, we introduce interactive structure learning, a framework that unifies many different interactive learning tasks. We present a generalization of the query-by-committee active learning algorithm for this setting, and we study its consistency and rate of convergence, both theoretically and empirically, with and without noise.
The streaming rollout of deep networks - towards fully model-parallel execution
Authors: Jan Koehler, Thomas Pfeil Volker Fischer
Published in: Advances in Neural Information Processing Systems 31  (NeurIPS 2018) (Main Conference Track), 2018

Abstract: Deep neural networks, and in particular recurrent networks, are promising candidates to control autonomous agents that interact in real-time with the physical world. However, this requires a seamless integration of temporal features into the network’s architecture. For the training of and inference with recurrent neural networks, they are usually rolled out over time, and different rollouts exist. Conventionally during inference, the layers of a network are computed in a sequential manner resulting in sparse temporal integration of information and long response times. In this study, we present a theoretical framework to describe rollouts, the level of model-parallelization they induce, and demonstrate differences in solving specific tasks. We prove that certain rollouts, also for networks with only skip and no recurrent connections, enable earlier and more frequent responses, and show empirically that these early responses have better performance. The streaming rollout maximizes these properties and enables a fully parallel execution of the network reducing runtime on massively parallel devices. Finally, we provide an open-source toolbox to design, train, evaluate, and interact with streaming rollouts.
Contextual Stochastic Block Models
Authors: Subhabrata Sen, Andrea Montanari, Elchanan Mossel Yash Deshpande
Published in: Advances in Neural Information Processing Systems 31  (NeurIPS 2018) (Main Conference Track), 2018

Abstract: We provide the first information theoretical tight analysis for inference of latent community structure given a sparse graph along with high dimensional node covariates, correlated with the same latent communities. Our work bridges recent theoretical breakthroughs in detection of latent community structure without nodes covariates and a large body of empirical work using diverse heuristics for combining node covariates with graphs for inference. The tightness of our analysis implies in particular, the information theoretic necessity of combining the different sources of information. 
Our analysis holds for networks of large degrees as well as for a Gaussian version of the model.
Unsupervised Learning of Artistic Styles with Archetypal Style Analysis
Authors: Cordelia Schmid, Julien Mairal Daan Wynen
Published in: Advances in Neural Information Processing Systems 31  (NeurIPS 2018) (Main Conference Track), 2018

Abstract: In this paper, we introduce an unsupervised learning approach to automatically dis-
cover, summarize, and manipulate artistic styles from large collections of paintings.
Our method is based on archetypal analysis, which is an unsupervised learning
technique akin to sparse coding with a geometric interpretation. When applied
to deep image representations from a data collection, it learns a dictionary of
archetypal styles, which can be easily visualized. After training the model, the style
of a new image, which is characterized by local statistics of deep visual features,
is approximated by a sparse convex combination of archetypes. This allows us
to interpret which archetypal styles are present in the input image, and in which
proportion. Finally, our approach allows us to manipulate the coefficients of the
latent archetypal decomposition, and achieve various special effects such as style
enhancement, transfer, and interpolation between multiple archetypes.
Generalisation in humans and deep neural networks
Authors: Carlos R. M. Temme, Jonas Rauber, Heiko H. Schütt, Matthias Bethge, Felix A. Wichmann Robert Geirhos
Published in: Advances in Neural Information Processing Systems 31  (NeurIPS 2018) (Main Conference Track), 2018

Abstract: We compare the robustness of humans and current convolutional deep neural networks (DNNs) on object recognition under twelve different types of image degradations. First, using three well known DNNs (ResNet-152, VGG-19, GoogLeNet) we find the human visual system to be more robust to nearly all of the tested image manipulations, and we observe progressively diverging classification error-patterns between humans and DNNs when the signal gets weaker. Secondly, we show that DNNs trained directly on distorted images consistently surpass human performance on the exact distortion types they were trained on, yet they display extremely poor generalisation abilities when tested on other distortion types. For example, training on salt-and-pepper noise does not imply robustness on uniform white noise and vice versa. Thus, changes in the noise distribution between training and testing constitutes a crucial challenge to deep learning vision systems that can be systematically addressed in a lifelong machine learning approach. Our new dataset consisting of 83K carefully measured human psychophysical trials provide a useful reference for lifelong robustness against image degradations set by the human visual system.
Distributed Weight Consolidation: A Brain Segmentation Case Study
Authors: Charles Y Zheng, Jakub Kaczmarzyk, John Rogers-Lee, Satra Ghosh, Dylan Nielson, Peter A Bandettini, Francisco Pereira Patrick McClure
Published in: Advances in Neural Information Processing Systems 31  (NeurIPS 2018) (Main Conference Track), 2018

Abstract: Collecting the large datasets needed to train deep neural networks can be very difficult, particularly for the many applications for which sharing and pooling data is complicated by practical, ethical, or legal concerns. However, it may be the case that derivative datasets or predictive models developed within individual sites can be shared and combined with fewer restrictions. Training on distributed data and combining the resulting networks is often viewed as continual learning, but these methods require networks to be trained sequentially. In this paper, we introduce distributed weight consolidation (DWC), a continual learning method to consolidate the weights of separate neural networks, each trained on an independent dataset. We evaluated DWC with a brain segmentation case study, where we consolidated dilated convolutional neural networks trained on independent structural magnetic resonance imaging (sMRI) datasets from different sites. We found that DWC led to increased performance on test sets from the different sites, while maintaining generalization performance for a very large and completely independent multi-site dataset, compared to an ensemble baseline.
IntroVAE: Introspective Variational Autoencoders for Photographic Image Synthesis
Authors: zhihang li, Ran He, Zhenan Sun, Tieniu Tan Huaibo Huang
Published in: Advances in Neural Information Processing Systems 31  (NeurIPS 2018) (Main Conference Track), 2018

Abstract: We present a novel introspective variational autoencoder (IntroVAE) model for synthesizing high-resolution photographic images. IntroVAE is capable of self-evaluating the quality of its generated samples and improving itself accordingly. Its inference and generator models are jointly trained in an introspective way. On one hand, the generator is required to reconstruct the input images from the noisy outputs of the inference model as normal VAEs. On the other hand, the inference model is encouraged to classify between the generated and real samples while the generator tries to fool it as GANs. These two famous generative frameworks are integrated in a simple yet efficient single-stream architecture that can be trained in a single stage. IntroVAE preserves the advantages of VAEs, such as stable training and nice latent manifold. Unlike most other hybrid models of VAEs and GANs, IntroVAE requires no extra discriminators, because the inference model itself serves as a discriminator to distinguish between the generated and real samples.  Experiments demonstrate that our method produces high-resolution photo-realistic images (e.g., CELEBA images at (1024^{2})), which are comparable to or better than the state-of-the-art GANs.
MixLasso: Generalized Mixed Regression via Convex Atomic-Norm Regularization
Authors: Wei-Cheng Lee, Kai Zhong, Sung-En Chang, Pradeep K Ravikumar, Shou-De Lin Ian En-Hsu Yen
Published in: Advances in Neural Information Processing Systems 31  (NeurIPS 2018) (Main Conference Track), 2018

Abstract: We consider a generalization of mixed regression where the response is an additive combination of several mixture components. Standard mixed regression is a special case where each response is generated from exactly one component. Typical approaches to the mixture regression problem employ local search methods such as Expectation Maximization (EM) that are prone to spurious local optima. On the other hand, a number of recent theoretically-motivated \emph{Tensor-based methods} either have high sample complexity, or require the knowledge of the input distribution, which is not available in most of practical situations. In this work, we study a novel convex estimator \emph{MixLasso} for the estimation of generalized mixed regression, based on an atomic norm specifically constructed to regularize the number of mixture components. Our algorithm gives a risk bound that trades off between prediction accuracy and model sparsity without imposing stringent assumptions on the input/output distribution, and can be easily adapted to the case of non-linear functions. In our numerical experiments on mixtures of linear as well as nonlinear regressions, the proposed method yields high-quality solutions in a wider range of settings than existing approaches.
A Dual Framework for Low-rank Tensor Completion
Authors: Pratik Kumar Jawanpuria, Bamdev Mishra Madhav Nimishakavi
Published in: Advances in Neural Information Processing Systems 31  (NeurIPS 2018) (Main Conference Track), 2018

Abstract: One of the popular approaches for low-rank tensor completion is to use the latent trace norm regularization. However, most existing works in this direction learn a sparse combination of tensors. In this work, we fill this gap by proposing a variant of the latent trace norm that helps in learning a non-sparse combination of tensors. We develop a dual framework for solving the low-rank tensor completion problem. We first show a novel characterization of the dual solution space with an interesting factorization of the optimal solution. Overall, the optimal solution is shown to lie on a Cartesian  product of Riemannian manifolds. Furthermore, we exploit the versatile Riemannian optimization framework for proposing computationally efficient trust region algorithm. The experiments illustrate the efficacy of the proposed algorithm on several real-world datasets across applications.
Predict Responsibly: Improving Fairness and Accuracy by Learning to Defer
Authors: Toni Pitassi, Richard Zemel David Madras
Published in: Advances in Neural Information Processing Systems 31  (NeurIPS 2018) (Main Conference Track), 2018

Abstract: In many machine learning applications, there are multiple decision-makers involved, both automated and human. The interaction between these agents often goes unaddressed in algorithmic development. In this work, we explore a simple version of this interaction with a two-stage framework containing an automated model and an external decision-maker. The model can choose to say PASS, and pass the decision downstream, as explored in rejection learning. We extend this concept by proposing "learning to defer", which generalizes rejection learning by considering the effect of other agents in the decision-making process. We propose a learning algorithm which accounts for potential biases held by external decision-makers in a system. Experiments demonstrate that learning to defer can make systems not only more accurate but also less biased. Even when working with inconsistent or biased users, we show that deferring models still greatly improve the accuracy and/or fairness of the entire system.
Enhancing the Accuracy and Fairness of Human Decision Making
Authors: Adish Singla, Manuel Gomez Rodriguez Isabel Valera
Published in: Advances in Neural Information Processing Systems 31  (NeurIPS 2018) (Main Conference Track), 2018

Abstract: Societies often rely on human experts to take a wide variety of decisions affecting their members, from jail-or-release decisions taken by judges and stop-and-frisk decisions taken by police officers to accept-or-reject decisions taken  by academics. In this context, each decision is taken by an expert who is typically chosen uniformly at random from a pool of experts. However, these decisions may be imperfect due to limited experience, implicit biases, or faulty probabilistic reasoning. Can we improve the accuracy and fairness of the overall decision making process by optimizing the assignment between experts and decisions?
In this paper, we address the above problem from the perspective of sequential decision making and show that, for different fairness notions from the literature, it reduces to a sequence of (constrained) weighted bipartite matchings, which can be solved efficiently using algorithms with approximation guarantees. Moreover, these algorithms also benefit from posterior sampling to actively trade off exploitation---selecting expert assignments which lead to accurate and fair decisions---and exploration---selecting expert assignments to learn about the experts' preferences and biases. We demonstrate the effectiveness of our algorithms on both synthetic and real-world data and show that they can significantly improve both the accuracy and fairness of the decisions taken by pools of experts.
Computing Higher Order Derivatives of Matrix and Tensor Expressions
Authors: Matthias Mitterreiter, Joachim Giesen Soeren Laue
Published in: Advances in Neural Information Processing Systems 31  (NeurIPS 2018) (Main Conference Track), 2018

Abstract: Optimization is an integral part of most machine learning systems and most numerical optimization schemes rely on the computation of derivatives. Therefore, frameworks for computing derivatives are an active area of machine learning research. Surprisingly, as of yet, no existing framework is capable of computing higher order matrix and tensor derivatives directly.  Here, we close this fundamental gap and present an algorithmic framework for computing matrix and tensor derivatives that extends seamlessly to higher order derivatives. The framework can be used for symbolic as well as for forward and reverse mode automatic differentiation. Experiments show a speedup between one and four orders of magnitude over state-of-the-art frameworks when evaluating higher order derivatives.
Efficient online algorithms for fast-rate regret bounds under sparsity
Authors: Olivier Wintenberger Pierre Gaillard
Published in: Advances in Neural Information Processing Systems 31  (NeurIPS 2018) (Main Conference Track), 2018

Abstract: We consider the problem of online convex optimization in two different settings: arbitrary and  i.i.d. sequence of convex loss functions. In both settings, we provide efficient algorithms whose cumulative excess risks are controlled with fast-rate sparse bounds. 
First, the excess risks bounds depend on the sparsity of the objective rather than on the dimension of the parameters space. Second, their rates are faster than the slow-rate $1/\sqrt{T}$ under additional convexity assumptions on the loss functions. In the adversarial setting, we develop an algorithm BOA+ whose cumulative excess risks is controlled by several bounds with different trade-offs between sparsity and rate for strongly convex loss functions. In the i.i.d. setting under the Łojasiewicz's assumption, we establish new risk bounds that are sparse with a rate adaptive to the convexity of the risk (ranging from a rate $1/\sqrt{T}$ for general convex risk to $1/T$ for strongly convex risk). These results generalize previous works on sparse online learning under weak assumptions on the risk.
Human-in-the-Loop Interpretability Prior
Authors: Andrew Ross, Samuel J Gershman, Been Kim, Finale Doshi-Velez Isaac Lage
Published in: Advances in Neural Information Processing Systems 31  (NeurIPS 2018) (Main Conference Track), 2018

Abstract: We often desire our models to be interpretable as well as accurate. Prior work on optimizing models for interpretability has relied on easy-to-quantify proxies for interpretability, such as sparsity or the number of operations required.  In this work, we optimize for interpretability by directly including humans in the optimization loop.  We develop an algorithm that minimizes the number of user studies to find models that are both predictive and interpretable and demonstrate our approach on several data sets.  Our human subjects results show trends towards different proxy notions of interpretability on different datasets, which suggests that different proxies are preferred on different tasks.