OpenRaiser/Intern-Atlas huggingface dataset:
MapLUR: Exploring a new Paradigm for Estimating Air Pollution using Deep Learning on Map Images
Venue: arXiv cs.LG 2020
Year: 2020

Land-use regression (LUR) models are important for the assessment of air pollution concentrations in areas without measurement stations. While many such models exist, they often use manually constructed features based on restricted, locally available data. Thus, they are typically hard to reproduce and challenging to adapt to areas beyond those they have been developed for. In this paper, we advocate a paradigm shift for LUR models: We propose the Data-driven, Open, Global (DOG) paradigm that entails models based on purely data-driven approaches using only openly and globally available data. Progress within this paradigm will alleviate the need for experts to adapt models to the local characteristics of the available data sources and thus facilitate the generalizability of air pollution models to new areas on a global scale. In order to illustrate the feasibility of the DOG paradigm for LUR, we introduce a deep learning model called MapLUR. It is based on a convolutional neural network architecture and is trained exclusively on globally and openly available map data without requiring manual feature engineering. We compare our model to state-of-the-art baselines like linear regression, random forests and multi-layer perceptrons using a large data set of modeled $\text{NO}_2$ concentrations in Central London. Our results show that MapLUR significantly outperforms these approaches even though they are provided with manually tailored features. Furthermore, we illustrate that the automatic feature extraction inherent to models based on the DOG paradigm can learn features that are readily interpretable and closely resemble those commonly used in traditional LUR approaches.
Characterizing Synchronous Writes in Stable Memory Devices
Venue: arXiv cs.OS 2020
Year: 2020

Distributed algorithms that operate in the fail-recovery model rely on the state stored in stable memory to guarantee the irreversibility of operations even in the presence of failures. The performance of these algorithms lean heavily on the performance of stable memory. Current storage technologies have a defined performance profile: data is accessed in blocks of hundreds or thousands of bytes, random access to these blocks is expensive and sequential access is somewhat better. File system implementations hide some of the performance limitations of the underlying storage devices using buffers and caches. However, fail-recovery distributed algorithms bypass some of these techniques and perform synchronous writes to be able to tolerate a failure during the write itself. Assuming the distributed system designer is able to buffer the algorithm's writes, we ask how buffer size and latency complement each other. In this paper we start to answer this question by characterizing the performance (throughput and latency) of typical stable memory devices using a representative set of current file systems.
A Computationally Efficient Neural Network Invariant to the Action of Symmetry Subgroups
Venue: arXiv cs.LG 2020
Year: 2020

We introduce a method to design a computationally efficient $G$-invariant neural network that approximates functions invariant to the action of a given permutation subgroup $G \leq S_n$ of the symmetric group on input data. The key element of the proposed network architecture is a new $G$-invariant transformation module, which produces a $G$-invariant latent representation of the input data. This latent representation is then processed with a multi-layer perceptron in the network. We prove the universality of the proposed architecture, discuss its properties and highlight its computational and memory efficiency. Theoretical considerations are supported by numerical experiments involving different network configurations, which demonstrate the effectiveness and strong generalization properties of the proposed method in comparison to other $G$-invariant neural networks.
A Spiking Neural Network Emulating the Structure of the Oculomotor System Requires No Learning to Control a Biomimetic Robotic Head
Venue: arXiv cs.RO 2020
Year: 2020

Robotic vision introduces requirements for real-time processing of fast-varying, noisy information in a continuously changing environment. In a real-world environment, convenient assumptions, such as static camera systems and deep learning algorithms devouring high volumes of ideally slightly-varying data are hard to survive. Leveraging on recent studies on the neural connectome associated with eye movements, we designed a neuromorphic oculomotor controller and placed it at the heart of our in-house biomimetic robotic head prototype. The controller is unique in the sense that (1) all data are encoded and processed by a spiking neural network (SNN), and (2) by mimicking the associated brain areas' topology, the SNN is biologically interpretable and requires no training to operate. Here, we report the robot's target tracking ability, demonstrate that its eye kinematics are similar to those reported in human eye studies and show that a biologically-constrained learning, although not required for the SNN's function, can be used to further refine its performance. This work aligns with our ongoing effort to develop energy-efficient neuromorphic SNNs and harness their emerging intelligence to control biomimetic robots with versatility and robustness.
Expected Linear Round Synchronization: The Missing Link for Linear Byzantine SMR
Venue: arXiv cs.CR 2020
Year: 2020

State Machine Replication (SMR) solutions often divide time into rounds, with a designated leader driving decisions in each round. Progress is guaranteed once all correct processes synchronize to the same round, and the leader of that round is correct. Recently suggested Byzantine SMR solutions such as HotStuff, Tendermint, and LibraBFT achieve progress with a linear message complexity and a constant time complexity once such round synchronization occurs. But round synchronization itself incurs an additional cost. By Dolev and Reischuk's lower bound, any deterministic solution must have $Ω(n^2)$ communication complexity. Yet the question of randomized round synchronization with an expected linear message complexity remained open. We present an algorithm that, for the first time, achieves round synchronization with expected linear message complexity and expected constant latency. Existing protocols can use our round synchronization algorithm to solve Byzantine SMR with the same asymptotic performance.
Synthesis in Presence of Dynamic Links
Venue: arXiv cs.FL 2020
Year: 2020

The problem of distributed synthesis is to automatically generate a distributed algorithm, given a target communication network and a specification of the algorithm's correct behavior. Previous work has focused on static networks with an a priori fixed message size. This approach has two shortcomings: Recent work in distributed computing is shifting towards dynamically changing communication networks rather than static ones, and an important class of distributed algorithms are so-called full-information protocols, where nodes piggy-pack previously received messages onto current messages. In this work, we consider the synthesis problem for a system of two nodes communicating in rounds over a dynamic link whose message size is not bounded. Given a network model, i.e., a set of link directions, in each round of the execution, the adversary choses a link from the network model, restricted only by the specification, and delivers messages according to the current link's directions. Motivated by communication buses with direct acknowledge mechanisms, we further assume that nodes are aware of which messages have been delivered. We show that the synthesis problem is decidable for a network model if and only if it does not contain the empty link that dismisses both nodes' messages.
A Computational Approach to Packet Classification
Venue: arXiv cs.DC 2020
Year: 2020

Multi-field packet classification is a crucial component in modern software-defined data center networks. To achieve high throughput and low latency, state-of-the-art algorithms strive to fit the rule lookup data structures into on-die caches; however, they do not scale well with the number of rules. We present a novel approach, NuevoMatch, which improves the memory scaling of existing methods. A new data structure, Range Query Recursive Model Index (RQ-RMI), is the key component that enables NuevoMatch to replace most of the accesses to main memory with model inference computations. We describe an efficient training algorithm that guarantees the correctness of the RQ-RMI-based classification. The use of RQ-RMI allows the rules to be compressed into model weights that fit into the hardware cache. Further, it takes advantage of the growing support for fast neural network processing in modern CPUs, such as wide vector instructions, achieving a rate of tens of nanoseconds per lookup. Our evaluation using 500K multi-field rules from the standard ClassBench benchmark shows a geometric mean compression factor of 4.9x, 8x, and 82x, and average performance improvement of 2.4x, 2.6x, and 1.6x in throughput compared to CutSplit, NeuroCuts, and TupleMerge, all state-of-the-art algorithms.
Three-dimensional convolutional neural network (3D-CNN) for heterogeneous material homogenization
Venue: arXiv cs.CE 2020
Year: 2020

Homogenization is a technique commonly used in multiscale computational science and engineering for predicting collective response of heterogeneous materials and extracting effective mechanical properties. In this paper, a three-dimensional deep convolutional neural network (3D-CNN) is proposed to predict the effective material properties for representative volume elements (RVEs) with random spherical inclusions. The high-fidelity dataset generated by a computational homogenization approach is used for training the 3D-CNN models. The inference results of the trained networks on unseen data indicate that the network is capable of capturing the microstructural features of RVEs and produces an accurate prediction of effective stiffness and Poisson's ratio. The benefits of the 3D-CNN over conventional finite-element-based homogenization with regard to computational efficiency, uncertainty quantification and model's transferability are discussed in sequence. We find the salient features of the 3D-CNN approach make it a potentially suitable alternative for facilitating material design with fast product design iteration and efficient uncertainty quantification.
An interpretable classifier for high-resolution breast cancer screening images utilizing weakly supervised localization
Venue: arXiv cs.CV 2020
Year: 2020

Medical images differ from natural images in significantly higher resolutions and smaller regions of interest. Because of these differences, neural network architectures that work well for natural images might not be applicable to medical image analysis. In this work, we extend the globally-aware multiple instance classifier, a framework we proposed to address these unique properties of medical images. This model first uses a low-capacity, yet memory-efficient, network on the whole image to identify the most informative regions. It then applies another higher-capacity network to collect details from chosen regions. Finally, it employs a fusion module that aggregates global and local information to make a final prediction. While existing methods often require lesion segmentation during training, our model is trained with only image-level labels and can generate pixel-level saliency maps indicating possible malignant findings. We apply the model to screening mammography interpretation: predicting the presence or absence of benign and malignant lesions. On the NYU Breast Cancer Screening Dataset, consisting of more than one million images, our model achieves an AUC of 0.93 in classifying breasts with malignant findings, outperforming ResNet-34 and Faster R-CNN. Compared to ResNet-34, our model is 4.1x faster for inference while using 78.4% less GPU memory. Furthermore, we demonstrate, in a reader study, that our model surpasses radiologist-level AUC by a margin of 0.11. The proposed model is available online: https://github.com/nyukat/GMIC.
Golay Layer: Limiting Peak-to-Average Power Ratio for OFDM-based Autoencoders
Venue: arXiv cs.IT 2020
Year: 2020

In this study, we propose a differentiable layer for OFDM-based autoencoders (OFDM-AEs) to avoid high instantaneous power without regularizing the cost function used during the training. The proposed approach relies on the manipulation of the parameters of a set of functions that yield complementary sequences (CSs) through a deep neural network (DNN). We guarantee the peak-to-average-power ratio (PAPR) of each OFDM-AE symbol to be less than or equal to 3 dB. We also show how to normalize the mean power by using the functions in addition to PAPR. The introduced layer admits auxiliary parameters that allow one to control the amplitude and phase deviations in the frequency domain. Numerical results show that DNNs at the transmitter and receiver can achieve reliable communications under this protection layer at the expense of complexity.
Local Propagation in Constraint-based Neural Network
Venue: arXiv cs.LG 2020
Year: 2020

In this paper we study a constraint-based representation of neural network architectures. We cast the learning problem in the Lagrangian framework and we investigate a simple optimization procedure that is well suited to fulfil the so-called architectural constraints, learning from the available supervisions. The computational structure of the proposed Local Propagation (LP) algorithm is based on the search for saddle points in the adjoint space composed of weights, neural outputs, and Lagrange multipliers. All the updates of the model variables are locally performed, so that LP is fully parallelizable over the neural units, circumventing the classic problem of gradient vanishing in deep networks. The implementation of popular neural models is described in the context of LP, together with those conditions that trace a natural connection with Backpropagation. We also investigate the setting in which we tolerate bounded violations of the architectural constraints, and we provide experimental evidence that LP is a feasible approach to train shallow and deep networks, opening the road to further investigations on more complex architectures, easily describable by constraints.
Image encryption based on flexible computing of chaotic systems
Venue: arXiv cs.CR 2020
Year: 2020

The increase in data traffic on the internet has significantly increased the relevance of data and image encryption. Among the techniques most used in cryptography, chaotic systems have received great attention due to their easy implementation. However, it has recently been observed that these systems can lose their chaotic properties due to the finite precision of computers. In this work, we intend to investigate flexible computing tools, particularly interval analysis, to reduce this problem. We opted for the Lorenz System, as it is one of the few systems whose chaoticity is proven analytically. The results of this study, based on the correlation and entropy indexes, were superior to other studies published in the recent literature.
Mapping the Interplanetary Filesystem
Venue: arXiv cs.NI 2020
Year: 2020

The Interplanetary Filesystem (IPFS) is a distributed data storage service frequently used by blockchain applications and for sharing content in a censorship-resistant manner. Data is distributed within an open set of peers using a Kademlia-based distributed hash table (DHT). In this paper, we study the structure of the resulting overlay network, as it significantly influences the robustness and performance of IPFS. We monitor and systematically crawl IPFS' DHT towards mapping the IPFS overlay network. Our measurements found an average of 44474 nodes at every given time. At least 52.19% of these reside behind a NAT and are not reachable from the outside, suggesting that a large share of the network is operated by private individuals on an as-needed basis. Based on our measurements and our analysis of the IPFS code, we conclude that the topology of the IPFS network is, in its current state, closer to an unstructured overlay network than it is to a classical DHT. While such a structure has benefits for robustness and the resistance against Sybil attacks, it leaves room for improvement in terms of performance and query privacy.
GCSA Codes with Noise Alignment for Secure Coded Multi-Party Batch Matrix Multiplication
Venue: arXiv cs.IT 2020
Year: 2020

A secure multi-party batch matrix multiplication problem (SMBMM) is considered, where the goal is to allow a master to efficiently compute the pairwise products of two batches of massive matrices, by distributing the computation across S servers. Any X colluding servers gain no information about the input, and the master gains no additional information about the input beyond the product. A solution called Generalized Cross Subspace Alignment codes with Noise Alignment (GCSA-NA) is proposed in this work, based on cross-subspace alignment codes. The state of art solution to SMBMM is a coding scheme called polynomial sharing (PS) that was proposed by Nodehi and Maddah-Ali. GCSA-NA outperforms PS codes in several key aspects - more efficient and secure inter-server communication, lower latency, flexible inter-server network topology, efficient batch processing, and tolerance to stragglers. The idea of noise alignment can also be combined with N-source Cross Subspace Alignment (N-CSA) codes and fast matrix multiplication algorithms like Strassen's construction. Moreover, noise alignment can be applied to symmetric secure private information retrieval to achieve the asymptotic capacity.
Marvel: A Data-centric Compiler for DNN Operators on Spatial Accelerators
Venue: arXiv cs.DC 2020
Year: 2020

The efficiency of a spatial DNN accelerator depends heavily on the compiler and its cost model ability to generate optimized mappings for various operators of DNN models on to the accelerator's compute and memory resources. But, existing cost models lack a formal boundary over the operators for precise and tractable analysis, which poses adaptability challenges for new DNN operators. To address this challenge, we leverage the recently introduced Maestro Data-Centric (MDC) notation. We develop a formal understanding of DNN operators whose mappings can be described in the MDC notation, because any mapping adhering to the notation is always analyzable by the MDC's cost model. Furthermore, we introduce a transformation for translating mappings into the MDC notation for exploring the mapping space. Searching for the optimal mappings is challenging because of the large space of mappings, and this challenge gets exacerbated with new operators and diverse accelerator configurations.To address this challenge, we propose a decoupled off-chip/on-chip approach that decomposes the mapping space into off-chip and on-chip subspaces, and first optimizes the off-chip subspace followed by the on-chip subspace. The motivation for this decomposition is to reduce the size of the search space dramatically and also to prioritize the optimization of off-chip data movement, which is 2-3 orders of magnitude more compared to the on-chip data movement. We implemented our approach in a tool called {\em Marvel}, and another major benefit of our approach is that it is applicable to any DNN operator conformable with the MDC notation.
Verified Instruction-Level Energy Consumption Measurement for NVIDIA GPUs
Venue: arXiv cs.DC 2020
Year: 2020

GPUs are prevalent in modern computing systems at all scales. They consume a significant fraction of the energy in these systems. However, vendors do not publish the actual cost of the power/energy overhead of their internal microarchitecture. In this paper, we accurately measure the energy consumption of various PTX instructions found in modern NVIDIA GPUs. We provide an exhaustive comparison of more than 40 instructions for four high-end NVIDIA GPUs from four different generations (Maxwell, Pascal, Volta, and Turing). Furthermore, we show the effect of the CUDA compiler optimizations on the energy consumption of each instruction. We use three different software techniques to read the GPU on-chip power sensors, which use NVIDIA's NVML API and provide an in-depth comparison between these techniques. Additionally, we verified the software measurement techniques against a custom-designed hardware power measurement. The results show that Volta GPUs have the best energy efficiency of all the other generations for the different categories of the instructions. This work should aid in understanding NVIDIA GPUs' microarchitecture. It should also make energy measurements of any GPU kernel both efficient and accurate.
Polynomial Time Algorithms for Tracking Path Problems
Venue: arXiv cs.DS 2020
Year: 2020

Given a graph $G$, and terminal vertices $s$ and $t$, the TRACKING PATHS problem asks to compute a minimum number of vertices to be marked as trackers, such that the sequence of trackers encountered in each s-t path is unique. TRACKING PATHS is NP-hard in both directed and undirected graphs in general. In this paper we give a collection of polynomial time algorithms for some restricted versions of TRACKING PATHS. We prove that TRACKING PATHS is polynomial time solvable for chordal graphs and tournament graphs. We prove that TRACKING PATHS is NP-hard in graphs with bounded maximum degree $δ\geq 6$, and give a $2(δ+1)$-approximate algorithm for the same. We also analyze the version of tracking s-t paths where paths are tracked using edges instead of vertices, and we give a polynomial time algorithm for the same. Finally, we show how to reconstruct an s-t path, given a sequence of trackers and a tracking set for the graph in consideration.
Collusion Attacks on Decentralized Attributed-Based Encryption: Analyses and a Solution
Venue: arXiv cs.CR 2020
Year: 2020

Attribute-based Encryption (ABE) is an information centric security solution that moves beyond traditional restrictions of point-to-point encryption by allowing for flexible, fine-grain policy-based and content-based access control that is cryptographically enforced. As the original ABE systems are managed by a single authority, several efforts have decentralized different ABE schemes to address the key escrow problem, where the authority can issue secret keys to itself to decrypt all the ciphertext. However, decentralized ABE (DABE) schemes raise the issue of collusion attacks. In this paper, we review two existing types of collusion attacks on DABE systems, and introduce a new type of collusion among authorities and data users. We show that six existing DABE systems are vulnerable to the newly introduced collusion and propose a model to secure one of the DABE schemes.
Theoretical Convergence of Multi-Step Model-Agnostic Meta-Learning
Venue: arXiv cs.LG 2020
Year: 2020

As a popular meta-learning approach, the model-agnostic meta-learning (MAML) algorithm has been widely used due to its simplicity and effectiveness. However, the convergence of the general multi-step MAML still remains unexplored. In this paper, we develop a new theoretical framework to provide such convergence guarantee for two types of objective functions that are of interest in practice: (a) resampling case (e.g., reinforcement learning), where loss functions take the form in expectation and new data are sampled as the algorithm runs; and (b) finite-sum case (e.g., supervised learning), where loss functions take the finite-sum form with given samples. For both cases, we characterize the convergence rate and the computational complexity to attain an $ε$-accurate solution for multi-step MAML in the general nonconvex setting. In particular, our results suggest that an inner-stage stepsize needs to be chosen inversely proportional to the number $N$ of inner-stage steps in order for $N$-step MAML to have guaranteed convergence. From the technical perspective, we develop novel techniques to deal with the nested structure of the meta gradient for multi-step MAML, which can be of independent interest.