mtybilly/Instruct2DS huggingface dataset:
A Polynomial Time Algorithm for Log-Concave Maximum Likelihood via Locally Exponential Families
Authors: Ilias Diakonikolas, Alistair Stewart, Anastasios Sidiropoulos, Gregory Valiant Brian Axelrod
Published in: Advances in Neural Information Processing Systems 32  (NeurIPS 2019) (Main Conference Track), 2019

Abstract: We consider the problem of computing the maximum likelihood multivariate log-concave distribution for a set of points.  Specifically, we present an algorithm which, given $n$ points in $\mathbb{R}^d$ and an accuracy parameter $\eps>0$, runs in time $\poly(n,d,1/\eps),$ and returns a log-concave distribution which, with high probability, has the property that the likelihood of the $n$ points under the returned distribution is at most an additive $\eps$ less than the maximum likelihood that could be achieved via any log-concave distribution.  This is the first computationally efficient (polynomial time) algorithm for this fundamental and practically important task.  Our algorithm rests on a novel connection with exponential families: the maximum likelihood log-concave distribution belongs to a class of structured distributions which, while not an exponential family, ``locally'' possesses key properties of exponential families.  This connection then allows the problem of computing the log-concave maximum likelihood distribution to be formulated as a convex optimization problem, and solved via an approximate first-order method.  Efficiently approximating the (sub) gradients of the objective function of this optimization problem is quite delicate, and is the main technical challenge in this work.
Towards Automatic Concept-based Explanations
Authors: James Wexler, James Y Zou, Been Kim Amirata Ghorbani
Published in: Advances in Neural Information Processing Systems 32  (NeurIPS 2019) (Main Conference Track), 2019

Abstract: Interpretability has become an important topic of research as more machine learning (ML) models are deployed and widely used to make important decisions. 
    Most of the current explanation methods provide explanations through feature importance scores, which identify features that are important for each individual input. However, how to systematically summarize and interpret such per sample feature importance scores itself is challenging. In this work, we propose principles and desiderata for \emph{concept} based explanation, which goes beyond per-sample features to identify higher level human-understandable concepts that apply across the entire dataset. We develop a new algorithm, ACE, to automatically extract visual concepts. Our systematic experiments demonstrate that \alg discovers concepts that are human-meaningful, coherent and important for the neural network's predictions.
Brain-Like Object Recognition with High-Performing Shallow Recurrent ANNs
Authors: Martin Schrimpf, Kohitij Kar, Rishi Rajalingham, Ha Hong, Najib Majaj, Elias Issa, Pouya Bashivan, Jonathan Prescott-Roy, Kailyn Schmidt, Aran Nayebi, Daniel Bear, Daniel L Yamins, James J DiCarlo Jonas Kubilius
Published in: Advances in Neural Information Processing Systems 32  (NeurIPS 2019) (Main Conference Track), 2019

Abstract: Deep convolutional artificial neural networks (ANNs) are the leading class of candidate models of the mechanisms of visual processing in the primate ventral stream. While initially inspired by brain anatomy, over the past years, these ANNs have evolved from a simple eight-layer architecture in AlexNet to extremely deep and branching architectures, demonstrating increasingly better object categorization performance, yet bringing into question how brain-like they still are. In particular, typical deep models from the machine learning community are often hard to map onto the brain's anatomy due to their vast number of layers and missing biologically-important connections, such as recurrence. Here we demonstrate that better anatomical alignment to the brain and high performance on machine learning as well as neuroscience measures do not have to be in contradiction. We developed CORnet-S, a shallow ANN with four anatomically mapped areas and recurrent connectivity, guided by Brain-Score, a new large-scale composite of neural and behavioral benchmarks for quantifying the functional fidelity of models of the primate ventral visual stream. Despite being significantly shallower than most models, CORnet-S is the top model on Brain-Score and outperforms similarly compact models on ImageNet. Moreover, our extensive analyses of CORnet-S circuitry variants reveal that recurrence is the main predictive factor of both Brain-Score and ImageNet top-1 performance. Finally, we report that the temporal evolution of the CORnet-S "IT" neural population resembles the actual monkey IT population dynamics. Taken together, these results establish CORnet-S, a compact, recurrent ANN, as the current best model of the primate ventral visual stream.
Defending Neural Backdoors via Generative Distribution Modeling
Authors: Yukun Yang, Hai Li Ximing Qiao
Published in: Advances in Neural Information Processing Systems 32  (NeurIPS 2019) (Main Conference Track), 2019

Abstract: Neural backdoor attack is emerging as a severe security threat to deep learning, while the capability of existing defense methods is limited, especially for complex backdoor triggers. In the work, we explore the space formed by the pixel values of all possible backdoor triggers. An original trigger used by an attacker to build the backdoored model represents only a point in the space. It then will be generalized into a distribution of valid triggers, all of which can influence the backdoored model. Thus, previous methods that model only one point of the trigger distribution is not sufficient. Getting the entire trigger distribution, e.g., via generative modeling, is a key of effective defense. However, existing generative modeling techniques for image generation are not applicable to the backdoor scenario as the trigger distribution is completely unknown. In this work, we propose max-entropy staircase approximator (MESA) for high-dimensional sampling-free generative modeling and use it to recover the trigger distribution. We also develop a defense technique to remove the triggers from the backdoored model. Our experiments on Cifar10/100 dataset demonstrate the effectiveness of MESA in modeling the trigger distribution and the robustness of the proposed defense method.
Correlation clustering with local objectives
Authors: Konstantin Makarychev, Timothy Zhou Sanchit Kalhan
Published in: Advances in Neural Information Processing Systems 32  (NeurIPS 2019) (Main Conference Track), 2019

Abstract: Correlation Clustering is a powerful graph partitioning model that aims to cluster items based on the notion of similarity between items. An instance of the Correlation Clustering problem consists of a graph G (not necessarily complete) whose edges are labeled by a binary classifier as
similar and dissimilar. Classically, we are tasked with producing a clustering that minimizes the number of disagreements: an edge is in disagreement if it is a similar edge and is present across clusters or if it is a dissimilar edge and is present within a cluster. Define the disagreements vector to be an n dimensional vector indexed by the vertices, where the v-th index is the number of disagreements at vertex v.
Recently, Puleo and Milenkovic (ICML '16) initiated the study of the Correlation Clustering framework in which the objectives were more general functions of the disagreements vector. In this paper, we study algorithms for minimizing \ellq norms (q >= 1) of the disagreements vector for both arbitrary and complete graphs. We present the first known algorithm for minimizing the \ellq norm of the disagreements vector on arbitrary graphs and also provide an improved algorithm for minimizing the \ell_q norm (q >= 1) of the disagreements vector on complete graphs. We also study an alternate cluster-wise local objective introduced by Ahmadi, Khuller and Saha (IPCO '19), which aims to minimize the maximum number of disagreements associated with a cluster. We present an improved (2 + \eps) approximation algorithm for this objective.
Logarithmic Regret for Online Control
Authors: Elad Hazan, Karan Singh Naman Agarwal
Published in: Advances in Neural Information Processing Systems 32  (NeurIPS 2019) (Main Conference Track), 2019

Abstract: We study optimal regret bounds for control in linear dynamical systems under adversarially changing strongly convex cost functions, given the knowledge of transition dynamics. This includes several well studied and influential frameworks such as the Kalman filter and the linear quadratic regulator. State of the art methods achieve regret which scales as T^0.5, where T is the time horizon. 
We show that the optimal regret in this fundamental setting can be significantly smaller, scaling as polylog(T). This regret bound is achieved by two different efficient iterative methods, online gradient descent and online natural gradient.
Offline Contextual Bayesian Optimization
Authors: Youngseog Chung, Willie Neiswanger, Kirthevasan Kandasamy, Andrew Oakleigh Nelson, Mark Boyer, Egemen Kolemen, Jeff Schneider Ian Char
Published in: Advances in Neural Information Processing Systems 32  (NeurIPS 2019) (Main Conference Track), 2019

Abstract: In black-box optimization, an agent repeatedly chooses a configuration to test, so as to find an optimal configuration.
In many practical problems of interest, one would like to optimize several systems, or tasks'', simultaneously; however, in most of these scenarios the current task is determined by nature. In this work, we explore theoffline'' case in which one is able to bypass nature and choose the next task to evaluate (e.g. via a simulator). Because some tasks may be easier to optimize and others may be more critical, it is crucial to leverage algorithms that not only consider which configurations to try next, but also which tasks to make evaluations for. In this work, we describe a theoretically grounded Bayesian optimization method to tackle this problem. We also demonstrate that if the model of the reward structure does a poor job of capturing variation in difficulty between tasks, then algorithms that actively pick tasks for evaluation may end up doing more harm than good. Following this, we show how our approach can be used for real world applications in science and engineering, including optimizing tokamak controls for nuclear fusion.
Transfer Anomaly Detection by Inferring Latent Domain Representations
Authors: Tomoharu Iwata, Yasuhiro Fujiwara Atsutoshi Kumagai
Published in: Advances in Neural Information Processing Systems 32  (NeurIPS 2019) (Main Conference Track), 2019

Abstract: We propose a method to improve the anomaly detection performance on target
domains by transferring knowledge on related domains. Although anomaly labels
are valuable to learn anomaly detectors, they are difficult to obtain due to their rarity.
To alleviate this problem, existing methods use anomalous and normal instances
in the related domains as well as target normal instances. These methods require
training on each target domain. However, this requirement can be problematic
in some situations due to the high computational cost of training. The proposed
method can infer the anomaly detectors for target domains without re-training by
introducing the concept of latent domain vectors, which are latent representations
of the domains and are used for inferring the anomaly detectors. The latent
domain vector for each domain is inferred from the set of normal instances in the
domain. The anomaly score function for each domain is modeled on the basis of
autoencoders, and its domain-specific property is controlled by the latent domain
vector. The anomaly score function for each domain is trained so that the scores of
normal instances become low and the scores of anomalies become higher than those
of the normal instances, while considering the uncertainty of the latent domain
vectors. When target normal instances can be used during training, the proposed
method can also use them for training in a unified framework. The effectiveness
of the proposed method is demonstrated through experiments using one synthetic
and four real-world datasets. Especially, the proposed method without re-training
outperforms existing methods with target specific training.
Uncertainty on Asynchronous Time Event Prediction
Authors: Bertrand Charpentier, Stephan Günnemann Marin Biloš
Published in: Advances in Neural Information Processing Systems 32  (NeurIPS 2019) (Main Conference Track), 2019

Abstract: Asynchronous event sequences are the basis of many applications throughout different industries. In this work, we tackle the task of predicting the next event (given a history), and how this prediction changes with the passage of time. Since at some time points (e.g. predictions far into the future) we might not be able to predict anything with confidence, capturing uncertainty in the predictions  is crucial. We present two new architectures, WGP-LN and FD-Dir, modelling the evolution of the distribution on the probability simplex with time-dependent logistic normal and Dirichlet distributions. In both cases, the combination of RNNs with either Gaussian process or function decomposition allows to express rich temporal evolution of the distribution parameters, and naturally captures uncertainty. Experiments on class prediction, time prediction and anomaly detection demonstrate the high performances of our models on various datasets compared to other approaches.
Breaking the Glass Ceiling for Embedding-Based Classifiers for Large Output Spaces
Authors: Ali Mousavi, Xiang Wu, Daniel N Holtmann-Rice, Satyen Kale, Sashank Reddi, Sanjiv Kumar Chuan Guo
Published in: Advances in Neural Information Processing Systems 32  (NeurIPS 2019) (Main Conference Track), 2019

Abstract: In extreme classification settings, embedding-based neural network models are currently not competitive with sparse linear and tree-based methods in terms of accuracy. Most prior works attribute this poor performance to the low-dimensional bottleneck in embedding-based methods. In this paper, we demonstrate that theoretically there is no limitation to using low-dimensional embedding-based methods, and provide experimental evidence that overfitting is the root cause of the poor performance of embedding-based methods. These findings motivate us to investigate novel data augmentation and regularization techniques to mitigate overfitting. To this end, we propose GLaS, a new regularizer for embedding-based neural network approaches. It is a natural generalization from the graph Laplacian and spread-out regularizers, and empirically it addresses the drawback of each regularizer alone when applied to the extreme classification setup. With the proposed techniques, we attain or improve upon the state-of-the-art on most widely tested public extreme classification datasets with hundreds of thousands of labels.
Faster width-dependent algorithm for mixed packing and covering LPs
Authors: Saurabh Sawlani, Di Wang Digvijay Boob
Published in: Advances in Neural Information Processing Systems 32  (NeurIPS 2019) (Main Conference Track), 2019

Abstract: In this paper, we give a faster width-dependent algorithm for mixed packing-covering LPs. Mixed packing-covering LPs are fundamental to combinatorial optimization in computer science and operations research. Our algorithm finds a $1+\eps$ approximate solution in time $O(Nw/ \varepsilon)$, where $N$ is number of nonzero entries in the constraint matrix, and $w$ is the maximum number of nonzeros in any constraint. This algorithm is faster than Nesterov's smoothing algorithm which requires $O(N\sqrt{n}w/ \eps)$ time, where $n$ is the dimension of the problem. Our work utilizes the framework of area convexity introduced in [Sherman-FOCS'17] to obtain the best dependence on $\varepsilon$ while breaking the infamous $\ell_{\infty}$ barrier to eliminate the factor of $\sqrt{n}$. The current best width-independent algorithm for this problem runs in time $O(N/\eps^2)$ [Young-arXiv-14] and hence has worse running time dependence on $\varepsilon$. Many real life instances of mixed packing-covering problems exhibit small width and for such cases, our algorithm can report higher precision results when compared to width-independent algorithms. As a special case of our result, we report a $1+\varepsilon$ approximation algorithm for the densest subgraph problem which runs in time $O(md/ \varepsilon)$, where $m$ is the number of edges in the graph and $d$ is the maximum graph degree.
Hierarchical Decision Making by Generating and Following Natural Language Instructions
Authors: Denis Yarats, Qucheng Gong, Yuandong Tian, Mike Lewis Hengyuan Hu
Published in: Advances in Neural Information Processing Systems 32  (NeurIPS 2019) (Main Conference Track), 2019

Abstract: We explore using latent natural language instructions as an expressive and compositional representation of complex actions for hierarchical decision making.
Rather than directly selecting micro-actions, our agent first generates a latent plan in natural language, which is then executed by a separate model. We introduce a challenging real-time strategy game environment in which the actions of a large number of units must be coordinated across long time scales. We gather a dataset of 76 thousand pairs of instructions and executions from human play, and train instructor and executor models. Experiments show that models using natural language as a latent variable significantly outperform models that directly imitate human actions. The compositional structure of language proves crucial to its effectiveness for action representation. We also release our code, models and data.
Structured Prediction with Projection Oracles
Authors: Mathieu Blondel
Published in: Advances in Neural Information Processing Systems 32  (NeurIPS 2019) (Main Conference Track), 2019

Abstract: We propose in this paper a general framework for deriving loss functions for structured prediction.  In our framework, the user chooses a convex set including the output space and provides an oracle for projecting onto that set.  Given that oracle, our framework automatically generates a corresponding convex and smooth loss function.  As we show, adding a projection as output layer provably makes the loss smaller.  We identify the marginal polytope, the output space's convex hull, as the best convex set on which to project.  However, because the projection onto the marginal polytope can sometimes be expensive to compute, we allow to use any convex superset instead, with potentially cheaper-to-compute projection.  Since efficient projection algorithms are available for numerous convex sets, this allows us to construct loss functions for a variety of tasks.  On the theoretical side, when combined with calibrated decoding, we prove that our loss functions can be used as a consistent surrogate for a (potentially non-convex) target loss function of interest.  We demonstrate our losses on label ranking, ordinal regression and multilabel classification, confirming the improved accuracy enabled by projections.
Sobolev Independence Criterion
Authors: Tom Sercu, Mattia Rigotti, Inkit Padhi, Cicero Nogueira dos Santos Youssef Mroueh
Published in: Advances in Neural Information Processing Systems 32  (NeurIPS 2019) (Main Conference Track), 2019

Abstract: We propose the Sobolev Independence Criterion (SIC), an interpretable dependency measure between a high dimensional random variable X and a response variable Y. SIC decomposes to the sum of feature importance scores and hence can be used for nonlinear feature selection. SIC can be seen as a gradient regularized Integral Probability Metric (IPM) between the joint distribution of the two random variables and the product of their marginals. We use sparsity inducing gradient penalties to promote input sparsity of the critic of the IPM. In the kernel version we show that SIC can be cast as a convex optimization problem by introducing auxiliary variables that play an important role in feature selection as they are normalized feature importance scores. We then present a neural version of SIC where the critic is parameterized as a homogeneous neural network, improving its representation power as well as its interpretability. We conduct experiments validating SIC for feature selection in synthetic and real-world experiments. We show that SIC enables reliable and interpretable discoveries, when used in conjunction with the holdout randomization test and knockoffs to control the False Discovery Rate. Code is available at http://github.com/ibm/sic.
Accelerating Rescaled Gradient Descent: Fast Optimization of Smooth Functions
Authors: Lester Mackey, Andre Wibisono Ashia C Wilson
Published in: Advances in Neural Information Processing Systems 32  (NeurIPS 2019) (Main Conference Track), 2019

Abstract: We present a family of algorithms, called descent algorithms, for optimizing convex and non-convex functions. We also introduce a new first-order algorithm, called rescaled gradient descent (RGD), and show that RGD achieves a faster convergence rate than gradient descent provided the function is strongly smooth  - a natural generalization of the standard smoothness assumption on the objective function. When the objective function is convex, we present two frameworks for “accelerating” descent methods, one in the style of Nesterov and the other in the style of Monteiro and Svaiter. Rescaled gradient descent can be accelerated under the same strong smoothness assumption using both frameworks. We provide several examples of strongly smooth loss functions in machine learning and numerical experiments that verify our theoretical findings.
Minimax Optimal Estimation of Approximate Differential Privacy on Neighboring Databases
Authors: Sewoong Oh Xiyang Liu
Published in: Advances in Neural Information Processing Systems 32  (NeurIPS 2019) (Main Conference Track), 2019

Abstract: Differential privacy has become a widely accepted notion of privacy, leading to the introduction and deployment of numerous privatization mechanisms. However, ensuring the privacy guarantee is an error-prone process, both in designing mechanisms and in implementing those mechanisms. Both types of errors will be greatly reduced, if we have a data-driven approach to verify privacy guarantees, from a black-box access to a mechanism. We pose it as a property estimation problem, and study the fundamental trade-offs involved in the accuracy in estimated privacy guarantees and the number of samples required. We introduce a novel estimator that uses polynomial approximation of a carefully chosen degree to optimally trade-off bias and variance. With n samples, we show that this estimator achieves performance of a straightforward plug-in estimator with n*log(n) samples, a phenomenon referred to as effective sample size amplification. The minimax optimality of the proposed estimator is proved by comparing it to a matching fundamental lower bound.
Reconciling meta-learning and continual learning with online mixtures of tasks
Authors: Erin Grant, Tom Griffiths, Katherine A. Heller Ghassen Jerfel
Published in: Advances in Neural Information Processing Systems 32  (NeurIPS 2019) (Main Conference Track), 2019

Abstract: Learning-to-learn or meta-learning leverages data-driven inductive bias to increase the efficiency of learning on a novel task. This approach encounters difficulty when transfer is not advantageous, for instance, when tasks are considerably dissimilar or change over time. We use the connection between gradient-based meta-learning and hierarchical Bayes to propose a Dirichlet process mixture of hierarchical Bayesian models over the parameters of an arbitrary parametric model such as a neural network. In contrast to consolidating inductive biases into a single set of hyperparameters, our approach of task-dependent hyperparameter selection better handles latent distribution shift, as demonstrated on a set of evolving, image-based, few-shot learning benchmarks.
Neural Spline Flows
Authors: Artur Bekasov, Iain Murray, George Papamakarios Conor Durkan
Published in: Advances in Neural Information Processing Systems 32  (NeurIPS 2019) (Main Conference Track), 2019

Abstract: A normalizing flow models a complex probability density as an invertible transformation of a simple base density. Flows based on either coupling or autoregressive transforms both offer exact density evaluation and sampling, but rely on the parameterization of an easily invertible elementwise transformation, whose choice determines the flexibility of these models. Building upon recent work, we propose a fully-differentiable module based on monotonic rational-quadratic splines, which enhances the flexibility of both coupling and autoregressive transforms while retaining analytic invertibility. We demonstrate that neural spline flows improve density estimation, variational inference, and generative modeling of images.
Embedding Symbolic Knowledge into Deep Networks
Authors: Ziwei Xu, Mohan S Kankanhalli, Kuldeep S Meel, Harold Soh Yaqi Xie
Published in: Advances in Neural Information Processing Systems 32  (NeurIPS 2019) (Main Conference Track), 2019

Abstract: In this work, we aim to leverage prior symbolic knowledge to improve the performance of deep models. We propose a graph embedding network that projects propositional formulae (and assignments) onto a manifold via an augmented Graph Convolutional Network (GCN). To generate semantically-faithful embeddings, we develop techniques to recognize node heterogeneity, and semantic regularization that incorporate structural constraints into the embedding. Experiments show that our approach improves the performance of models trained to perform entailment checking and visual relation prediction. Interestingly, we observe a connection between the tractability of the propositional theory representation and the ease of embedding. Future exploration of this connection may elucidate the relationship between knowledge compilation and vector representation learning.
Partitioning Structure Learning for Segmented Linear Regression Trees
Authors: Song Xi Chen Xiangyu Zheng
Published in: Advances in Neural Information Processing Systems 32  (NeurIPS 2019) (Main Conference Track), 2019

Abstract: This paper proposes a partitioning structure learning method for segmented linear regression trees (SLRT), which assigns linear predictors over the terminal nodes. The recursive partitioning process is driven by an adaptive split selection algorithm that maximizes, at each node, a criterion function based on a conditional Kendall’s τ statistic that measures the rank dependence between the regressors and the fit- ted linear residuals. Theoretical analysis shows that the split selection algorithm permits consistent identification and estimation of the unknown segments. A suffi- ciently large tree is induced by applying the split selection algorithm recursively. Then the minimal cost-complexity tree pruning procedure is applied to attain the right-sized tree, that ensures (i) the nested structure of pruned subtrees and (ii) consistent estimation to the number of segments. Implanting the SLRT as the built-in base predictor, we obtain the ensemble predictors by random forests (RF) and the proposed weighted random forests (WRF). The practical performance of the SLRT and its ensemble versions are evaluated via numerical simulations and empirical studies. The latter shows their advantageous predictive performance over a set of state-of-the-art tree-based models on well-studied public datasets.
Sparse Variational Inference: Bayesian Coresets from Scratch
Authors: Boyan Beronov Trevor Campbell
Published in: Advances in Neural Information Processing Systems 32  (NeurIPS 2019) (Main Conference Track), 2019

Abstract: The proliferation of automated inference algorithms in Bayesian statistics has provided practitioners newfound access to fast, reproducible data analysis and powerful statistical models.  Designing automated methods that are also both computationally scalable and theoretically sound, however, remains a significant challenge.  Recent work on Bayesian coresets takes the approach of compressing the dataset before running a standard inference algorithm, providing both scalability and guarantees on posterior approximation error.  But the automation of past coreset methods is limited because they depend on the availability of a reasonable coarse posterior approximation, which is difficult to specify in practice.  In the present work we remove this requirement by formulating coreset construction as sparsity-constrained variational inference within an exponential family.  This perspective leads to a novel construction via greedy optimization, and also provides a unifying information-geometric view of present and past methods.  The proposed Riemannian coreset construction algorithm is fully automated, requiring no problem-specific inputs aside from the probabilistic model and dataset.  In addition to being significantly easier to use than past methods, experiments demonstrate that past coreset constructions are fundamentally limited by the fixed coarse posterior approximation; in contrast, the proposed algorithm is able to continually improve the coreset, providing state-of-the-art Bayesian dataset summarization with orders-of-magnitude reduction in KL divergence to the exact posterior.
Policy Evaluation with Latent Confounders via Optimal Balance
Authors: Nathan Kallus Andrew Bennett
Published in: Advances in Neural Information Processing Systems 32  (NeurIPS 2019) (Main Conference Track), 2019

Abstract: Evaluating novel contextual bandit policies using logged data is crucial in applications where exploration is costly, such as medicine. But it usually relies on the assumption of no unobserved confounders, which is bound to fail in practice. We study the question of policy evaluation when we instead have proxies for the latent confounders and develop an importance weighting method that avoids fitting a latent outcome regression model. Surprisingly, we show that there exist no single set of weights that give unbiased evaluation regardless of outcome model, unlike the case with no unobserved confounders where density ratios are sufficient. Instead, we propose an adversarial objective and weights that minimize it, ensuring sufficient balance in the latent confounders regardless of outcome model. We develop theory characterizing the consistency of our method and tractable algorithms for it. Empirical results validate the power of our method when confounders are latent.
Dancing to Music
Authors: Xiaodong Yang, Ming-Yu Liu, Ting-Chun Wang, Yu-Ding Lu, Ming-Hsuan Yang, Jan Kautz Hsin-Ying Lee
Published in: Advances in Neural Information Processing Systems 32  (NeurIPS 2019) (Main Conference Track), 2019

Abstract: Dancing to music is an instinctive move by humans. Learning to model the music-to-dance generation process is, however, a challenging problem. It requires significant efforts to measure the correlation between music and dance as one needs to simultaneously consider multiple aspects, such as style and beat of both music and dance. Additionally, dance is inherently multimodal and various following movements of a pose at any moment are equally likely. In this paper, we propose a synthesis-by-analysis learning framework to generate dance from music. In the top-down analysis phase, we decompose a dance into a series of basic dance units, through which the model learns how to move. In the bottom-up synthesis phase, the model learns how to compose a dance by combining multiple basic dancing movements seamlessly according to input music. Experimental qualitative and quantitative results demonstrate that the proposed method can synthesize realistic, diverse, style-consistent, and beat-matching dances from music.
Learning Hierarchical Priors in VAEs
Authors: Nutan Chen, Richard Kurle, Botond Cseke, Patrick van der Smagt Alexej Klushyn
Published in: Advances in Neural Information Processing Systems 32  (NeurIPS 2019) (Main Conference Track), 2019

Abstract: We propose to learn a hierarchical prior in the context of variational autoencoders to avoid the over-regularisation resulting from a standard normal prior distribution. To incentivise an informative latent representation of the data, we formulate the learning problem as a constrained optimisation problem by extending the Taming VAEs framework to two-level hierarchical models. We introduce a graph-based interpolation method, which shows that the topology of the learned latent representation corresponds to the topology of the data manifold---and present several examples, where desired properties of latent representation such as smoothness and simple explanatory factors are learned by the prior.
Stochastic Runge-Kutta Accelerates Langevin Monte Carlo and Beyond
Authors: Yi Wu, Lester Mackey, Murat A Erdogdu Xuechen Li
Published in: Advances in Neural Information Processing Systems 32  (NeurIPS 2019) (Main Conference Track), 2019

Abstract: Sampling with Markov chain Monte Carlo methods typically amounts to discretizing some continuous-time dynamics with numerical integration. In this paper, we establish the convergence rate of sampling algorithms obtained by discretizing smooth It\^o diffusions exhibiting fast $2$-Wasserstein contraction, based on local deviation properties of the integration scheme. In particular, we study a sampling algorithm constructed by discretizing the overdamped Langevin diffusion with the method of stochastic Runge-Kutta. For strongly convex potentials that are smooth up to a certain order, its iterates 
converge to the target distribution in $2$-Wasserstein distance in $\tilde{\mathcal{O}}(d\epsilon^{-2/3})$ iterations. This improves upon the best-known rate for strongly log-concave sampling based on the overdamped Langevin equation using only the gradient oracle without adjustment. Additionally, we extend our analysis of stochastic Runge-Kutta methods to uniformly dissipative diffusions with possibly non-convex potentials and
show they achieve better rates compared to the Euler-Maruyama scheme on the dependence on tolerance $\epsilon$. Numerical studies show that these algorithms lead to better stability and lower asymptotic errors.
From voxels to pixels and back: Self-supervision in natural-image reconstruction from fMRI
Authors: Guy Gaziv, Assaf Hoogi, Francesca Strappini, Tal Golan, Michal Irani Roman Beliy
Published in: Advances in Neural Information Processing Systems 32  (NeurIPS 2019) (Main Conference Track), 2019

Abstract: Reconstructing observed images from fMRI brain recordings is challenging. Unfortunately, acquiring sufficient ''labeled'' pairs of {Image, fMRI} (i.e., images with their corresponding fMRI responses) to span the huge space of natural images is prohibitive for many reasons. We present a novel approach which, in addition to the scarce labeled data (training pairs), allows to train fMRI-to-image reconstruction networks also on "unlabeled" data (i.e., images without fMRI recording, and fMRI recording without images). The proposed model utilizes both an Encoder network (image-to-fMRI) and a Decoder network (fMRI-to-image). Concatenating these two networks back-to-back (Encoder-Decoder & Decoder-Encoder) allows augmenting the training data with both types of unlabeled data. Importantly, it allows training on the unlabeled test-fMRI data. This self-supervision adapts the reconstruction network to the new input test-data, despite its deviation from the statistics of the scarce training data.
Direct Estimation of Differential Functional Graphical Models
Authors: Y. Samuel Wang, Mladen Kolar Boxin Zhao
Published in: Advances in Neural Information Processing Systems 32  (NeurIPS 2019) (Main Conference Track), 2019

Abstract: We consider the problem of estimating the difference between two functional undirected graphical models with shared structures. In many applications, data are naturally regarded as high-dimensional random function vectors rather than multivariate scalars. For example, electroencephalography (EEG) data are more appropriately treated as functions of time. In these problems, not only can the number of functions measured per sample be large, but each function is itself an infinite dimensional object, making estimation of model parameters challenging. We develop a method that directly estimates the difference of graphs, avoiding separate estimation of each graph, and show it is consistent in certain high-dimensional settings. We illustrate finite sample properties of our method through simulation studies. Finally, we apply our method to EEG data to uncover differences in functional brain connectivity between alcoholics and control subjects.
Backpropagation-Friendly Eigendecomposition
Authors: Zheng Dang, Yinlin Hu, Pascal Fua, Mathieu Salzmann Wei Wang
Published in: Advances in Neural Information Processing Systems 32  (NeurIPS 2019) (Main Conference Track), 2019

Abstract: Eigendecomposition (ED) is widely used in deep networks. However, the backpropagation of its results tends to be numerically unstable, whether using ED directly or approximating it with the Power Iteration method, particularly when dealing with large matrices. While this can be mitigated by partitioning the data in small and arbitrary groups, doing so has no theoretical basis and makes its impossible to exploit the power of ED to the full. In this paper, we introduce a numerically stable and differentiable approach to leveraging eigenvectors in deep networks. It can handle large matrices without requiring to split them. We demonstrate the better robustness of our approach over standard ED and PI for ZCA whitening, an alternative to batch normalization, and for PCA denoising, which we introduce as a new normalization strategy for deep networks, aiming to further denoise the network's features.
Reverse KL-Divergence Training of Prior Networks: Improved Uncertainty and Adversarial Robustness
Authors: Mark Gales Andrey Malinin
Published in: Advances in Neural Information Processing Systems 32  (NeurIPS 2019) (Main Conference Track), 2019

Abstract: Ensemble approaches for uncertainty estimation have recently been applied to the tasks of misclassification detection, out-of-distribution input detection and adversarial attack detection. Prior Networks have been proposed as an approach to efficiently emulate an ensemble of models for classification by parameterising a Dirichlet prior distribution over output distributions. These models have been shown to outperform alternative ensemble approaches, such as Monte-Carlo Dropout, on the task of out-of-distribution input detection. However, scaling Prior Networks to complex datasets with many classes is difficult using the training criteria originally proposed. This paper makes two contributions. First, we show that the appropriate training criterion for Prior Networks is the reverse KL-divergence between Dirichlet distributions. This addresses issues in the nature of the training data target distributions, enabling prior networks to be successfully trained on classification tasks with arbitrarily many classes, as well as improving out-of-distribution detection performance. Second, taking advantage of this new training criterion, this paper investigates using Prior Networks to detect adversarial attacks and proposes a generalized form of adversarial training. It is shown that the construction of successful adaptive whitebox attacks, which affect the prediction and evade detection, against Prior Networks trained on CIFAR-10 and CIFAR-100 using the proposed approach requires a greater amount of computational effort than against networks defended using standard adversarial training or MC-dropout.
Adversarial Fisher Vectors for Unsupervised Representation Learning
Authors: Walter Talbott, Carlos Guestrin, Joshua Susskind Shuangfei Zhai
Published in: Advances in Neural Information Processing Systems 32  (NeurIPS 2019) (Main Conference Track), 2019

Abstract: We examine Generative Adversarial Networks (GANs) through the lens of deep Energy Based Models (EBMs), with the goal of exploiting the density model that follows from this formulation. In contrast to a traditional view where the discriminator learns a constant function when reaching convergence, here we show that it can provide useful information for downstream tasks, e.g., feature extraction for classification. To be concrete, in the EBM formulation,  the discriminator learns an unnormalized density function (i.e., the negative energy term) that characterizes the data manifold. We propose to evaluate both the generator and the discriminator by deriving corresponding Fisher Score and Fisher Information from the EBM. We show that by assuming that the generated examples form an estimate of the learned density, both the Fisher Information and the normalized Fisher Vectors are easy to compute. We also show that we are able to derive a distance metric between examples and between sets of examples. We conduct experiments showing that the GAN-induced Fisher Vectors demonstrate competitive performance as unsupervised feature extractors for classification and perceptual similarity tasks. Code is available at \url{https://github.com/apple/ml-afv}.
Don't Blame the ELBO! A Linear VAE Perspective on Posterior Collapse
Authors: George Tucker, Roger B Grosse, Mohammad Norouzi James Lucas
Published in: Advances in Neural Information Processing Systems 32  (NeurIPS 2019) (Main Conference Track), 2019

Abstract: Posterior collapse in Variational Autoencoders (VAEs) with uninformative priors arises when the variational posterior distribution closely matches the prior for a subset of latent variables. This paper presents a simple and intuitive explanation for posterior collapse through the analysis of linear VAEs and their direct correspondence with Probabilistic PCA (pPCA). We explain how posterior collapse may occur in pPCA due to local maxima in the log marginal likelihood. Unexpectedly, we prove that the ELBO objective for the linear VAE does not introduce additional spurious local maxima relative to log marginal likelihood. We show further that training a linear VAE with exact variational inference recovers a uniquely identifiable global maximum corresponding to the principal component directions. Empirically, we find that our linear analysis is predictive even for high-capacity, non-linear VAEs and helps explain the relationship between the observation noise, local maxima, and posterior collapse in deep Gaussian VAEs.
Kernel-Based Approaches for Sequence Modeling: Connections to Neural Methods
Authors: Guoyin Wang, Yitong Li, Ricardo Henao, Lawrence Carin Kevin Liang
Published in: Advances in Neural Information Processing Systems 32  (NeurIPS 2019) (Main Conference Track), 2019

Abstract: We investigate time-dependent data analysis from the perspective of recurrent kernel machines, from which models with hidden units and gated memory cells arise naturally. By considering dynamic gating of the memory cell, a model closely related to the long short-term memory (LSTM) recurrent neural network is derived. Extending this setup to $n$-gram filters, the convolutional neural network (CNN), Gated CNN, and recurrent additive network (RAN) are also recovered as special cases. Our analysis provides a new perspective on the LSTM, while also extending it to $n$-gram convolutional filters. Experiments are performed on natural language processing tasks and on analysis of local field potentials (neuroscience). We demonstrate that the variants we derive from kernels perform on par or even better than traditional neural methods. For the neuroscience application, the new models demonstrate significant improvements relative to the prior state of the art.
Efficient Symmetric Norm Regression via Linear Sketching
Authors: Ruosong Wang, Lin Yang, Hongyang Zhang, Peilin Zhong Zhao Song
Published in: Advances in Neural Information Processing Systems 32  (NeurIPS 2019) (Main Conference Track), 2019

Abstract: We provide efficient algorithms for overconstrained linear regression problems with size $n \times d$ when the loss function is a symmetric norm (a norm invariant under sign-flips and coordinate-permutations). An important class of symmetric norms are Orlicz norms, where for a function  $G$ and a vector $y \in \mathbb{R}^n$, the corresponding Orlicz norm $\|y\|_G$ is defined as the unique value $\alpha$ such that $\sum_{i=1}^n G(|y_i|/\alpha) = 1$. When the loss function is an Orlicz norm, our algorithm produces a $(1 + \varepsilon)$-approximate solution for an arbitrarily small constant $\varepsilon > 0$ in input-sparsity time, improving over the previously best-known algorithm which produces a $d \cdot \polylog n$-approximate solution. When the loss function is a general symmetric norm, our algorithm produces a $\sqrt{d} \cdot \polylog n \cdot \mathrm{mmc}(\ell)$-approximate solution in input-sparsity time, where $\mathrm{mmc}(\ell)$ is a quantity related to the symmetric norm under consideration. To the best of our knowledge, this is the first input-sparsity time algorithm with provable guarantees for the general class of symmetric norm regression problem. Our results shed light on resolving the universal sketching problem for linear regression, and the techniques might be of independent interest to numerical linear algebra problems more broadly.
Dichotomize and Generalize: PAC-Bayesian Binary Activated Deep Neural Networks
Authors: Pascal Germain, Benjamin Guedj, Francois Laviolette Gaël Letarte
Published in: Advances in Neural Information Processing Systems 32  (NeurIPS 2019) (Main Conference Track), 2019

Abstract: We present a comprehensive study of multilayer neural networks with binary activation, relying on the PAC-Bayesian theory. Our contributions are twofold: (i) we develop an end-to-end framework to train a binary activated deep neural network, (ii) we provide nonvacuous PAC-Bayesian generalization bounds for binary activated deep neural networks. Our results are obtained by minimizing the expected loss of an architecture-dependent aggregation of binary activated deep neural networks. Our analysis inherently overcomes the fact that binary activation function is non-differentiable. The performance of our approach is assessed on a thorough numerical experiment protocol on real-life datasets.
Approximate Feature Collisions in Neural Nets
Authors: Tianhao Zhang, Jitendra Malik Ke Li
Published in: Advances in Neural Information Processing Systems 32  (NeurIPS 2019) (Main Conference Track), 2019

Abstract: Work on adversarial examples has shown that neural nets are surprisingly sensitive to adversarially chosen changes of small magnitude. In this paper, we show the opposite: neural nets could be surprisingly insensitive to adversarially chosen changes of large magnitude. We observe that this phenomenon can arise from the intrinsic properties of the ReLU activation function. As a result, two very different examples could share the same feature activation and therefore the same classification decision. We refer to this phenomenon as feature collision and the corresponding examples as colliding examples. We find that colliding examples are quite abundant: we empirically demonstrate the existence of polytopes of approximately colliding examples in the neighbourhood of practically any example.
Characterizing Bias in Classifiers using Generative Models
Authors: Shuang Ma, Yale Song, Ashish Kapoor Daniel McDuff
Published in: Advances in Neural Information Processing Systems 32  (NeurIPS 2019) (Main Conference Track), 2019

Abstract: Models that are learned from real-world data are often biased because the data used to train them is biased. This can propagate systemic human biases that exist and ultimately lead to inequitable treatment of people, especially minorities. To characterize bias in learned classifiers, existing approaches rely on human oracles labeling real-world examples to identify the "blind spots" of the classifiers; these are ultimately limited due to the human labor required and the finite nature of existing image examples. 
We propose a simulation-based approach for interrogating classifiers using generative adversarial models in a systematic manner. We incorporate a progressive conditional generative model for synthesizing photo-realistic facial images and Bayesian Optimization for an efficient interrogation of independent facial image classification systems. We show how this approach can be used to efficiently characterize racial and gender biases in commercial systems.