OpenRaiser/Intern-Atlas huggingface dataset:
The Error-Feedback Framework: Better Rates for SGD with Delayed Gradients and Compressed Communication
Venue: arXiv cs.LG 2021
Year: 2021

We analyze (stochastic) gradient descent (SGD) with delayed updates on smooth quasi-convex and non-convex functions and derive concise, non-asymptotic, convergence rates. We show that the rate of convergence in all cases consists of two terms: (i) a stochastic term which is not affected by the delay, and (ii) a higher order deterministic term which is only linearly slowed down by the delay. Thus, in the presence of noise, the effects of the delay become negligible after a few iterations and the algorithm converges at the same optimal rate as standard SGD. This result extends a line of research that showed similar results in the asymptotic regime or for strongly-convex quadratic functions only. We further show similar results for SGD with more intricate form of delayed gradients -- compressed gradients under error compensation and for local~SGD where multiple workers perform local steps before communicating with each other. In all of these settings, we improve upon the best known rates. These results show that SGD is robust to compressed and/or delayed stochastic gradient updates. This is in particular important for distributed parallel implementations, where asynchronous and communication efficient methods are the key to achieve linear speedups for optimization with multiple devices.
Online Linear Programming: Dual Convergence, New Algorithms, and Regret Bounds
Venue: arXiv cs.DS 2021
Year: 2021

We study an online linear programming (OLP) problem under a random input model in which the columns of the constraint matrix along with the corresponding coefficients in the objective function are generated i.i.d. from an unknown distribution and revealed sequentially over time. Virtually all pre-existing online algorithms were based on learning the dual optimal solutions/prices of the linear programs (LP), and their analyses were focused on the aggregate objective value and solving the packing LP where all coefficients in the constraint matrix and objective are nonnegative. However, two major open questions were: (i) Does the set of LP optimal dual prices learned in the pre-existing algorithms converge to those of the "offline" LP, and (ii) Could the results be extended to general LP problems where the coefficients can be either positive or negative. We resolve these two questions by establishing convergence results for the dual prices under moderate regularity conditions for general LP problems. Specifically, we identify an equivalent form of the dual problem which relates the dual LP with a sample average approximation to a stochastic program. Furthermore, we propose a new type of OLP algorithm, Action-History-Dependent Learning Algorithm, which improves the previous algorithm performances by taking into account the past input data as well as decisions/actions already made. We derive an $O(\log n \log \log n)$ regret bound (under a locally strong convexity and smoothness condition) for the proposed algorithm, against the $O(\sqrt{n})$ bound for typical dual-price learning algorithms, where $n$ is the number of decision variables. Numerical experiments demonstrate the effectiveness of the proposed algorithm and the action-history-dependent design.
Predicate Transformer Semantics for Hybrid Systems: Verification Components for Isabelle/HOL
Venue: arXiv cs.LO 2021
Year: 2021

We present a semantic framework for the deductive verification of hybrid systems with Isabelle/HOL. It supports reasoning about the temporal evolutions of hybrid programs in the style of differential dynamic logic modelled by flows or invariant sets for vector fields. We introduce the semantic foundations of this framework and summarise their Isabelle formalisation as well as the resulting verification components. A series of simple examples shows our approach at work.
Adversarial learning for revenue-maximizing auctions
Venue: arXiv cs.GT 2021
Year: 2021

We introduce a new numerical framework to learn optimal bidding strategies in repeated auctions when the seller uses past bids to optimize her mechanism. Crucially, we do not assume that the bidders know what optimization mechanism is used by the seller. We recover essentially all state-of-the-art analytical results for the single-item framework derived previously in the setup where the bidder knows the optimization mechanism used by the seller and extend our approach to multi-item settings, in which no optimal shading strategies were previously known. Our approach yields substantial increases in bidder utility in all settings. Our approach also has a strong potential for practical usage since it provides a simple way to optimize bidding strategies on modern marketplaces where buyers face unknown data-driven mechanisms.
Efficient Rational Creative Telescoping
Venue: arXiv cs.SC 2021
Year: 2021

We present a new algorithm to compute minimal telescopers for rational functions in two discrete variables. As with recent reduction-based approaches, our algorithm has the important feature that the computation of a telescoper is independent of its certificate. In addition, our algorithm uses a compact representation of the certificate, which allows it to be easily manipulated and analyzed without knowing the precise expanded form. This representation hides potential expression swell until the final (and optional) expansion, which can be accomplished in time polynomial in the size of the expanded certificate. A complexity analysis, along with a Maple implementation, indicates that our algorithm has better theoretical and practical performance than the reduction-based approach in the rational case.
Where are the Keys? -- Learning Object-Centric Navigation Policies on Semantic Maps with Graph Convolutional Networks
Venue: arXiv cs.LG 2021
Year: 2021

Emerging object-based SLAM algorithms can build a graph representation of an environment comprising nodes for robot poses and object landmarks. However, while this map will contain static objects such as furniture or appliances, many moveable objects (e.g. the car keys, the glasses, or a magazine), are not suitable as landmarks and will not be part of the map due to their non-static nature. We show that Graph Convolutional Networks can learn navigation policies to find such unmapped objects by learning to exploit the hidden probabilistic model that governs where these objects appear in the environment. The learned policies can generalise to object classes unseen during training by using word vectors that express semantic similarity as representations for object nodes in the graph. Furthermore, we show that the policies generalise to unseen environments with only minimal loss of performance. We demonstrate that pre-training the policy network with a proxy task can significantly speed up learning, improving sample efficiency.
HAD-GAN: A Human-perception Auxiliary Defense GAN to Defend Adversarial Examples
Venue: arXiv cs.CV 2021
Year: 2021

Adversarial examples reveal the vulnerability and unexplained nature of neural networks. Studying the defense of adversarial examples is of considerable practical importance. Most adversarial examples that misclassify networks are often undetectable by humans. In this paper, we propose a defense model to train the classifier into a human-perception classification model with shape preference. The proposed model comprising a texture transfer network (TTN) and an auxiliary defense generative adversarial networks (GAN) is called Human-perception Auxiliary Defense GAN (HAD-GAN). The TTN is used to extend the texture samples of a clean image and helps classifiers focus on its shape. GAN is utilized to form a training framework for the model and generate the necessary images. A series of experiments conducted on MNIST, Fashion-MNIST and CIFAR10 show that the proposed model outperforms the state-of-the-art defense methods for network robustness. The model also demonstrates a significant improvement on defense capability of adversarial examples.
SCDP: Systematic Rateless Coding for Efficient Data Transport in Data Centres (Complete Version)
Venue: arXiv cs.NI 2021
Year: 2021

In this paper we propose SCDP, a general-purpose data transport protocol for data centres that, in contrast to all other protocols proposed to date, supports efficient one-to-many and many-to-one communication, which is extremely common in modern data centres. SCDP does so without compromising on efficiency for short and long unicast flows. SCDP achieves this by integrating RaptorQ codes with receiver-driven data transport, packet trimming and Multi-Level Feedback Queuing (MLFQ); (1) RaptorQ codes enable efficient one-to-many and many-to-one data transport; (2) on top of RaptorQ codes, receiver-driven flow control, in combination with in-network packet trimming, enable efficient usage of network resources as well as multi-path transport and packet spraying for all transport modes. Incast and Outcast are eliminated; (3) the systematic nature of RaptorQ codes, in combination with MLFQ, enable fast, decoding-free completion of short flows. We extensively evaluate SCDP in a wide range of simulated scenarios with realistic data centre workloads. For one-to-many and many-to-one transport sessions, SCDP performs significantly better compared to NDP and PIAS. For short and long unicast flows, SCDP performs equally well or better compared to NDP and PIAS.
Output-sensitive Information flow analysis
Venue: arXiv cs.CR 2021
Year: 2021

Constant-time programming is a countermeasure to prevent cache based attacks where programs should not perform memory accesses that depend on secrets. In some cases this policy can be safely relaxed if one can prove that the program does not leak more information than the public outputs of the computation. We propose a novel approach for verifying constant-time programming based on a new information flow property, called output-sensitive noninterference. Noninterference states that a public observer cannot learn anything about the private data. Since real systems need to intentionally declassify some information, this property is too strong in practice. In order to take into account public outputs we proceed as follows: instead of using complex explicit declassification policies, we partition variables in three sets: input, output and leakage variables. Then, we propose a typing system to statically check that leakage variables do not leak more information about the secret inputs than the public normal output. The novelty of our approach is that we track the dependence of leakage variables with respect not only to the initial values of input variables (as in classical approaches for noninterference), but taking also into account the final values of output variables. We adapted this approach to LLVM IR and we developed a prototype to verify LLVM implementations.
Towards Automated Biometric Identification of Sea Turtles (Chelonia mydas)
Venue: arXiv cs.CV 2021
Year: 2021

Passive biometric identification enables wildlife monitoring with minimal disturbance. Using a motion-activated camera placed at an elevated position and facing downwards, we collected images of sea turtle carapace, each belonging to one of sixteen Chelonia mydas juveniles. We then learned co-variant and robust image descriptors from these images, enabling indexing and retrieval. In this work, we presented several classification results of sea turtle carapaces using the learned image descriptors. We found that a template-based descriptor, i.e., Histogram of Oriented Gradients (HOG) performed exceedingly better during classification than keypoint-based descriptors. For our dataset, a high-dimensional descriptor is a must due to the minimal gradient and color information inside the carapace images. Using HOG, we obtained an average classification accuracy of 65%.
Implementation of three LWC Schemes in the WiFi 4-Way Handshake with Software Defined Radio
Venue: arXiv cs.CR 2021
Year: 2021

With the rapid deployment of Internet of Things (IoT) devices in applications such as smarthomes, healthcare and industrial automation, security and privacy has become a major concern. Recently, National Institute of Standards and Technology (NIST) has initiated a lightweight cryptography (LWC) competition to standardize new cryptographic algorithm(s) for providing security in resource-constrained environments. In this context, measuring the suitability of new algorithms with existing communication and authentication protocols is an important problem. This paper investigates the performance of three NIST lightweight authenticated ciphers in round 2 namely ACE, SPIX and WAGE in the WiFi and CoAP handshaking authentication protocols. We implement the WiFi and CoAP handshake protocols and the IEEE802.11a physical layer communication protocol in software defined radio (SDR) and embed these two handshaking protocols into the IEEE802.11a OFDM communication protocol to measure the performance of three ciphers. We present the construction of KDF and MIC used in the handshaking authentication protocols and provide optimized implementations of ACE, SPIX and WAGE including KDF and MIC on three different (low-power) microcontrollers. The performance results of these three ciphers when adopted in WiFi and CoAP protocols are presented. Our experimental results show that the cryptographic functionalities are the bottleneck in the handshaking and data protection protocols.
The Stroke Correspondence Problem, Revisited
Venue: arXiv cs.CV 2021
Year: 2021

We revisit the stroke correspondence problem [13,14]. We optimize this algorithm by 1) evaluating suitable preprocessing (normalization) methods 2) extending the algorithm with an additional distance measure to handle Hiragana, Katakana and Kanji characters with a low number of strokes and c) simplify the stroke linking algorithms. Our contributions are implemented in the free, open-source library ctegaki and in the demo-tools jTegaki and Kanjicanvas.
Imitation Learning Based on Bilateral Control for Human-Robot Cooperation
Venue: arXiv cs.RO 2021
Year: 2021

Robots are required to autonomously respond to changing situations. Imitation learning is a promising candidate for achieving generalization performance, and extensive results have been demonstrated in object manipulation. However, cooperative work between humans and robots is still a challenging issue because robots must control dynamic interactions among themselves, humans, and objects. Furthermore, it is difficult to follow subtle perturbations that may occur among coworkers. In this study, we find that cooperative work can be accomplished by imitation learning using bilateral control. Thanks to bilateral control, which can extract response values and command values independently, human skills to control dynamic interactions can be extracted. Then, the task of serving food is considered. The experimental results clearly demonstrate the importance of force control, and the dynamic interactions can be controlled by the inferred action force.
Capacity Preserving Mapping for High-dimensional Data Visualization
Venue: arXiv cs.LG 2021
Year: 2021

We provide a rigorous mathematical treatment to the crowding issue in data visualization when high dimensional data sets are projected down to low dimensions for visualization. By properly adjusting the capacity of high dimensional balls, our method makes right enough room to prepare for the embedding. A key component of the proposed method is an estimation of the correlation dimension at various scales which reflects the data density variation. The proposed adjustment to the capacity applies to any distance (Euclidean, geodesic, diffusion) and can potentially be used in many existing methods to mitigate the crowding during the dimension reduction. We demonstrate the effectiveness of the new method using synthetic and real datasets.
Lane Attention: Predicting Vehicles' Moving Trajectories by Learning Their Attention over Lanes
Venue: arXiv cs.LG 2021
Year: 2021

Accurately forecasting the future movements of surrounding vehicles is essential for safe and efficient operations of autonomous driving cars. This task is difficult because a vehicle's moving trajectory is greatly determined by its driver's intention, which is often hard to estimate. By leveraging attention mechanisms along with long short-term memory (LSTM) networks, this work learns the relation between a driver's intention and the vehicle's changing positions relative to road infrastructures, and uses it to guide the prediction. Different from other state-of-the-art solutions, our work treats the on-road lanes as non-Euclidean structures, unfolds the vehicle's moving history to form a spatio-temporal graph, and uses methods from Graph Neural Networks to solve the problem. Not only is our approach a pioneering attempt in using non-Euclidean methods to process static environmental features around a predicted object, our model also outperforms other state-of-the-art models in several metrics. The practicability and interpretability analysis of the model shows great potential for large-scale deployment in various autonomous driving systems in addition to our own.
BEAN: Interpretable Representation Learning with Biologically-Enhanced Artificial Neuronal Assembly Regularization
Venue: arXiv cs.NE 2021
Year: 2021

Deep neural networks (DNNs) are known for extracting useful information from large amounts of data. However, the representations learned in DNNs are typically hard to interpret, especially in dense layers. One crucial issue of the classical DNN model such as multilayer perceptron (MLP) is that neurons in the same layer of DNNs are conditionally independent of each other, which makes co-training and emergence of higher modularity difficult. In contrast to DNNs, biological neurons in mammalian brains display substantial dependency patterns. Specifically, biological neural networks encode representations by so-called neuronal assemblies: groups of neurons interconnected by strong synaptic interactions and sharing joint semantic content. The resulting population coding is essential for human cognitive and mnemonic processes. Here, we propose a novel Biologically Enhanced Artificial Neuronal assembly (BEAN) regularization to model neuronal correlations and dependencies, inspired by cell assembly theory from neuroscience. Experimental results show that BEAN enables the formation of interpretable neuronal functional clusters and consequently promotes a sparse, memory/computation-efficient network without loss of model performance. Moreover, our few-shot learning experiments demonstrate that BEAN could also enhance the generalizability of the model when training samples are extremely limited.
A relaxation of the Directed Disjoint Paths problem: a global congestion metric helps
Venue: arXiv cs.DS 2021
Year: 2021

In the Directed Disjoint Paths problem, we are given a digraph $D$ and a set of requests $\{(s_1, t_1), \ldots, (s_k, t_k)\}$, and the task is to find a collection of pairwise vertex-disjoint paths $\{P_1, \ldots, P_k\}$ such that each $P_i$ is a path from $s_i$ to $t_i$ in $D$. This problem is NP-complete for fixed $k=2$ and W[1]-hard with parameter $k$ in DAGs. A few positive results are known under restrictions on the input digraph, such as being planar or having bounded directed tree-width, or under relaxations of the problem, such as allowing for vertex congestion. Positive results are scarce, however, for general digraphs. In this article we propose a novel global congestion metric for the problem: we only require the paths to be "disjoint enough", in the sense that they must behave properly not in the whole graph, but in an unspecified part of size prescribed by a parameter. Namely, in the Disjoint Enough Directed Paths problem, given an $n$-vertex digraph $D$, a set of $k$ requests, and non-negative integers $d$ and $s$, the task is to find a collection of paths connecting the requests such that at least $d$ vertices of $D$ occur in at most $s$ paths of the collection. We study the parameterized complexity of this problem for a number of choices of the parameter, including the directed tree-width of $D$. Among other results, we show that the problem is W[1]-hard in DAGs with parameter $d$ and, on the positive side, we give an algorithm in time $\mathcal{O}(n^{d+2} \cdot k^{d\cdot s})$ and a kernel of size $d \cdot 2^{k-s}\cdot \binom{k}{s} + 2k$ in general digraphs. This latter result has consequences for the Steiner Network problem: we show that it is FPT parameterized by the number $k$ of terminals and $p$, where $p = n - q$ and $q$ is the size of the solution.
Sub-Architecture Ensemble Pruning in Neural Architecture Search
Venue: arXiv cs.LG 2021
Year: 2021

Neural architecture search (NAS) is gaining more and more attention in recent years due to its flexibility and remarkable capability to reduce the burden of neural network design. To achieve better performance, however, the searching process usually costs massive computations that might not be affordable for researchers and practitioners. While recent attempts have employed ensemble learning methods to mitigate the enormous computational cost, however, they neglect a key property of ensemble methods, namely diversity, which leads to collecting more similar sub-architectures with potential redundancy in the final design. To tackle this problem, we propose a pruning method for NAS ensembles called "Sub-Architecture Ensemble Pruning in Neural Architecture Search (SAEP)." It targets to leverage diversity and to achieve sub-ensemble architectures at a smaller size with comparable performance to ensemble architectures that are not pruned. Three possible solutions are proposed to decide which sub-architectures to prune during the searching process. Experimental results exhibit the effectiveness of the proposed method by largely reducing the number of sub-architectures without degrading the performance.
OpenUAV Cloud Testbed: a Collaborative Design Studio for Field Robotics
Venue: arXiv cs.RO 2021
Year: 2021

Simulations play a crucial role in robotics research and education. This paper presents the OpenUAV testbed, an open-source, easy-to-use, web-based, and reproducible software system that enables students and researchers to run robotic simulations on the cloud. We have built upon our previous work and have addressed some of the educational and research challenges associated with the prior work. The critical contributions of the paper to the robotics and automation community are threefold: First, OpenUAV saves students and researchers from tedious and complicated software setups by providing web-browser-based Linux desktop sessions with standard robotics software like Gazebo, ROS, and flight autonomy stack. Second, a method for saving an individual's research work with its dependencies for the work's future reproducibility. Third, the platform provides a mechanism to support photorealistic robotics simulations by combining Unity game engine-based camera rendering and Gazebo physics. The paper addresses a research need for photorealistic simulations and describes a methodology for creating a photorealistic aquatic simulation. We also present the various academic and research use-cases of this platform to improve robotics education and research, especially during times like the COVID-19 pandemic, when virtual collaboration is necessary.