OpenRaiser/Intern-Atlas huggingface dataset:
Learning perturbation sets for robust machine learning
Venue: arXiv cs.LG 2020
Year: 2020

Although much progress has been made towards robust deep learning, a significant gap in robustness remains between real-world perturbations and more narrowly defined sets typically studied in adversarial defenses. In this paper, we aim to bridge this gap by learning perturbation sets from data, in order to characterize real-world effects for robust training and evaluation. Specifically, we use a conditional generator that defines the perturbation set over a constrained region of the latent space. We formulate desirable properties that measure the quality of a learned perturbation set, and theoretically prove that a conditional variational autoencoder naturally satisfies these criteria. Using this framework, our approach can generate a variety of perturbations at different complexities and scales, ranging from baseline spatial transformations, through common image corruptions, to lighting variations. We measure the quality of our learned perturbation sets both quantitatively and qualitatively, finding that our models are capable of producing a diverse set of meaningful perturbations beyond the limited data seen during training. Finally, we leverage our learned perturbation sets to train models which are empirically and certifiably robust to adversarial image corruptions and adversarial lighting variations, while improving generalization on non-adversarial data. All code and configuration files for reproducing the experiments as well as pretrained model weights can be found at https://github.com/locuslab/perturbation_learning.
Vulnerability-Aware Resilient Networks: Software Diversity-based Network Adaptation
Venue: arXiv cs.CR 2020
Year: 2020

By leveraging the principle of software polyculture to ensure security in a network, we proposed a vulnerability-based software diversity metric to determine how a network topology can be adapted to minimize security vulnerability while maintaining maximum network connectivity. Our proposed software diversity-based adaptation (SDA) scheme estimates a node's software diversity based on the vulnerabilities of software packages installed on other nodes on attack paths reachable to the node and employs it for edge adaptations, such as removing an edge with a neighboring node that exposes high security vulnerability because two connected nodes use the same software packages or a neighboring node may have high software vulnerability or adding an edge with another node with less or no security vulnerability because the two nodes use different software packages or have low vulnerabilities associated with them. To validate the proposed SDA scheme, we conducted extensive experiments comparing the proposed SDA scheme with counterpart baseline schemes in real networks. Our simulation experimental results proved the outperformance of our proposed SDA compared to the existing counterparts and provided insightful findings in terms of the effectiveness and efficiency of the proposed SDA scheme under three real network topologies with vastly different network density.
Implicit Mesh Reconstruction from Unannotated Image Collections
Venue: arXiv cs.CV 2020
Year: 2020

We present an approach to infer the 3D shape, texture, and camera pose for an object from a single RGB image, using only category-level image collections with foreground masks as supervision. We represent the shape as an image-conditioned implicit function that transforms the surface of a sphere to that of the predicted mesh, while additionally predicting the corresponding texture. To derive supervisory signal for learning, we enforce that: a) our predictions when rendered should explain the available image evidence, and b) the inferred 3D structure should be geometrically consistent with learned pixel to surface mappings. We empirically show that our approach improves over prior work that leverages similar supervision, and in fact performs competitively to methods that use stronger supervision. Finally, as our method enables learning with limited supervision, we qualitatively demonstrate its applicability over a set of about 30 object categories.
Soft Errors Detection and Automatic Recovery based on Replication combined with different Levels of Checkpointing
Venue: arXiv cs.DC 2020
Year: 2020

Handling faults is a growing concern in HPC. In future exascale systems, it is projected that silent undetected errors will occur several times a day, increasing the occurrence of corrupted results. In this article, we propose SEDAR, which is a methodology that improves system reliability against transient faults when running parallel message-passing applications. Our approach, based on process replication for detection, combined with different levels of checkpointing for automatic recovery, has the goal of helping users of scientific applications to obtain executions with correct results. SEDAR is structured in three levels: (1) only detection and safe-stop with notification; (2) recovery based on multiple system-level checkpoints; and (3) recovery based on a single valid user-level checkpoint. As each of these variants supplies a particular coverage but involves limitations and implementation costs, SEDAR can be adapted to the needs of the system. In this work, a description of the methodology is presented and the temporal behavior of employing each SEDAR strategy is mathematically described, both in the absence and presence of faults. A model that considers all the fault scenarios on a test application is introduced to show the validity of the detection and recovery mechanisms. An overhead evaluation of each variant is performed with applications involving different communication patterns; this is also used to extract guidelines about when it is beneficial to employ each SEDAR protection level. As a result, we show its efficacy and viability to tolerate transient faults in target HPC environments.
Age of Information: An Introduction and Survey
Venue: arXiv cs.IT 2020
Year: 2020

We summarize recent contributions in the broad area of age of information (AoI). In particular, we describe the current state of the art in the design and optimization of low-latency cyberphysical systems and applications in which sources send time-stamped status updates to interested recipients. These applications desire status updates at the recipients to be as timely as possible; however, this is typically constrained by limited system resources. We describe AoI timeliness metrics and present general methods of AoI evaluation analysis that are applicable to a wide variety of sources and systems. Starting from elementary single-server queues, we apply these AoI methods to a range of increasingly complex systems, including energy harvesting sensors transmitting over noisy channels, parallel server systems, queueing networks, and various single-hop and multi-hop wireless networks. We also explore how update age is related to MMSE methods of sampling, estimation and control of stochastic processes. The paper concludes with a review of efforts to employ age optimization in cyberphysical applications.
SRv6-PM: Performance Monitoring of SRv6 Networks with a Cloud-Native Architecture
Venue: arXiv cs.NI 2020
Year: 2020

Segment Routing over IPv6 (SRv6 in short) is a networking solution for IP backbones and datacenters. The SRv6 standardization, implementation and research are actively progressing and SRv6 has already been adopted in a number of large scale network deployments. Effective Performance Monitoring (PM) solutions for SRv6 networks are strongly needed. The design, implementation and deployment of such PM solutions span the different planes of a networking architecture: Performance Measurements data (packet loss and delay) needs to be measured (in the Data Plane), the monitored nodes needs to be controlled (in the Control Plane), the measured data needs to be collected (in the Control/Management Planes), then the Data must be processed and stored, using Big-Data processing solutions. We focus on Loss Monitoring, by considering a solution capable of tracking single packet loss events in near-real time (e.g. with a delay in the order of 20 seconds). We describe SRv6-PM, a solution for Performance Monitoring of SRv6 networks. SRv6-PM features a cloud-native architecture for the SDN-based control of Linux routers and for ingestion, processing, storage and visualization of PM data. In the Data Plane, SRv6-PM includes efficient building blocks for packet loss evaluation (e.g. the packet counting components) in a Linux router. SRv6-PM is released as open source. Not only we provide a reproducible environment for PM experiments, but we also offer a re-usable and extensible cloud-native platform that can be automatically deployed in different environments, from a single host to multiple servers on private/public clouds.
SiamParseNet: Joint Body Parsing and Label Propagation in Infant Movement Videos
Venue: arXiv cs.CV 2020
Year: 2020

General movement assessment (GMA) of infant movement videos (IMVs) is an effective method for the early detection of cerebral palsy (CP) in infants. Automated body parsing is a crucial step towards computer-aided GMA, in which infant body parts are segmented and tracked over time for movement analysis. However, acquiring fully annotated data for video-based body parsing is particularly expensive due to the large number of frames in IMVs. In this paper, we propose a semi-supervised body parsing model, termed SiamParseNet (SPN), to jointly learn single frame body parsing and label propagation between frames in a semi-supervised fashion. The Siamese-structured SPN consists of a shared feature encoder, followed by two separate branches: one for intra-frame body parts segmentation, and one for inter-frame label propagation. The two branches are trained jointly, taking pairs of frames from the same videos as their input. An adaptive training process is proposed that alternates training modes between using input pairs of only labeled frames and using inputs of both labeled and unlabeled frames. During testing, we employ a multi-source inference mechanism, where the final result for a test frame is either obtained via the segmentation branch or via propagation from a nearby key frame. We conduct extensive experiments on a partially-labeled IMV dataset where SPN outperforms all prior arts, demonstrating the effectiveness of our proposed method.
A Technical Report for VIPriors Image Classification Challenge
Venue: arXiv cs.CV 2020
Year: 2020

Image classification has always been a hot and challenging task. This paper is a brief report to our submission to the VIPriors Image Classification Challenge. In this challenge, the difficulty is how to train the model from scratch without any pretrained weight. In our method, several strong backbones and multiple loss functions are used to learn more representative features. To improve the models' generalization and robustness, efficient image augmentation strategies are utilized, like autoaugment and cutmix. Finally, ensemble learning is used to increase the performance of the models. The final Top-1 accuracy of our team DeepBlueAI is 0.7015, ranking second in the leaderboard.
Tight Bounds for the Price of Anarchy and Stability in Sequential Transportation Games
Venue: arXiv cs.GT 2020
Year: 2020

In this paper, we analyze a transportation game first introduced by Fotakis, Gourvès, and Monnot in 2017, where players want to be transported to a common destination as quickly as possible and, in order to achieve this goal, they have to choose one of the available buses. We introduce a sequential version of this game and provide bounds for the Sequential Price of Stability and the Sequential Price of Anarchy in both metric and non-metric instances, considering three social cost functions: the total traveled distance by all buses, the maximum distance traveled by a bus, and the sum of the distances traveled by all players (a new social cost function that we introduce). Finally, we analyze the Price of Stability and the Price of Anarchy for this new function in simultaneous transportation games.
Deep Learning Based Traffic Surveillance System For Missing and Suspicious Car Detection
Venue: arXiv cs.CV 2020
Year: 2020

Vehicle theft is arguably one of the fastest-growing types of crime in India. In some of the urban areas, vehicle theft cases are believed to be around 100 each day. Identification of stolen vehicles in such precarious scenarios is not possible using traditional methods like manual checking and radio frequency identification(RFID) based technologies. This paper presents a deep learning based automatic traffic surveillance system for the detection of stolen/suspicious cars from the closed circuit television(CCTV) camera footage. It mainly comprises of four parts: Select-Detector, Image Quality Enhancer, Image Transformer, and Smart Recognizer. The Select-Detector is used for extracting the frames containing vehicles and to detect the license plates much efficiently with minimum time complexity. The quality of the license plates is then enhanced using Image Quality Enhancer which uses pix2pix generative adversarial network(GAN) for enhancing the license plates that are affected by temporal changes like low light, shadow, etc. Image Transformer is used to tackle the problem of inefficient recognition of license plates which are not horizontal(which are at an angle) by transforming the license plate to different levels of rotation and cropping. Smart Recognizer recognizes the license plate number using Tesseract optical character recognition(OCR) and corrects the wrongly recognized characters using Error-Detector. The effectiveness of the proposed approach is tested on the government's CCTV camera footage, which resulted in identifying the stolen/suspicious cars with an accuracy of 87%.
Effect of Retransmissions on the Performance of C-V2X Communication for 5G
Venue: arXiv cs.NI 2020
Year: 2020

In recent years, the next generation of wireless communication (5G) plays a significant role in both industry and academy societies. Cellular Vehicle-to-Everything (C-V2X) communication technology has been one of the prominent services for 5G. For C-V2X transmission mode, there is a newly defined communication channel (sidelink) that can support direct C-V2X communication. Direct C-V2X communication is a technology that allows vehicles to communicate and share safety-related information with other traffic participates directly without going through the cellular network. The C-V2X data packet will be delivered to all traffic Users (UE) in the proximity of the Transmitter (Tx). Some UEs might not successfully receive the data packets during one transmission but the sidelink Tx is not able to check whether the Receivers (Rxs) get the information or not due to the lack of feedback channel. For enabling the strict requirements in terms of reliability and latency for C-V2X communication, we propose and evaluate one retransmission scheme and retransmission with different traffic speed scheme. These schemes try to improve the reliability of the safety-related data by one blind retransmission without requiring feedback. Although this retransmission scheme is essential to C-V2X communication, the scheme has a limitation in the performance aspect because of its redundant retransmission. Since radio resources for CV2X communication are limited, we have to detect the effect of retransmission on the performance of the communication system. To the end, the simulator for evaluating the proposed schemes for the C-V2X communication has been implemented, and the performances of the different communication schemes are shown through the Packet Reception Ratio (PRR).
A Differential Game Theoretic Neural Optimizer for Training Residual Networks
Venue: arXiv cs.LG 2020
Year: 2020

Connections between Deep Neural Networks (DNNs) training and optimal control theory has attracted considerable attention as a principled tool of algorithmic design. Differential Dynamic Programming (DDP) neural optimizer is a recently proposed method along this line. Despite its empirical success, the applicability has been limited to feedforward networks and whether such a trajectory-optimization inspired framework can be extended to modern architectures remains unclear. In this work, we derive a generalized DDP optimizer that accepts both residual connections and convolution layers. The resulting optimal control representation admits a game theoretic perspective, in which training residual networks can be interpreted as cooperative trajectory optimization on state-augmented dynamical systems. This Game Theoretic DDP (GT-DDP) optimizer enjoys the same theoretic connection in previous work, yet generates a much complex update rule that better leverages available information during network propagation. Evaluation on image classification datasets (e.g. MNIST and CIFAR100) shows an improvement in training convergence and variance reduction over existing methods. Our approach highlights the benefit gained from architecture-aware optimization.
All-Pairs LCA in DAGs: Breaking through the $O(n^{2.5})$ barrier
Venue: arXiv cs.DS 2020
Year: 2020

Let $G=(V,E)$ be an $n$-vertex directed acyclic graph (DAG). A lowest common ancestor (LCA) of two vertices $u$ and $v$ is a common ancestor $w$ of $u$ and $v$ such that no descendant of $w$ has the same property. In this paper, we consider the problem of computing an LCA, if any, for all pairs of vertices in a DAG. The fastest known algorithms for this problem exploit fast matrix multiplication subroutines and have running times ranging from $O(n^{2.687})$ [Bender et al.~SODA'01] down to $O(n^{2.615})$ [Kowaluk and Lingas~ICALP'05] and $O(n^{2.569})$ [Czumaj et al.~TCS'07]. Somewhat surprisingly, all those bounds would still be $Ω(n^{2.5})$ even if matrix multiplication could be solved optimally (i.e., $ω=2$). This appears to be an inherent barrier for all the currently known approaches, which raises the natural question on whether one could break through the $O(n^{2.5})$ barrier for this problem. In this paper, we answer this question affirmatively: in particular, we present an $\tilde O(n^{2.447})$ ($\tilde O(n^{7/3})$ for $ω=2$) algorithm for finding an LCA for all pairs of vertices in a DAG, which represents the first improvement on the running times for this problem in the last 13 years. A key tool in our approach is a fast algorithm to partition the vertex set of the transitive closure of $G$ into a collection of $O(\ell)$ chains and $O(n/\ell)$ antichains, for a given parameter $\ell$. As usual, a chain is a path while an antichain is an independent set. We then find, for all pairs of vertices, a \emph{candidate} LCA among the chain and antichain vertices, separately. The first set is obtained via a reduction to min-max matrix multiplication. The computation of the second set can be reduced to Boolean matrix multiplication similarly to previous results on this problem. We finally combine the two solutions together in a careful (non-obvious) manner.
Parameterized Complexity of Scheduling Chains of Jobs with Delays
Venue: arXiv cs.CC 2020
Year: 2020

In this paper, we consider the parameterized complexity of the following scheduling problem. We must schedule a number of jobs on $m$ machines, where each job has unit length, and the graph of precedence constraints consists of a set of chains. Each precedence constraint is labelled with an integer that denotes the exact (or minimum) delay between the jobs. We study different cases; delays can be given in unary and in binary, and the case that we have a single machine is discussed separately. We consider the complexity of this problem parameterized by the number of chains, and by the thickness of the instance, which is the maximum number of chains whose intervals between release date and deadline overlap. We show that this scheduling problem with exact delays in unary is $W[t]$-hard for all $t$, when parameterized by the thickness, even when we have a single machine ($m = 1$). When parameterized by the number of chains, this problem is $W[1]$-complete when we have a single or a constant number of machines, and $W[2]$-complete when the number of machines is a variable. The problem with minimum delays, given in unary, parameterized by the number of chains (and as a simple corollary, also when parameterized by the thickness) is $W[1]$-hard for a single or a constant number of machines, and $W[2]$-hard when the number of machines is variable. With a dynamic programming algorithm, one can show membership in XP for exact and minimum delays in unary, for any number of machines, when parameterized by thickness or number of chains. For a single machine, with exact delays in binary, parameterized by the number of chains, membership in XP can be shown with branching and solving a system of difference constraints. For all other cases for delays in binary, membership in XP is open.
Standing on the Shoulders of Giants: Hardware and Neural Architecture Co-Search with Hot Start
Venue: arXiv cs.LG 2020
Year: 2020

Hardware and neural architecture co-search that automatically generates Artificial Intelligence (AI) solutions from a given dataset is promising to promote AI democratization; however, the amount of time that is required by current co-search frameworks is in the order of hundreds of GPU hours for one target hardware. This inhibits the use of such frameworks on commodity hardware. The root cause of the low efficiency in existing co-search frameworks is the fact that they start from a "cold" state (i.e., search from scratch). In this paper, we propose a novel framework, namely HotNAS, that starts from a "hot" state based on a set of existing pre-trained models (a.k.a. model zoo) to avoid lengthy training time. As such, the search time can be reduced from 200 GPU hours to less than 3 GPU hours. In HotNAS, in addition to hardware design space and neural architecture search space, we further integrate a compression space to conduct model compressing during the co-search, which creates new opportunities to reduce latency but also brings challenges. One of the key challenges is that all of the above search spaces are coupled with each other, e.g., compression may not work without hardware design support. To tackle this issue, HotNAS builds a chain of tools to design hardware to support compression, based on which a global optimizer is developed to automatically co-search all the involved search spaces. Experiments on ImageNet dataset and Xilinx FPGA show that, within the timing constraint of 5ms, neural architectures generated by HotNAS can achieve up to 5.79% Top-1 and 3.97% Top-5 accuracy gain, compared with the existing ones.
The Combinatorial Santa Claus Problem or: How to Find Good Matchings in Non-Uniform Hypergraphs
Venue: arXiv cs.DS 2020
Year: 2020

We consider hypergraphs on vertices $P\cup R$ where each hyperedge contains exactly one vertex in $P$. Our goal is to select a matching that covers all of $P$, but we allow each selected hyperedge to drop all but an $(1/α)$-fraction of its intersection with $R$ (thus relaxing the matching constraint). Here $α$ is to be minimized. We dub this problem the Combinatorial Santa Claus problem, since we show in this paper that this problem and the Santa Claus problem are almost equivalent in terms of their approximability. The non-trivial observation that any uniform regular hypergraph admits a relaxed matching for $α= O(1)$ was a major step in obtaining a constant approximation rate for a special case of the Santa Claus problem, which received great attention in literature. It is natural to ask if the uniformity condition can be omitted. Our main result is that every (non-uniform) regular hypergraph admits a relaxed matching for $α= O(\log\log(|R|))$, when all hyperedges are sufficiently large (a condition that is necessary). In particular, this implies an $O(\log\log(|R|))$-approximation algorithm for the Combinatorial Santa Claus problem with large hyperedges.