OpenRaiser/Intern-Atlas huggingface dataset:
Collusion Resistant Federated Learning with Oblivious Distributed Differential Privacy
Venue: arXiv cs.CR 2022
Year: 2022

Privacy-preserving federated learning enables a population of distributed clients to jointly learn a shared model while keeping client training data private, even from an untrusted server. Prior works do not provide efficient solutions that protect against collusion attacks in which parties collaborate to expose an honest client's model parameters. We present an efficient mechanism based on oblivious distributed differential privacy that is the first to protect against such client collusion, including the "Sybil" attack in which a server preferentially selects compromised devices or simulates fake devices. We leverage the novel privacy mechanism to construct a secure federated learning protocol and prove the security of that protocol. We conclude with empirical analysis of the protocol's execution speed, learning accuracy, and privacy performance on two data sets within a realistic simulation of 5,000 distributed network clients.
Mining Robust Default Configurations for Resource-constrained AutoML
Venue: arXiv cs.LG 2022
Year: 2022

Automatic machine learning (AutoML) is a key enabler of the mass deployment of the next generation of machine learning systems. A key desideratum for future ML systems is the automatic selection of models and hyperparameters. We present a novel method of selecting performant configurations for a given task by performing offline autoML and mining over a diverse set of tasks. By mining the training tasks, we can select a compact portfolio of configurations that perform well over a wide variety of tasks, as well as learn a strategy to select portfolio configurations for yet-unseen tasks. The algorithm runs in a zero-shot manner, that is without training any models online except the chosen one. In a compute- or time-constrained setting, this virtually instant selection is highly performant. Further, we show that our approach is effective for warm-starting existing autoML platforms. In both settings, we demonstrate an improvement on the state-of-the-art by testing over 62 classification and regression datasets. We also demonstrate the utility of recommending data-dependent default configurations that outperform widely used hand-crafted defaults.
Online Spanners in Metric Spaces
Venue: arXiv cs.CG 2022
Year: 2022

Given a metric space $\mathcal{M}=(X,δ)$, a weighted graph $G$ over $X$ is a metric $t$-spanner of $\mathcal{M}$ if for every $u,v \in X$, $δ(u,v)\le d_G(u,v)\le t\cdot δ(u,v)$, where $d_G$ is the shortest path metric in $G$. In this paper, we construct spanners for finite sets in metric spaces in the online setting. Here, we are given a sequence of points $(s_1, \ldots, s_n)$, where the points are presented one at a time (i.e., after $i$ steps, we saw $S_i = \{s_1, \ldots , s_i\}$). The algorithm is allowed to add edges to the spanner when a new point arrives, however, it is not allowed to remove any edge from the spanner. The goal is to maintain a $t$-spanner $G_i$ for $S_i$ for all $i$, while minimizing the number of edges, and their total weight. We construct online $(1+\varepsilon)$-spanners in Euclidean $d$-space, $(2k-1)(1+\varepsilon)$-spanners for general metrics, and $(2+\varepsilon)$-spanners for ultrametrics. Most notably, in Euclidean plane, we construct a $(1+\varepsilon)$-spanner with competitive ratio $O(\varepsilon^{-3/2}\log\varepsilon^{-1}\log n)$, bypassing the classic lower bound $Ω(\varepsilon^{-2})$ for lightness, which compares the weight of the spanner, to that of the MST.
Obtaining Approximately Optimal and Diverse Solutions via Dispersion
Venue: arXiv cs.DS 2022
Year: 2022

There has been a long-standing interest in computing diverse solutions to optimization problems. Motivated by reallocation of governmental institutions in Sweden, in 1995 J. Krarup posed the problem of finding $k$ edge-disjoint Hamiltonian Circuits of minimum total weight, called the peripatetic salesman problem (PSP). Since then researchers have investigated the complexity of finding diverse solutions to spanning trees, paths, vertex covers, matchings, and more. Unlike the PSP that has a constraint on the total weight of the solutions, recent work has involved finding diverse solutions that are all optimal. However, sometimes the space of exact solutions may be too small to achieve sufficient diversity. Motivated by this, we initiate the study of obtaining sufficiently-diverse, yet approximately-optimal solutions to optimization problems. Formally, given an integer $k$, an approximation factor $c$, and an instance $I$ of an optimization problem, we aim to obtain a set of $k$ solutions to $I$ that a) are all $c$ approximately-optimal for $I$ and b) maximize the diversity of the $k$ solutions. Finding such solutions, therefore, requires a better understanding of the global landscape of the optimization function. We show that, given any metric on the space of solutions, and the diversity measure as the sum of pairwise distances between solutions, this problem can be solved by combining ideas from dispersion and multicriteria optimization. We first provide a general reduction to an associated budget-constrained optimization (BCO) problem, where one objective function is to be maximized (minimized) subject to a bound on the second objective function. We then prove that bi-approximations to the BCO can be used to give bi-approximations to the diverse approximately optimal solutions problem with a little overhead.
Analysis of Two-Station Polling Queues with Setups using Continuous Time Markov Chain
Venue: arXiv cs.PF 2022
Year: 2022

The paper analyzes the performance of tandem network of polling queue with setups. For a system with two-products and two-stations, we propose a new approach based on a partially-collapsible state-space characterization to reduce state-space complexity. In this approach, the size of the state-space is varied depending on the information needed to determine buffer levels and waiting times. We evaluate system performance under different system setting and comment on the numerical accuracy of the approach as well as provide managerial insights. Numerical results show that approach yields reliable estimates of the performance measures. We also show how product and station asymmetry significantly affect the systems performance.
Analysis of Digital Sovereignty and Identity: From Digitization to Digitalization
Venue: arXiv cs.CR 2022
Year: 2022

Advances in emerging technologies have accelerated digital transformation with the pervasive digitalization of the economy and society, driving innovations such as smart cities, industry 4.0 and FinTech. Unlike digitization, digitalization is a transformation to improve processes by leveraging digital technologies and digitized data. The cyberspace has evolved from a hardware internetworking infrastructure to the notion of a virtual environment, transforming how people, business and government interact and operate. Through this transformation, lots of personal data are captured which individuals have no ownership or control over, threatening their privacy. It is therefore necessary for the data owners to have control over the ownership, custody and utilization of their data and to protect one's digital assets and identity through proper data governance, cybersecurity control and privacy protection. This results in the notions of data sovereignty and digital sovereignty - two conceptually related terms, but different focuses. This paper first explains these two concepts in terms of their guiding principles, laws and regulations requirements, and analyse and discuss the technical challenges of implementing these requirements. Next, to understand the emerging trend shift in digital sovereignty towards individuals to take complete control of the security and privacy of their own digital assets, this paper conducts a systematic study and analysis of Self-Sovereign Identity, and discuss existing solutions and point out that an efficient key management system, scalability and interoperability of the solutions and well established standards are some of its challenges and open problems to wide deployments.
bAdvertisement: Attacking Advanced Driver-Assistance Systems Using Print Advertisements
Venue: arXiv cs.CR 2022
Year: 2022

In this paper, we present bAdvertisement, a novel attack method against advanced driver-assistance systems (ADASs). bAdvertisement is performed as a supply chain attack via a compromised computer in a printing house, by embedding a "phantom" object in a print advertisement. When the compromised print advertisement is observed by an ADAS in a passing car, an undesired reaction is triggered from the ADAS. We analyze state-of-the-art object detectors and show that they do not take color or context into account in object detection. Our validation of these findings on Mobileye 630 PRO shows that this ADAS also fails to take color or context into account. Then, we show how an attacker can take advantage of these findings to execute an attack on a commercial ADAS, by embedding a phantom road sign in a print advertisement, which causes a car equipped with Mobileye 630 PRO to trigger a false notification to slow down. Finally, we discuss multiple countermeasures which can be deployed in order to mitigate the effect of our proposed attack.
Applications of blockchain and artificial intelligence technologies for enabling prosumers in smart grids: A review
Venue: arXiv cs.IT 2022
Year: 2022

Governments' net zero emission target aims at increasing the share of renewable energy sources as well as influencing the behaviours of consumers to support the cost-effective balancing of energy supply and demand. These will be achieved by the advanced information and control infrastructures of smart grids which allow the interoperability among various stakeholders. Under this circumstance, increasing number of consumers produce, store, and consume energy, giving them a new role of prosumers. The integration of prosumers and accommodation of incurred bidirectional flows of energy and information rely on two key factors: flexible structures of energy markets and intelligent operations of power systems. The blockchain and artificial intelligence (AI) are innovative technologies to fulfil these two factors, by which the blockchain provides decentralised trading platforms for energy markets and the AI supports the optimal operational control of power systems. This paper attempts to address how to incorporate the blockchain and AI in the smart grids for facilitating prosumers to participate in energy markets. To achieve this objective, first, this paper reviews how policy designs price carbon emissions caused by the fossil-fuel based generation so as to facilitate the integration of prosumers with renewable energy sources. Second, the potential structures of energy markets with the support of the blockchain technologies are discussed. Last, how to apply the AI for enhancing the state monitoring and decision making during the operations of power systems is introduced.
Defining long words succinctly in FO and MSO
Venue: arXiv cs.LO 2022
Year: 2022

We consider the length of the longest word definable in FO and MSO via a formula of size n. For both logics we obtain as an upper bound for this number an exponential tower of height linear in n. We prove this by counting types with respect to a fixed quantifier rank. As lower bounds we obtain for both FO and MSO an exponential tower of height in the order of a rational power of n. We show these lower bounds by giving concrete formulas defining word representations of levels of the cumulative hierarchy of sets. In addition, we consider the Löwenheim-Skolem and Hanf numbers of these logics on words and obtain similar bounds for these as well.
Path of Destruction: Learning an Iterative Level Generator Using a Small Dataset
Venue: arXiv cs.LG 2022
Year: 2022

We propose a new procedural content generation method which learns iterative level generators from a dataset of existing levels. The Path of Destruction method, as we call it, views level generation as repair; levels are created by iteratively repairing from a random starting level. The first step is to generate an artificial dataset from the original set of levels by introducing many different sequences of mutations to existing levels. In the generated dataset, features are observations of destroyed levels and targets are the specific actions that repair the mutated tile in the middle of the observations. Using this dataset, a convolutional network is trained to map from observations to their respective appropriate repair actions. The trained network is then used to iteratively produce levels from random starting maps. We demonstrate this method by applying it to generate unique and playable tile-based levels for several 2D games (Zelda, Danger Dave, and Sokoban) and vary key hyperparameters.
Permutation Predictions for Non-Clairvoyant Scheduling
Venue: arXiv cs.DS 2022
Year: 2022

In non-clairvoyant scheduling, the task is to find an online strategy for scheduling jobs with a priori unknown processing requirements with the objective to minimize the total (weighted) completion time. We revisit this well-studied problem in a recently popular learning-augmented setting that integrates (untrusted) predictions in online algorithm design. While previous works used predictions on processing requirements, we propose a new prediction model, which provides a relative order of jobs which could be seen as predicting algorithmic actions rather than parts of the unknown input. We show that these predictions have desired properties, admit a natural error measure as well as algorithms with strong performance guarantees and that they are learnable in both, theory and practice. We generalize the algorithmic framework proposed in the seminal paper by Kumar et al. (NeurIPS'18) and present the first learning-augmented scheduling results for weighted jobs and unrelated machines. We demonstrate in empirical experiments the practicability and superior performance compared to the previously suggested single-machine algorithms.
OG-SGG: Ontology-Guided Scene Graph Generation. A Case Study in Transfer Learning for Telepresence Robotics
Venue: arXiv cs.RO 2022
Year: 2022

Scene graph generation from images is a task of great interest to applications such as robotics, because graphs are the main way to represent knowledge about the world and regulate human-robot interactions in tasks such as Visual Question Answering (VQA). Unfortunately, its corresponding area of machine learning is still relatively in its infancy, and the solutions currently offered do not specialize well in concrete usage scenarios. Specifically, they do not take existing "expert" knowledge about the domain world into account; and that might indeed be necessary in order to provide the level of reliability demanded by the use case scenarios. In this paper, we propose an initial approximation to a framework called Ontology-Guided Scene Graph Generation (OG-SGG), that can improve the performance of an existing machine learning based scene graph generator using prior knowledge supplied in the form of an ontology (specifically, using the axioms defined within); and we present results evaluated on a specific scenario founded in telepresence robotics. These results show quantitative and qualitative improvements in the generated scene graphs.
I/O-Optimal Algorithms for Symmetric Linear Algebra Kernels
Venue: arXiv cs.DC 2022
Year: 2022

In this paper, we consider two fundamental symmetric kernels in linear algebra: the Cholesky factorization and the symmetric rank-$k$ update (SYRK), with the classical three nested loops algorithms for these kernels. In addition, we consider a machine model with a fast memory of size $S$ and an unbounded slow memory. In this model, all computations must be performed on operands in fast memory, and the goal is to minimize the amount of communication between slow and fast memories. As the set of computations is fixed by the choice of the algorithm, only the ordering of the computations (the schedule) directly influences the volume of communications.We prove lower bounds of $\frac{1}{3\sqrt{2}}\frac{N^3}{\sqrt{S}}$ for the communication volume of the Cholesky factorization of an $N\times N$ symmetric positive definite matrix, and of $\frac{1}{\sqrt{2}}\frac{N^2M}{\sqrt{S}}$ for the SYRK computation of $\mat{A}\cdot\transpose{\mat{A}}$, where $\mathbf{A}$ is an $N\times M$ matrix. Both bounds improve the best known lower bounds from the literature by a factor $\sqrt{2}$.In addition, we present two out-of-core, sequential algorithms with matching communication volume: \TBS for SYRK, with a volume of $\frac{1}{\sqrt{2}}\frac{N^2M}{\sqrt{S}} + \bigo{NM\log N}$, and \LBC for Cholesky, with a volume of $\frac{1}{3\sqrt{2}}\frac{N^3}{\sqrt{S}} + \bigo{N^{5/2}}$. Both algorithms improve over the best known algorithms from the literature by a factor $\sqrt{2}$, and prove that the leading terms in our lower bounds cannot be improved further. This work shows that the operational intensity of symmetric kernels like SYRK or Cholesky is intrinsically higher (by a factor $\sqrt{2}$) than that of corresponding non-symmetric kernels (GEMM and LU factorization).
Robots Learn Increasingly Complex Tasks with Intrinsic Motivation and Automatic Curriculum Learning
Venue: arXiv cs.RO 2022
Year: 2022

Multi-task learning by robots poses the challenge of the domain knowledge: complexity of tasks, complexity of the actions required, relationship between tasks for transfer learning. We demonstrate that this domain knowledge can be learned to address the challenges in life-long learning. Specifically, the hierarchy between tasks of various complexities is key to infer a curriculum from simple to composite tasks. We propose a framework for robots to learn sequences of actions of unbounded complexity in order to achieve multiple control tasks of various complexity. Our hierarchical reinforcement learning framework, named SGIM-SAHT, offers a new direction of research, and tries to unify partial implementations on robot arms and mobile robots. We outline our contributions to enable robots to map multiple control tasks to sequences of actions: representations of task dependencies, an intrinsically motivated exploration to learn task hierarchies, and active imitation learning. While learning the hierarchy of tasks, it infers its curriculum by deciding which tasks to explore first, how to transfer knowledge, and when, how and whom to imitate.
Efficient Cross-Modal Retrieval via Deep Binary Hashing and Quantization
Venue: arXiv cs.IR 2022
Year: 2022

Cross-modal retrieval aims to search for data with similar semantic meanings across different content modalities. However, cross-modal retrieval requires huge amounts of storage and retrieval time since it needs to process data in multiple modalities. Existing works focused on learning single-source compact features such as binary hash codes that preserve similarities between different modalities. In this work, we propose a jointly learned deep hashing and quantization network (HQ) for cross-modal retrieval. We simultaneously learn binary hash codes and quantization codes to preserve semantic information in multiple modalities by an end-to-end deep learning architecture. At the retrieval step, binary hashing is used to retrieve a subset of items from the search space, then quantization is used to re-rank the retrieved items. We theoretically and empirically show that this two-stage retrieval approach provides faster retrieval results while preserving accuracy. Experimental results on the NUS-WIDE, MIR-Flickr, and Amazon datasets demonstrate that HQ achieves boosts of more than 7% in precision compared to supervised neural network-based compact coding models.
A Dynamic Model of a Skydiver With Validation in Wind Tunnel and Free Fall
Venue: arXiv cs.RO 2022
Year: 2022

An innovative approach of gaining insight into motor skills involved in human body flight is proposed. The key idea is the creation of a model autonomous system capable of virtually performing skydiving maneuvers. A dynamic skydiver model and simulator is developed, comprising biomechanical, aerodynamic, and kinematic models, dynamic equations of motion, and a virtual reality environment. Limb relative orientations, and resulting inertial body angular position and velocity are measured in skydiving experiments in a vertical wind tunnel and in free fall. These experimental data are compared with corresponding simulation data to tune and verify the model for basic skydiving maneuvers. The model is further extended to reconstruct advanced aerial maneuvers, such as transitions between stable equilibria. The experimental data are used to estimate skydiver's conscious inputs as a function of time, via an Unscented Kalman Filter modified for this purpose.
VRConvMF: Visual Recurrent Convolutional Matrix Factorization for Movie Recommendation
Venue: arXiv cs.IR 2022
Year: 2022

Sparsity of user-to-item rating data becomes one of challenging issues in the recommender systems, which severely deteriorates the recommendation performance. Fortunately, context-aware recommender systems can alleviate the sparsity problem by making use of some auxiliary information, such as the information of both the users and items. In particular, the visual information of items, such as the movie poster, can be considered as the supplement for item description documents, which helps to obtain more item features. In this paper, we focus on movie recommender system and propose a probabilistic matrix factorization based recommendation scheme called visual recurrent convolutional matrix factorization (VRConvMF), which utilizes the textual and multi-level visual features extracted from the descriptive texts and posters respectively. We implement the proposed VRConvMF and conduct extensive experiments on three commonly used real world datasets to validate its effectiveness. The experimental results illustrate that the proposed VRConvMF outperforms the existing schemes.
Priority Algorithms with Advice for Disjoint Path Allocation Problems
Venue: arXiv cs.DS 2022
Year: 2022

We analyze the Disjoint Path Allocation problem (DPA) in the priority framework. Motivated by the problem of traffic regulation in communication networks, DPA consists of allocating edge-disjoint paths in a graph. While online algorithms for DPA have been thoroughly studied in the past, we extend the analysis of this optimization problem by considering the more powerful class of priority algorithms. Like an online algorithm, a priority algorithm receives its input only sequentially and must output irrevocable decisions for individual input items before having seen the input in its entirety. However, in contrast to the online setting, a priority algorithm may choose an order on the set of all possible input items and the actual input is then presented according to this order. A priority algorithm is a natural model for the intuitively well-understood concept of a greedy algorithm. Apart from analyzing the classical priority setting, we also consider priority algorithms with advice. Originally conceived to study online algorithms from an information-theoretic point of view, the concept of advice has recently been extended to the priority framework. In this paper, we analyze the classical variant of the DPA problem on the graph class of paths, the related problem of Length-Weighted DPA, and finally, DPA on the graph class of trees. We show asymptotically matching upper and lower bounds on the advice necessary for optimality in LWDPA and generalize the known optimality result for DPA on paths to trees with maximal degree at most 3. On trees with maximal degree greater than 3, we prove matching upper and lower bounds on the approximation ratio in the advice-free priority setting. Finally, we present upper and lower bounds on the advice necessary to achieve optimality on such trees.