OpenRaiser/Intern-Atlas huggingface dataset:
A survey on subjecting electronic product code and non-ID objects to IP identification
Venue: arXiv cs.NI 2020
Year: 2020

Over the last decade, both research on the Internet of Things (IoT) and real-world IoT applications have grown exponentially. The IoT provides us with smarter cities, intelligent homes, and generally more comfortable lives. However, the introduction of these devices has led to several new challenges that must be addressed. One of the critical challenges facing interacting with IoT devices is to address billions of devices (things) around the world, including computers, tablets, smartphones, wearable devices, sensors, and embedded computers, and so on. This article provides a survey on subjecting Electronic Product Code and non-ID objects to IP identification for IoT devices, including their advantages and disadvantages thereof. Different metrics are here proposed and used for evaluating these methods. In particular, the main methods are evaluated in terms of their: (i) computational overhead, (ii) scalability, (iii) adaptability, (iv) implementation cost, and (v) whether applicable to already ID-based objects and presented in tabular format. Finally, the article proves that this field of research will still be ongoing, but any new technique must favorably offer the mentioned five evaluative parameters.
Accelerated physical emulation of Bayesian inference in spiking neural networks
Venue: arXiv cs.NE 2020
Year: 2020

The massively parallel nature of biological information processing plays an important role for its superiority to human-engineered computing devices. In particular, it may hold the key to overcoming the von Neumann bottleneck that limits contemporary computer architectures. Physical-model neuromorphic devices seek to replicate not only this inherent parallelism, but also aspects of its microscopic dynamics in analog circuits emulating neurons and synapses. However, these machines require network models that are not only adept at solving particular tasks, but that can also cope with the inherent imperfections of analog substrates. We present a spiking network model that performs Bayesian inference through sampling on the BrainScaleS neuromorphic platform, where we use it for generative and discriminative computations on visual data. By illustrating its functionality on this platform, we implicitly demonstrate its robustness to various substrate-specific distortive effects, as well as its accelerated capability for computation. These results showcase the advantages of brain-inspired physical computation and provide important building blocks for large-scale neuromorphic applications.
Tractable $n$-Metrics for Multiple Graphs
Venue: arXiv cs.DM 2020
Year: 2020

Graphs are used in almost every scientific discipline to express relations among a set of objects. Algorithms that compare graphs, and output a closeness score, or a correspondence among their nodes, are thus extremely important. Despite the large amount of work done, many of the scalable algorithms to compare graphs do not produce closeness scores that satisfy the intuitive properties of metrics. This is problematic since non-metrics are known to degrade the performance of algorithms such as distance-based clustering of graphs (Stratis and Bento 2018). On the other hand, the use of metrics increases the performance of several machine learning tasks (Indyk et al. 1999, Clarkson et al. 1999, Angiulli et al. 2002, Ackermann et al. 2010). In this paper, we introduce a new family of multi-distances (a distance between more than two elements) that satisfies a generalization of the properties of metrics to multiple elements. In the context of comparing graphs, we are the first to show the existence of multi-distances that simultaneously incorporate the useful property of alignment consistency (Nguyen et al. 2011), and a generalized metric property. Furthermore, we show that these multi-distances can be relaxed to convex optimization problems, without losing the generalized metric property.
Make $\ell_1$ Regularization Effective in Training Sparse CNN
Venue: arXiv cs.LG 2020
Year: 2020

Compressed Sensing using $\ell_1$ regularization is among the most powerful and popular sparsification technique in many applications, but why has it not been used to obtain sparse deep learning model such as convolutional neural network (CNN)? This paper is aimed to provide an answer to this question and to show how to make it work. We first demonstrate that the commonly used stochastic gradient decent (SGD) and variants training algorithm is not an appropriate match with $\ell_1$ regularization and then replace it with a different training algorithm based on a regularized dual averaging (RDA) method. RDA was originally designed specifically for convex problem, but with new theoretical insight and algorithmic modifications (using proper initialization and adaptivity), we have made it an effective match with $\ell_1$ regularization to achieve a state-of-the-art sparsity for CNN compared to other weight pruning methods without compromising accuracy (achieving 95\% sparsity for ResNet18 on CIFAR-10, for example).
Fast Exact Algorithms Using Hadamard Product of Polynomials
Venue: arXiv cs.DS 2020
Year: 2020

Let $C$ be an arithmetic circuit of $poly(n)$ size given as input that computes a polynomial $f\in\mathbb{F}[X]$, where $X=\{x_1,x_2,\ldots,x_n\}$ and $\mathbb{F}$ is any field where the field arithmetic can be performed efficiently. We obtain new algorithms for the following two problems first studied by Koutis and Williams \cite{Kou08, Wi09, KW16}. k-MLC: Compute the sum of the coefficients of all degree-$k$ multilinear monomials in the polynomial $f$. k-MMD: Test if there is a nonzero degree-$k$ multilinear monomial in the polynomial $f$. Our algorithms are based on the fact that the Hadamard product $f\circ S_{n,k}$, is the degree-$k$ multilinear part of $f$, where $S_{n,k}$ is the $k^{th}$ elementary symmetric polynomial. 1. For k-MLC problem, we give a deterministic algorithm of run time $O^*(n^{k/2+c\log k})$ (where $c$ is a constant), answering an open question of Koutis and Williams \cite[ICALP'09]{KW16}. As corollaries, we show $O^*(\binom{n}{\downarrow k/2})$-time exact counting algorithms for several combinatorial problems: k-Tree, t-Dominating Set, m-Dimensional k-Matching. 2. For k-MMD problem, we give a randomized algorithm of run time $4.32^k\cdot poly(n,k)$. Our algorithm uses only $poly(n,k)$ space. This matches the run time of a recent algorithm \cite{BDH18} for $k-MMD$ which requires exponential (in $k$) space. Other results include fast deterministic algorithms for k-MLC and k-MMD problems for depth three circuits.
Convolutional Sparse Kernel Network for Unsupervised Medical Image Analysis
Venue: arXiv cs.CV 2020
Year: 2020

The availability of large-scale annotated image datasets and recent advances in supervised deep learning methods enable the end-to-end derivation of representative image features that can impact a variety of image analysis problems. Such supervised approaches, however, are difficult to implement in the medical domain where large volumes of labelled data are difficult to obtain due to the complexity of manual annotation and inter- and intra-observer variability in label assignment. We propose a new convolutional sparse kernel network (CSKN), which is a hierarchical unsupervised feature learning framework that addresses the challenge of learning representative visual features in medical image analysis domains where there is a lack of annotated training data. Our framework has three contributions: (i) We extend kernel learning to identify and represent invariant features across image sub-patches in an unsupervised manner. (ii) We initialise our kernel learning with a layer-wise pre-training scheme that leverages the sparsity inherent in medical images to extract initial discriminative features. (iii) We adapt a multi-scale spatial pyramid pooling (SPP) framework to capture subtle geometric differences between learned visual features. We evaluated our framework in medical image retrieval and classification on three public datasets. Our results show that our CSKN had better accuracy when compared to other conventional unsupervised methods and comparable accuracy to methods that used state-of-the-art supervised convolutional neural networks (CNNs). Our findings indicate that our unsupervised CSKN provides an opportunity to leverage unannotated big data in medical imaging repositories.
Distributed local approximation algorithms for maximum matching in graphs and hypergraphs
Venue: arXiv cs.DS 2020
Year: 2020

We describe approximation algorithms in Linial's classic LOCAL model of distributed computing to find maximum-weight matchings in a hypergraph of rank $r$. Our main result is a deterministic algorithm to generate a matching which is an $O(r)$-approximation to the maximum weight matching, running in $\tilde O(r \log Δ+ \log^2 Δ+ \log^* n)$ rounds. (Here, the $\tilde O()$ notations hides $\text{polyloglog } Δ$ and $\text{polylog } r$ factors). This is based on a number of new derandomization techniques extending methods of Ghaffari, Harris & Kuhn (2017). As a main application, we obtain nearly-optimal algorithms for the long-studied problem of maximum-weight graph matching. Specifically, we get a $(1+ε)$ approximation algorithm using $\tilde O(\log Δ/ ε^3 + \text{polylog}(1/ε, \log \log n))$ randomized time and $\tilde O(\log^2 Δ/ ε^4 + \log^*n / ε)$ deterministic time. The second application is a faster algorithm for hypergraph maximal matching, a versatile subroutine introduced in Ghaffari et al. (2017) for a variety of local graph algorithms. This gives an algorithm for $(2 Δ- 1)$-edge-list coloring in $\tilde O(\log^2 Δ\log n)$ rounds deterministically or $\tilde O( (\log \log n)^3 )$ rounds randomly. Another consequence (with additional optimizations) is an algorithm which generates an edge-orientation with out-degree at most $\lceil (1+ε) λ\rceil$ for a graph of arboricity $λ$; for fixed $ε$ this runs in $\tilde O(\log^6 n)$ rounds deterministically or $\tilde O(\log^3 n )$ rounds randomly.
Atomic Swaptions: Cryptocurrency Derivatives
Venue: arXiv cs.CR 2020
Year: 2020

The atomic swap protocol allows for the exchange of cryptocurrencies on different blockchains without the need to trust a third-party. However, market participants who desire to hold derivative assets such as options or futures would also benefit from trustless exchange. In this paper I propose the atomic swaption, which extends the atomic swap to allow for such exchanges. Crucially, atomic swaptions do not require the use of oracles. I also introduce the margin contract, which provides the ability to create leveraged and short positions. Lastly, I discuss how atomic swaptions may be routed on the Lightning Network.
On the logical complexity of cyclic arithmetic
Venue: arXiv cs.LO 2020
Year: 2020

We study the logical complexity of proofs in cyclic arithmetic ($\mathsf{CA}$), as introduced in Simpson '17, in terms of quantifier alternations of formulae occurring. Writing $CΣ_n$ for (the logical consequences of) cyclic proofs containing only $Σ_n$ formulae, our main result is that $IΣ_{n+1}$ and $CΣ_n$ prove the same $Π_{n+1}$ theorems, for all $n\geq 0$. Furthermore, due to the 'uniformity' of our method, we also show that $\mathsf{CA}$ and Peano Arithmetic ($\mathsf{PA}$) proofs of the same theorem differ only exponentially in size. The inclusion $IΣ_{n+1} \subseteq CΣ_n$ is obtained by proof theoretic techniques, relying on normal forms and structural manipulations of $\mathsf{PA}$ proofs. It improves upon the natural result that $IΣ_n$ is contained in $CΣ_n$. The converse inclusion, $CΣ_n \subseteq IΣ_{n+1}$, is obtained by calibrating the approach of Simpson '17 with recent results on the reverse mathematics of Büchi's theorem in Kołodziejczyk, Michalewski, Pradic & Skrzypczak '16 (KMPS'16), and specialising to the case of cyclic proofs. These results improve upon the bounds on proof complexity and logical complexity implicit in Simpson '17 and also an alternative approach due to Berardi & Tatsuta '17. The uniformity of our method also allows us to recover a metamathematical account of fragments of $\mathsf{CA}$; in particular we show that, for $n\geq 0$, the consistency of $CΣ_n$ is provable in $IΣ_{n+2}$ but not $IΣ_{n+1}$. As a result, we show that certain versions of McNaughton's theorem (the determinisation of $ω$-word automata) are not provable in $\mathsf{RCA}_0$, partially resolving an open problem from KMPS '16.
Compositional (In)Finite Abstractions for Large-Scale Interconnected Stochastic Systems
Venue: arXiv cs.SY 2020
Year: 2020

This paper is concerned with a compositional approach for constructing both infinite (reduced-order models) and finite abstractions (a.k.a. finite Markov decision processes (MDPs)) of large-scale interconnected discrete-time stochastic systems. The proposed framework is based on the notion of stochastic simulation functions enabling us to employ an abstract system as a substitution of the original one in the controller design process with guaranteed error bounds. In the first part of the paper, we derive sufficient small-gain type conditions for the compositional quantification of the probabilistic distance between the interconnection of stochastic control subsystems and that of their infinite abstractions. We then construct infinite abstractions together with their corresponding stochastic simulation functions for a particular class of discrete-time nonlinear stochastic control systems. In the second part of the paper, we leverage small-gain type conditions for the compositional construction of finite abstractions. We propose an approach to construct finite MDPs as finite abstractions of concrete models or their reduced-order versions satisfying an incremental input-to-state stability property. We demonstrate the effectiveness of the proposed results by applying our approaches to a fully interconnected network of 20 nonlinear subsystems (totally 100 dimensions). We construct finite MDPs from their reduced-order versions (together 20 dimensions) with guaranteed error bounds on their output trajectories. We also apply the proposed results to a temperature regulation in a circular building and construct compositionally a finite abstraction of a network containing 1000 rooms. We employ the constructed finite abstractions as substitutes to compositionally synthesize policies regulating the temperature in each room for a bounded time horizon.
Exploiting Local Indexing and Deep Feature Confidence Scores for Fast Image-to-Video Search
Venue: arXiv cs.CV 2020
Year: 2020

The cost-effective visual representation and fast query-by-example search are two challenging goals that should be maintained for web-scale visual retrieval tasks on moderate hardware. This paper introduces a fast and robust method that ensures both of these goals by obtaining state-of-the-art performance for an image-to-video search scenario. Hence, we present critical enhancements to well-known indexing and visual representation techniques by promoting faster, better and moderate retrieval performance. We also boost the superiority of our method for some visual challenges by exploiting individual decisions of local and global descriptors at query time. For instance, local content descriptors represent copied/duplicated scenes with large geometric deformations such as scale, orientation and affine transformation. In contrast, the use of global content descriptors is more practical for near-duplicate and semantic searches. Experiments are conducted on a large-scale Stanford I2V dataset. The experimental results show that our method is useful in terms of complexity and query processing time for large-scale visual retrieval scenarios, even if local and global representations are used together. The proposed method is superior and achieves state-of-the-art performance based on the mean average precision (MAP) score of this dataset. Lastly, we report additional MAP scores after updating the ground annotations unveiled by retrieval results of the proposed method, and it shows that the actual performance.
Coordinate Methods for Accelerating $\ell_\infty$ Regression and Faster Approximate Maximum Flow
Venue: arXiv cs.DS 2020
Year: 2020

We provide faster algorithms for approximately solving $\ell_{\infty}$ regression, a fundamental problem prevalent in both combinatorial and continuous optimization. In particular, we provide accelerated coordinate descent methods capable of provably exploiting dynamic measures of coordinate smoothness, and apply them to $\ell_\infty$ regression over a box to give algorithms which converge in $k$ iterations at a $O(1/k)$ rate. Our algorithms can be viewed as an alternative approach to the recent breakthrough result of Sherman [She17] which achieves a similar runtime improvement over classic algorithmic approaches, i.e. smoothing and gradient descent, which either converge at a $O(1/\sqrt{k})$ rate or have running times with a worse dependence on problem parameters. Our runtimes match those of [She17] across a broad range of parameters and achieve improvement in certain structured cases. We demonstrate the efficacy of our result by providing faster algorithms for the well-studied maximum flow problem. Directly leveraging our accelerated $\ell_\infty$ regression algorithms imply a $\tilde{O}\left(m + \sqrt{mn}/ε\right)$ runtime to compute an $ε$-approximate maximum flow for an undirected graph with $m$ edges and $n$ vertices, generically improving upon the previous best known runtime of $\tilde{O}\left(m/ε\right)$ in [She17] whenever the graph is slightly dense. We further design an algorithm adapted to the structure of the regression problem induced by maximum flow obtaining a runtime of $\tilde{O}\left(m + \max(n, \sqrt{ns})/ε\right)$, where $s$ is the squared $\ell_2$ norm of the congestion of any optimal flow. Moreover, we show how to leverage this result to achieve improved exact algorithms for maximum flow on a variety of unit capacity graphs. We hope that our work serves as an important step towards achieving even faster maximum flow algorithms.
DeepCloak: Adversarial Crafting As a Defensive Measure to Cloak Processes
Venue: arXiv cs.CR 2020
Year: 2020

Over the past decade, side-channels have proven to be significant and practical threats to modern computing systems. Recent attacks have all exploited the underlying shared hardware. While practical, mounting such a complicated attack is still akin to listening on a private conversation in a crowded train station. The attacker has to either perform significant manual labor or use AI systems to automate the process. The recent academic literature points to the latter option. With the abundance of cheap computing power and the improvements made in AI, it is quite advantageous to automate such tasks. By using AI systems however, malicious parties also inherit their weaknesses. One such weakness is undoubtedly the vulnerability to adversarial samples. In contrast to the previous literature, for the first time, we propose the use of adversarial learning as a defensive tool to obfuscate and mask private information. We demonstrate the viability of this approach by first training CNNs and other machine learning classifiers on leakage trace of different processes. After training highly accurate models (99+% accuracy), we investigate their resolve against adversarial learning methods. By applying minimal perturbations to input traces, the adversarial traffic by the defender can run as an attachment to the original process and cloak it against a malicious classifier. Finally, we investigate whether an attacker can protect her classifier model by employing adversarial defense methods, namely adversarial re-training and defensive distillation. Our results show that even in the presence of an intelligent adversary that employs such techniques, all 10 of the tested adversarial learning methods still manage to successfully craft adversarial perturbations and the proposed cloaking methodology succeeds.
Deep Reinforcement Learning for Online Computation Offloading in Wireless Powered Mobile-Edge Computing Networks
Venue: arXiv cs.NI 2020
Year: 2020

Wireless powered mobile-edge computing (MEC) has recently emerged as a promising paradigm to enhance the data processing capability of low-power networks, such as wireless sensor networks and internet of things (IoT). In this paper, we consider a wireless powered MEC network that adopts a binary offloading policy, so that each computation task of wireless devices (WDs) is either executed locally or fully offloaded to an MEC server. Our goal is to acquire an online algorithm that optimally adapts task offloading decisions and wireless resource allocations to the time-varying wireless channel conditions. This requires quickly solving hard combinatorial optimization problems within the channel coherence time, which is hardly achievable with conventional numerical optimization methods. To tackle this problem, we propose a Deep Reinforcement learning-based Online Offloading (DROO) framework that implements a deep neural network as a scalable solution that learns the binary offloading decisions from the experience. It eliminates the need of solving combinatorial optimization problems, and thus greatly reduces the computational complexity especially in large-size networks. To further reduce the complexity, we propose an adaptive procedure that automatically adjusts the parameters of the DROO algorithm on the fly. Numerical results show that the proposed algorithm can achieve near-optimal performance while significantly decreasing the computation time by more than an order of magnitude compared with existing optimization methods. For example, the CPU execution latency of DROO is less than $0.1$ second in a $30$-user network, making real-time and optimal offloading truly viable even in a fast fading environment.
Efficient and DoS-resistant Consensus for Permissioned Blockchains
Venue: arXiv cs.DC 2020
Year: 2020

Existing permissioned blockchain systems designate a fixed and explicit group of committee nodes to run a consensus protocol that confirms the same sequence of blocks among all nodes. Unfortunately, when such a permissioned blockchain runs in a large scale on the Internet, these explicit committee nodes can be easily turned down by denial-of-service (DoS) or network partition attacks. Although work proposes scalable BFT protocols that run on a larger number of committee nodes, their efficiency drops dramatically when only a small number of nodes are attacked. In this paper, our EGES protocol leverages Intel SGX to develop a new abstraction called "stealth committee", which effectively hides the committee nodes into a large pool of fake committee nodes. EGES selects a distinct group of stealth committee for each block and confirms the same sequence of blocks among all nodes with overwhelming probability. Evaluation on typical geo-distributed settings shows that: (1)EGES is the first permissioned blockchain's consensus protocol that can tolerate tough DoS and network partition attacks; and (2) EGES achieves comparable throughput and latency as existing permissioned blockchains' protocols