pwc-archive/papers-with-abstracts huggingface dataset:
Model-free Representation Learning and Exploration in Low-rank MDPs
Authors: Aditya Modi, Jinglin Chen, Akshay Krishnamurthy, Nan Jiang, Alekh Agarwal
Date: 2021-02-14 00:00:00
Tasks: Reinforcement Learning (RL), Representation Learning

The low rank MDP has emerged as an important model for studying representation learning and exploration in reinforcement learning. With a known representation, several model-free exploration strategies exist. In contrast, all algorithms for the unknown representation setting are model-based, thereby requiring the ability to model the full dynamics. In this work, we present the first model-free representation learning algorithms for low rank MDPs. The key algorithmic contribution is a new minimax representation learning objective, for which we provide variants with differing tradeoffs in their statistical and computational properties. We interleave this representation learning step with an exploration strategy to cover the state space in a reward-free manner. The resulting algorithms are provably sample efficient and can accommodate general function approximation to scale to complex environments.
Connecting Interpretability and Robustness in Decision Trees through Separation
Authors: Michal Moshkovitz, Yao-Yuan Yang, Kamalika Chaudhuri
Date: 2021-02-14 00:00:00

Recent research has recognized interpretability and robustness as essential properties of trustworthy classification. Curiously, a connection between robustness and interpretability was empirically observed, but the theoretical reasoning behind it remained elusive. In this paper, we rigorously investigate this connection. Specifically, we focus on interpretation using decision trees and robustness to $l_{\infty}$-perturbation. Previous works defined the notion of $r$-separation as a sufficient condition for robustness. We prove upper and lower bounds on the tree size in case the data is $r$-separated. We then show that a tighter bound on the size is possible when the data is linearly separated. We provide the first algorithm with provable guarantees both on robustness, interpretability, and accuracy in the context of decision trees. Experiments confirm that our algorithm yields classifiers that are both interpretable and robust and have high accuracy. The code for the experiments is available at https://github.com/yangarbiter/interpretable-robust-trees .
Perceptually Constrained Adversarial Attacks
Authors: Muhammad Zaid Hameed, Andras Gyorgy
Date: 2021-02-14 00:00:00
Tasks: image-classification, Image Classification, SSIM

Motivated by previous observations that the usually applied $L_p$ norms ($p=1,2,\infty$) do not capture the perceptual quality of adversarial examples in image classification, we propose to replace these norms with the structural similarity index (SSIM) measure, which was developed originally to measure the perceptual similarity of images. Through extensive experiments with adversarially trained classifiers for MNIST and CIFAR-10, we demonstrate that our SSIM-constrained adversarial attacks can break state-of-the-art adversarially trained classifiers and achieve similar or larger success rate than the elastic net attack, while consistently providing adversarial images of better perceptual quality. Utilizing SSIM to automatically identify and disallow adversarial images of low quality, we evaluate the performance of several defense schemes in a perceptually much more meaningful way than was done previously in the literature.
Distribution Free Uncertainty for the Minimum Norm Solution of Over-parameterized Linear Regression
Authors: Koby Bibas, Meir Feder
Date: 2021-02-14 00:00:00
Tasks: Learning Theory, Prediction, regression

A fundamental principle of learning theory is that there is a trade-off between the complexity of a prediction rule and its ability to generalize. Modern machine learning models do not obey this paradigm: They produce an accurate prediction even with a perfect fit to the training set. We investigate over-parameterized linear regression models focusing on the minimum norm solution: This is the solution with the minimal norm that attains a perfect fit to the training set. We utilize the recently proposed predictive normalized maximum likelihood (pNML) learner which is the min-max regret solution for the distribution-free setting. We derive an upper bound of this min-max regret which is associated with the prediction uncertainty. We show that if the test sample lies mostly in a subspace spanned by the eigenvectors associated with the large eigenvalues of the empirical correlation matrix of the training data, the model generalizes despite its over-parameterized nature. We demonstrate the use of the pNML regret as a point-wise learnability measure on synthetic data and successfully observe the double-decent phenomenon of the over-parameterized models on UCI datasets.
Sample Efficient Subspace-based Representations for Nonlinear Meta-Learning
Authors: Halil Ibrahim Gulluk, Yue Sun, Samet Oymak, Maryam Fazel
Date: 2021-02-14 00:00:00
Tasks: Binary Classification, General Classification, Meta-Learning, regression

Constructing good representations is critical for learning complex tasks in a sample efficient manner. In the context of meta-learning, representations can be constructed from common patterns of previously seen tasks so that a future task can be learned quickly. While recent works show the benefit of subspace-based representations, such results are limited to linear-regression tasks. This work explores a more general class of nonlinear tasks with applications ranging from binary classification, generalized linear models and neural nets. We prove that subspace-based representations can be learned in a sample-efficient manner and provably benefit future tasks in terms of sample complexity. Numerical results verify the theoretical predictions in classification and neural-network regression tasks.
Nearly Minimax Optimal Regret for Learning Infinite-horizon Average-reward MDPs with Linear Function Approximation
Authors: Yue Wu, Dongruo Zhou, Quanquan Gu
Date: 2021-02-15 00:00:00

We study reinforcement learning in an infinite-horizon average-reward setting with linear function approximation, where the transition probability function of the underlying Markov Decision Process (MDP) admits a linear form over a feature mapping of the current state, action, and next state. We propose a new algorithm UCRL2-VTR, which can be seen as an extension of the UCRL2 algorithm with linear function approximation. We show that UCRL2-VTR with Bernstein-type bonus can achieve a regret of $\tilde{O}(d\sqrt{DT})$, where $d$ is the dimension of the feature mapping, $T$ is the horizon, and $\sqrt{D}$ is the diameter of the MDP. We also prove a matching lower bound $\tilde{\Omega}(d\sqrt{DT})$, which suggests that the proposed UCRL2-VTR is minimax optimal up to logarithmic factors. To the best of our knowledge, our algorithm is the first nearly minimax optimal RL algorithm with function approximation in the infinite-horizon average-reward setting.
Relaxation of optimal transport problem via strictly convex functions
Authors: Asuka Takatsu
Date: 2021-02-15 00:00:00

An optimal transport problem on finite spaces is a linear program. Recently, a relaxation of the optimal transport problem via strictly convex functions, especially via the Kullback--Leibler divergence, sheds new light on data sciences. This paper provides the mathematical foundations and an iterative process based on a gradient descent for the relaxed optimal transport problem via Bregman divergences.
A Near-Optimal Algorithm for Stochastic Bilevel Optimization via Double-Momentum
Authors: Prashant Khanduri, Siliang Zeng, Mingyi Hong, Hoi-To Wai, Zhaoran Wang, Zhuoran Yang
Date: 2021-02-15 00:00:00
Proceeding: NeurIPS 2021 12
Tasks: Bilevel Optimization, Hyperparameter Optimization

This paper proposes a new algorithm -- the \underline{S}ingle-timescale Do\underline{u}ble-momentum \underline{St}ochastic \underline{A}pprox\underline{i}matio\underline{n} (SUSTAIN) -- for tackling stochastic unconstrained bilevel optimization problems. We focus on bilevel problems where the lower level subproblem is strongly-convex and the upper level objective function is smooth. Unlike prior works which rely on \emph{two-timescale} or \emph{double loop} techniques, we design a stochastic momentum-assisted gradient estimator for both the upper and lower level updates. The latter allows us to control the error in the stochastic gradient updates due to inaccurate solution to both subproblems. If the upper objective function is smooth but possibly non-convex, we show that {\aname}~requires $\mathcal{O}(\epsilon^{-3/2})$ iterations (each using ${\cal O}(1)$ samples) to find an $\epsilon$-stationary solution. The $\epsilon$-stationary solution is defined as the point whose squared norm of the gradient of the outer function is less than or equal to $\epsilon$. The total number of stochastic gradient samples required for the upper and lower level objective functions matches the best-known complexity for single-level stochastic gradient algorithms. We also analyze the case when the upper level objective function is strongly-convex.
Almost Optimal Algorithms for Two-player Zero-Sum Linear Mixture Markov Games
Authors: Zixiang Chen, Dongruo Zhou, Quanquan Gu
Date: 2021-02-15 00:00:00

We study reinforcement learning for two-player zero-sum Markov games with simultaneous moves in the finite-horizon setting, where the transition kernel of the underlying Markov games can be parameterized by a linear function over the current state, both players' actions and the next state. In particular, we assume that we can control both players and aim to find the Nash Equilibrium by minimizing the duality gap. We propose an algorithm Nash-UCRL based on the principle "Optimism-in-Face-of-Uncertainty". Our algorithm only needs to find a Coarse Correlated Equilibrium (CCE), which is computationally efficient. Specifically, we show that Nash-UCRL can provably achieve an $\tilde{O}(dH\sqrt{T})$ regret, where $d$ is the linear function dimension, $H$ is the length of the game and $T$ is the total number of steps in the game. To assess the optimality of our algorithm, we also prove an $\tilde{\Omega}( dH\sqrt{T})$ lower bound on the regret. Our upper bound matches the lower bound up to logarithmic factors, which suggests the optimality of our algorithm.
Distributed Online Learning for Joint Regret with Communication Constraints
Authors: Dirk van der Hoeven, Hédi Hadiji, Tim van Erven
Date: 2021-02-15 00:00:00

We consider distributed online learning for joint regret with communication constraints. In this setting, there are multiple agents that are connected in a graph. Each round, an adversary first activates one of the agents to issue a prediction and provides a corresponding gradient, and then the agents are allowed to send a $b$-bit message to their neighbors in the graph. All agents cooperate to control the joint regret, which is the sum of the losses of the activated agents minus the losses evaluated at the best fixed common comparator parameters $u$. We observe that it is suboptimal for agents to wait for gradients that take too long to arrive. Instead, the graph should be partitioned into local clusters that communicate among themselves. Our main result is a new method that can adapt to the optimal graph partition for the adversarial activations and gradients, where the graph partition is selected from a set of candidate partitions. A crucial building block along the way is a new algorithm for online convex optimization with delayed gradient information that is comparator-adaptive, meaning that its joint regret scales with the norm of the comparator $||u||$. We further provide near-optimal gradient compression schemes depending on the ratio of $b$ and the dimension times the diameter of the graph.
A generalized quadratic loss for SVM and Deep Neural Networks
Authors: Filippo Portera
Date: 2021-02-15 00:00:00
Tasks: Binary Classification, regression

We consider some supervised binary classification tasks and a regression task, whereas SVM and Deep Learning, at present, exhibit the best generalization performances. We extend the work [3] on a generalized quadratic loss for learning problems that examines pattern correlations in order to concentrate the learning problem into input space regions where patterns are more densely distributed. From a shallow methods point of view (e.g.: SVM), since the following mathematical derivation of problem (9) in [3] is incorrect, we restart from problem (8) in [3] and we try to solve it with one procedure that iterates over the dual variables until the primal and dual objective functions converge. In addition we propose another algorithm that tries to solve the classification problem directly from the primal problem formulation. We make also use of Multiple Kernel Learning to improve generalization performances. Moreover, we introduce for the first time a custom loss that takes in consideration pattern correlation for a shallow and a Deep Learning task. We propose some pattern selection criteria and the results on 4 UCI data-sets for the SVM method. We also report the results on a larger binary classification data-set based on Twitter, again drawn from UCI, combined with shallow Learning Neural Networks, with and without the generalized quadratic loss. At last, we test our loss with a Deep Neural Network within a larger regression task taken from UCI. We compare the results of our optimizers with the well known solver SVMlight and with Keras Multi-Layers Neural Networks with standard losses and with a parameterized generalized quadratic loss, and we obtain comparable results.
Goal-oriented adaptive sampling under random field modelling of response probability distributions
Authors: Athénaïs Gautier, David Ginsbourger, Guillaume Pirot
Date: 2021-02-15 00:00:00

In the study of natural and artificial complex systems, responses that are not completely determined by the considered decision variables are commonly modelled probabilistically, resulting in response distributions varying across decision space. We consider cases where the spatial variation of these response distributions does not only concern their mean and/or variance but also other features including for instance shape or uni-modality versus multi-modality. Our contributions build upon a non-parametric Bayesian approach to modelling the thereby induced fields of probability distributions, and in particular to a spatial extension of the logistic Gaussian model. The considered models deliver probabilistic predictions of response distributions at candidate points, allowing for instance to perform (approximate) posterior simulations of probability density functions, to jointly predict multiple moments and other functionals of target distributions, as well as to quantify the impact of collecting new samples on the state of knowledge of the distribution field of interest. In particular, we introduce adaptive sampling strategies leveraging the potential of the considered random distribution field models to guide system evaluations in a goal-oriented way, with a view towards parsimoniously addressing calibration and related problems from non-linear (stochastic) inversion and global optimisation.
Multimodal Data Visualization and Denoising with Integrated Diffusion
Authors: Manik Kuchroo, Abhinav Godavarthi, Alexander Tong, Guy Wolf, Smita Krishnaswamy
Date: 2021-02-12 00:00:00
Tasks: Clustering, Data Visualization, Denoising

We propose a method called integrated diffusion for combining multimodal datasets, or data gathered via several different measurements on the same system, to create a joint data diffusion operator. As real world data suffers from both local and global noise, we introduce mechanisms to optimally calculate a diffusion operator that reflects the combined information from both modalities. We show the utility of this joint operator in data denoising, visualization and clustering, performing better than other methods to integrate and analyze multimodal data. We apply our method to multi-omic data generated from blood cells, measuring both gene expression and chromatin accessibility. Our approach better visualizes the geometry of the joint data, captures known cross-modality associations and identifies known cellular populations. More generally, integrated diffusion is broadly applicable to multimodal datasets generated in many medical and biological systems.
On automatic extraction of on-street parking spaces using park-out events data
Authors: J. -Emeterio Navarro-B, Martin Gebert, Ralf Bielig
Date: 2021-02-12 00:00:00
Tasks: valid

This article proposes two different approaches to automatically create a map for valid on-street car parking spaces. For this, we use car sharing park-out events data. The first one uses spatial aggregation and the second a machine learning algorithm. For the former, we chose rasterization and road sectioning; for the latter we chose decision trees. We compare the results of these approaches and discuss their advantages and disadvantages. Furthermore, we show our results for a neighborhood in the city of Berlin and report a classification accuracy of 91.6\% on the original imbalanced data. Finally, we discuss further work; from gathering more data over a longer period of time to fitting spatial Gaussian densities to the data and the usage of apps for manual validation and annotation of parking spaces to improve ground truth data.
Stochastic Gradient Langevin Dynamics with Variance Reduction
Authors: Zhishen Huang, Stephen Becker
Date: 2021-02-12 00:00:00
Tasks: global-optimization

Stochastic gradient Langevin dynamics (SGLD) has gained the attention of optimization researchers due to its global optimization properties. This paper proves an improved convergence property to local minimizers of nonconvex objective functions using SGLD accelerated by variance reductions. Moreover, we prove an ergodicity property of the SGLD scheme, which gives insights on its potential to find global minimizers of nonconvex objectives.
Generalizing Decision Making for Automated Driving with an Invariant Environment Representation using Deep Reinforcement Learning
Authors: Karl Kurzer, Philip Schörner, Alexander Albers, Hauke Thomsen, Karam Daaboul, J. Marius Zöllner
Date: 2021-02-12 00:00:00
Tasks: Decision Making, Deep Reinforcement Learning, Navigate

Data driven approaches for decision making applied to automated driving require appropriate generalization strategies, to ensure applicability to the world's variability. Current approaches either do not generalize well beyond the training data or are not capable to consider a variable number of traffic participants. Therefore we propose an invariant environment representation from the perspective of the ego vehicle. The representation encodes all necessary information for safe decision making. To assess the generalization capabilities of the novel environment representation, we train our agents on a small subset of scenarios and evaluate on the entire diverse set of scenarios. Here we show that the agents are capable to generalize successfully to unseen scenarios, due to the abstraction. In addition we present a simple occlusion model that enables our agents to navigate intersections with occlusions without a significant change in performance.
Machine Learning for Mechanical Ventilation Control
Authors: Daniel Suo, Naman Agarwal, Wenhan Xia, Xinyi Chen, Udaya Ghai, Alexander Yu, Paula Gradu, Karan Singh, Cyril Zhang, Edgar Minasyan, Julienne LaChance, Tom Zajdel, Manuel Schottdorf, Daniel Cohen, Elad Hazan
Date: 2021-02-12 00:00:00
Tasks: BIG-bench Machine Learning

We consider the problem of controlling an invasive mechanical ventilator for pressure-controlled ventilation: a controller must let air in and out of a sedated patient's lungs according to a trajectory of airway pressures specified by a clinician. Hand-tuned PID controllers and similar variants have comprised the industry standard for decades, yet can behave poorly by over- or under-shooting their target or oscillating rapidly. We consider a data-driven machine learning approach: First, we train a simulator based on data we collect from an artificial lung. Then, we train deep neural network controllers on these simulators.We show that our controllers are able to track target pressure waveforms significantly better than PID controllers. We further show that a learned controller generalizes across lungs with varying characteristics much more readily than PID controllers do.
Q-Value Weighted Regression: Reinforcement Learning with Limited Data
Authors: Piotr Kozakowski, Łukasz Kaiser, Henryk Michalewski, Afroz Mohiuddin, Katarzyna Kańska
Date: 2021-02-12 00:00:00
Tasks: Atari Games, continuous-control, Continuous Control, Deep Reinforcement Learning, MuJoCo, Offline RL, regression, reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

Sample efficiency and performance in the offline setting have emerged as significant challenges of deep reinforcement learning. We introduce Q-Value Weighted Regression (QWR), a simple RL algorithm that excels in these aspects. QWR is an extension of Advantage Weighted Regression (AWR), an off-policy actor-critic algorithm that performs very well on continuous control tasks, also in the offline setting, but has low sample efficiency and struggles with high-dimensional observation spaces. We perform an analysis of AWR that explains its shortcomings and use these insights to motivate QWR. We show experimentally that QWR matches the state-of-the-art algorithms both on tasks with continuous and discrete actions. In particular, QWR yields results on par with SAC on the MuJoCo suite and - with the same set of hyperparameters - yields results on par with a highly tuned Rainbow implementation on a set of Atari games. We also verify that QWR performs well in the offline RL setting.
Hybrid Artificial Intelligence Methods for Predicting Air Demand in Dam Bottom Outlet
Authors: Aliakbar Narimani, Mahdi Moghimi, Amir Mosavi
Date: 2021-02-13 00:00:00

In large infrastructures such as dams, which have a relatively high economic value, ensuring the proper operation of the associated hydraulic facilities in different operating conditions is of utmost importance. To ensure the correct and successful operation of the dam's hydraulic equipment and prevent possible damages, including gates and downstream tunnel, to build laboratory models and perform some tests are essential (the advancement of the smart sensors based on artificial intelligence is essential). One of the causes of damage to dam bottom outlets is cavitation in downstream and between the gates, which can impact on dam facilities, and air aeration can be a solution to improve it. In the present study, six dams in different provinces in Iran has been chosen to evaluate the air entrainment in the downstream tunnel experimentally. Three artificial neural networks (ANN) based machine learning (ML) algorithms are used to model and predict the air aeration in the bottom outlet. The proposed models are trained with genetic algorithms (GA), particle swarm optimization (PSO), i.e., ANN-GA, ANN-PSO, and ANFIS-PSO. Two hydrodynamic variables, namely volume rate and opening percentage of the gate, are used as inputs into all bottom outlet models. The results showed that the most optimal model is ANFIS-PSO to predict the dependent value compared with ANN-GA and ANN-PSO. The importance of the volume rate and opening percentage of the dams' gate parameters is more effective for suitable air aeration.