OpenRaiser/Intern-Atlas huggingface dataset:
Versatile Dueling Bandits: Best-of-both-World Analyses for Online Learning from Preferences
Venue: arXiv cs.LG 2022
Year: 2022

We study the problem of $K$-armed dueling bandit for both stochastic and adversarial environments, where the goal of the learner is to aggregate information through relative preferences of pair of decisions points queried in an online sequential manner. We first propose a novel reduction from any (general) dueling bandits to multi-armed bandits and despite the simplicity, it allows us to improve many existing results in dueling bandits. In particular, \emph{we give the first best-of-both world result for the dueling bandits regret minimization problem} -- a unified framework that is guaranteed to perform optimally for both stochastic and adversarial preferences simultaneously. Moreover, our algorithm is also the first to achieve an optimal $O(\sum_{i = 1}^K \frac{\log T}{Δ_i})$ regret bound against the Condorcet-winner benchmark, which scales optimally both in terms of the arm-size $K$ and the instance-specific suboptimality gaps $\{Δ_i\}_{i = 1}^K$. This resolves the long-standing problem of designing an instancewise gap-dependent order optimal regret algorithm for dueling bandits (with matching lower bounds up to small constant factors). We further justify the robustness of our proposed algorithm by proving its optimal regret rate under adversarially corrupted preferences -- this outperforms the existing state-of-the-art corrupted dueling results by a large margin. In summary, we believe our reduction idea will find a broader scope in solving a diverse class of dueling bandits setting, which are otherwise studied separately from multi-armed bandits with often more complex solutions and worse guarantees. The efficacy of our proposed algorithms is empirically corroborated against the existing dueling bandit methods.
Digital Contact Tracing Solutions: Promises, Pitfalls and Challenges
Venue: arXiv cs.CR 2022
Year: 2022

The COVID-19 pandemic has caused many countries to deploy novel digital contact tracing (DCT) systems to boost the efficiency of manual tracing of infection chains. In this paper, we systematically analyze DCT solutions and categorize them based on their design approaches and architectures. We analyze them with regard to effectiveness, security, privacy, and ethical aspects and compare prominent solutions with regard to these requirements. In particular, we discuss the shortcomings of the Google and Apple Exposure Notification API (GAEN) that is currently widely adopted all over the world. We find that the security and privacy of GAEN have considerable deficiencies as it can be compromised by severe, large-scale attacks. We also discuss other proposed approaches for contact tracing, including our proposal TRACECORONA, that are based on Diffie-Hellman (DH) key exchange and aim at tackling shortcomings of existing solutions. Our extensive analysis shows thatTRACECORONA fulfills the above security requirements better than deployed state-of-the-art approaches. We have implementedTRACECORONA, and its beta test version has been used by more than 2000 users without any major functional problems, demonstrating that there are no technical reasons requiring to make compromises with regard to the requirements of DCTapproaches.
On Triangle Counting Parameterized by Twin-Width
Venue: arXiv cs.DS 2022
Year: 2022

In this report we present an algorithm solving Triangle Counting in time $O(d^2n+m)$, where n and m, respectively, denote the number of vertices and edges of a graph G and d denotes its twin-width, a recently introduced graph parameter. We assume that a compact representation of a d-contraction sequence of G is given.
A Data-Centric Approach to Generate Invariants for a Smart Grid Using Machine Learning
Venue: arXiv cs.CR 2022
Year: 2022

Cyber-Physical Systems (CPS) have gained popularity due to the increased requirements on their uninterrupted connectivity and process automation. Due to their connectivity over the network including intranet and internet, dependence on sensitive data, heterogeneous nature, and large-scale deployment, they are highly vulnerable to cyber-attacks. Cyber-attacks are performed by creating anomalies in the normal operation of the systems with a goal either to disrupt the operation or destroy the system completely. The study proposed here focuses on detecting those anomalies which could be the cause of cyber-attacks. This is achieved by deriving the rules that govern the physical behavior of a process within a plant. These rules are called Invariants. We have proposed a Data-Centric approach (DaC) to generate such invariants. The entire study was conducted using the operational data of a functional smart power grid which is also a living lab.
Quantitative Strongest Post
Venue: arXiv cs.LO 2022
Year: 2022

We present a novel strongest-postcondition-style calculus for quantitative reasoning about non-deterministic programs with loops. Whereas existing quantitative weakest pre allows reasoning about the value of a quantity after a program terminates on a given initial state, quantitative strongest post allows reasoning about the value that a quantity had before the program was executed and reached a given final state. We show how strongest post enables reasoning about the flow of quantitative information through programs. Similarly to weakest liberal preconditions, we also develop a quantitative strongest liberal post. As a byproduct, we obtain the entirely unexplored notion of strongest liberal postconditions and show how these foreshadow a potential new program logic - partial incorrectness logic - which would be a more liberal version of O'Hearn's recent incorrectness logic.
Parallel Repetition For All 3-Player Games Over Binary Alphabet
Venue: arXiv cs.CC 2022
Year: 2022

We prove that for every 3-player game with binary questions and answers and value $<1$, the value of the $n$-fold parallel repetition of the game decays polynomially fast to 0. That is, for every such game, there exists a constant $c>0$, such that the value of the $n$-fold parallel repetition of the game is at most $n^{-c}$. Along the way to proving this theorem, we prove two additional parallel repetition theorems for multiplayer games, that may be of independent interest: Playerwise Connected Games (with any number of players and any Alphabet size): We identify a large class of multiplayer games and prove that for every game with value $<1$ in that class, the value of the $n$-fold parallel repetition of the game decays polynomially fast to 0. More precisely, our result applies for playerwise connected games, with any number of players and any alphabet size. The class of playerwise connected games is strictly larger than the class of connected games that was defined in [DHVY17] and for which exponentially fast decay bounds are known [DHVY17]. For playerwise connected games that are not connected, only inverse Ackermann decay bounds were previously known [Ver96]. Exponential Bounds for the Anti-Correlation Game: In the 3-player anti-correlation game, two out of three players are given $1$ as input, and the remaining player is given $0$. The two players who were given $1$ must produce different outputs in $\{0,1\}$. We prove that the value of the $n$-fold parallel repetition of that game decays exponentially fast to 0. Only inverse Ackermann decay bounds were previously known [Ver96]. This game was studied and motivated in several previous works. In particular, Holmgren and Yang gave it as an example for a 3-player game whose non-signaling value (is smaller than 1 and yet) does not decrease at all under parallel repetition [HY19].
Minimizing the Weighted Number of Tardy Jobs via (max,+)-Convolutions
Venue: arXiv cs.DS 2022
Year: 2022

The $1 \mid \mid Σw_j U_j$ problem asks to determine -- given $n$ jobs each with its own processing time, weight, and due date -- the minimum weighted number of tardy jobs in any single machine non-preemptive schedule for these jobs. This is a classical scheduling problem that generalizes both Knapsack, and Subset Sum. The best known pseudo-polynomial algorithm for $1 \mid \mid Σw_j U_j$, due to Lawler and Moore [Management Science'69], dates back to the late 60s and has a running time of $O(d_{\max}n)$, where $n$ is the number of jobs and $d_{\max}$ is their maximal due date. A recent lower bound by Cygan \emph{et al.}~[ICALP'19] for Knapsack shows that $1 \mid \mid Σw_j U_j$ cannot be solved in $\widetilde{O}((n+d_{\max})^{2-\varepsilon})$ time, for any $\varepsilon > 0$, under a plausible conjecture. This still leaves a gap between the best known lower bound and upper bound for the problem. In this paper we design a new simple algorithm for $1 \mid \mid Σw_j U_j$ that uses $(\max,+)$-convolutions as its main tool, and outperforms the Lawler and Moore algorithm under several parameter ranges. In particular, depending on the specific method of computing $(\max,+)$-convolutions, its running time can be bounded by - $\widetilde{O}(n+d_{\#}d_{\max}^2)$. - $\widetilde{O}(d_{\#}n +d^2_{\#}d_{\max}w_{\max})$. - $\widetilde{O}(d_{\#}n +d_{\#}d_{\max}p_{\max})$. - $\widetilde{O}(n^2 +d_{\max}w^2_{\max})$. - $\widetilde{O}(n^2 + d_{\#}(d_{\max}w_{\max})^{1.5})$. Here, $d_{\#}$ denotes the number of \emph{different} due dates in the instance, $p_{\max}$ denotes the maximum processing time of any job, and $w_{\max}$ denotes the maximum weight of any job.
AnoMili: Spoofing Prevention and Explainable Anomaly Detection for the 1553 Military Avionic Bus
Venue: arXiv cs.CR 2022
Year: 2022

MIL-STD-1553, a standard that defines a communication bus for interconnected devices, is widely used in military and aerospace avionic platforms. Due to its lack of security mechanisms, MIL-STD-1553 is exposed to cyber threats. The methods previously proposed to address these threats are very limited, resulting in the need for more advanced techniques. Inspired by the defense in depth principle, we propose AnoMili, a novel protection system for the MIL-STD-1553 bus, which consists of: (i) a physical intrusion detection mechanism that detects unauthorized devices connected to the 1553 bus, even if they are passive (sniffing), (ii) a device fingerprinting mechanism that protects against spoofing attacks (two approaches are proposed: prevention and detection), (iii) a context-based anomaly detection mechanism, and (iv) an anomaly explanation engine responsible for explaining the detected anomalies in real time. We evaluate AnoMili's effectiveness and practicability in two real 1553 hardware-based testbeds. The effectiveness of the anomaly explanation engine is also demonstrated. All of the detection and prevention mechanisms employed had high detection rates (over 99.45%) with low false positive rates. The context-based anomaly detection mechanism obtained perfect results when evaluated on a dataset used in prior work.
Sequence-to-Sequence Resources for Catalan
Venue: arXiv cs.CL 2022
Year: 2022

In this work, we introduce sequence-to-sequence language resources for Catalan, a moderately under-resourced language, towards two tasks, namely: Summarization and Machine Translation (MT). We present two new abstractive summarization datasets in the domain of newswire. We also introduce a parallel Catalan-English corpus, paired with three different brand new test sets. Finally, we evaluate the data presented with competing state of the art models, and we develop baselines for these tasks using a newly created Catalan BART. We release the resulting resources of this work under open license to encourage the development of language technology in Catalan.
Stochastic models of Jaya and semi-steady-state Jaya algorithms
Venue: arXiv cs.NE 2022
Year: 2022

We build stochastic models for analyzing Jaya and semi-steady-state Jaya algorithms. The analysis shows that for semi-steady-state Jaya (a) the maximum expected value of the number of worst-index updates per generation is a paltry 1.7 regardless of the population size; (b) regardless of the population size, the expectation of the number of best-index updates per generation decreases monotonically with generations; (c) exact upper bounds as well as asymptotics of the expected best-update counts can be obtained for specific distributions; the upper bound is 0.5 for normal and logistic distributions, $\ln 2$ for the uniform distribution, and $e^{-γ} \ln 2$ for the exponential distribution, where $γ$ is the Euler-Mascheroni constant; the asymptotic is $e^{-γ} \ln 2$ for logistic and exponential distributions and $\ln 2$ for the uniform distribution (the asymptotic cannot be obtained analytically for the normal distribution). The models lead to the derivation of computational complexities of Jaya and semi-steady-state Jaya. The theoretical analysis is supported with empirical results on a benchmark suite. The insights provided by our stochastic models should help design new, improved population-based search/optimization heuristics.
ASC me to Do Anything: Multi-task Training for Embodied AI
Venue: arXiv cs.CV 2022
Year: 2022

Embodied AI has seen steady progress across a diverse set of independent tasks. While these varied tasks have different end goals, the basic skills required to complete them successfully overlap significantly. In this paper, our goal is to leverage these shared skills to learn to perform multiple tasks jointly. We propose Atomic Skill Completion (ASC), an approach for multi-task training for Embodied AI, where a set of atomic skills shared across multiple tasks are composed together to perform the tasks. The key to the success of this approach is a pre-training scheme that decouples learning of the skills from the high-level tasks making joint training effective. We use ASC to train agents within the AI2-THOR environment to perform four interactive tasks jointly and find it to be remarkably effective. In a multi-task setting, ASC improves success rates by a factor of 2x on Seen scenes and 4x on Unseen scenes compared to no pre-training. Importantly, ASC enables us to train a multi-task agent that has a 52% higher Success Rate than training 4 independent single task agents. Finally, our hierarchical agents are more interpretable than traditional black-box architectures.
Autonomous Vehicles on the Edge: A Survey on Autonomous Vehicle Racing
Venue: arXiv cs.RO 2022
Year: 2022

The rising popularity of self-driving cars has led to the emergence of a new research field in the recent years: Autonomous racing. Researchers are developing software and hardware for high performance race vehicles which aim to operate autonomously on the edge of the vehicles limits: High speeds, high accelerations, low reaction times, highly uncertain, dynamic and adversarial environments. This paper represents the first holistic survey that covers the research in the field of autonomous racing. We focus on the field of autonomous racecars only and display the algorithms, methods and approaches that are used in the fields of perception, planning and control as well as end-to-end learning. Further, with an increasing number of autonomous racing competitions, researchers now have access to a range of high performance platforms to test and evaluate their autonomy algorithms. This survey presents a comprehensive overview of the current autonomous racing platforms emphasizing both the software-hardware co-evolution to the current stage. Finally, based on additional discussion with leading researchers in the field we conclude with a summary of open research challenges that will guide future researchers in this field.
The Multibillion Dollar Software Supply Chain of Ethereum
Venue: arXiv cs.SE 2022
Year: 2022

The rise of blockchain technologies has triggered tremendous research interest, coding efforts, and monetary investments in the last decade. Ethereum is the single largest programmable blockchain platform today. It features cryptocurrency trading, digital art, and decentralized finance through smart contracts. So-called Ethereum nodes operate the blockchain, relying on a vast supply chain of third-party software dependencies maintained by diverse organizations. These software suppliers have a direct impact on the reliability and the security of Ethereum. In this article, we perform an analysis of the software supply chain of Java Ethereum nodes and distill the challenges of maintaining and securing this blockchain technology.
Vector Coded Caching Multiplicatively Boosts the Throughput of Realistic Downlink Systems
Venue: arXiv cs.IT 2022
Year: 2022

The recent introduction of vector coded caching has revealed that multi-rank transmissions in the presence of receiver-side cache content can dramatically ameliorate the file-size bottleneck of coded caching and substantially boost performance in error-free wire-like channels. We here employ large-matrix analysis to explore the effect of vector coded caching in realistic wireless multi-antenna downlink systems. Our analysis answers a simple question: Under a fixed set of antenna and SNR resources, and a given downlink MISO system which can already enjoy an optimized exploitation of multiplexing and beamforming gains, what is the multiplicative boost in the throughput when we are now allowed to occasionally add content inside reasonably-sized receiver-side caches? The derived closed-form expressions capture various linear precoders, and a variety of practical considerations such as power dissemination across signals, realistic SNR values, as well as feedback costs. The schemes are very simple (we simply collapse precoding vectors into a single vector), and the recorded gains are notable. For example, for 32 transmit antennas, a received SNR of 20 dB, a coherence bandwidth of 300 kHz, a coherence period of 40 ms, and under realistic file-size and cache-size constraints, vector coded caching is here shown to offer a multiplicative throughput boost of about 310% with ZF/RZF precoding and a 430% boost in the performance of already optimized MF-based systems. Interestingly, vector coded caching also accelerates channel hardening to the benefit of feedback acquisition, often surpassing 540% gains over traditional hardening-constrained downlink systems.
Universal Adversarial Examples in Remote Sensing: Methodology and Benchmark
Venue: arXiv cs.CV 2022
Year: 2022

Deep neural networks have achieved great success in many important remote sensing tasks. Nevertheless, their vulnerability to adversarial examples should not be neglected. In this study, we systematically analyze the universal adversarial examples in remote sensing data for the first time, without any knowledge from the victim model. Specifically, we propose a novel black-box adversarial attack method, namely Mixup-Attack, and its simple variant Mixcut-Attack, for remote sensing data. The key idea of the proposed methods is to find common vulnerabilities among different networks by attacking the features in the shallow layer of a given surrogate model. Despite their simplicity, the proposed methods can generate transferable adversarial examples that deceive most of the state-of-the-art deep neural networks in both scene classification and semantic segmentation tasks with high success rates. We further provide the generated universal adversarial examples in the dataset named UAE-RS, which is the first dataset that provides black-box adversarial samples in the remote sensing field. We hope UAE-RS may serve as a benchmark that helps researchers to design deep neural networks with strong resistance toward adversarial attacks in the remote sensing field. Codes and the UAE-RS dataset are available online (https://github.com/YonghaoXu/UAE-RS).
Towards hardware Implementation of WTA for CPG-based control of a Spiking Robotic Arm
Venue: arXiv cs.RO 2022
Year: 2022

Biological nervous systems typically perform the control of numerous degrees of freedom for example in animal limbs. Neuromorphic engineers study these systems by emulating them in hardware for a deeper understanding and its possible application to solve complex problems in engineering and robotics. Central-Pattern-Generators (CPGs) are part of neuro-controllers, typically used at their last steps to produce rhythmic patterns for limbs movement. Different patterns and gaits typically compete through winner-take-all (WTA) circuits to produce the right movements. In this work we present a WTA circuit implemented in a Spiking-Neural-Network (SNN) processor to produce such patterns for controlling a robotic arm in real-time. The robot uses spike-based proportional-integrativederivative (SPID) controllers to keep a commanded joint position from the winner population of neurons of the WTA circuit. Experiments demonstrate the feasibility of robotic control with spiking circuits following brain-inspiration.
NewsPod: Automatic and Interactive News Podcasts
Venue: arXiv cs.HC 2022
Year: 2022

News podcasts are a popular medium to stay informed and dive deep into news topics. Today, most podcasts are handcrafted by professionals. In this work, we advance the state-of-the-art in automatically generated podcasts, making use of recent advances in natural language processing and text-to-speech technology. We present NewsPod, an automatically generated, interactive news podcast. The podcast is divided into segments, each centered on a news event, with each segment structured as a Question and Answer conversation, whose goal is to engage the listener. A key aspect of the design is the use of distinct voices for each role (questioner, responder), to better simulate a conversation. Another novel aspect of NewsPod allows listeners to interact with the podcast by asking their own questions and receiving automatically generated answers. We validate the soundness of this system design through two usability studies, focused on evaluating the narrative style and interactions with the podcast, respectively. We find that NewsPod is preferred over a baseline by participants, with 80% claiming they would use the system in the future.
On the Origins of the Block Structure Phenomenon in Neural Network Representations
Venue: arXiv cs.LG 2022
Year: 2022

Recent work has uncovered a striking phenomenon in large-capacity neural networks: they contain blocks of contiguous hidden layers with highly similar representations. This block structure has two seemingly contradictory properties: on the one hand, its constituent layers exhibit highly similar dominant first principal components (PCs), but on the other hand, their representations, and their common first PC, are highly dissimilar across different random seeds. Our work seeks to reconcile these discrepant properties by investigating the origin of the block structure in relation to the data and training methods. By analyzing properties of the dominant PCs, we find that the block structure arises from dominant datapoints - a small group of examples that share similar image statistics (e.g. background color). However, the set of dominant datapoints, and the precise shared image statistic, can vary across random seeds. Thus, the block structure reflects meaningful dataset statistics, but is simultaneously unique to each model. Through studying hidden layer activations and creating synthetic datapoints, we demonstrate that these simple image statistics dominate the representational geometry of the layers inside the block structure. We explore how the phenomenon evolves through training, finding that the block structure takes shape early in training, but the underlying representations and the corresponding dominant datapoints continue to change substantially. Finally, we study the interplay between the block structure and different training mechanisms, introducing a targeted intervention to eliminate the block structure, as well as examining the effects of pretraining and Shake-Shake regularization.