pwc-archive/papers-with-abstracts huggingface dataset:
Predicting traffic overflows on private peering
Authors: Elad Rapaport, Ingmar Poese, Polina Zilberman, Oliver Holschke, Rami Puzis
Date: 2020-10-03 00:00:00

Large content providers and content distribution network operators usually connect with large Internet service providers (eyeball networks) through dedicated private peering. The capacity of these private network interconnects is provisioned to match the volume of the real content demand by the users. Unfortunately, in case of a surge in traffic demand, for example due to a content trending in a certain country, the capacity of the private interconnect may deplete and the content provider/distributor would have to reroute the excess traffic through transit providers. Although, such overflow events are rare, they have significant negative impacts on content providers, Internet service providers, and end-users. These include unexpected delays and disruptions reducing the user experience quality, as well as direct costs paid by the Internet service provider to the transit providers. If the traffic overflow events could be predicted, the Internet service providers would be able to influence the routes chosen for the excess traffic to reduce the costs and increase user experience quality. In this article we propose a method based on an ensemble of deep learning models to predict overflow events over a short term horizon of 2-6 hours and predict the specific interconnections that will ingress the overflow traffic. The method was evaluated with 2.5 years' traffic measurement data from a large European Internet service provider resulting in a true-positive rate of 0.8 while maintaining a 0.05 false-positive rate. The lockdown imposed by the COVID-19 pandemic reduced the overflow prediction accuracy. Nevertheless, starting from the end of April 2020 with the gradual lockdown release, the old models trained before the pandemic perform equally well.
Sparse Quantized Spectral Clustering
Authors: Zhenyu Liao, Romain Couillet, Michael W. Mahoney
Date: 2020-10-03 00:00:00
Proceeding: ICLR 2021 1
Tasks: Clustering, Quantization

Given a large data matrix, sparsifying, quantizing, and/or performing other entry-wise nonlinear operations can have numerous benefits, ranging from speeding up iterative algorithms for core numerical linear algebra problems to providing nonlinear filters to design state-of-the-art neural network models. Here, we exploit tools from random matrix theory to make precise statements about how the eigenspectrum of a matrix changes under such nonlinear transformations. In particular, we show that very little change occurs in the informative eigenstructure even under drastic sparsification/quantization, and consequently that very little downstream performance loss occurs with very aggressively sparsified or quantized spectral clustering. We illustrate how these results depend on the nonlinearity, we characterize a phase transition beyond which spectral clustering becomes possible, and we show when such nonlinear transformations can introduce spurious non-informative eigenvectors.
Exponential Lower Bounds for Planning in MDPs With Linearly-Realizable Optimal Action-Value Functions
Authors: Gellért Weisz, Philip Amortila, Csaba Szepesvári
Date: 2020-10-03 00:00:00

We consider the problem of local planning in fixed-horizon and discounted Markov Decision Processes (MDPs) with linear function approximation and a generative model under the assumption that the optimal action-value function lies in the span of a feature map that is available to the planner. Previous work has left open the question of whether there exist sound planners that need only poly(H,d) queries regardless of the MDP, where H is the horizon and d is the dimensionality of the features. We answer this question in the negative: we show that any sound planner must query at least $\min(\exp({\Omega}(d)), {\Omega}(2^H))$ samples in the fized-horizon setting and $\exp({\Omega}(d))$ samples in the discounted setting. We also show that for any ${\delta}>0$, the least-squares value iteration algorithm with $O(H^5d^{H+1}/{\delta}^2)$ queries can compute a ${\delta}$-optimal policy in the fixed-horizon setting. We discuss implications and remaining open questions.
Computational Separation Between Convolutional and Fully-Connected Networks
Authors: Eran Malach, Shai Shalev-Shwartz
Date: 2020-10-03 00:00:00
Proceeding: ICLR 2021 1

Convolutional neural networks (CNN) exhibit unmatched performance in a multitude of computer vision tasks. However, the advantage of using convolutional networks over fully-connected networks is not understood from a theoretical perspective. In this work, we show how convolutional networks can leverage locality in the data, and thus achieve a computational advantage over fully-connected networks. Specifically, we show a class of problems that can be efficiently solved using convolutional networks trained with gradient-descent, but at the same time is hard to learn using a polynomial-size fully-connected network.
EECBS: A Bounded-Suboptimal Search for Multi-Agent Path Finding
Authors: Jiaoyang Li, Wheeler Ruml, Sven Koenig
Date: 2020-10-03 00:00:00
Tasks: Multi-Agent Path Finding

Multi-Agent Path Finding (MAPF), i.e., finding collision-free paths for multiple robots, is important for many applications where small runtimes are necessary, including the kind of automated warehouses operated by Amazon. CBS is a leading two-level search algorithm for solving MAPF optimally. ECBS is a bounded-suboptimal variant of CBS that uses focal search to speed up CBS by sacrificing optimality and instead guaranteeing that the costs of its solutions are within a given factor of optimal. In this paper, we study how to decrease its runtime even further using inadmissible heuristics. Motivated by Explicit Estimation Search (EES), we propose Explicit Estimation CBS (EECBS), a new bounded-suboptimal variant of CBS, that uses online learning to obtain inadmissible estimates of the cost of the solution of each high-level node and uses EES to choose which high-level node to expand next. We also investigate recent improvements of CBS and adapt them to EECBS. We find that EECBS with the improvements runs significantly faster than the state-of-the-art bounded-suboptimal MAPF algorithms ECBS, BCP-7, and eMDD-SAT on a variety of MAPF instances. We hope that the scalability of EECBS enables additional applications for bounded-suboptimal MAPF algorithms.
COVID-19 Classification of X-ray Images Using Deep Neural Networks
Authors: Elisha Goldstein, Daphna Keidar, Daniel Yaron, Yair Shachar, Ayelet Blass, Leonid Charbinsky, Israel Aharony, Liza Lifshitz, Dimitri Lumelsky, Ziv Neeman, Matti Mizrachi, Majd Hajouj, Nethanel Eizenbach, Eyal Sela, Chedva S Weiss, Philip Levin, Ofer Benjaminov, Gil N Bachar, Shlomit Tamir, Yael Rapson, Dror Suhami, Amiel A Dror, Naama R Bogot, Ahuva Grubstein, Nogah Shabshin, Yishai M Elyada, Yonina C Eldar
Date: 2020-10-03 00:00:00
Tasks: Data Augmentation, General Classification, Sensitivity

In the midst of the coronavirus disease 2019 (COVID-19) outbreak, chest X-ray (CXR) imaging is playing an important role in the diagnosis and monitoring of patients with COVID-19. Machine learning solutions have been shown to be useful for X-ray analysis and classification in a range of medical contexts. The purpose of this study is to create and evaluate a machine learning model for diagnosis of COVID-19, and to provide a tool for searching for similar patients according to their X-ray scans. In this retrospective study, a classifier was built using a pre-trained deep learning model (ReNet50) and enhanced by data augmentation and lung segmentation to detect COVID-19 in frontal CXR images collected between January 2018 and July 2020 in four hospitals in Israel. A nearest-neighbors algorithm was implemented based on the network results that identifies the images most similar to a given image. The model was evaluated using accuracy, sensitivity, area under the curve (AUC) of receiver operating characteristic (ROC) curve and of the precision-recall (P-R) curve. The dataset sourced for this study includes 2362 CXRs, balanced for positive and negative COVID-19, from 1384 patients (63 +/- 18 years, 552 men). Our model achieved 89.7% (314/350) accuracy and 87.1% (156/179) sensitivity in classification of COVID-19 on a test dataset comprising 15% (350 of 2326) of the original data, with AUC of ROC 0.95 and AUC of the P-R curve 0.94. For each image we retrieve images with the most similar DNN-based image embeddings; these can be used to compare with previous cases.
Practical Precoding via Asynchronous Stochastic Successive Convex Approximation
Authors: Basil M. Idrees, Javed Akhtar, Ketan Rajawat
Date: 2020-10-03 00:00:00
Tasks: Stochastic Optimization

We consider stochastic optimization of a smooth non-convex loss function with a convex non-smooth regularizer. In the online setting, where a single sample of the stochastic gradient of the loss is available at every iteration, the problem can be solved using the proximal stochastic gradient descent (SGD) algorithm and its variants. However in many problems, especially those arising in communications and signal processing, information beyond the stochastic gradient may be available thanks to the structure of the loss function. Such extra-gradient information is not used by SGD, but has been shown to be useful, for instance in the context of stochastic expectation-maximization, stochastic majorization-minimization, and stochastic successive convex approximation (SCA) approaches. By constructing a stochastic strongly convex surrogates of the loss function at every iteration, the stochastic SCA algorithms can exploit the structural properties of the loss function and achieve superior empirical performance as compared to the SGD. In this work, we take a closer look at the stochastic SCA algorithm and develop its asynchronous variant which can be used for resource allocation in wireless networks. While the stochastic SCA algorithm is known to converge asymptotically, its iteration complexity has not been well-studied, and is the focus of the current work. The insights obtained from the non-asymptotic analysis allow us to develop a more practical asynchronous variant of the stochastic SCA algorithm which allows the use of surrogates calculated in earlier iterations. We characterize precise bound on the maximum delay the algorithm can tolerate, while still achieving the same convergence rate. We apply the algorithm to the problem of linear precoding in wireless sensor networks, where it can be implemented at low complexity but is shown to perform well in practice.
Perplexity-free Parametric t-SNE
Authors: Francesco Crecchi, Cyril de Bodt, Michel Verleysen, John A. Lee, Davide Bacciu
Date: 2020-10-03 00:00:00
Tasks: Dimensionality Reduction

The t-distributed Stochastic Neighbor Embedding (t-SNE) algorithm is a ubiquitously employed dimensionality reduction (DR) method. Its non-parametric nature and impressive efficacy motivated its parametric extension. It is however bounded to a user-defined perplexity parameter, restricting its DR quality compared to recently developed multi-scale perplexity-free approaches. This paper hence proposes a multi-scale parametric t-SNE scheme, relieved from the perplexity tuning and with a deep neural network implementing the mapping. It produces reliable embeddings with out-of-sample extensions, competitive with the best perplexity adjustments in terms of neighborhood preservation on multiple data sets.
Actionet: An Interactive End-To-End Platform For Task-Based Data Collection And Augmentation In 3D Environment
Authors: Jiafei Duan, Samson Yu, Hui Li Tan, Cheston Tan
Date: 2020-10-03 00:00:00
Tasks: Dataset Generation, Task Planning

The problem of task planning for artificial agents remains largely unsolved. While there has been increasing interest in data-driven approaches for the study of task planning for artificial agents, a significant remaining bottleneck is the dearth of large-scale comprehensive task-based datasets. In this paper, we present ActioNet, an interactive end-to-end platform for data collection and augmentation of task-based dataset in 3D environment. Using ActioNet, we collected a large-scale comprehensive task-based dataset, comprising over 3000 hierarchical task structures and videos. Using the hierarchical task structures, the videos are further augmented across 50 different scenes to give over 150,000 video. To our knowledge, ActioNet is the first interactive end-to-end platform for such task-based dataset generation and the accompanying dataset is the largest task-based dataset of such comprehensive nature. The ActioNet platform and dataset will be made available to facilitate research in hierarchical task planning.
Expectigrad: Fast Stochastic Optimization with Robust Convergence Properties
Authors: Brett Daley, Christopher Amato
Date: 2020-10-03 00:00:00
Tasks: Stochastic Optimization

Many popular adaptive gradient methods such as Adam and RMSProp rely on an exponential moving average (EMA) to normalize their stepsizes. While the EMA makes these methods highly responsive to new gradient information, recent research has shown that it also causes divergence on at least one convex optimization problem. We propose a novel method called Expectigrad, which adjusts stepsizes according to a per-component unweighted mean of all historical gradients and computes a bias-corrected momentum term jointly between the numerator and denominator. We prove that Expectigrad cannot diverge on every instance of the optimization problem known to cause Adam to diverge. We also establish a regret bound in the general stochastic nonconvex setting that suggests Expectigrad is less susceptible to gradient variance than existing methods are. Testing Expectigrad on several high-dimensional machine learning tasks, we find it often performs favorably to state-of-the-art methods with little hyperparameter tuning.
Disentangling causal effects for hierarchical reinforcement learning
Authors: Oriol Corcoll, Raul Vicente
Date: 2020-10-03 00:00:00
Tasks: counterfactual, Descriptive, Hierarchical Reinforcement Learning, reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

Exploration and credit assignment under sparse rewards are still challenging problems. We argue that these challenges arise in part due to the intrinsic rigidity of operating at the level of actions. Actions can precisely define how to perform an activity but are ill-suited to describe what activity to perform. Instead, causal effects are inherently composable and temporally abstract, making them ideal for descriptive tasks. By leveraging a hierarchy of causal effects, this study aims to expedite the learning of task-specific behavior and aid exploration. Borrowing counterfactual and normality measures from causal literature, we disentangle controllable effects from effects caused by other dynamics of the environment. We propose CEHRL, a hierarchical method that models the distribution of controllable effects using a Variational Autoencoder. This distribution is used by a high-level policy to 1) explore the environment via random effect exploration so that novel effects are continuously discovered and learned, and to 2) learn task-specific behavior by prioritizing the effects that maximize a given reward function. In comparison to exploring with random actions, experimental results show that random effect exploration is a more efficient mechanism and that by assigning credit to few effects rather than many actions, CEHRL learns tasks more rapidly.
A Geometry-Inspired Attack for Generating Natural Language Adversarial Examples
Authors: Zhao Meng, Roger Wattenhofer
Date: 2020-10-03 00:00:00
Proceeding: COLING 2020 8

Generating adversarial examples for natural language is hard, as natural language consists of discrete symbols, and examples are often of variable lengths. In this paper, we propose a geometry-inspired attack for generating natural language adversarial examples. Our attack generates adversarial examples by iteratively approximating the decision boundary of Deep Neural Networks (DNNs). Experiments on two datasets with two different models show that our attack fools natural language models with high success rates, while only replacing a few words. Human evaluation shows that adversarial examples generated by our attack are hard for humans to recognize. Further experiments show that adversarial training can improve model robustness against our attack.
A Variational Information Bottleneck Based Method to Compress Sequential Networks for Human Action Recognition
Authors: Ayush Srivastava, Oshin Dutta, Prathosh AP, Sumeet Agarwal, Jigyasa Gupta
Date: 2020-10-03 00:00:00
Tasks: Action Recognition, Temporal Action Localization

In the last few years, compression of deep neural networks has become an important strand of machine learning and computer vision research. Deep models require sizeable computational complexity and storage, when used for instance for Human Action Recognition (HAR) from videos, making them unsuitable to be deployed on edge devices. In this paper, we address this issue and propose a method to effectively compress Recurrent Neural Networks (RNNs) such as Gated Recurrent Units (GRUs) and Long-Short-Term-Memory Units (LSTMs) that are used for HAR. We use a Variational Information Bottleneck (VIB) theory-based pruning approach to limit the information flow through the sequential cells of RNNs to a small subset. Further, we combine our pruning method with a specific group-lasso regularization technique that significantly improves compression. The proposed techniques reduce model parameters and memory footprint from latent representations, with little or no reduction in the validation accuracy while increasing the inference speed several-fold. We perform experiments on the three widely used Action Recognition datasets, viz. UCF11, HMDB51, and UCF101, to validate our approach. It is shown that our method achieves over 70 times greater compression than the nearest competitor with comparable accuracy for the task of action recognition on UCF11.
End-to-End Training of CNN Ensembles for Person Re-Identification
Authors: Ayse Serbetci, Yusuf Sinan Akgul
Date: 2020-10-03 00:00:00
Tasks: Ensemble Learning, Person Re-Identification

We propose an end-to-end ensemble method for person re-identification (ReID) to address the problem of overfitting in discriminative models. These models are known to converge easily, but they are biased to the training data in general and may produce a high model variance, which is known as overfitting. The ReID task is more prone to this problem due to the large discrepancy between training and test distributions. To address this problem, our proposed ensemble learning framework produces several diverse and accurate base learners in a single DenseNet. Since most of the costly dense blocks are shared, our method is computationally efficient, which makes it favorable compared to the conventional ensemble models. Experiments on several benchmark datasets demonstrate that our method achieves state-of-the-art results. Noticeable performance improvements, especially on relatively small datasets, indicate that the proposed method deals with the overfitting problem effectively.
EGMM: an Evidential Version of the Gaussian Mixture Model for Clustering
Authors: Lianmeng Jiao, Thierry Denoeux, Zhun-Ga Liu, Quan Pan
Date: 2020-10-03 00:00:00
Tasks: Brain Image Segmentation, Clustering, Image Segmentation, Semantic Segmentation

The Gaussian mixture model (GMM) provides a simple yet principled framework for clustering, with properties suitable for statistical inference. In this paper, we propose a new model-based clustering algorithm, called EGMM (evidential GMM), in the theoretical framework of belief functions to better characterize cluster-membership uncertainty. With a mass function representing the cluster membership of each object, the evidential Gaussian mixture distribution composed of the components over the powerset of the desired clusters is proposed to model the entire dataset. The parameters in EGMM are estimated by a specially designed Expectation-Maximization (EM) algorithm. A validity index allowing automatic determination of the proper number of clusters is also provided. The proposed EGMM is as simple as the classical GMM, but can generate a more informative evidential partition for the considered dataset. The synthetic and real dataset experiments show that the proposed EGMM performs better than other representative clustering algorithms. Besides, its superiority is also demonstrated by an application to multi-modal brain image segmentation.
Multi-Step Adversarial Perturbations on Recommender Systems Embeddings
Authors: Vito Walter Anelli, Alejandro Bellogín, Yashar Deldjoo, Tommaso Di Noia, Felice Antonio Merra
Date: 2020-10-03 00:00:00
Tasks: Recommendation Systems

Recommender systems (RSs) have attained exceptional performance in learning users' preferences and helping them in finding the most suitable products. Recent advances in adversarial machine learning (AML) in the computer vision domain have raised interests in the security of state-of-the-art model-based recommenders. Recently, worrying deterioration of recommendation accuracy has been acknowledged on several state-of-the-art model-based recommenders (e.g., BPR-MF) when machine-learned adversarial perturbations contaminate model parameters. However, while the single-step fast gradient sign method (FGSM) is the most explored perturbation strategy, multi-step (iterative) perturbation strategies, that demonstrated higher efficacy in the computer vision domain, have been highly under-researched in recommendation tasks. In this work, inspired by the basic iterative method (BIM) and the projected gradient descent (PGD) strategies proposed in the CV domain, we adapt the multi-step strategies for the item recommendation task to study the possible weaknesses of embedding-based recommender models under minimal adversarial perturbations. Letting the magnitude of the perturbation be fixed, we illustrate the highest efficacy of the multi-step perturbation compared to the single-step one with extensive empirical evaluation on two widely adopted recommender datasets. Furthermore, we study the impact of structural dataset characteristics, i.e., sparsity, density, and size, on the performance degradation issued by presented perturbations to support RS designer in interpreting recommendation performance variation due to minimal variations of model parameters. Our implementation and datasets are available at https://anonymous.4open.science/r/9f27f909-93d5-4016-b01c-8976b8c14bc5/.
Deep learning algorithms for solving high dimensional nonlinear backward stochastic differential equations
Authors: Lorenc Kapllani, Long Teng
Date: 2020-10-03 00:00:00
Tasks: global-optimization

In this work, we propose a new deep learning-based scheme for solving high dimensional nonlinear backward stochastic differential equations (BSDEs). The idea is to reformulate the problem as a global optimization, where the local loss functions are included. Essentially, we approximate the unknown solution of a BSDE using a deep neural network and its gradient with automatic differentiation. The approximations are performed by globally minimizing the quadratic local loss function defined at each time step, which always includes the terminal condition. This kind of loss functions are obtained by iterating the Euler discretization of the time integrals with the terminal condition. Our formulation can prompt the stochastic gradient descent algorithm not only to take the accuracy at each time layer into account, but also converge to a good local minima. In order to demonstrate performances of our algorithm, several high-dimensional nonlinear BSDEs including pricing problems in finance are provided.