pwc-archive/papers-with-abstracts huggingface dataset:
Temporal FiLM: Capturing Long-Range Sequence Dependencies with Feature-Wise Modulations.
Authors: Sawyer Birnbaum, Volodymyr Kuleshov, Zayd Enam, Pang Wei W. Koh, Stefano Ermon
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12
Tasks: Audio Super-Resolution, Super-Resolution, text-classification, Text Classification

Learning representations that accurately capture long-range dependencies in sequential inputs --- including text, audio, and genomic data --- is a key problem in deep learning. Feed-forward convolutional models capture only feature interactions within finite receptive fields while recurrent architectures can be slow and difficult to train due to vanishing gradients. Here, we propose Temporal Feature-Wise Linear Modulation (TFiLM) --- a novel architectural component inspired by adaptive batch normalization and its extensions --- that uses a recurrent neural network to alter the activations of a convolutional model. This approach expands the receptive field of convolutional sequence models with minimal computational overhead. Empirically, we find that TFiLM significantly improves the learning speed and accuracy of feed-forward neural networks on a range of generative and discriminative learning tasks, including text classification and audio super-resolution.
Efficient Near-Optimal Testing of Community Changes in Balanced Stochastic Block Models
Authors: Aditya Gangrade, Praveen Venkatesh, Bobak Nazer, Venkatesh Saligrama
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12
Tasks: Two-sample testing

We propose and analyze the  problems of \textit{community goodness-of-fit and two-sample testing} for stochastic block models (SBM), where changes arise due to modification in community memberships of nodes. Motivated by practical applications, we consider the challenging sparse regime, where expected node degrees are constant, and the inter-community mean degree ($b$) scales proportionally to intra-community mean degree ($a$). Prior work has sharply characterized partial or full community recovery in terms of a  ``signal-to-noise ratio'' ($\mathrm{SNR}$) based on $a$ and $b$. For both problems, we propose computationally-efficient tests that can succeed far beyond the regime where recovery of community membership is even possible. Overall, for large changes, $s \gg \sqrt{n}$, we need only $\mathrm{SNR}= O(1)$ whereas a na\"ive test based on community recovery with $O(s)$ errors requires $\mathrm{SNR}= \Theta(\log n)$. Conversely, in the small change regime, $s \ll \sqrt{n}$, via an information theoretic lower bound, we show that, surprisingly, no algorithm can do better than the na\"ive algorithm that first estimates the community up to $O(s)$ errors and then detects changes. 
We validate these phenomena numerically on SBMs and on real-world datasets as well as Markov Random Fields where we only observe node data rather than the existence of links.
Statistical-Computational Tradeoff in Single Index Models
Authors: Lingxiao Wang, Zhuoran Yang, Zhaoran Wang
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12

We study the statistical-computational  tradeoffs in a high dimensional single index model $Y=f(X^\top\beta^*) +\epsilon$, where $f$ is unknown, $X$ is a Gaussian vector and $\beta^*$ is $s$-sparse with unit norm. When $\cov(Y,X^\top\beta^*)\neq 0$, \cite{plan2016generalized} shows that the direction and support of $\beta^*$ can be recovered using a generalized version of Lasso. In this paper, we investigate the case when this critical assumption fails to hold, where the problem becomes considerably harder. Using the statistical query model to characterize the computational cost of an algorithm, we show that when $\cov(Y,X^\top\beta^*)=0$ and $\cov(Y,(X^\top\beta^*)^2)>0$, no computationally tractable algorithms can achieve the information-theoretic limit of the minimax risk. This implies that one must pay an extra computational cost for the nonlinearity involved in the model.
On Fenchel Mini-Max Learning
Authors: Chenyang Tao, Liqun Chen, Shuyang Dai, Junya Chen, Ke Bai, Dong Wang, Jianfeng Feng, Wenlian Lu, Georgiy Bobashev, Lawrence Carin
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12
Tasks: Density Estimation

Inference, estimation, sampling and likelihood evaluation are four primary goals of probabilistic modeling. Practical considerations often force modeling approaches to make compromises between these objectives. We present a novel probabilistic learning framework, called Fenchel Mini-Max Learning (FML), that accommodates all four desiderata in a flexible and scalable manner. Our derivation is rooted in classical maximum likelihood estimation, and it overcomes a longstanding challenge that prevents unbiased estimation of unnormalized statistical models. By reformulating MLE as a mini-max game, FML enjoys an unbiased training objective that (i) does not explicitly involve the intractable normalizing constant and (ii) is directly amendable to stochastic gradient descent optimization. To demonstrate the utility of the proposed approach, we consider learning unnormalized statistical models, nonparametric density estimation and training generative models, with encouraging empirical results presented.
MarginGAN: Adversarial Training in Semi-Supervised Learning
Authors: Jinhao Dong, Tong Lin
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12
Tasks: Generative Adversarial Network

A Margin Generative Adversarial Network (MarginGAN) is proposed for semi-supervised learning problems. Like Triple-GAN, the proposed MarginGAN consists of three components---a generator, a discriminator and a classifier, among which two forms of adversarial training arise. The discriminator is trained as usual to distinguish real examples from fake examples produced by the generator. The new feature is that the classifier attempts to increase the margin of real examples and to decrease the margin of fake examples. On the contrary, the purpose of the generator is yielding realistic and large-margin examples in order to fool the discriminator and the classifier simultaneously. Pseudo labels are used for generated and unlabeled examples in training. Our method is motivated by the success of large-margin classifiers and the recent viewpoint that good semi-supervised learning requires a ``bad'' GAN. Experiments on benchmark datasets testify that MarginGAN is orthogonal to several state-of-the-art methods, offering improved error rates and shorter training time as well.
Efficient Convex Relaxations for Streaming PCA
Authors: Raman Arora, Teodor Vanislavov Marinov
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12

We revisit two algorithms, matrix stochastic gradient (MSG) and $\ell_2$-regularized MSG (RMSG), that are instances of stochastic gradient descent (SGD) on a convex relaxation to principal component analysis (PCA). These algorithms have been shown to outperform Oja’s algorithm, empirically, in terms of the iteration complexity, and to have runtime comparable with Oja’s. However, these findings are not supported by  existing theoretical results. While the iteration complexity bound for $\ell_2$-RMSG was recently shown to match that of Oja’s algorithm, its theoretical efficiency was left as an open problem. In this work, we give improved bounds on per iteration cost of mini-batched variants of both MSG and $\ell_2$-RMSG and arrive at an algorithm with total computational complexity matching that of Oja's algorithm.
Sample Complexity of Learning Mixture of Sparse Linear Regressions
Authors: Akshay Krishnamurthy, Arya Mazumdar, Andrew McGregor, Soumyabrata Pal
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12
Tasks: compressed sensing, Open-Ended Question Answering

In the problem of learning mixtures of linear regressions, the goal is to learn a col-lection of signal vectors from a sequence of (possibly noisy) linear measurements,where each measurement is evaluated on an unknown signal drawn uniformly fromthis collection. This setting is quite expressive and has been studied both in termsof practical applications and for the sake of establishing theoretical guarantees. Inthis paper, we consider the case where the signal vectors aresparse; this generalizesthe popular compressed sensing paradigm. We improve upon the state-of-the-artresults as follows: In the noisy case, we resolve an open question of Yin et al. (IEEETransactions on Information Theory, 2019) by showing how to handle collectionsof more than two vectors and present the first robust reconstruction algorithm, i.e.,if the signals are not perfectly sparse, we still learn a good sparse approximationof the signals. In the noiseless case, as well as in the noisy case, we show how tocircumvent the need for a restrictive assumption required in the previous work. Ourtechniques are quite different from those in the previous work: for the noiselesscase, we rely on a property of sparse polynomials and for the noisy case, we providenew connections to learning Gaussian mixtures and use ideas from the theory of
Neural Trust Region/Proximal Policy Optimization Attains Globally Optimal Policy
Authors: Boyi Liu, Qi Cai, Zhuoran Yang, Zhaoran Wang
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12
Tasks: Deep Reinforcement Learning, Reinforcement Learning, Reinforcement Learning (RL)

Proximal policy optimization and trust region policy optimization (PPO and TRPO) with actor and critic parametrized by neural networks achieve significant empirical success in deep reinforcement learning. However, due to nonconvexity, the global convergence of PPO and TRPO remains less understood, which separates theory from practice. In this paper, we prove that a variant of PPO and TRPO equipped with overparametrized neural networks converges to the globally optimal policy at a sublinear rate. The key to our analysis is the global convergence of infinite-dimensional mirror descent under a notion of one-point monotonicity, where the gradient and iterate are instantiated by neural networks. In particular, the desirable representation power and optimization geometry induced by the overparametrization of such neural networks allow them to accurately approximate the infinite-dimensional gradient and iterate.
Dimensionality reduction: theoretical perspective on practical measures
Authors: Yair Bartal, Nova Fandina, Ofer Neiman
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12
Tasks: BIG-bench Machine Learning, Dimensionality Reduction, Math

Dimensionality reduction plays a central role in real-world applications for Machine Learning, among many fields. In particular,  metric dimensionality reduction where data from a general metric is mapped into low dimensional space, is often used as a first step before applying machine learning algorithms. In almost all these applications the quality of the embedding is measured by various average case criteria. Metric dimensionality reduction has also been studied in Math and TCS, within the extremely fruitful and influential field of metric embedding. Yet, the vast majority of theoretical research has been devoted to analyzing the worst case behavior of embeddings and therefore has little relevance to practical settings. The goal of this paper is to bridge the gap between theory and practice view-points of metric dimensionality reduction, laying the foundation for a theoretical study of more practically oriented analysis. This paper can be viewed as providing a comprehensive theoretical framework addressing a line of research initiated by VL [NeuroIPS' 18] who have set the goal of analyzing different distortion measurement criteria, with the lens of Machine Learning applicability, from both theoretical and practical perspectives.
We complement their work by considering some important and vastly used average case criteria, some of which originated within the well-known Multi-Dimensional Scaling framework.  While often studied in practice, no theoretical studies have thus far attempted at providing rigorous analysis of these criteria. In this paper we provide the first analysis of these, as well as the new distortion measure developed by [VL18] designed to possess Machine Learning desired properties. Moreover, we show that all measures considered can be adapted to possess similar qualities. The main consequences of our work are nearly tight bounds on the absolute values of all distortion criteria, as well as first approximation algorithms with provable guarantees.
Oracle-Efficient Algorithms for Online Linear Optimization with Bandit Feedback
Authors: Shinji Ito, Daisuke Hatano, Hanna Sumita, Kei Takemura, Takuro Fukunaga, Naonori Kakimura, Ken-ichi Kawarabayashi
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12
Tasks: Computational Efficiency

We propose computationally efficient algorithms for \textit{online linear optimization with bandit feedback}, in which a player chooses an \textit{action vector} from a given (possibly infinite) set $\mathcal{A} \subseteq \mathbb{R}^d$, and then suffers a loss that can be expressed as a linear function in action vectors. Although existing algorithms achieve an optimal regret bound of $\tilde{O}(\sqrt{T})$ for $T$ rounds (ignoring factors of $\mathrm{poly} (d, \log T)$), computationally efficient ways of implementing them have not yet been specified, in particular when $|\mathcal{A}|$ is not bounded by a polynomial size in $d$. A standard way to pursue computational efficiency is to assume that we have an efficient algorithm referred to as \textit{oracle} that solves (offline) linear optimization problems over $\mathcal{A}$. Under this assumption, the computational efficiency of a bandit algorithm can then be measured in terms of \textit{oracle complexity}, i.e., the number of oracle calls. Our contribution is to propose algorithms that offer optimal regret bounds of $\tilde{O}(\sqrt{T})$ as well as low oracle complexity for both \textit{non-stochastic settings} and \textit{stochastic settings}. Our algorithm for non-stochastic settings has an oracle complexity of $\tilde{O}( T )$ and is the first algorithm that achieves both a regret bound of $\tilde{O}( \sqrt{T} )$ and an oracle complexity of $\tilde{O} ( \mathrm{poly} ( T ) )$, given only linear optimization oracles. Our algorithm for stochastic settings calls the oracle only $O( \mathrm{poly} (d, \log T))$ times, which is smaller than the current best oracle complexity of $O( T )$ if $T$ is sufficiently large.
Transfer Learning via Minimizing the Performance Gap Between Domains
Authors: Boyu Wang, Jorge Mendez, Mingbo Cai, Eric Eaton
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12
Tasks: Generalization Bounds, Transfer Learning

We propose a new principle for transfer learning, based on a straightforward intuition: if two domains are similar to each other, the model trained on one domain should also perform well on the other domain, and vice versa. To formalize this intuition, we define the performance gap as a measure of the discrepancy between the source and target domains. We derive generalization bounds for the instance weighting approach to transfer learning, showing that the performance gap can be viewed as an algorithm-dependent regularizer, which controls the model complexity. Our theoretical analysis provides new insight into transfer learning and motivates a set of general, principled rules for designing new instance weighting schemes for transfer learning. These rules lead to gapBoost, a novel and principled boosting approach for transfer learning. Our experimental evaluation on benchmark data sets shows that gapBoost significantly outperforms previous boosting-based transfer learning algorithms.
A Model-Based Reinforcement Learning with Adversarial Training for Online Recommendation
Authors: Xueying Bai, Jian Guan, Hongning Wang
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12
Tasks: Generative Adversarial Network, Model-based Reinforcement Learning, Recommendation Systems, reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

Reinforcement learning is effective in optimizing policies for recommender systems. Current solutions mostly focus on model-free approaches, which require frequent interactions with a real environment, and thus are expensive in model learning. Offline evaluation methods, such as importance sampling, can alleviate such limitations, but usually request a large amount of logged data and do not work well when the action space is large. In this work, we propose a model-based reinforcement learning solution which models the user-agent interaction for offline policy learning via a generative adversarial network. To reduce bias in the learnt policy, we use the discriminator to evaluate the quality of generated sequences and rescale the generated rewards. Our theoretical analysis and empirical evaluations demonstrate the effectiveness of our solution in identifying patterns from given offline data and learning policies based on the offline and generated data.
Optimizing Generalized Rate Metrics with Three Players
Authors: Harikrishna Narasimhan, Andrew Cotter, Maya Gupta
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12
Tasks: Fairness

We present a general framework for solving a large class of learning problems with non-linear functions of classification rates. This includes problems where one wishes to optimize a non-decomposable performance metric such as the F-measure or G-mean, and constrained training problems where the classifier needs to satisfy non-linear rate constraints such as predictive parity fairness, distribution divergences or churn ratios. We extend previous two-player game approaches for constrained optimization to an approach with three players to decouple the classifier rates from the non-linear objective, and seek to find an equilibrium of the game. Our approach generalizes many existing algorithms, and makes possible new algorithms with more flexibility and tighter handling of non-linear rate constraints. We provide convergence guarantees for convex functions of rates, and show how our methodology can be extended to handle sums-of-ratios of rates. Experiments on different fairness tasks confirm the efficacy of our approach.
Consistency-based Semi-supervised Learning for Object detection
Authors: Jisoo Jeong, Seungeui Lee, Jeesoo Kim, Nojun Kwak
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12
Tasks: Object, object-detection, Object Detection, Semi-Supervised Object Detection

Making a precise annotation in a large dataset is crucial to the performance of object detection. While the object detection task requires a huge number of annotated samples to guarantee its performance, placing bounding boxes for every object in each sample is time-consuming and costs a lot. To alleviate this problem, we propose a Consistency-based Semi-supervised learning method for object Detection (CSD), which is a way of using consistency constraints as a tool for enhancing detection performance by making full use of available unlabeled data. Specifically, the consistency constraint is applied not only for object classification but also for the localization. We also proposed Background Elimination (BE) to avoid the negative effect of the predominant backgrounds on the detection performance. We have evaluated the proposed CSD both in single-stage and two-stage detectors and the results show the effectiveness of our method.
Cross-Modal Learning with Adversarial Samples
Authors: Chao Li, Shangqian Gao, Cheng Deng, De Xie, Wei Liu
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12
Tasks: Retrieval

With the rapid developments of deep neural networks, numerous deep cross-modal analysis methods have been presented and are being applied in widespread real-world applications, including healthcare and safety-critical environments. However, the recent studies on robustness and stability of deep neural networks show that a microscopic modification, known as adversarial sample, which is even imperceptible to humans, can easily fool a well-performed deep neural network and brings a new obstacle to deep cross-modal correlation exploring. In this paper, we propose a novel Cross-Modal correlation Learning with Adversarial samples, namely CMLA, which for the first time presents the existence of adversarial samples in cross-modal data. Moreover, we provide a simple yet effective adversarial sample learning method, where inter- and intra- modality similarity regularizations across different modalities are simultaneously integrated into the learning of adversarial samples. Finally, our proposed CMLA is demonstrated to be highly effective in cross-modal hashing based retrieval. Extensive experiments on two cross-modal benchmark datasets show that the adversarial examples produced by our CMLA are efficient in fooling a target deep cross-modal hashing network. On the other hand, such adversarial examples can significantly strengthen the robustness of the target network by conducting an adversarial training.
Random Projections with Asymmetric Quantization
Authors: Xiaoyun Li, Ping Li
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12
Tasks: Data Compression, Quantization

The method of random projection has been a popular tool for data compression,
similarity search, and machine learning. In many practical scenarios, applying
quantization on randomly projected data could be very helpful to further reduce
storage cost and facilitate more efficient retrievals, while only suffering from
little loss in accuracy. In real-world applications, however, data collected from
different sources may be quantized under different schemes, which calls for a need to study the asymmetric quantization problem. In this paper, we investigate the cosine similarity estimators derived in such setting under the Lloyd-Max (LM)
quantization scheme. We thoroughly analyze the biases and variances of a series of estimators including the basic simple estimators, their normalized versions, and
their debiased versions. Furthermore, by studying the monotonicity, we show that
the expectation of proposed estimators increases with the true cosine similarity,
on a broader family of stair-shaped quantizers. Experiments on nearest neighbor
search justify the theory and illustrate the effectiveness of our proposed estimators.
Private Testing of Distributions via Sample Permutations
Authors: Maryam Aliakbarpour, Ilias Diakonikolas, Daniel Kane, Ronitt Rubinfeld
Date: 2019-12-01 00:00:00
Proceeding: NeurIPS 2019 12

Statistical tests are at the heart of many scientific tasks.
To validate their hypothesis, researchers in medical and 
social sciences use individuals' data. The sensitivity of 
participants' data requires the design of statistical tests that 
ensure the privacy of the individuals in the most efficient way. 
In this paper, we use the framework of property testing to design algorithms to test the properties of the distribution that the data is drawn from with respect to differential privacy. 
In particular, we investigate testing two fundamental properties of distributions:  (1) testing the equivalence of two distributions when we have unequal numbers of 
samples from the two distributions. 
(2) Testing independence of two random variables. 
In both cases, we show that our testers achieve near optimal sample complexity (up to logarithmic factors). 
Moreover, our dependence on the privacy parameter is an additive term, which indicates that differential privacy can be obtained 
in most regimes of parameters for free.