pwc-archive/papers-with-abstracts huggingface dataset:
Understanding and Accelerating Neural Architecture Search with Training-Free and Theory-Grounded Metrics
Authors: Wuyang Chen, Xinyu Gong, Junru Wu, Yunchao Wei, Humphrey Shi, Zhicheng Yan, Yi Yang, Zhangyang Wang
Date: 2021-08-26 00:00:00
Tasks: Neural Architecture Search

This work targets designing a principled and unified training-free framework for Neural Architecture Search (NAS), with high performance, low cost, and in-depth interpretation. NAS has been explosively studied to automate the discovery of top-performer neural networks, but suffers from heavy resource consumption and often incurs search bias due to truncated training or approximations. Recent NAS works start to explore indicators that can predict a network's performance without training. However, they either leveraged limited properties of deep networks, or the benefits of their training-free indicators are not applied to more extensive search methods. By rigorous correlation analysis, we present a unified framework to understand and accelerate NAS, by disentangling "TEG" characteristics of searched networks - Trainability, Expressivity, Generalization - all assessed in a training-free manner. The TEG indicators could be scaled up and integrated with various NAS search methods, including both supernet and single-path approaches. Extensive studies validate the effective and efficient guidance from our TEG-NAS framework, leading to both improved search accuracy and over 56% reduction in search time cost. Moreover, we visualize search trajectories on three landscapes of "TEG" characteristics, observing that while a good local minimum is easier to find on NAS-Bench-201 given its simple topology, balancing "TEG" characteristics is much harder on the DARTS search space due to its complex landscape geometry. Our code is available at https://github.com/VITA-Group/TEGNAS.
Enabling SQL-based Training Data Debugging for Federated Learning
Authors: Yejia Liu, Weiyuan Wu, Lampros Flokas, Jiannan Wang, Eugene Wu
Date: 2021-08-26 00:00:00
Tasks: Federated Learning

How can we debug a logistical regression model in a federated learning setting when seeing the model behave unexpectedly (e.g., the model rejects all high-income customers' loan applications)? The SQL-based training data debugging framework has proved effective to fix this kind of issue in a non-federated learning setting. Given an unexpected query result over model predictions, this framework automatically removes the label errors from training data such that the unexpected behavior disappears in the retrained model. In this paper, we enable this powerful framework for federated learning. The key challenge is how to develop a security protocol for federated debugging which is proved to be secure, efficient, and accurate. Achieving this goal requires us to investigate how to seamlessly integrate the techniques from multiple fields (Databases, Machine Learning, and Cybersecurity). We first propose FedRain, which extends Rain, the state-of-the-art SQL-based training data debugging framework, to our federated learning setting. We address several technical challenges to make FedRain work and analyze its security guarantee and time complexity. The analysis results show that FedRain falls short in terms of both efficiency and security. To overcome these limitations, we redesign our security protocol and propose Frog, a novel SQL-based training data debugging framework tailored for federated learning. Our theoretical analysis shows that Frog is more secure, more accurate, and more efficient than FedRain. We conduct extensive experiments using several real-world datasets and a case study. The experimental results are consistent with our theoretical analysis and validate the effectiveness of Frog in practice.
DSKReG: Differentiable Sampling on Knowledge Graph for Recommendation with Relational GNN
Authors: Yu Wang, Zhiwei Liu, Ziwei Fan, Lichao Sun, Philip S. Yu
Date: 2021-08-26 00:00:00
Tasks: Knowledge Graphs, Recommendation Systems

In the information explosion era, recommender systems (RSs) are widely studied and applied to discover user-preferred information. A RS performs poorly when suffering from the cold-start issue, which can be alleviated if incorporating Knowledge Graphs (KGs) as side information. However, most existing works neglect the facts that node degrees in KGs are skewed and massive amount of interactions in KGs are recommendation-irrelevant. To address these problems, in this paper, we propose Differentiable Sampling on Knowledge Graph for Recommendation with Relational GNN (DSKReG) that learns the relevance distribution of connected items from KGs and samples suitable items for recommendation following this distribution. We devise a differentiable sampling strategy, which enables the selection of relevant items to be jointly optimized with the model training procedure. The experimental results demonstrate that our model outperforms state-of-the-art KG-based recommender systems. The code is available online at https://github.com/YuWang-1024/DSKReG.
A spatio-temporal LSTM model to forecast across multiple temporal and spatial scales
Authors: Yihao Hu, Fearghal O'Donncha, Paulito Palmes, Meredith Burke, Ramon Filgueira, Jon Grant
Date: 2021-08-26 00:00:00
Tasks: Missing Values, Time Series Analysis, Time Series Forecasting

This paper presents a novel spatio-temporal LSTM (SPATIAL) architecture for time series forecasting applied to environmental datasets. The framework was evaluated across multiple sensors and for three different oceanic variables: current speed, temperature, and dissolved oxygen. Network implementation proceeded in two directions that are nominally separated but connected as part of a natural environmental system -- across the spatial (between individual sensors) and temporal components of the sensor data. Data from four sensors sampling current speed, and eight measuring both temperature and dissolved oxygen evaluated the framework. Results were compared against RF and XGB baseline models that learned on the temporal signal of each sensor independently by extracting the date-time features together with the past history of data using sliding window matrix. Results demonstrated ability to accurately replicate complex signals and provide comparable performance to state-of-the-art benchmarks. Notably, the novel framework provided a simpler pre-processing and training pipeline that handles missing values via a simple masking layer. Enabling learning across the spatial and temporal directions, this paper addresses two fundamental challenges of ML applications to environmental science: 1) data sparsity and the challenges and costs of collecting measurements of environmental conditions such as ocean dynamics, and 2) environmental datasets are inherently connected in the spatial and temporal directions while classical ML approaches only consider one of these directions. Furthermore, sharing of parameters across all input steps makes SPATIAL a fast, scalable, and easily-parameterized forecasting framework.
Comparing Classes of Estimators: When does Gradient Descent Beat Ridge Regression in Linear Models?
Authors: Dominic Richards, Edgar Dobriban, Patrick Rebeschini
Date: 2021-08-26 00:00:00
Tasks: regression, Unity

Methods for learning from data depend on various types of tuning parameters, such as penalization strength or step size. Since performance can depend strongly on these parameters, it is important to compare classes of estimators-by considering prescribed finite sets of tuning parameters-not just particularly tuned methods. In this work, we investigate classes of methods via the relative performance of the best method in the class. We consider the central problem of linear regression-with a random isotropic ground truth-and investigate the estimation performance of two fundamental methods, gradient descent and ridge regression. We unveil the following phenomena. (1) For general designs, constant stepsize gradient descent outperforms ridge regression when the eigenvalues of the empirical data covariance matrix decay slowly, as a power law with exponent less than unity. If instead the eigenvalues decay quickly, as a power law with exponent greater than unity or exponentially, we show that ridge regression outperforms gradient descent. (2) For orthogonal designs, we compute the exact minimax optimal class of estimators (achieving min-max-min optimality), showing it is equivalent to gradient descent with decaying learning rate. We find the sub-optimality of ridge regression and gradient descent with constant step size. Our results highlight that statistical performance can depend strongly on tuning parameters. In particular, while optimally tuned ridge regression is the best estimator in our setting, it can be outperformed by gradient descent by an arbitrary/unbounded amount when both methods are only tuned over finitely many regularization parameters.
Active manifolds, stratifications, and convergence to local minima in nonsmooth optimization
Authors: Damek Davis, Dmitriy Drusvyatskiy, Liwei Jiang
Date: 2021-08-26 00:00:00

We show that the subgradient method converges only to local minimizers when applied to generic Lipschitz continuous and subdifferentially regular functions that are definable in an o-minimal structure. At a high level, the argument we present is appealingly transparent: we interpret the nonsmooth dynamics as an approximate Riemannian gradient method on a certain distinguished submanifold that captures the nonsmooth activity of the function. In the process, we develop new regularity conditions in nonsmooth analysis that parallel the stratification conditions of Whitney, Kuo, and Verdier and extend stochastic processes techniques of Pemantle.
Fine-Tuning Pretrained Language Models With Label Attention for Biomedical Text Classification
Authors: Bruce Nguyen, Shaoxiong Ji
Date: 2021-08-26 00:00:00
Tasks: text-classification, Text Classification

The massive scale and growth of textual biomedical data have made its indexing and classification increasingly important. However, existing research on this topic mainly utilized convolutional and recurrent neural networks, which generally achieve inferior performance than the novel transformers. On the other hand, systems that apply transformers only focus on the target documents, overlooking the rich semantic information that label descriptions contain. To address this gap, we develop a transformer-based biomedical text classifier that considers label information. The system achieves this with a label attention module incorporated into the fine-tuning process of pretrained language models (PTMs). Our results on two public medical datasets show that the proposed fine-tuning scheme outperforms the vanilla PTMs and state-of-the-art models.
On the use of test smells for prediction of flaky tests
Authors: B. H. P. Camara, M. A. G. Silva, A. T. Endo, S. R. Vergilio
Date: 2021-08-26 00:00:00

Regression testing is an important phase to deliver software with quality. However, flaky tests hamper the evaluation of test results and can increase costs. This is because a flaky test may pass or fail non-deterministically and to identify properly the flakiness of a test requires rerunning the test suite multiple times. To cope with this challenge, approaches have been proposed based on prediction models and machine learning. Existing approaches based on the use of the test case vocabulary may be context-sensitive and prone to overfitting, presenting low performance when executed in a cross-project scenario. To overcome these limitations, we investigate the use of test smells as predictors of flaky tests. We conducted an empirical study to understand if test smells have good performance as a classifier to predict the flakiness in the cross-project context, and analyzed the information gain of each test smell. We also compared the test smell-based approach with the vocabulary-based one. As a result, we obtained a classifier that had a reasonable performance (Random Forest, 0.83) to predict the flakiness in the testing phase. This classifier presented better performance than vocabulary-based model for cross-project prediction. The Assertion Roulette and Sleepy Test test smell types are the ones associated with the best information gain values.
Parallelised Diffeomorphic Sampling-based Motion Planning
Authors: Tin Lai, Weiming Zhi, Tucker Hermans, Fabio Ramos
Date: 2021-08-26 00:00:00
Tasks: MORPH, Motion Planning, Normalising Flows, valid

We propose Parallelised Diffeomorphic Sampling-based Motion Planning (PDMP). PDMP is a novel parallelised framework that uses bijective and differentiable mappings, or diffeomorphisms, to transform sampling distributions of sampling-based motion planners, in a manner akin to normalising flows. Unlike normalising flow models which use invertible neural network structures to represent these diffeomorphisms, we develop them from gradient information of desired costs, and encode desirable behaviour, such as obstacle avoidance. These transformed sampling distributions can then be used for sampling-based motion planning. A particular example is when we wish to imbue the sampling distribution with knowledge of the environment geometry, such that drawn samples are less prone to be in collisions. To this end, we propose to learn a continuous occupancy representation from environment occupancy data, such that gradients of the representation defines a valid diffeomorphism and is amenable to fast parallel evaluation. We use this to "morph" the sampling distribution to draw far fewer collision-prone samples. PDMP is able to leverage gradient information of costs, to inject specifications, in a manner similar to optimisation-based motion planning methods, but relies on drawing from a sampling distribution, retaining the tendency to find more global solutions, thereby bridging the gap between trajectory optimisation and sampling-based planning methods.
Byzantine Fault-Tolerance in Federated Local SGD under 2f-Redundancy
Authors: Nirupam Gupta, Thinh T. Doan, Nitin Vaidya
Date: 2021-08-26 00:00:00

We consider the problem of Byzantine fault-tolerance in federated machine learning. In this problem, the system comprises multiple agents each with local data, and a trusted centralized coordinator. In fault-free setting, the agents collaborate with the coordinator to find a minimizer of the aggregate of their local cost functions defined over their local data. We consider a scenario where some agents ($f$ out of $N$) are Byzantine faulty. Such agents need not follow a prescribed algorithm correctly, and may communicate arbitrary incorrect information to the coordinator. In the presence of Byzantine agents, a more reasonable goal for the non-faulty agents is to find a minimizer of the aggregate cost function of only the non-faulty agents. This particular goal is commonly referred as exact fault-tolerance. Recent work has shown that exact fault-tolerance is achievable if only if the non-faulty agents satisfy the property of $2f$-redundancy. Now, under this property, techniques are known to impart exact fault-tolerance to the distributed implementation of the classical stochastic gradient-descent (SGD) algorithm. However, we do not know of any such techniques for the federated local SGD algorithm - a more commonly used method for federated machine learning. To address this issue, we propose a novel technique named comparative elimination (CE). We show that, under $2f$-redundancy, the federated local SGD algorithm with CE can indeed obtain exact fault-tolerance in the deterministic setting when the non-faulty agents can accurately compute gradients of their local cost functions. In the general stochastic case, when agents can only compute unbiased noisy estimates of their local gradients, our algorithm achieves approximate fault-tolerance with approximation error proportional to the variance of stochastic gradients and the fraction of Byzantine agents.
The Number of Steps Needed for Nonconvex Optimization of a Deep Learning Optimizer is a Rational Function of Batch Size
Authors: Hideaki Iiduka
Date: 2021-08-26 00:00:00

Recently, convergence as well as convergence rate analyses of deep learning optimizers for nonconvex optimization have been widely studied. Meanwhile, numerical evaluations for the optimizers have precisely clarified the relationship between batch size and the number of steps needed for training deep neural networks. The main contribution of this paper is to show theoretically that the number of steps needed for nonconvex optimization of each of the optimizers can be expressed as a rational function of batch size. Having these rational functions leads to two particularly important facts, which were validated numerically in previous studies. The first fact is that there exists an optimal batch size such that the number of steps needed for nonconvex optimization is minimized. This implies that using larger batch sizes than the optimal batch size does not decrease the number of steps needed for nonconvex optimization. The second fact is that the optimal batch size depends on the optimizer. In particular, it is shown theoretically that momentum and Adam-type optimizers can exploit larger optimal batches and further reduce the minimum number of steps needed for nonconvex optimization than can the stochastic gradient descent optimizer.
Estimation of Riemannian distances between covariance operators and Gaussian processes
Authors: Ha Quang Minh
Date: 2021-08-26 00:00:00
Tasks: Gaussian Processes

In this work we study two Riemannian distances between infinite-dimensional positive definite Hilbert-Schmidt operators, namely affine-invariant Riemannian and Log-Hilbert-Schmidt distances, in the context of covariance operators associated with functional stochastic processes, in particular Gaussian processes. Our first main results show that both distances converge in the Hilbert-Schmidt norm. Using concentration results for Hilbert space-valued random variables, we then show that both distances can be consistently and efficiently estimated from (i) sample covariance operators, (ii) finite, normalized covariance matrices, and (iii) finite samples generated by the given processes, all with dimension-independent convergence. Our theoretical analysis exploits extensively the methodology of reproducing kernel Hilbert space (RKHS) covariance and cross-covariance operators. The theoretical formulation is illustrated with numerical experiments on covariance operators of Gaussian processes.
Why Adversarial Reprogramming Works, When It Fails, and How to Tell the Difference
Authors: Yang Zheng, Xiaoyi Feng, Zhaoqiang Xia, Xiaoyue Jiang, Ambra Demontis, Maura Pintor, Battista Biggio, Fabio Roli
Date: 2021-08-26 00:00:00
Tasks: BIG-bench Machine Learning, Transfer Learning

Adversarial reprogramming allows repurposing a machine-learning model to perform a different task. For example, a model trained to recognize animals can be reprogrammed to recognize digits by embedding an adversarial program in the digit images provided as input. Recent work has shown that adversarial reprogramming may not only be used to abuse machine-learning models provided as a service, but also beneficially, to improve transfer learning when training data is scarce. However, the factors affecting its success are still largely unexplained. In this work, we develop a first-order linear model of adversarial reprogramming to show that its success inherently depends on the size of the average input gradient, which grows when input gradients are more aligned, and when inputs have higher dimensionality. The results of our experimental analysis, involving fourteen distinct reprogramming tasks, show that the above factors are correlated with the success and the failure of adversarial reprogramming.
Hybrid quantum-classical machine learning for generative chemistry and drug design
Authors: A. I. Gircha, A. S. Boev, K. Avchaciov, P. O. Fedichev, A. K. Fedorov
Date: 2021-08-26 00:00:00
Tasks: Drug Design, Drug Discovery

Deep generative chemistry models emerge as powerful tools to expedite drug discovery. However, the immense size and complexity of the structural space of all possible drug-like molecules pose significant obstacles, which could be overcome with hybrid architectures combining quantum computers with deep classical networks. As the first step toward this goal, we built a compact discrete variational autoencoder (DVAE) with a Restricted Boltzmann Machine (RBM) of reduced size in its latent layer. The size of the proposed model was small enough to fit on a state-of-the-art D-Wave quantum annealer and allowed training on a subset of the ChEMBL dataset of biologically active compounds. Finally, we generated 2331 novel chemical structures with medicinal chemistry and synthetic accessibility properties in the ranges typical for molecules from ChEMBL. The presented results demonstrate the feasibility of using already existing or soon-to-be-available quantum computing devices as testbeds for future drug discovery applications.
Self-Attention for Audio Super-Resolution
Authors: Nathanaël Carraz Rakotonirina
Date: 2021-08-26 00:00:00
Tasks: Audio Super-Resolution, Super-Resolution

Convolutions operate only locally, thus failing to model global interactions. Self-attention is, however, able to learn representations that capture long-range dependencies in sequences. We propose a network architecture for audio super-resolution that combines convolution and self-attention. Attention-based Feature-Wise Linear Modulation (AFiLM) uses self-attention mechanism instead of recurrent neural networks to modulate the activations of the convolutional model. Extensive experiments show that our model outperforms existing approaches on standard benchmarks. Moreover, it allows for more parallelization resulting in significantly faster training.
Model-based Chance-Constrained Reinforcement Learning via Separated Proportional-Integral Lagrangian
Authors: Baiyu Peng, Jingliang Duan, Jianyu Chen, Shengbo Eben Li, Genjin Xie, Congsheng Zhang, Yang Guan, Yao Mu, Enxin Sun
Date: 2021-08-26 00:00:00
Tasks: reinforcement-learning, Reinforcement Learning (RL), Robot Navigation

Safety is essential for reinforcement learning (RL) applied in the real world. Adding chance constraints (or probabilistic constraints) is a suitable way to enhance RL safety under uncertainty. Existing chance-constrained RL methods like the penalty methods and the Lagrangian methods either exhibit periodic oscillations or learn an over-conservative or unsafe policy. In this paper, we address these shortcomings by proposing a separated proportional-integral Lagrangian (SPIL) algorithm. We first review the constrained policy optimization process from a feedback control perspective, which regards the penalty weight as the control input and the safe probability as the control output. Based on this, the penalty method is formulated as a proportional controller, and the Lagrangian method is formulated as an integral controller. We then unify them and present a proportional-integral Lagrangian method to get both their merits, with an integral separation technique to limit the integral value in a reasonable range. To accelerate training, the gradient of safe probability is computed in a model-based manner. We demonstrate our method can reduce the oscillations and conservatism of RL policy in a car-following simulation. To prove its practicality, we also apply our method to a real-world mobile robot navigation task, where our robot successfully avoids a moving obstacle with highly uncertain or even aggressive behaviors.