OpenRaiser/Intern-Atlas huggingface dataset:
Fast-Convergent Federated Learning with Adaptive Weighting
Venue: arXiv cs.LG 2021
Year: 2021

Federated learning (FL) enables resource-constrained edge nodes to collaboratively learn a global model under the orchestration of a central server while keeping privacy-sensitive data locally. The non-independent-and-identically-distributed (non-IID) data samples across participating nodes slow model training and impose additional communication rounds for FL to converge. In this paper, we propose Federated Adaptive Weighting (FedAdp) algorithm that aims to accelerate model convergence under the presence of nodes with non-IID dataset. We observe the implicit connection between the node contribution to the global model aggregation and data distribution on the local node through theoretical and empirical analysis. We then propose to assign different weights for updating the global model based on node contribution adaptively through each training round. The contribution of participating nodes is first measured by the angle between the local gradient vector and the global gradient vector, and then, weight is quantified by a designed non-linear mapping function subsequently. The simple yet effective strategy can reinforce positive (suppress negative) node contribution dynamically, resulting in communication round reduction drastically. Its superiority over the commonly adopted Federated Averaging (FedAvg) is verified both theoretically and experimentally. With extensive experiments performed in Pytorch and PySyft, we show that FL training with FedAdp can reduce the number of communication rounds by up to 54.1% on MNIST dataset and up to 45.4% on FashionMNIST dataset, as compared to FedAvg algorithm.
Lower Bounds for Semialgebraic Range Searching and Stabbing Problems
Venue: arXiv cs.CG 2021
Year: 2021

In the semialgebraic range searching problem, we are to preprocess $n$ points in $\mathbb{R}^d$ s.t. for any query range from a family of constant complexity semialgebraic sets, all the points intersecting the range can be reported or counted efficiently. When the ranges are composed of simplices, the problem can be solved using $S(n)$ space and with $Q(n)$ query time with $S(n)Q^d(n) = \tilde{O}(n^d)$ and this trade-off is almost tight. Consequently, there exists low space structures that use $\tilde{O}(n)$ space with $O(n^{1-1/d})$ query time and fast query structures that use $O(n^d)$ space with $O(\log^{d} n)$ query time. However, for the general semialgebraic ranges, only low space solutions are known, but the best solutions match the same trade-off curve as the simplex queries. It has been conjectured that the same could be done for the fast query case but this open problem has stayed unresolved. Here, we disprove this conjecture. We give the first nontrivial lower bounds for semilagebraic range searching and related problems. We show that any data structure for reporting the points between two concentric circles with $Q(n)$ query time must use $S(n)=Ω(n^{3-o(1)}/Q(n)^5)$ space, meaning, for $Q(n)=O(\log^{O(1)}n)$, $Ω(n^{3-o(1)})$ space must be used. We also study the problem of reporting the points between two polynomials of form $Y=\sum_{i=0}^Δa_i X^i$ where $a_0, \cdots, a_Δ$ are given at the query time. We show $S(n)=Ω(n^{Δ+1-o(1)}/Q(n)^{Δ^2+Δ})$. So for $Q(n)=O(\log^{O(1)}n)$, we must use $Ω(n^{Δ+1-o(1)})$ space. For the dual semialgebraic stabbing problems, we show that in linear space, any data structure that solves 2D ring stabbing must use $Ω(n^{2/3})$ query time. This almost matches the linearization upper bound. For general semialgebraic slab stabbing problems, again, we show an almost tight lower bounds.
A Study of Checkpointing in Large Scale Training of Deep Neural Networks
Venue: arXiv cs.DC 2021
Year: 2021

Deep learning (DL) applications are increasingly being deployed on HPC systems, to leverage the massive parallelism and computing power of those systems for DL model training. While significant effort has been put to facilitate distributed training by DL frameworks, fault tolerance has been largely ignored. In this work, we evaluate checkpoint-restart, a common fault tolerance technique in HPC workloads. We perform experiments with three state-of-the-art DL frameworks common in HPC Chainer, PyTorch, and TensorFlow). We evaluate the computational cost of checkpointing, file formats and file sizes, the impact of scale, and deterministic checkpointing. Our evaluation shows some critical differences in checkpoint mechanisms and exposes several bottlenecks in existing checkpointing implementations. We provide discussion points that can aid users in selecting a fault-tolerant framework to use in HPC. We also provide takeaway points that framework developers can use to facilitate better checkpointing of DL workloads in HPC.
Visually Imperceptible Adversarial Patch Attacks on Digital Images
Venue: arXiv cs.CV 2021
Year: 2021

The vulnerability of deep neural networks (DNNs) to adversarial examples has attracted more attention. Many algorithms have been proposed to craft powerful adversarial examples. However, most of these algorithms modified the global or local region of pixels without taking network explanations into account. Hence, the perturbations are redundant, which are easily detected by human eyes. In this paper, we propose a novel method to generate local region perturbations. The main idea is to find a contributing feature region (CFR) of an image by simulating the human attention mechanism and then add perturbations to CFR. Furthermore, a soft mask matrix is designed on the basis of an activation map to finely represent the contributions of each pixel in CFR. With this soft mask, we develop a new loss function with inverse temperature to search for optimal perturbations in CFR. Due to the network explanations, the perturbations added to CFR are more effective than those added to other regions. Extensive experiments conducted on CIFAR-10 and ILSVRC2012 demonstrate the effectiveness of the proposed method, including attack success rate, imperceptibility, and transferability.
DYNAMAP: Dynamic Algorithm Mapping Framework for Low Latency CNN Inference
Venue: arXiv cs.DC 2021
Year: 2021

Most of the existing work on FPGA acceleration of Convolutional Neural Network (CNN) focus on employing a single strategy (algorithm, dataflow, etc.) across all the layers. Such an approach does not achieve optimal latency on complex and deep CNNs. Emerging CNNs have diverse per-layer computation characteristics including parallelism, arithmetic intensity, locality, and memory footprint. Per-layer strategy selection and fine-grained tuning are required to achieve low end-to-end latency. However, specialized hardware modules dedicated to each layer limit the per-layer utilization and adversely affect end-to-end latency. In this paper, we address these problems by an algorithm-architecture co-optimization framework, DYNAMAP, consisting of (1) a unified hardware overlay that can be reused across layers, supporting dynamic mapping of all three families of popular convolution algorithms, and further allowing flexible dataflow switching to maximize hardware utilization for each layer; (2) a novel software Design Space Exploration (DSE) flow that customizes the hardware overlay and chooses optimal strategy mapping. We show that the algorithm mapping space increases exponentially with network depth, and while the optimal algorithm selection problem is NP-hard in general, by exploiting the series-parallel structure of CNN models, we demonstrate a polynomial-time solution for optimal algorithm mapping. DYNAMAP is optimized for any CNN, including those having diverse computation and memory requirements across the layers. We demonstrate DYNAMAP using two state-of-the-art CNNs - GoogleNet and Inception-V4. The generated accelerators achieve up to $2.8\times$ and $1.4\times$ speedups, respectively, wrt inference latency compared with the state-of-the-art FPGA implementations.
Reviewing the Need for Explainable Artificial Intelligence (xAI)
Venue: arXiv cs.HC 2021
Year: 2021

The diffusion of artificial intelligence (AI) applications in organizations and society has fueled research on explaining AI decisions. The explainable AI (xAI) field is rapidly expanding with numerous ways of extracting information and visualizing the output of AI technologies (e.g. deep neural networks). Yet, we have a limited understanding of how xAI research addresses the need for explainable AI. We conduct a systematic review of xAI literature on the topic and identify four thematic debates central to how xAI addresses the black-box problem. Based on this critical analysis of the xAI scholarship we synthesize the findings into a future research agenda to further the xAI body of knowledge.
Curiosity-driven 3D Object Detection Without Labels
Venue: arXiv cs.CV 2021
Year: 2021

In this paper we set out to solve the task of 6-DOF 3D object detection from 2D images, where the only supervision is a geometric representation of the objects we aim to find. In doing so, we remove the need for 6-DOF labels (i.e., position, orientation etc.), allowing our network to be trained on unlabeled images in a self-supervised manner. We achieve this through a neural network which learns an explicit scene parameterization which is subsequently passed into a differentiable renderer. We analyze why analysis-by-synthesis-like losses for supervision of 3D scene structure using differentiable rendering is not practical, as it almost always gets stuck in local minima of visual ambiguities. This can be overcome by a novel form of training, where an additional network is employed to steer the optimization itself to explore the entire parameter space i.e., to be curious, and hence, to resolve those ambiguities and find workable minima.
From One to All: Learning to Match Heterogeneous and Partially Overlapped Graphs
Venue: arXiv cs.LG 2021
Year: 2021

Recent years have witnessed a flurry of research activity in graph matching, which aims at finding the correspondence of nodes across two graphs and lies at the heart of many artificial intelligence applications. However, matching heterogeneous graphs with partial overlap remains a challenging problem in real-world applications. This paper proposes the first practical learning-to-match method to meet this challenge. The proposed unsupervised method adopts a novel partial OT paradigm to learn a transport plan and node embeddings simultaneously. In a from-one-to-all manner, the entire learning procedure is decomposed into a series of easy-to-solve sub-procedures, each of which only handles the alignment of a single type of nodes. A mechanism for searching the transport mass is also proposed. Experimental results demonstrate that the proposed method outperforms state-of-the-art graph matching methods.
Green Internet of Things: The Next Generation Energy Efficient Internet of Things
Venue: arXiv cs.CY 2021
Year: 2021

The Internet of Things (IoT) is seen as a novel technical paradigm aimed at enabling connectivity between billions of interconnected devices all around the world. This IoT is being served in various domains, such as smart healthcare, traffic surveillance, smart homes, smart cities, and various industries. IoT's main functionality includes sensing the surrounding environment, collecting data from the surrounding, and transmitting those data to the remote data centers or the cloud. This sharing of vast volumes of data between billions of IoT devices generates a large energy demand and increases energy wastage in the form of heat. The Green IoT envisages reducing the energy consumption of IoT devices and keeping the environment safe and clean. Inspired by achieving a sustainable next-generation IoT ecosystem and guiding us toward making a healthy green planet, we first offer an overview of Green IoT (GIoT), and then the challenges and the future directions regarding the GIoT are presented in our study.
$DA^3$:Dynamic Additive Attention Adaption for Memory-EfficientOn-Device Multi-Domain Learning
Venue: arXiv cs.CV 2021
Year: 2021

Nowadays, one practical limitation of deep neural network (DNN) is its high degree of specialization to a single task or domain (e.g., one visual domain). It motivates researchers to develop algorithms that can adapt DNN model to multiple domains sequentially, while still performing well on the past domains, which is known as multi-domain learning. Almost all conventional methods only focus on improving accuracy with minimal parameter update, while ignoring high computing and memory cost during training, which makes it difficult to deploy multi-domain learning into more and more widely used resource-limited edge devices, like mobile phones, IoT, embedded systems, etc. We observe that large memory used for activation storage is the bottleneck that largely limits the training time and cost on edge devices. To reduce training memory usage, while keeping the domain adaption accuracy performance, we propose Dynamic Additive Attention Adaption ($DA^3$), a novel memory-efficient on-device multi-domain learning method. $DA^3$ learns a novel additive attention adaptor module, while freezing the weights of the pre-trained backbone model for each domain. Differentiating from prior works, such module not only mitigates activation memory buffering for reducing memory usage during training but also serves as a dynamic gating mechanism to reduce the computation cost for fast inference. We validate $DA^3$ on multiple datasets against state-of-the-art methods, which shows great improvement in both accuracy and training time. Moreover, we deployed $DA^3$ into the popular NIVDIA Jetson Nano edge GPU, where the measured experimental results show our proposed $DA^3$ reduces the on-device training memory consumption by 19-37x, and training time by 2x, in comparison to the baseline methods (e.g., standard fine-tuning, Parallel and Series Res. adaptor, and Piggyback).
Going Beyond Classification Accuracy Metrics in Model Compression
Venue: arXiv cs.CV 2021
Year: 2021

With the rise in edge-computing devices, there has been an increasing demand to deploy energy and resource-efficient models. A large body of research has been devoted to developing methods that can reduce the size of the model considerably without affecting the standard metrics such as top-1 accuracy. However, these pruning approaches tend to result in a significant mismatch in other metrics such as fairness across classes and explainability. To combat such misalignment, we propose a novel multi-part loss function inspired by the knowledge-distillation literature. Through extensive experiments, we demonstrate the effectiveness of our approach across different compression algorithms, architectures, tasks as well as datasets. In particular, we obtain up to $4.1\times$ reduction in the number of prediction mismatches between the compressed and reference models, and up to $5.7\times$ in cases where the reference model makes the correct prediction; all while making no changes to the compression algorithm, and minor modifications to the loss function. Furthermore, we demonstrate how inducing simple alignment between the predictions of the models naturally improves the alignment on other metrics including fairness and attributions. Our framework can thus serve as a simple plug-and-play component for compression algorithms in the future.
Pedestrian Trajectory Prediction using Context-Augmented Transformer Networks
Venue: arXiv cs.CV 2021
Year: 2021

Forecasting the trajectory of pedestrians in shared urban traffic environments is still considered one of the challenging problems facing the development of autonomous vehicles (AVs). In the literature, this problem is often tackled using recurrent neural networks (RNNs). Despite the powerful capabilities of RNNs in capturing the temporal dependency in the pedestrians' motion trajectories, they were argued to be challenged when dealing with longer sequential data. Thus, in this work, we are introducing a framework based on the transformer networks that were shown recently to be more efficient and outperformed RNNs in many sequential-based tasks. We relied on a fusion of the past positional information, agent interactions information and scene physical semantics information as an input to our framework in order to provide a robust trajectory prediction of pedestrians. We have evaluated our framework on two real-life datasets of pedestrians in shared urban traffic environments and it has outperformed the compared baseline approaches in both short-term and long-term prediction horizons.
SemMT: A Semantic-based Testing Approach for Machine Translation Systems
Venue: arXiv cs.SE 2021
Year: 2021

Machine translation has wide applications in daily life. In mission-critical applications such as translating official documents, incorrect translation can have unpleasant or sometimes catastrophic consequences. This motivates recent research on testing methodologies for machine translation systems. Existing methodologies mostly rely on metamorphic relations designed at the textual level (e.g., Levenshtein distance) or syntactic level (e.g., the distance between grammar structures) to determine the correctness of translation results. However, these metamorphic relations do not consider whether the original and translated sentences have the same meaning (i.e., Semantic similarity). Therefore, in this paper, we propose SemMT, an automatic testing approach for machine translation systems based on semantic similarity checking. SemMT applies round-trip translation and measures the semantic similarity between the original and translated sentences. Our insight is that the semantics expressed by the logic and numeric constraint in sentences can be captured using regular expressions (or deterministic finite automata) where efficient equivalence/similarity checking algorithms are available. Leveraging the insight, we propose three semantic similarity metrics and implement them in SemMT. The experiment result reveals SemMT can achieve higher effectiveness compared with state-of-the-art works, achieving an increase of 21% and 23% on accuracy and F-Score, respectively. We also explore potential improvements that can be achieved when proper combinations of metrics are adopted. Finally, we discuss a solution to locate the suspicious trip in round-trip translation, which may shed lights on further exploration.
Towards Repairing Neural Networks Correctly
Venue: arXiv cs.LG 2021
Year: 2021

Neural networks are increasingly applied to support decision making in safety-critical applications (like autonomous cars, unmanned aerial vehicles and face recognition based authentication). While many impressive static verification techniques have been proposed to tackle the correctness problem of neural networks, it is possible that static verification may never be sufficiently scalable to handle real-world neural networks. In this work, we propose a runtime verification method to ensure the correctness of neural networks. Given a neural network and a desirable safety property, we adopt state-of-the-art static verification techniques to identify strategically locations to introduce additional gates which "correct" neural network behaviors at runtime. Experiment results show that our approach effectively generates neural networks which are guaranteed to satisfy the properties, whilst being consistent with the original neural network most of the time.
On Parameterized Complexity of Binary Networked Public Goods Game
Venue: arXiv cs.GT 2021
Year: 2021

In the Binary Networked Public Goods game, every player needs to decide if she participates in a public project whose utility is shared equally by the community. We study the problem of deciding if there exists a pure strategy Nash equilibrium (PSNE) in such games. The problem is already known to be NP-complete. We provide fine-grained analysis of this problem under the lens of parameterized complexity theory. We consider various natural graph parameters and show either W[1]-hardness or exhibit an FPT algorithm. We finally exhibit some special graph classes, for example path, cycle, bi-clique, complete graph, etc., which always have a PSNE if the utility function of the players are fully homogeneous.
SSGD: A safe and efficient method of gradient descent
Venue: arXiv cs.LG 2021
Year: 2021

With the vigorous development of artificial intelligence technology, various engineering technology applications have been implemented one after another. The gradient descent method plays an important role in solving various optimization problems, due to its simple structure, good stability and easy implementation. In multi-node machine learning system, the gradients usually need to be shared. Shared gradients are generally unsafe. Attackers can obtain training data simply by knowing the gradient information. In this paper, to prevent gradient leakage while keeping the accuracy of model, we propose the super stochastic gradient descent approach to update parameters by concealing the modulus length of gradient vectors and converting it or them into a unit vector. Furthermore, we analyze the security of super stochastic gradient descent approach. Our algorithm can defend against attacks on the gradient. Experiment results show that our approach is obviously superior to prevalent gradient descent approaches in terms of accuracy, robustness, and adaptability to large-scale batches.
Emergent Complexity and Zero-shot Transfer via Unsupervised Environment Design
Venue: arXiv cs.LG 2021
Year: 2021

A wide range of reinforcement learning (RL) problems - including robustness, transfer learning, unsupervised RL, and emergent complexity - require specifying a distribution of tasks or environments in which a policy will be trained. However, creating a useful distribution of environments is error prone, and takes a significant amount of developer time and effort. We propose Unsupervised Environment Design (UED) as an alternative paradigm, where developers provide environments with unknown parameters, and these parameters are used to automatically produce a distribution over valid, solvable environments. Existing approaches to automatically generating environments suffer from common failure modes: domain randomization cannot generate structure or adapt the difficulty of the environment to the agent's learning progress, and minimax adversarial training leads to worst-case environments that are often unsolvable. To generate structured, solvable environments for our protagonist agent, we introduce a second, antagonist agent that is allied with the environment-generating adversary. The adversary is motivated to generate environments which maximize regret, defined as the difference between the protagonist and antagonist agent's return. We call our technique Protagonist Antagonist Induced Regret Environment Design (PAIRED). Our experiments demonstrate that PAIRED produces a natural curriculum of increasingly complex environments, and PAIRED agents achieve higher zero-shot transfer performance when tested in highly novel environments.
Quantum Hoare Type Theory
Venue: arXiv cs.PL 2021
Year: 2021

As quantum computers become real, it is high time we come up with effective techniques that help programmers write correct quantum programs. Inspired by Hoare Type Theory in classical computing, we propose Quantum Hoare Type Theory (QHTT), in which precise specifications about the modification to the quantum state can be provided within the type of computation. These specifications within a Hoare type are given in the form of Hoare-logic style pre- and postconditions following the propositions-as-types principle. The type-checking process verifies that the implementation conforms to the provided specification. QHTT has the potential to be a unified system for programming, specifying, and reasoning about quantum programs.