pwc-archive/papers-with-abstracts huggingface dataset:
Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networks
Authors: Yuan Cao, Quanquan Gu
Date: 2019-05-30 00:00:00
Proceeding: NeurIPS 2019 12
Tasks: Generalization Bounds

We study the training and generalization of deep neural networks (DNNs) in the over-parameterized regime, where the network width (i.e., number of hidden nodes per layer) is much larger than the number of training data points. We show that, the expected $0$-$1$ loss of a wide enough ReLU network trained with stochastic gradient descent (SGD) and random initialization can be bounded by the training loss of a random feature model induced by the network gradient at initialization, which we call a neural tangent random feature (NTRF) model. For data distributions that can be classified by NTRF model with sufficiently small error, our result yields a generalization error bound in the order of $\tilde{\mathcal{O}}(n^{-1/2})$ that is independent of the network width. Our result is more general and sharper than many existing generalization error bounds for over-parameterized neural networks. In addition, we establish a strong connection between our generalization error bound and the neural tangent kernel (NTK) proposed in recent work.
AssembleNet: Searching for Multi-Stream Neural Connectivity in Video Architectures
Authors: Michael S. Ryoo, AJ Piergiovanni, Mingxing Tan, Anelia Angelova
Date: 2019-05-30 00:00:00
Proceeding: ICLR 2020 1
Tasks: Action Classification, Action Recognition, Multimodal Activity Recognition, Optical Flow Estimation, Video Classification, Video Understanding

Learning to represent videos is a very challenging task both algorithmically and computationally. Standard video CNN architectures have been designed by directly extending architectures devised for image understanding to include the time dimension, using modules such as 3D convolutions, or by using two-stream design to capture both appearance and motion in videos. We interpret a video CNN as a collection of multi-stream convolutional blocks connected to each other, and propose the approach of automatically finding neural architectures with better connectivity and spatio-temporal interactions for video understanding. This is done by evolving a population of overly-connected architectures guided by connection weight learning. Architectures combining representations that abstract different input types (i.e., RGB and optical flow) at multiple temporal resolutions are searched for, allowing different types or sources of information to interact with each other. Our method, referred to as AssembleNet, outperforms prior approaches on public video datasets, in some cases by a great margin. We obtain 58.6% mAP on Charades and 34.27% accuracy on Moments-in-Time.
Near-Term Quantum-Classical Associative Adversarial Networks
Authors: Eric R. Anschuetz, Cristian Zanoci
Date: 2019-05-30 00:00:00
Tasks: Generative Adversarial Network

We introduce a new hybrid quantum-classical adversarial machine learning architecture called a quantum-classical associative adversarial network (QAAN). This architecture consists of a classical generative adversarial network with a small auxiliary quantum Boltzmann machine that is simultaneously trained on an intermediate layer of the discriminator of the generative network. We numerically study the performance of QAANs compared to their classical counterparts on the MNIST and CIFAR-10 data sets, and show that QAANs attain a higher quality of learning when evaluated using the Inception score and the Fr\'{e}chet Inception distance. As the QAAN architecture only relies on sampling simple local observables of a small quantum Boltzmann machine, this model is particularly amenable for implementation on the current and next generations of quantum devices.
Exploiting Uncertainty of Loss Landscape for Stochastic Optimization
Authors: Vineeth S. Bhaskara, Sneha Desai
Date: 2019-05-30 00:00:00
Tasks: Stochastic Optimization

We introduce novel variants of momentum by incorporating the variance of the stochastic loss function. The variance characterizes the confidence or uncertainty of the local features of the averaged loss surface across the i.i.d. subsets of the training data defined by the mini-batches. We show two applications of the gradient of the variance of the loss function. First, as a bias to the conventional momentum update to encourage conformity of the local features of the loss function (e.g. local minima) across mini-batches to improve generalization and the cumulative training progress made per epoch. Second, as an alternative direction for "exploration" in the parameter space, especially, for non-convex objectives, that exploits both the optimistic and pessimistic views of the loss function in the face of uncertainty. We also introduce a novel data-driven stochastic regularization technique through the parameter update rule that is model-agnostic and compatible with arbitrary architectures. We further establish connections to probability distributions over loss functions and the REINFORCE policy gradient update with baseline in RL. Finally, we incorporate the new variants of momentum proposed into Adam, and empirically show that our methods improve the rate of convergence of training based on our experiments on the MNIST and CIFAR-10 datasets.
Persistent homology detects curvature
Authors: Peter Bubenik, Michael Hull, Dhruv Patel, Benjamin Whittle
Date: 2019-05-30 00:00:00
Tasks: Topological Data Analysis

In topological data analysis, persistent homology is used to study the "shape of data". Persistent homology computations are completely characterized by a set of intervals called a bar code. It is often said that the long intervals represent the "topological signal" and the short intervals represent "noise". We give evidence to dispute this thesis, showing that the short intervals encode geometric information. Specifically, we prove that persistent homology detects the curvature of disks from which points have been sampled. We describe a general computational framework for solving inverse problems using the average persistence landscape, a continuous mapping from metric spaces with a probability measure to a Hilbert space. In the present application, the average persistence landscapes of points sampled from disks of constant curvature results in a path in this Hilbert space which may be learned using standard tools from statistical and machine learning.
Modeling Uncertainty by Learning a Hierarchy of Deep Neural Connections
Authors: Raanan Y. Rohekar, Yaniv Gurwicz, Shami Nisimov, Gal Novik
Date: 2019-05-30 00:00:00
Proceeding: NeurIPS 2019 12
Tasks: Out-of-Distribution Detection

Modeling uncertainty in deep neural networks, despite recent important advances, is still an open problem. Bayesian neural networks are a powerful solution, where the prior over network weights is a design choice, often a normal distribution or other distribution encouraging sparsity. However, this prior is agnostic to the generative process of the input data, which might lead to unwarranted generalization for out-of-distribution tested data. We suggest the presence of a confounder for the relation between the input data and the discriminative function given the target label. We propose an approach for modeling this confounder by sharing neural connectivity patterns between the generative and discriminative networks. This approach leads to a new deep architecture, where networks are sampled from the posterior of local causal structures, and coupled into a compact hierarchy. We demonstrate that sampling networks from this hierarchy, proportionally to their posterior, is efficient and enables estimating various types of uncertainties. Empirical evaluations of our method demonstrate significant improvement compared to state-of-the-art calibration and out-of-distribution detection methods.
Sinkhorn Barycenters with Free Support via Frank-Wolfe Algorithm
Authors: Giulia Luise, Saverio Salzo, Massimiliano Pontil, Carlo Ciliberto
Date: 2019-05-30 00:00:00
Proceeding: NeurIPS 2019 12

We present a novel algorithm to estimate the barycenter of arbitrary probability distributions with respect to the Sinkhorn divergence. Based on a Frank-Wolfe optimization strategy, our approach proceeds by populating the support of the barycenter incrementally, without requiring any pre-allocation. We consider discrete as well as continuous distributions, proving convergence rates of the proposed algorithm in both settings. Key elements of our analysis are a new result showing that the Sinkhorn divergence on compact domains has Lipschitz continuous gradient with respect to the Total Variation and a characterization of the sample complexity of Sinkhorn potentials. Experiments validate the effectiveness of our method in practice.
Graph Neural Tangent Kernel: Fusing Graph Neural Networks with Graph Kernels
Authors: Simon S. Du, Kangcheng Hou, Barnabás Póczos, Ruslan Salakhutdinov, Ruosong Wang, Keyulu Xu
Date: 2019-05-30 00:00:00
Proceeding: NeurIPS 2019 12
Tasks: Graph Classification

While graph kernels (GKs) are easy to train and enjoy provable theoretical guarantees, their practical performances are limited by their expressive power, as the kernel function often depends on hand-crafted combinatorial features of graphs. Compared to graph kernels, graph neural networks (GNNs) usually achieve better practical performance, as GNNs use multi-layer architectures and non-linear activation functions to extract high-order information of graphs as features. However, due to the large number of hyper-parameters and the non-convex nature of the training procedure, GNNs are harder to train. Theoretical guarantees of GNNs are also not well-understood. Furthermore, the expressive power of GNNs scales with the number of parameters, and thus it is hard to exploit the full power of GNNs when computing resources are limited. The current paper presents a new class of graph kernels, Graph Neural Tangent Kernels (GNTKs), which correspond to infinitely wide multi-layer GNNs trained by gradient descent. GNTKs enjoy the full expressive power of GNNs and inherit advantages of GKs. Theoretically, we show GNTKs provably learn a class of smooth functions on graphs. Empirically, we test GNTKs on graph classification datasets and show they achieve strong performance.
Understanding Goal-Oriented Active Learning via Influence Functions
Authors: Minjie Xu, Gary Kazantsev
Date: 2019-05-30 00:00:00
Tasks: Active Learning

Active learning (AL) concerns itself with learning a model from as few labelled data as possible through actively and iteratively querying an oracle with selected unlabelled samples. In this paper, we focus on analyzing a popular type of AL in which the utility of a sample is measured by a specified goal achieved by the retrained model after accounting for the sample's marginal influence. Such AL strategies attract a lot of attention thanks to their intuitive motivations, yet they also suffer from impractically high computational costs due to their need for many iterations of model retraining. With the help of influence functions, we present an effective approximation that bypasses model retraining altogether, and propose a general efficient implementation that makes such AL strategies applicable in practice, both in the serial and the more challenging batch-mode setting. Additionally, we present both theoretical and empirical findings which call into question a few common practices and beliefs about such AL strategies.
Recovery of binary sparse signals from compressed linear measurements via polynomial optimization
Authors: Sophie M. Fosson, Mohammad Abuabiah
Date: 2019-05-30 00:00:00
Tasks: compressed sensing

The recovery of signals with finite-valued components from few linear measurements is a problem with widespread applications and interesting mathematical characteristics. In the compressed sensing framework, tailored methods have been recently proposed to deal with the case of finite-valued sparse signals. In this work, we focus on binary sparse signals and we propose a novel formulation, based on polynomial optimization. This approach is analyzed and compared to the state-of-the-art binary compressed sensing methods.
Toward Runtime-Throttleable Neural Networks
Authors: Jesse Hostetler
Date: 2019-05-30 00:00:00
Tasks: Edge-computing, image-classification, Image Classification, Management, object-detection, Object Detection

As deep neural network (NN) methods have matured, there has been increasing interest in deploying NN solutions to "edge computing" platforms such as mobile phones or embedded controllers. These platforms are often resource-constrained, especially in energy storage and power, but state-of-the-art NN architectures are designed with little regard for resource use. Existing techniques for reducing the resource footprint of NN models produce static models that occupy a single point in the trade-space between performance and resource use. This paper presents an approach to creating runtime-throttleable NNs that can adaptively balance performance and resource use in response to a control signal. Throttleable networks allow intelligent resource management, for example by allocating fewer resources in "easy" conditions or when battery power is low. We describe a generic formulation of throttling via block-level gating, apply it to create throttleable versions of several standard CNN architectures, and demonstrate that our approach allows smooth performance throttling over a wide range of operating points in image classification and object detection tasks, with only a small loss in peak accuracy.
Learning from the Past: How Previous Technological Transformations Can Guide AI Development
Authors: Risto Miikkulainen, Jerry Smith, Babak Hodjat
Date: 2019-05-30 00:00:00

Artificial Intelligence (AI) is rapidly changing many areas of society. While this transformation has tremendous potential, there are several challenges as well. Using the history of computing and the world-wide web as a guide, in this paper we identify pitfalls and solutions that suggest how AI can be developed to its full potential. If done right, AI will be instrumental in achieving the goals we set for the economy, the society, and the world in general.
Graph Normalizing Flows
Authors: Jenny Liu, Aviral Kumar, Jimmy Ba, Jamie Kiros, Kevin Swersky
Date: 2019-05-30 00:00:00
Proceeding: NeurIPS 2019 12
Tasks: Graph Neural Network

We introduce graph normalizing flows: a new, reversible graph neural network model for prediction and generation. On supervised tasks, graph normalizing flows perform similarly to message passing neural networks, but at a significantly reduced memory footprint, allowing them to scale to larger graphs. In the unsupervised case, we combine graph normalizing flows with a novel graph auto-encoder to create a generative model of graph structures. Our model is permutation-invariant, generating entire graphs with a single feed-forward pass, and achieves competitive results with the state-of-the art auto-regressive models, while being better suited to parallel computing architectures.
Confirmatory Bayesian Online Change Point Detection in the Covariance Structure of Gaussian Processes
Authors: Jiyeon Han, Kyowoon Lee, Anh Tong, Jaesik Choi
Date: 2019-05-30 00:00:00
Tasks: Change Point Detection, Gaussian Processes, Time Series, Time Series Analysis

In the analysis of sequential data, the detection of abrupt changes is important in predicting future changes. In this paper, we propose statistical hypothesis tests for detecting covariance structure changes in locally smooth time series modeled by Gaussian Processes (GPs). We provide theoretically justified thresholds for the tests, and use them to improve Bayesian Online Change Point Detection (BOCPD) by confirming statistically significant changes and non-changes. Our Confirmatory BOCPD (CBOCPD) algorithm finds multiple structural breaks in GPs even when hyperparameters are not tuned precisely. We also provide conditions under which CBOCPD provides the lower prediction error compared to BOCPD. Experimental results on synthetic and real-world datasets show that our new tests correctly detect changes in the covariance structure in GPs. The proposed algorithm also outperforms existing methods for the prediction of nonstationarity in terms of both regression error and log likelihood.
Defining Admissible Rewards for High Confidence Policy Evaluation
Authors: Niranjani Prasad, Barbara E. Engelhardt, Finale Doshi-Velez
Date: 2019-05-30 00:00:00
Tasks: Off-policy evaluation, Reinforcement Learning, Reinforcement Learning (RL), Vocal Bursts Intensity Prediction

A key impediment to reinforcement learning (RL) in real applications with limited, batch data is defining a reward function that reflects what we implicitly know about reasonable behaviour for a task and allows for robust off-policy evaluation. In this work, we develop a method to identify an admissible set of reward functions for policies that (a) do not diverge too far from past behaviour, and (b) can be evaluated with high confidence, given only a collection of past trajectories. Together, these ensure that we propose policies that we trust to be implemented in high-risk settings. We demonstrate our approach to reward design on synthetic domains as well as in a critical care context, for a reward that consolidates clinical objectives to learn a policy for weaning patients from mechanical ventilation.
Hierarchical Transformers for Multi-Document Summarization
Authors: Yang Liu, Mirella Lapata
Date: 2019-05-30 00:00:00
Proceeding: ACL 2019 7
Tasks: Document Summarization, Multi-Document Summarization

In this paper, we develop a neural summarization model which can effectively process multiple input documents and distill Transformer architecture with the ability to encode documents in a hierarchical manner. We represent cross-document relationships via an attention mechanism which allows to share information as opposed to simply concatenating text spans and processing them as a flat sequence. Our model learns latent dependencies among textual units, but can also take advantage of explicit graph representations focusing on similarity or discourse relations. Empirical results on the WikiSum dataset demonstrate that the proposed architecture brings substantial improvements over several strong baselines.
Deep Adversarial Social Recommendation
Authors: Wenqi Fan, Tyler Derr, Yao Ma, JianPing Wang, Jiliang Tang, Qing Li
Date: 2019-05-30 00:00:00
Tasks: Recommendation Systems, Representation Learning

Recent years have witnessed rapid developments on social recommendation techniques for improving the performance of recommender systems due to the growing influence of social networks to our daily life. The majority of existing social recommendation methods unify user representation for the user-item interactions (item domain) and user-user connections (social domain). However, it may restrain user representation learning in each respective domain, since users behave and interact differently in the two domains, which makes their representations to be heterogeneous. In addition, most of traditional recommender systems can not efficiently optimize these objectives, since they utilize negative sampling technique which is unable to provide enough informative guidance towards the training during the optimization process. In this paper, to address the aforementioned challenges, we propose a novel deep adversarial social recommendation framework DASO. It adopts a bidirectional mapping method to transfer users' information between social domain and item domain using adversarial learning. Comprehensive experiments on two real-world datasets show the effectiveness of the proposed framework.
Distribution-dependent and Time-uniform Bounds for Piecewise i.i.d Bandits
Authors: Subhojyoti Mukherjee, Odalric-Ambrym Maillard
Date: 2019-05-30 00:00:00
Tasks: Multi-Armed Bandits

We consider the setup of stochastic multi-armed bandits in the case when reward distributions are piecewise i.i.d. and bounded with unknown changepoints. We focus on the case when changes happen simultaneously on all arms, and in stark contrast with the existing literature, we target gap-dependent (as opposed to only gap-independent) regret bounds involving the magnitude of changes $(\Delta^{chg}_{i,g})$ and optimality-gaps ($\Delta^{opt}_{i,g}$). Diverging from previous works, we assume the more realistic scenario that there can be undetectable changepoint gaps and under a different set of assumptions, we show that as long as the compounded delayed detection for each changepoint is bounded there is no need for forced exploration to actively detect changepoints. We introduce two adaptations of UCB-strategies that employ scan-statistics in order to actively detect the changepoints, without knowing in advance the changepoints and also the mean before and after any change. Our first method \UCBLCPD does not know the number of changepoints $G$ or time horizon $T$ and achieves the first time-uniform concentration bound for this setting using the Laplace method of integration. The second strategy \ImpCPD makes use of the knowledge of $T$ to achieve the order optimal regret bound of $\min\big\lbrace O(\sum\limits_{i=1}^{K} \sum\limits_{g=1}^{G}\frac{\log(T/H_{1,g})}{\Delta^{opt}_{i,g}}), O(\sqrt{GT})\big\rbrace$, (where $H_{1,g}$ is the problem complexity) thereby closing an important gap with respect to the lower bound in a specific challenging setting. Our theoretical findings are supported by numerical experiments on synthetic and real-life datasets.
Grounding Language Attributes to Objects using Bayesian Eigenobjects
Authors: Vanya Cohen, Benjamin Burchfiel, Thao Nguyen, Nakul Gopalan, Stefanie Tellex, George Konidaris
Date: 2019-05-30 00:00:00
Tasks: 3D Shape Representation, Object

We develop a system to disambiguate object instances within the same class based on simple physical descriptions. The system takes as input a natural language phrase and a depth image containing a segmented object and predicts how similar the observed object is to the object described by the phrase. Our system is designed to learn from only a small amount of human-labeled language data and generalize to viewpoints not represented in the language-annotated depth image training set. By decoupling 3D shape representation from language representation, this method is able to ground language to novel objects using a small amount of language-annotated depth-data and a larger corpus of unlabeled 3D object meshes, even when these objects are partially observed from unusual viewpoints. Our system is able to disambiguate between novel objects, observed via depth images, based on natural language descriptions. Our method also enables view-point transfer; trained on human-annotated data on a small set of depth images captured from frontal viewpoints, our system successfully predicted object attributes from rear views despite having no such depth images in its training set. Finally, we demonstrate our approach on a Baxter robot, enabling it to pick specific objects based on human-provided natural language descriptions.