pwc-archive/papers-with-abstracts huggingface dataset:
Generalization Bounds for Meta-Learning via PAC-Bayes and Uniform Stability
Authors: Alec Farid, Anirudha Majumdar
Date: 2021-02-12 00:00:00
Proceeding: NeurIPS 2021 12
Tasks: Generalization Bounds, Meta-Learning

We are motivated by the problem of providing strong generalization guarantees in the context of meta-learning. Existing generalization bounds are either challenging to evaluate or provide vacuous guarantees in even relatively simple settings. We derive a probably approximately correct (PAC) bound for gradient-based meta-learning using two different generalization frameworks in order to deal with the qualitatively different challenges of generalization at the "base" and "meta" levels. We employ bounds for uniformly stable algorithms at the base level and bounds from the PAC-Bayes framework at the meta level. The result of this approach is a novel PAC bound that is tighter when the base learner adapts quickly, which is precisely the goal of meta-learning. We show that our bound provides a tighter guarantee than other bounds on a toy non-convex problem on the unit sphere and a text-based classification example. We also present a practical regularization scheme motivated by the bound in settings where the bound is loose and demonstrate improved performance over baseline techniques.
Disturbing Reinforcement Learning Agents with Corrupted Rewards
Authors: Rubén Majadas, Javier García, Fernando Fernández
Date: 2021-02-12 00:00:00
Tasks: Autonomous Driving, reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL), Starcraft

Reinforcement Learning (RL) algorithms have led to recent successes in solving complex games, such as Atari or Starcraft, and to a huge impact in real-world applications, such as cybersecurity or autonomous driving. In the side of the drawbacks, recent works have shown how the performance of RL algorithms decreases under the influence of soft changes in the reward function. However, little work has been done about how sensitive these disturbances are depending on the aggressiveness of the attack and the learning exploration strategy. In this paper, we propose to fill this gap in the literature analyzing the effects of different attack strategies based on reward perturbations, and studying the effect in the learner depending on its exploration strategy. In order to explain all the behaviors, we choose a sub-class of MDPs: episodic, stochastic goal-only-rewards MDPs, and in particular, an intelligible grid domain as a benchmark. In this domain, we demonstrate that smoothly crafting adversarial rewards are able to mislead the learner, and that using low exploration probability values, the policy learned is more robust to corrupt rewards. Finally, in the proposed learning scenario, a counterintuitive result arises: attacking at each learning episode is the lowest cost attack strategy.
Linear programming approach to nonparametric inference under shape restrictions: with an application to regression kink designs
Authors: Harold D. Chiang, Kengo Kato, Yuya Sasaki, Takuya Ura
Date: 2021-02-12 00:00:00
Tasks: regression

We develop a novel method of constructing confidence bands for nonparametric regression functions under shape constraints. This method can be implemented via a linear programming, and it is thus computationally appealing. We illustrate a usage of our proposed method with an application to the regression kink design (RKD). Econometric analyses based on the RKD often suffer from wide confidence intervals due to slow convergence rates of nonparametric derivative estimators. We demonstrate that economic models and structures motivate shape restrictions, which in turn contribute to shrinking the confidence interval for an analysis of the causal effects of unemployment insurance benefits on unemployment durations.
A Computability Perspective on (Verified) Machine Learning
Authors: Tonicha Crook, Jay Morgan, Arno Pauly, Markus Roggenbach
Date: 2021-02-12 00:00:00
Tasks: BIG-bench Machine Learning

There is a strong consensus that combining the versatility of machine learning with the assurances given by formal verification is highly desirable. It is much less clear what verified machine learning should mean exactly. We consider this question from the (unexpected?) perspective of computable analysis. This allows us to define the computational tasks underlying verified ML in a model-agnostic way, and show that they are in principle computable.
Reviving Iterative Training with Mask Guidance for Interactive Segmentation
Authors: Konstantin Sofiiuk, Ilia A. Petrov, Anton Konushin
Date: 2021-02-12 00:00:00
Tasks: Interactive Segmentation, Segmentation

Recent works on click-based interactive segmentation have demonstrated state-of-the-art results by using various inference-time optimization schemes. These methods are considerably more computationally expensive compared to feedforward approaches, as they require performing backward passes through a network during inference and are hard to deploy on mobile frameworks that usually support only forward passes. In this paper, we extensively evaluate various design choices for interactive segmentation and discover that new state-of-the-art results can be obtained without any additional optimization schemes. Thus, we propose a simple feedforward model for click-based interactive segmentation that employs the segmentation masks from previous steps. It allows not only to segment an entirely new object, but also to start with an external mask and correct it. When analyzing the performance of models trained on different datasets, we observe that the choice of a training dataset greatly impacts the quality of interactive segmentation. We find that the models trained on a combination of COCO and LVIS with diverse and high-quality annotations show performance superior to all existing models. The code and trained models are available at https://github.com/saic-vul/ritm_interactive_segmentation.
Improving Zero-shot Neural Machine Translation on Language-specific Encoders-Decoders
Authors: Junwei Liao, Yu Shi, Ming Gong, Linjun Shou, Hong Qu, Michael Zeng
Date: 2021-02-12 00:00:00
Tasks: Decoder, Denoising, Machine Translation, NMT, Translation

Recently, universal neural machine translation (NMT) with shared encoder-decoder gained good performance on zero-shot translation. Unlike universal NMT, jointly trained language-specific encoders-decoders aim to achieve universal representation across non-shared modules, each of which is for a language or language family. The non-shared architecture has the advantage of mitigating internal language competition, especially when the shared vocabulary and model parameters are restricted in their size. However, the performance of using multiple encoders and decoders on zero-shot translation still lags behind universal NMT. In this work, we study zero-shot translation using language-specific encoders-decoders. We propose to generalize the non-shared architecture and universal NMT by differentiating the Transformer layers between language-specific and interlingua. By selectively sharing parameters and applying cross-attentions, we explore maximizing the representation universality and realizing the best alignment of language-agnostic information. We also introduce a denoising auto-encoding (DAE) objective to jointly train the model with the translation task in a multi-task manner. Experiments on two public multilingual parallel datasets show that our proposed model achieves a competitive or better results than universal NMT and strong pivot baseline. Moreover, we experiment incrementally adding new language to the trained model by only updating the new model parameters. With this little effort, the zero-shot translation between this newly added language and existing languages achieves a comparable result with the model trained jointly from scratch on all languages.
Shrinkage Bayesian Causal Forests for Heterogeneous Treatment Effects Estimation
Authors: Alberto Caron, Gianluca Baio, Ioanna Manolopoulou
Date: 2021-02-12 00:00:00
Tasks: regression, Variable Selection

This paper develops a sparsity-inducing version of Bayesian Causal Forests, a recently proposed nonparametric causal regression model that employs Bayesian Additive Regression Trees and is specifically designed to estimate heterogeneous treatment effects using observational data. The sparsity-inducing component we introduce is motivated by empirical studies where not all the available covariates are relevant, leading to different degrees of sparsity underlying the surfaces of interest in the estimation of individual treatment effects. The extended version presented in this work, which we name Shrinkage Bayesian Causal Forest, is equipped with an additional pair of priors allowing the model to adjust the weight of each covariate through the corresponding number of splits in the tree ensemble. These priors improve the model's adaptability to sparse data generating processes and allow to perform fully Bayesian feature shrinkage in a framework for treatment effects estimation, and thus to uncover the moderating factors driving heterogeneity. In addition, the method allows prior knowledge about the relevant confounding covariates and the relative magnitude of their impact on the outcome to be incorporated in the model. We illustrate the performance of our method in simulated studies, in comparison to Bayesian Causal Forest and other state-of-the-art models, to demonstrate how it scales up with an increasing number of covariates and how it handles strongly confounded scenarios. Finally, we also provide an example of application using real-world data.
Bayesian Neural Network Priors Revisited
Authors: Vincent Fortuin, Adrià Garriga-Alonso, Sebastian W. Ober, Florian Wenzel, Gunnar Rätsch, Richard E. Turner, Mark van der Wilk, Laurence Aitchison
Date: 2021-02-12 00:00:00
Proceeding: NeurIPS Workshop ICBINB 2020 12
Tasks: image-classification, Image Classification

Isotropic Gaussian priors are the de facto standard for modern Bayesian neural network inference. However, it is unclear whether these priors accurately reflect our true beliefs about the weight distributions or give optimal performance. To find better priors, we study summary statistics of neural network weights in networks trained using stochastic gradient descent (SGD). We find that convolutional neural network (CNN) and ResNet weights display strong spatial correlations, while fully connected networks (FCNNs) display heavy-tailed weight distributions. We show that building these observations into priors can lead to improved performance on a variety of image classification datasets. Surprisingly, these priors mitigate the cold posterior effect in FCNNs, but slightly increase the cold posterior effect in ResNets.
Analysis of Interpolation based Image In-painting Approaches
Authors: Mustafa Zor, Erkan Bostanci, Mehmet Serdar Guzel, Erinc Karatas
Date: 2021-02-12 00:00:00
Tasks: SSIM

Interpolation and internal painting are one of the basic approaches in image internal painting, which is used to eliminate undesirable parts that occur in digital images or to enhance faulty parts. This study was designed to compare the interpolation algorithms used in image in-painting in the literature. Errors and noise generated on the colour and grayscale formats of some of the commonly used standard images in the literature were corrected by using Cubic, Kriging, Radial based function and High dimensional model representation approaches and the results were compared using standard image comparison criteria, namely, PSNR (peak signal-to-noise ratio), SSIM (Structural SIMilarity), Mean Square Error (MSE). According to the results obtained from the study, the absolute superiority of the methods against each other was not observed. However, Kriging and RBF interpolation give better results both for numerical data and visual evaluation for image in-painting problems with large area losses.
How Far Should We Look Back to Achieve Effective Real-Time Time-Series Anomaly Detection?
Authors: Ming-Chang Lee, Jia-Chun Lin, Ernst Gunnar Gran
Date: 2021-02-12 00:00:00
Tasks: Anomaly Detection, Fraud Detection, Intrusion Detection, Time Series, Time Series Analysis, Time Series Anomaly Detection

Anomaly detection is the process of identifying unexpected events or ab-normalities in data, and it has been applied in many different areas such as system monitoring, fraud detection, healthcare, intrusion detection, etc. Providing real-time, lightweight, and proactive anomaly detection for time series with neither human intervention nor domain knowledge could be highly valuable since it reduces human effort and enables appropriate countermeasures to be undertaken before a disastrous event occurs. To our knowledge, RePAD (Real-time Proactive Anomaly Detection algorithm) is a generic approach with all above-mentioned features. To achieve real-time and lightweight detection, RePAD utilizes Long Short-Term Memory (LSTM) to detect whether or not each upcoming data point is anomalous based on short-term historical data points. However, it is unclear that how different amounts of historical data points affect the performance of RePAD. Therefore, in this paper, we investigate the impact of different amounts of historical data on RePAD by introducing a set of performance metrics that cover novel detection accuracy measures, time efficiency, readiness, and resource consumption, etc. Empirical experiments based on real-world time series datasets are conducted to evaluate RePAD in different scenarios, and the experimental results are presented and discussed.
Infinitely Deep Bayesian Neural Networks with Stochastic Differential Equations
Authors: Winnie Xu, Ricky T. Q. Chen, Xuechen Li, David Duvenaud
Date: 2021-02-12 00:00:00
Tasks: Variational Inference

We perform scalable approximate inference in continuous-depth Bayesian neural networks. In this model class, uncertainty about separate weights in each layer gives hidden units that follow a stochastic differential equation. We demonstrate gradient-based stochastic variational inference in this infinite-parameter setting, producing arbitrarily-flexible approximate posteriors. We also derive a novel gradient estimator that approaches zero variance as the approximate posterior over weights approaches the true posterior. This approach brings continuous-depth Bayesian neural nets to a competitive comparison against discrete-depth alternatives, while inheriting the memory-efficient training and tunable precision of Neural ODEs.
Continuous Learning in Neural Machine Translation using Bilingual Dictionaries
Authors: Jan Niehues
Date: 2021-02-12 00:00:00
Proceeding: EACL 2021 2
Tasks: LEMMA, Machine Translation, One-Shot Learning, Translation

While recent advances in deep learning led to significant improvements in machine translation, neural machine translation is often still not able to continuously adapt to the environment. For humans, as well as for machine translation, bilingual dictionaries are a promising knowledge source to continuously integrate new knowledge. However, their exploitation poses several challenges: The system needs to be able to perform one-shot learning as well as model the morphology of source and target language. In this work, we proposed an evaluation framework to assess the ability of neural machine translation to continuously learn new phrases. We integrate one-shot learning methods for neural machine translation with different word representations and show that it is important to address both in order to successfully make use of bilingual dictionaries. By addressing both challenges we are able to improve the ability to translate new, rare words and phrases from 30% to up to 70%. The correct lemma is even generated by more than 90%.
Online Graph Dictionary Learning
Authors: Cédric Vincent-Cuaz, Titouan Vayer, Rémi Flamary, Marco Corneli, Nicolas Courty
Date: 2021-02-12 00:00:00
Tasks: Dictionary Learning, Graph Classification, Graph Learning, Representation Learning

Dictionary learning is a key tool for representation learning, that explains the data as linear combination of few basic elements. Yet, this analysis is not amenable in the context of graph learning, as graphs usually belong to different metric spaces. We fill this gap by proposing a new online Graph Dictionary Learning approach, which uses the Gromov Wasserstein divergence for the data fitting term. In our work, graphs are encoded through their nodes' pairwise relations and modeled as convex combination of graph atoms, i.e. dictionary elements, estimated thanks to an online stochastic algorithm, which operates on a dataset of unregistered graphs with potentially different number of nodes. Our approach naturally extends to labeled graphs, and is completed by a novel upper bound that can be used as a fast approximation of Gromov Wasserstein in the embedding space. We provide numerical evidences showing the interest of our approach for unsupervised embedding of graph datasets and for online graph subspace estimation and tracking.
Exploiting Spline Models for the Training of Fully Connected Layers in Neural Network
Authors: Kanya Mo, Shen Zheng, Xiwei Wang, Jinghua Wang, Klaus-Dieter Schewe
Date: 2021-02-12 00:00:00

The fully connected (FC) layer, one of the most fundamental modules in artificial neural networks (ANN), is often considered difficult and inefficient to train due to issues including the risk of overfitting caused by its large amount of parameters. Based on previous work studying ANN from linear spline perspectives, we propose a spline-based approach that eases the difficulty of training FC layers. Given some dataset, we first obtain a continuous piece-wise linear (CPWL) fit through spline methods such as multivariate adaptive regression spline (MARS). Next, we construct an ANN model from the linear spline model and continue to train the ANN model on the dataset using gradient descent optimization algorithms. Our experimental results and theoretical analysis show that our approach reduces the computational cost, accelerates the convergence of FC layers, and significantly increases the interpretability of the resulting model (FC layers) compared with standard ANN training with random parameter initialization followed by gradient descent optimizations.
From System Level Synthesis to Robust Closed-loop Data-enabled Predictive Control
Authors: Yinghao Lian, Colin N. Jones
Date: 2021-02-12 00:00:00
Tasks: LEMMA, valid

The Willems' fundamental lemma and the system level synthesis characterize trajectories generated by a linear system. While the former method is valid for deterministic LTI systems, the latter one is further effective for stochastic linear time varying systems. In this paper, these two methods offers equivalent characterization of stochastic LTI systems. Inspired by this observation, a robust closed-loop data-enabled predictive control scheme is proposed for stochastic LTI systems. A causal feedback structure is further derived, leading to an computational cost similar to standard robust MPC with full state measurements. The proposed method is validated by a second order system a single-zone building control problem.
Like Attract Like? A Structural Comparison of Homogamy across Same-Sex and Different-Sex Households
Authors: Edoardo Ciscato, Alfred Galichon, Marion Goussé
Date: 2021-02-12 00:00:00

In this paper, we extend Gary Becker's empirical analysis of the marriage market to same-sex couples. Becker's theory rationalizes the well-known phenomenon of homogamy among different-sex couples: individuals mate with their likes because many characteristics, such as education, consumption behaviour, desire to nurture children, religion, etc., exhibit strong complementarities in the household production function. However, because of asymmetries in the distributions of male and female characteristics, men and women may need to marry "up" or "down" according to the relative shortage of their characteristics among the populations of men and women. Yet, among same-sex couples, this limitation does not exist as partners are drawn from the same population, and thus the theory of assortative mating would boldly predict that individuals will choose a partner with nearly identical characteristics. Empirical evidence suggests a very different picture: a robust stylized fact is that the correlation of the characteristics is in fact weaker among same-sex couples. In this paper, we build an equilibrium model of same-sex marriage market which allows for straightforward identification of the gains to marriage. We estimate the model with 2008-2012 ACS data on California and show that positive assortative mating is weaker for homosexuals than for heterosexuals with respect to age and race. Our results suggest that positive assortative mating with respect to education is stronger among lesbians, and not significantly different when comparing gay men and married different-sex couples. As regards labor market outcomes, such as hourly wages and working hours, we find some indications that the process of specialization within the household mainly applies to different-sex couples.
Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysis
Authors: Gen Li, Changxiao Cai, Yuxin Chen, Yuting Wei, Yuejie Chi
Date: 2021-02-12 00:00:00
Tasks: Natural Questions, Q-Learning

Q-learning, which seeks to learn the optimal Q-function of a Markov decision process (MDP) in a model-free fashion, lies at the heart of reinforcement learning. When it comes to the synchronous setting (such that independent samples for all state-action pairs are drawn from a generative model in each iteration), substantial progress has been made towards understanding the sample efficiency of Q-learning. Consider a $\gamma$-discounted infinite-horizon MDP with state space $\mathcal{S}$ and action space $\mathcal{A}$: to yield an entrywise $\varepsilon$-approximation of the optimal Q-function, state-of-the-art theory for Q-learning requires a sample size exceeding the order of $\frac{|\mathcal{S}||\mathcal{A}|}{(1-\gamma)^5\varepsilon^{2}}$, which fails to match existing minimax lower bounds. This gives rise to natural questions: what is the sharp sample complexity of Q-learning? Is Q-learning provably sub-optimal? This paper addresses these questions for the synchronous setting: (1) when $|\mathcal{A}|=1$ (so that Q-learning reduces to TD learning), we prove that the sample complexity of TD learning is minimax optimal and scales as $\frac{|\mathcal{S}|}{(1-\gamma)^3\varepsilon^2}$ (up to log factor); (2) when $|\mathcal{A}|\geq 2$, we settle the sample complexity of Q-learning to be on the order of $\frac{|\mathcal{S}||\mathcal{A}|}{(1-\gamma)^4\varepsilon^2}$ (up to log factor). Our theory unveils the strict sub-optimality of Q-learning when $|\mathcal{A}|\geq 2$, and rigorizes the negative impact of over-estimation in Q-learning. Finally, we extend our analysis to accommodate asynchronous Q-learning (i.e., the case with Markovian samples), sharpening the horizon dependency of its sample complexity to be $\frac{1}{(1-\gamma)^4}$.
Computing Betweenness Centrality in Link Streams
Authors: Frédéric Simard, Clémence Magnien, Matthieu Latapy
Date: 2021-02-12 00:00:00

Betweeness centrality is one of the most important concepts in graph analysis. It was recently extended to link streams, a graph generalization where links arrive over time. However, its computation raises non-trivial issues, due in particular to the fact that time is considered as continuous. We provide here the first algorithms to compute this generalized betweenness centrality, as well as several companion algorithms that have their own interest. They work in polynomial time and space, we illustrate them on typical examples, and we provide an implementation.