OpenRaiser/Intern-Atlas huggingface dataset:
Assessing the Feasibility of Web-Request Prediction Models on Mobile Platforms
Venue: arXiv cs.SE 2021
Year: 2021

Prefetching web pages is a well-studied solution to reduce network latency by predicting users' future actions based on their past behaviors. However, such techniques are largely unexplored on mobile platforms. Today's privacy regulations make it infeasible to explore prefetching with the usual strategy of amassing large amounts of data over long periods and constructing conventional, "large" prediction models. Our work is based on the observation that this may not be necessary: Given previously reported mobile-device usage trends (e.g., repetitive behaviors in brief bursts), we hypothesized that prefetching should work effectively with "small" models trained on mobile-user requests collected during much shorter time periods. To test this hypothesis, we constructed a framework for automatically assessing prediction models, and used it to conduct an extensive empirical study based on over 15 million HTTP requests collected from nearly 11,500 mobile users during a 24-hour period, resulting in over 7 million models. Our results demonstrate the feasibility of prefetching with small models on mobile platforms, directly motivating future work in this area. We further introduce several strategies for improving prediction models while reducing the model size. Finally, our framework provides the foundation for future explorations of effective prediction models across a range of usage scenarios.
Windowed Backoff Algorithms for WiFi: Theory and Performance under Batched Arrivals
Venue: arXiv cs.DC 2021
Year: 2021

Binary exponential backoff (BEB) is a decades-old algorithm for coordinating access to a shared channel. In modern networks, BEB plays an important role in WiFi (IEEE 802.11) and other wireless communication standards. Despite this track record, well-known theoretical results indicate that under bursty traffic BEB yields poor makespan, and superior algorithms are possible. To date, the degree to which these findings impact performance in wireless networks has not been examined. To address this issue, we investigate one of the strongest cases against BEB: a single burst batch of packets that simultaneously contend for access to a wireless channel. Using Network Simulator 3, we incorporate into IEEE 802.11g several newer algorithms that, while inspired by BEB, possess makespan guarantees that are theoretically superior. Surprisingly, we discover that these newer algorithms underperform BEB. Investigating further, we identify as the culprit a common abstraction regarding the cost of collisions. Our experimental results are complemented by analytical arguments that the number of collisions - and not solely makespan - is an important metric to optimize. We argue that these findings have implications for the design of backoff algorithms in wireless networks.
Multi-modal Fusion for Single-Stage Continuous Gesture Recognition
Venue: arXiv cs.CV 2021
Year: 2021

Gesture recognition is a much studied research area which has myriad real-world applications including robotics and human-machine interaction. Current gesture recognition methods have focused on recognising isolated gestures, and existing continuous gesture recognition methods are limited to two-stage approaches where independent models are required for detection and classification, with the performance of the latter being constrained by detection performance. In contrast, we introduce a single-stage continuous gesture recognition framework, called Temporal Multi-Modal Fusion (TMMF), that can detect and classify multiple gestures in a video via a single model. This approach learns the natural transitions between gestures and non-gestures without the need for a pre-processing segmentation step to detect individual gestures. To achieve this, we introduce a multi-modal fusion mechanism to support the integration of important information that flows from multi-modal inputs, and is scalable to any number of modes. Additionally, we propose Unimodal Feature Mapping (UFM) and Multi-modal Feature Mapping (MFM) models to map uni-modal features and the fused multi-modal features respectively. To further enhance performance, we propose a mid-point based loss function that encourages smooth alignment between the ground truth and the prediction, helping the model to learn natural gesture transitions. We demonstrate the utility of our proposed framework, which can handle variable-length input videos, and outperforms the state-of-the-art on three challenging datasets: EgoGesture, IPN hand, and ChaLearn LAP Continuous Gesture Dataset (ConGD). Furthermore, ablation experiments show the importance of different components of the proposed framework.
Exploiting Scheduled Access Features of mmWave WLANs for Periodic Traffic Sources
Venue: arXiv cs.NI 2021
Year: 2021

Many current and future multimedia and industrial applications, like video streaming, eXtended Reality or remote robot control, are characterized by periodic data transmissions with strict latency and reliability constraints. In an effort to meet the stringent demand of such traffic sources, the WiGig standards support a contention-free channel access mechanism, named Service Period, that makes it possible to allocate dedicated time intervals to certain wireless stations. However, the standard only covers the fundamental aspects that ensure interoperability, while the actual schedule logic is left to vendors. In this paper, we propose two algorithms for joint admission control and scheduling of periodic traffic streams with contrasting performance objectives, specifically a simple scheduler and a max-min fair scheduler. The schemes are compared in two different scenarios, in order to characterize and highlight some fundamental trade-offs. As expected from their design principles, the simple scheduler tends to trade acceptance rate for resource availability, contrary to the max-min fair scheduler, giving to implementers a clear performance trade-off, although performance cannot be balanced by means of a tunable parameter.
Multi-Task Sequence Prediction For Tunisian Arabizi Multi-Level Annotation
Venue: arXiv cs.CL 2021
Year: 2021

In this paper we propose a multi-task sequence prediction system, based on recurrent neural networks and used to annotate on multiple levels an Arabizi Tunisian corpus. The annotation performed are text classification, tokenization, PoS tagging and encoding of Tunisian Arabizi into CODA* Arabic orthography. The system is learned to predict all the annotation levels in cascade, starting from Arabizi input. We evaluate the system on the TIGER German corpus, suitably converting data to have a multi-task problem, in order to show the effectiveness of our neural architecture. We show also how we used the system in order to annotate a Tunisian Arabizi corpus, which has been afterwards manually corrected and used to further evaluate sequence models on Tunisian data. Our system is developed for the Fairseq framework, which allows for a fast and easy use for any other sequence prediction problem.
Mapping Stencils on Coarse-grained Reconfigurable Spatial Architecture
Venue: arXiv cs.DC 2021
Year: 2021

Stencils represent a class of computational patterns where an output grid point depends on a fixed shape of neighboring points in an input grid. Stencil computations are prevalent in scientific applications engaging a significant portion of supercomputing resources. Therefore, it has been always important to optimize stencil programs for the best performance. A rich body of research has focused on optimizing stencil computations on almost all parallel architectures. Stencil applications have regular dependency patterns, inherent pipeline-parallelism, and plenty of data reuse. This makes these applications a perfect match for a coarse-grained reconfigurable spatial architecture (CGRA). A CGRA consists of many simple, small processing elements (PEs) connected with an on-chip network. Each PE can be configured to execute part of a stencil computation and all PEs run in parallel; the network can also be configured so that data loaded can be passed from a PE to a neighbor PE directly and thus reused by many PEs without register spilling and memory traffic. How to efficiently map a stencil computation to a CGRA is the key to performance. In this paper, we show a few unique and generalizable ways of mapping one- and multidimensional stencil computations to a CGRA, fully exploiting the data reuse opportunities and parallelism. Our simulation experiments demonstrate that these mappings are efficient and enable the CGRA to outperform state-of-the-art GPUs.
Privacy Preservation in Federated Learning: An insightful survey from the GDPR Perspective
Venue: arXiv cs.CR 2021
Year: 2021

Along with the blooming of AI and Machine Learning-based applications and services, data privacy and security have become a critical challenge. Conventionally, data is collected and aggregated in a data centre on which machine learning models are trained. This centralised approach has induced severe privacy risks to personal data leakage, misuse, and abuse. Furthermore, in the era of the Internet of Things and big data in which data is essentially distributed, transferring a vast amount of data to a data centre for processing seems to be a cumbersome solution. This is not only because of the difficulties in transferring and sharing data across data sources but also the challenges on complying with rigorous data protection regulations and complicated administrative procedures such as the EU General Data Protection Regulation (GDPR). In this respect, Federated learning (FL) emerges as a prospective solution that facilitates distributed collaborative learning without disclosing original training data whilst naturally complying with the GDPR. Recent research has demonstrated that retaining data and computation on-device in FL is not sufficient enough for privacy-guarantee. This is because ML model parameters exchanged between parties in an FL system still conceal sensitive information, which can be exploited in some privacy attacks. Therefore, FL systems shall be empowered by efficient privacy-preserving techniques to comply with the GDPR. This article is dedicated to surveying on the state-of-the-art privacy-preserving techniques which can be employed in FL in a systematic fashion, as well as how these techniques mitigate data security and privacy risks. Furthermore, we provide insights into the challenges along with prospective approaches following the GDPR regulatory guidelines that an FL system shall implement to comply with the GDPR.
Sampling Matrices from Harish-Chandra-Itzykson-Zuber Densities with Applications to Quantum Inference and Differential Privacy
Venue: arXiv cs.DS 2021
Year: 2021

Given two $n \times n$ Hermitian matrices $Y$ and $Λ$, the Harish-Chandra-Itzykson-Zuber (HCIZ) distribution on the unitary group $\text{U}(n)$ is $e^{\text{tr}(UΛU^*Y)}dμ(U)$, where $μ$ is the Haar measure on $\text{U}(n)$. The density $e^{\text{tr}(UΛU^*Y)}$ is known as the HCIZ density. Random unitary matrices distributed according to the HCIZ density are important in various settings in physics and random matrix theory. However, the basic question of efficient sampling from the HCIZ distribution has remained open. We present two efficient algorithms to sample matrices from distributions that are close to the HCIZ distribution. The first algorithm outputs samples that are $ξ$-close in total variation distance and requires polynomially many arithmetic operations in $\log 1/ξ$ and the number of bits needed to encode $Y$ and $Λ$. The second algorithm comes with a stronger guarantee that the samples are $ξ$-close in infinity divergence, but the number of arithmetic operations depends polynomially on $1/ξ$, the number of bits needed to encode $Y$ and $Λ$, and the differences of the largest and the smallest eigenvalues of $Y$ and $Λ$. HCIZ densities can also be viewed as exponential densities on $\text{U}(n)$-orbits, and these densities have been studied in statistics, machine learning, and theoretical computer science. Thus our results have the following applications: 1) an efficient algorithm to sample from complex versions of matrix Langevin distributions studied in statistics, 2) an efficient algorithm to sample from continuous max-entropy distributions on unitary orbits, which implies an efficient algorithm to sample a pure quantum state from the entropy-maximizing ensemble representing a given density matrix, and 3) an efficient algorithm for differentially private rank-$k$ approximation, with improved utility bounds for $k>1$.
Deep Sound Change: Deep and Iterative Learning, Convolutional Neural Networks, and Language Change
Venue: arXiv cs.CL 2021
Year: 2021

This paper proposes a framework for modeling sound change that combines deep learning and iterative learning. Acquisition and transmission of speech is modeled by training generations of Generative Adversarial Networks (GANs) on unannotated raw speech data. The paper argues that several properties of sound change emerge from the proposed architecture. GANs (Goodfellow et al. 2014 arXiv:1406.2661, Donahue et al. 2019 arXiv:1705.07904) are uniquely appropriate for modeling language change because the networks are trained on raw unsupervised acoustic data, contain no language-specific features and, as argued in Beguš (2020 arXiv:2006.03965), encode phonetic and phonological representations in their latent space and generate linguistically informative innovative data. The first generation of networks is trained on the relevant sequences in human speech from TIMIT. The subsequent generations are not trained on TIMIT, but on generated outputs from the previous generation and thus start learning from each other in an iterative learning task. The initial allophonic distribution is progressively being lost with each generation, likely due to pressures from the global distribution of aspiration in the training data. The networks show signs of a gradual shift in phonetic targets characteristic of a gradual phonetic sound change. At endpoints, the outputs superficially resemble a phonological change -- rule loss.
Stability of Gradient Learning Dynamics in Continuous Games: Vector Action Spaces
Venue: arXiv cs.GT 2021
Year: 2021

Towards characterizing the optimization landscape of games, this paper analyzes the stability of gradient-based dynamics near fixed points of two-player continuous games. We introduce the quadratic numerical range as a method to characterize the spectrum of game dynamics and prove the robustness of equilibria to variations in learning rates. By decomposing the game Jacobian into symmetric and skew-symmetric components, we assess the contribution of a vector field's potential and rotational components to the stability of differential Nash equilibria. Our results show that in zero-sum games, all Nash are stable and robust; in potential games, all stable points are Nash. For general-sum games, we provide a sufficient condition for instability. We conclude with a numerical example in which learning with timescale separation results in faster convergence.
Colorado in Context: Congressional Redistricting and Competing Fairness Criteria in Colorado
Venue: arXiv cs.CY 2021
Year: 2021

In this paper, we apply techniques of ensemble analysis to understand the political baseline for Congressional representation in Colorado. We generate a large random sample of reasonable redistricting plans and determine the partisan balance of each district using returns from state-wide elections in 2018, and analyze the 2011/2012 enacted districts in this context. Colorado recently adopted a new framework for redistricting, creating an independent commission to draw district boundaries, prohibiting partisan bias and incumbency considerations, requiring that political boundaries (such as counties) be preserved as much as possible, and also requiring that mapmakers maximize the number of competitive districts. We investigate the relationships between partisan outcomes, number of counties which are split, and number of competitive districts in a plan. This paper also features two novel improvements in methodology--a more rigorous statistical framework for understanding necessary sample size, and a weighted-graph method for generating random plans which split approximately as few counties as acceptable human-drawn maps.
Total Completion Time Minimization for Scheduling with Incompatibility Cliques
Venue: arXiv cs.CC 2021
Year: 2021

This paper considers parallel machine scheduling with incompatibilities between jobs. The jobs form a graph and no two jobs connected by an edge are allowed to be assigned to the same machine. In particular, we study the case where the graph is a collection of disjoint cliques. Scheduling with incompatibilities between jobs represents a well-established line of research in scheduling theory and the case of disjoint cliques has received increasing attention in recent years. While the research up to this point has been focused on the makespan objective, we broaden the scope and study the classical total completion time criterion. In the setting without incompatibilities, this objective is well known to admit polynomial time algorithms even for unrelated machines via matching techniques. We show that the introduction of incompatibility cliques results in a richer, more interesting picture. Scheduling on identical machines remains solvable in polynomial time, while scheduling on unrelated machines becomes APX-hard. Furthermore, we study the problem under the paradigm of fixed-parameter tractable algorithms (FPT). In particular, we consider a problem variant with assignment restrictions for the cliques rather than the jobs. We prove that it is NP-hard and can be solved in FPT time with respect to the number of cliques. Moreover, we show that the problem on unrelated machines can be solved in FPT time for reasonable parameters, e.g., the parameter pair: number of machines and maximum processing time. The latter result is a natural extension of known results for the case without incompatibilities and can even be extended to the case of total weighted completion time. All of the FPT results make use of n-fold Integer Programs that recently have received great attention by proving their usefulness for scheduling problems.
Coded Computing for Low-Latency Federated Learning over Wireless Edge Networks
Venue: arXiv cs.DC 2021
Year: 2021

Federated learning enables training a global model from data located at the client nodes, without data sharing and moving client data to a centralized server. Performance of federated learning in a multi-access edge computing (MEC) network suffers from slow convergence due to heterogeneity and stochastic fluctuations in compute power and communication link qualities across clients. We propose a novel coded computing framework, CodedFedL, that injects structured coding redundancy into federated learning for mitigating stragglers and speeding up the training procedure. CodedFedL enables coded computing for non-linear federated learning by efficiently exploiting distributed kernel embedding via random Fourier features that transforms the training task into computationally favourable distributed linear regression. Furthermore, clients generate local parity datasets by coding over their local datasets, while the server combines them to obtain the global parity dataset. Gradient from the global parity dataset compensates for straggling gradients during training, and thereby speeds up convergence. For minimizing the epoch deadline time at the MEC server, we provide a tractable approach for finding the amount of coding redundancy and the number of local data points that a client processes during training, by exploiting the statistical properties of compute as well as communication delays. We also characterize the leakage in data privacy when clients share their local parity datasets with the server. We analyze the convergence rate and iteration complexity of CodedFedL under simplifying assumptions, by treating CodedFedL as a stochastic gradient descent algorithm. Furthermore, we conduct numerical experiments using practical network parameters and benchmark datasets, where CodedFedL speeds up the overall training time by up to $15\times$ in comparison to the benchmark schemes.
Machine Learning Interpretability Meets TLS Fingerprinting
Venue: arXiv cs.NI 2021
Year: 2021

Protecting users' privacy over the Internet is of great importance; however, it becomes harder and harder to maintain due to the increasing complexity of network protocols and components. Therefore, investigating and understanding how data is leaked from the information transmission platforms and protocols can lead us to a more secure environment. In this paper, we propose a framework to systematically find the most vulnerable information fields in a network protocol. To this end, focusing on the transport layer security (TLS) protocol, we perform different machine-learning-based fingerprinting attacks on the collected data from more than 70 domains (websites) to understand how and where this information leakage occurs in the TLS protocol. Then, by employing the interpretation techniques developed in the machine learning community and applying our framework, we find the most vulnerable information fields in the TLS protocol. Our findings demonstrate that the TLS handshake (which is mainly unencrypted), the TLS record length appearing in the TLS application data header, and the initialization vector (IV) field are among the most critical leaker parts in this protocol, respectively.
Online Influence Maximization under Linear Threshold Model
Venue: arXiv cs.LG 2021
Year: 2021

Online influence maximization (OIM) is a popular problem in social networks to learn influence propagation model parameters and maximize the influence spread at the same time. Most previous studies focus on the independent cascade (IC) model under the edge-level feedback. In this paper, we address OIM in the linear threshold (LT) model. Because node activations in the LT model are due to the aggregated effect of all active neighbors, it is more natural to model OIM with the node-level feedback. And this brings new challenge in online learning since we only observe aggregated effect from groups of nodes and the groups are also random. Based on the linear structure in node activations, we incorporate ideas from linear bandits and design an algorithm LT-LinUCB that is consistent with the observed feedback. By proving group observation modulated (GOM) bounded smoothness property, a novel result of the influence difference in terms of the random observations, we provide a regret of order $\tilde{O}(\mathrm{poly}(m)\sqrt{T})$, where $m$ is the number of edges and $T$ is the number of rounds. This is the first theoretical result in such order for OIM under the LT model. In the end, we also provide an algorithm OIM-ETC with regret bound $O(\mathrm{poly}(m)\ T^{2/3})$, which is model-independent, simple and has less requirement on online feedback and offline computation.
FusedMM: A Unified SDDMM-SpMM Kernel for Graph Embedding and Graph Neural Networks
Venue: arXiv cs.LG 2021
Year: 2021

We develop a fused matrix multiplication kernel that unifies sampled dense-dense matrix multiplication and sparse-dense matrix multiplication under a single operation called FusedMM. By using user-defined functions, FusedMM can capture almost all computational patterns needed by popular graph embedding and GNN approaches. FusedMM is an order of magnitude faster than its equivalent kernels in Deep Graph Library. The superior performance of FusedMM comes from the low-level vectorized kernels, a suitable load balancing scheme and an efficient utilization of the memory bandwidth. FusedMM can tune its performance using a code generator and perform equally well on Intel, AMD and ARM processors. FusedMM speeds up an end-to-end graph embedding algorithm by up to 28x on different processors.