pwc-archive/papers-with-abstracts huggingface dataset:
Better Exploration with Optimistic Actor-Critic
Authors: Kamil Ciosek, Quan Vuong, Robert Loftin, Katja Hofmann
Date: 2019-10-28 00:00:00
Tasks: continuous-control, Continuous Control, Efficient Exploration, Reinforcement Learning

Actor-critic methods, a type of model-free Reinforcement Learning, have been successfully applied to challenging tasks in continuous control, often achieving state-of-the art performance. However, wide-scale adoption of these methods in real-world domains is made difficult by their poor sample efficiency. We address this problem both theoretically and empirically. On the theoretical side, we identify two phenomena preventing efficient exploration in existing state-of-the-art algorithms such as Soft Actor Critic. First, combining a greedy actor update with a pessimistic estimate of the critic leads to the avoidance of actions that the agent does not know about, a phenomenon we call pessimistic underexploration. Second, current algorithms are directionally uninformed, sampling actions with equal probability in opposite directions from the current mean. This is wasteful, since we typically need actions taken along certain directions much more than others. To address both of these phenomena, we introduce a new algorithm, Optimistic Actor Critic, which approximates a lower and upper confidence bound on the state-action value function. This allows us to apply the principle of optimism in the face of uncertainty to perform directed exploration using the upper bound while still using the lower bound to avoid overestimation. We evaluate OAC in several challenging continuous control tasks, achieving state-of the art sample efficiency.
An Ensemble Approach toward Automated Variable Selection for Network Anomaly Detection
Authors: Makiya Nakashima, Alex Sim, Youngsoo Kim, Jonghyun Kim, Jinoh Kim
Date: 2019-10-28 00:00:00
Tasks: Anomaly Detection, Variable Selection

While variable selection is essential to optimize the learning complexity by prioritizing features, automating the selection process is preferred since it requires laborious efforts with intensive analysis otherwise. However, it is not an easy task to enable the automation due to several reasons. First, selection techniques often need a condition to terminate the reduction process, for example, by using a threshold or the number of features to stop, and searching an adequate stopping condition is highly challenging. Second, it is uncertain that the reduced variable set would work well; our preliminary experimental result shows that well-known selection techniques produce different sets of variables as a result of reduction (even with the same termination condition), and it is hard to estimate which of them would work the best in future testing. In this paper, we demonstrate the potential power of our approach to the automation of selection process that incorporates well-known selection methods identifying important variables. Our experimental results with two public network traffic data (UNSW-NB15 and IDS2017) show that our proposed method identifies a small number of core variables, with which it is possible to approximate the performance to the one with the entire variables.
Model-Free Mean-Field Reinforcement Learning: Mean-Field MDP and Mean-Field Q-Learning
Authors: René Carmona, Mathieu Laurière, Zongjun Tan
Date: 2019-10-28 00:00:00
Tasks: General Reinforcement Learning, Q-Learning, Reinforcement Learning, Reinforcement Learning (RL)

We study infinite horizon discounted Mean Field Control (MFC) problems with common noise through the lens of Mean Field Markov Decision Processes (MFMDP). We allow the agents to use actions that are randomized not only at the individual level but also at the level of the population. This common randomization allows us to establish connections between both closed-loop and open-loop policies for MFC and Markov policies for the MFMDP. In particular, we show that there exists an optimal closed-loop policy for the original MFC. Building on this framework and the notion of state-action value function, we then propose reinforcement learning (RL) methods for such problems, by adapting existing tabular and deep RL methods to the mean-field setting. The main difficulty is the treatment of the population state, which is an input of the policy and the value function. We provide convergence guarantees for tabular algorithms based on discretizations of the simplex. Neural network based algorithms are more suitable for continuous spaces and allow us to avoid discretizing the mean field state space. Numerical examples are provided.
Attenuating Random Noise in Seismic Data by a Deep Learning Approach
Authors: Xing Zhao, Ping Lu, Yanyan Zhang, Jianxiong Chen, Xiaoyang Li
Date: 2019-10-28 00:00:00

In the geophysical field, seismic noise attenuation has been considered as a critical and long-standing problem, especially for the pre-stack data processing. Here, we propose a model to leverage the deep-learning model for this task. Rather than directly applying an existing de-noising model from ordinary images to the seismic data, we have designed a particular deep-learning model, based on residual neural networks. It is named as N2N-Seismic, which has a strong ability to recover the seismic signals back to intact condition with the preservation of primary signals. The proposed model, achieving with great success in attenuating noise, has been tested on two different seismic datasets. Several metrics show that our method outperforms conventional approaches in terms of Signal-to-Noise-Ratio, Mean-Squared-Error, Phase Spectrum, etc. Moreover, robust tests in terms of effectively removing random noise from any dataset with strong and weak noises have been extensively scrutinized in making sure that the proposed model is able to maintain a good level of adaptation while dealing with large variations of noise characteristics and intensities.
Deep learning is adaptive to intrinsic dimensionality of model smoothness in anisotropic Besov space
Authors: Taiji Suzuki, Atsushi Nitanda
Date: 2019-10-28 00:00:00
Proceeding: NeurIPS 2021 12
Tasks: Deep Learning

Deep learning has exhibited superior performance for various tasks, especially for high-dimensional datasets, such as images. To understand this property, we investigate the approximation and estimation ability of deep learning on anisotropic Besov spaces. The anisotropic Besov space is characterized by direction-dependent smoothness and includes several function classes that have been investigated thus far. We demonstrate that the approximation error and estimation error of deep learning only depend on the average value of the smoothness parameters in all directions. Consequently, the curse of dimensionality can be avoided if the smoothness of the target function is highly anisotropic. Unlike existing studies, our analysis does not require a low-dimensional structure of the input data. We also investigate the minimax optimality of deep learning and compare its performance with that of the kernel method (more generally, linear estimators). The results show that deep learning has better dependence on the input dimensionality if the target function possesses anisotropic smoothness, and it achieves an adaptive rate for functions with spatially inhomogeneous smoothness.
Learning Data Manipulation for Augmentation and Weighting
Authors: Zhiting Hu, Bowen Tan, Ruslan Salakhutdinov, Tom Mitchell, Eric P. Xing
Date: 2019-10-28 00:00:00
Proceeding: NeurIPS 2019 12
Tasks: Data Augmentation, Reinforcement Learning, Reinforcement Learning (RL), text-classification, Text Classification

Manipulating data, such as weighting data examples or augmenting with new instances, has been increasingly used to improve model training. Previous work has studied various rule- or learning-based approaches designed for specific types of data manipulation. In this work, we propose a new method that supports learning different manipulation schemes with the same gradient-based algorithm. Our approach builds upon a recent connection of supervised learning and reinforcement learning (RL), and adapts an off-the-shelf reward learning algorithm from RL for joint data manipulation learning and model training. Different parameterization of the "data reward" function instantiates different manipulation schemes. We showcase data augmentation that learns a text transformation network, and data weighting that dynamically adapts the data sample importance. Experiments show the resulting algorithms significantly improve the image and text classification performance in low data regime and class-imbalance problems.
Stein Variational Gradient Descent With Matrix-Valued Kernels
Authors: Dilin Wang, Ziyang Tang, Chandrajit Bajaj, Qiang Liu
Date: 2019-10-28 00:00:00
Proceeding: NeurIPS 2019 12
Tasks: Bayesian Inference

Stein variational gradient descent (SVGD) is a particle-based inference algorithm that leverages gradient information for efficient approximate inference. In this work, we enhance SVGD by leveraging preconditioning matrices, such as the Hessian and Fisher information matrix, to incorporate geometric information into SVGD updates. We achieve this by presenting a generalization of SVGD that replaces the scalar-valued kernels in vanilla SVGD with more general matrix-valued kernels. This yields a significant extension of SVGD, and more importantly, allows us to flexibly incorporate various preconditioning matrices to accelerate the exploration in the probability landscape. Empirical results show that our method outperforms vanilla SVGD and a variety of baseline approaches over a range of real-world Bayesian inference tasks.
Distributed Networked Learning with Correlated Data
Authors: Lingzhou Hong, Alfredo Garcia, Ceyhun Eksin
Date: 2019-10-28 00:00:00
Tasks: Federated Learning

We consider a distributed estimation method in a setting with heterogeneous streams of correlated data distributed across nodes in a network. In the considered approach, linear models are estimated locally (i.e., with only local data) subject to a network regularization term that penalizes a local model that differs from neighboring models. We analyze computation dynamics (associated with stochastic gradient updates) and information exchange (associated with exchanging current models with neighboring nodes). We provide a finite-time characterization of convergence of the weighted ensemble average estimate and compare this result to federated learning, an alternative approach to estimation wherein a single model is updated by locally generated gradient updates. This comparison highlights the trade-off between speed vs precision: while model updates take place at a faster rate in federated learning, the proposed networked approach to estimation enables the identification of models with higher precision. We illustrate the method's general applicability in two examples: estimating a Markov random field using wireless sensor networks and modeling prey escape behavior of flocking birds based on a publicly available dataset.
Empirical Analysis of Session-Based Recommendation Algorithms
Authors: Malte Ludewig, Noemi Mauro, Sara Latifi, Dietmar Jannach
Date: 2019-10-28 00:00:00
Tasks: Recommendation Systems, Session-Based Recommendations

Recommender systems are tools that support online users by pointing them to potential items of interest in situations of information overload. In recent years, the class of session-based recommendation algorithms received more attention in the research literature. These algorithms base their recommendations solely on the observed interactions with the user in an ongoing session and do not require the existence of long-term preference profiles. Most recently, a number of deep learning based ("neural") approaches to session-based recommendations were proposed. However, previous research indicates that today's complex neural recommendation methods are not always better than comparably simple algorithms in terms of prediction accuracy. With this work, our goal is to shed light on the state-of-the-art in the area of session-based recommendation and on the progress that is made with neural approaches. For this purpose, we compare twelve algorithmic approaches, among them six recent neural methods, under identical conditions on various datasets. We find that the progress in terms of prediction accuracy that is achieved with neural methods is still limited. In most cases, our experiments show that simple heuristic methods based on nearest-neighbors schemes are preferable over conceptually and computationally more complex methods. Observations from a user study furthermore indicate that recommendations based on heuristic methods were also well accepted by the study participants. To support future progress and reproducibility in this area, we publicly share the session-rec evaluation framework that was used in our research.
A First-Order Algorithmic Framework for Wasserstein Distributionally Robust Logistic Regression
Authors: Jiajin Li, Sen Huang, Anthony Man-Cho So
Date: 2019-10-28 00:00:00
Tasks: regression

Wasserstein distance-based distributionally robust optimization (DRO) has received much attention lately due to its ability to provide a robustness interpretation of various learning models. Moreover, many of the DRO problems that arise in the learning context admits exact convex reformulations and hence can be tackled by off-the-shelf solvers. Nevertheless, the use of such solvers severely limits the applicability of DRO in large-scale learning problems, as they often rely on general purpose interior-point algorithms. On the other hand, there are very few works that attempt to develop fast iterative methods to solve these DRO problems, which typically possess complicated structures. In this paper, we take a first step towards resolving the above difficulty by developing a first-order algorithmic framework for tackling a class of Wasserstein distance-based distributionally robust logistic regression (DRLR) problem. Specifically, we propose a novel linearized proximal ADMM to solve the DRLR problem, whose objective is convex but consists of a smooth term plus two non-separable non-smooth terms. We prove that our method enjoys a sublinear convergence rate. Furthermore, we conduct three different experiments to show its superb performance on both synthetic and real-world datasets. In particular, our method can achieve the same accuracy up to 800+ times faster than the standard off-the-shelf solver.
Missing Not at Random in Matrix Completion: The Effectiveness of Estimating Missingness Probabilities Under a Low Nuclear Norm Assumption
Authors: Wei Ma, George H. Chen
Date: 2019-10-28 00:00:00
Proceeding: NeurIPS 2019 12
Tasks: Matrix Completion, regression

Matrix completion is often applied to data with entries missing not at random (MNAR). For example, consider a recommendation system where users tend to only reveal ratings for items they like. In this case, a matrix completion method that relies on entries being revealed at uniformly sampled row and column indices can yield overly optimistic predictions of unseen user ratings. Recently, various papers have shown that we can reduce this bias in MNAR matrix completion if we know the probabilities of different matrix entries being missing. These probabilities are typically modeled using logistic regression or naive Bayes, which make strong assumptions and lack guarantees on the accuracy of the estimated probabilities. In this paper, we suggest a simple approach to estimating these probabilities that avoids these shortcomings. Our approach follows from the observation that missingness patterns in real data often exhibit low nuclear norm structure. We can then estimate the missingness probabilities by feeding the (always fully-observed) binary matrix specifying which entries are revealed or missing to an existing nuclear-norm-constrained matrix completion algorithm by Davenport et al. [2014]. Thus, we tackle MNAR matrix completion by solving a different matrix completion problem first that recovers missingness probabilities. We establish finite-sample error bounds for how accurate these probability estimates are and how well these estimates debias standard matrix completion losses for the original matrix to be completed. Our experiments show that the proposed debiasing strategy can improve a variety of existing matrix completion algorithms, and achieves downstream matrix completion accuracy at least as good as logistic regression and naive Bayes debiasing baselines that require additional auxiliary information.
Skip-Clip: Self-Supervised Spatiotemporal Representation Learning by Future Clip Order Ranking
Authors: Alaaeldin El-Nouby, Shuangfei Zhai, Graham W. Taylor, Joshua M. Susskind
Date: 2019-10-28 00:00:00
Tasks: Action Recognition, Future prediction, Representation Learning, Self-Supervised Action Recognition

Deep neural networks require collecting and annotating large amounts of data to train successfully. In order to alleviate the annotation bottleneck, we propose a novel self-supervised representation learning approach for spatiotemporal features extracted from videos. We introduce Skip-Clip, a method that utilizes temporal coherence in videos, by training a deep model for future clip order ranking conditioned on a context clip as a surrogate objective for video future prediction. We show that features learned using our method are generalizable and transfer strongly to downstream tasks. For action recognition on the UCF101 dataset, we obtain 51.8% improvement over random initialization and outperform models initialized using inflated ImageNet parameters. Skip-Clip also achieves results competitive with state-of-the-art self-supervision methods.
Quantum enhancements for deep reinforcement learning in large spaces
Authors: Sofiene Jerbi, Lea M. Trenkwalder, Hendrik Poulsen Nautrup, Hans J. Briegel, Vedran Dunjko
Date: 2019-10-28 00:00:00
Tasks: BIG-bench Machine Learning, Decision Making, Deep Reinforcement Learning, Quantum Machine Learning, reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

In the past decade, the field of quantum machine learning has drawn significant attention due to the prospect of bringing genuine computational advantages to now widespread algorithmic methods. However, not all domains of machine learning have benefited equally from quantum enhancements. Notably, deep learning and reinforcement learning, despite their tremendous success in the classical domain, both individually and combined, remain relatively unaddressed by the quantum community. Arguably, one reason behind this is the systematic use in these domains of models and methods without prominent computational bottlenecks, leaving little room for quantum improvements. In this work, we study the state-of-the-art neural-network approaches for reinforcement learning with quantum enhancements in mind. We demonstrate the substantial learning advantage that models with a sampling bottleneck can provide over conventional neural network architectures in complex learning environments. These so-called energy-based models, like deep energy-based reinforcement learning, and deep projective simulation that we also introduce in this work, effectively allow to trade off learning performance for efficiency of computation. To alleviate the additional computational costs, we propose to leverage future and near-term quantum algorithms, resulting in overall more advantageous learning algorithms. This is achieved using cutting-edge and new quantum computing machinery to speed-up classical sampling methods and by employing generalized models to gain an additional quantum advantage.
Fast classification rates without standard margin assumptions
Authors: Olivier Bousquet, Nikita Zhivotovskiy
Date: 2019-10-28 00:00:00
Tasks: Classification, General Classification, Learning Theory

We consider the classical problem of learning rates for classes with finite VC dimension. It is well known that fast learning rates up to $O\left(\frac{d}{n}\right)$ are achievable by the empirical risk minimization algorithm (ERM) if low noise or margin assumptions are satisfied. These usually require the optimal Bayes classifier to be in the class, and it has been shown that when this is not the case, the fast rates cannot be achieved even in the noise free case. In this paper, we further investigate the question of the fast rates under the misspecification, when the Bayes classifier is not in the class (also called the agnostic setting). First, we consider classification with a reject option, namely Chow's reject option model, and show that by slightly lowering the impact of hard instances, a learning rate of order $O\left(\frac{d}{n}\log \frac{n}{d}\right)$ is always achievable in the agnostic setting by a specific learning algorithm. Similar results were only known under special versions of margin assumptions. We also show that the performance of the proposed algorithm is never worse than the performance of ERM. Based on those results, we derive the necessary and sufficient conditions for classification (without a reject option) with fast rates in the agnostic setting achievable by improper learners. This simultaneously extends the work of Massart and N\'{e}d\'{e}lec (Ann. of Statistics, 2006), which studied this question in the case where the Bayesian optimal rule belongs to the class, and the work of Ben-David and Urner (COLT, 2014), which allows the misspecification but is limited to the no noise setting. Our result also provides the first general setup in statistical learning theory in which an improper learning algorithm may significantly improve the learning rate for non-convex losses.
Analytical classical density functionals from an equation learning network
Authors: Shang-Chun Lin, Georg Martius, Martin Oettel
Date: 2019-10-28 00:00:00
Tasks: BIG-bench Machine Learning

We explore the feasibility of using machine learning methods to obtain an analytic form of the classical free energy functional for two model fluids, hard rods and Lennard--Jones, in one dimension . The Equation Learning Network proposed in Ref. 1 is suitably modified to construct free energy densities which are functions of a set of weighted densities and which are built from a small number of basis functions with flexible combination rules. This setup considerably enlarges the functional space used in the machine learning optimization as compared to previous work 2 where the functional is limited to a simple polynomial form. As a result, we find a good approximation for the exact hard rod functional and its direct correlation function. For the Lennard--Jones fluid, we let the network learn (i) the full excess free energy functional and (ii) the excess free energy functional related to interparticle attractions. Both functionals show a good agreement with simulated density profiles for thermodynamic parameters inside and outside the training region.