OpenRaiser/Intern-Atlas huggingface dataset:
DeepParticle: learning invariant measure by a deep neural network minimizing Wasserstein distance on data generated from an interacting particle method
Venue: arXiv cs.LG 2022
Year: 2022

We introduce the so called DeepParticle method to learn and generate invariant measures of stochastic dynamical systems with physical parameters based on data computed from an interacting particle method (IPM). We utilize the expressiveness of deep neural networks (DNNs) to represent the transform of samples from a given input (source) distribution to an arbitrary target distribution, neither assuming distribution functions in closed form nor a finite state space for the samples. In training, we update the network weights to minimize a discrete Wasserstein distance between the input and target samples. To reduce computational cost, we propose an iterative divide-and-conquer (a mini-batch interior point) algorithm, to find the optimal transition matrix in the Wasserstein distance. We present numerical results to demonstrate the performance of our method for accelerating IPM computation of invariant measures of stochastic dynamical systems arising in computing reaction-diffusion front speeds through chaotic flows. The physical parameter is a large Peclét number reflecting the advection dominated regime of our interest.
Probabilistic Deep Learning for Real-Time Large Deformation Simulations
Venue: arXiv cs.LG 2022
Year: 2022

For many novel applications, such as patient-specific computer-aided surgery, conventional solution techniques of the underlying nonlinear problems are usually computationally too expensive and are lacking information about how certain can we be about their predictions. In the present work, we propose a highly efficient deep-learning surrogate framework that is able to accurately predict the response of bodies undergoing large deformations in real-time. The surrogate model has a convolutional neural network architecture, called U-Net, which is trained with force-displacement data obtained with the finite element method. We propose deterministic and probabilistic versions of the framework. The probabilistic framework utilizes the Variational Bayes Inference approach and is able to capture all the uncertainties present in the data as well as in the deep-learning model. Based on several benchmark examples, we show the predictive capabilities of the framework and discuss its possible limitations
Equivariant Deep Dynamical Model for Motion Prediction
Venue: arXiv cs.LG 2022
Year: 2022

Learning representations through deep generative modeling is a powerful approach for dynamical modeling to discover the most simplified and compressed underlying description of the data, to then use it for other tasks such as prediction. Most learning tasks have intrinsic symmetries, i.e., the input transformations leave the output unchanged, or the output undergoes a similar transformation. The learning process is, however, usually uninformed of these symmetries. Therefore, the learned representations for individually transformed inputs may not be meaningfully related. In this paper, we propose an SO(3) equivariant deep dynamical model (EqDDM) for motion prediction that learns a structured representation of the input space in the sense that the embedding varies with symmetry transformations. EqDDM is equipped with equivariant networks to parameterize the state-space emission and transition models. We demonstrate the superior predictive performance of the proposed model on various motion data.
Deterministic Min-cut in Poly-logarithmic Max-flows
Venue: arXiv cs.DS 2022
Year: 2022

We give a deterministic algorithm for finding the minimum (weight) cut of an undirected graph on $n$ vertices and $m$ edges using $\text{polylog}(n)$ calls to any maximum flow subroutine. Using the current best deterministic maximum flow algorithms, this yields an overall running time of $\tilde O(m \cdot \min(\sqrt{m}, n^{2/3}))$ for weighted graphs, and $m^{4/3+o(1)}$ for unweighted (multi)-graphs. This marks the first improvement for this problem since a running time bound of $\tilde O(mn)$ was established by several papers in the early 1990s. Our global minimum cut algorithm is obtained as a corollary of a minimum Steiner cut algorithm, where a minimum Steiner cut is a minimum (weight) set of edges whose removal disconnects at least one pair of vertices among a designated set of terminal vertices. The running time of our deterministic minimum Steiner cut algorithm matches that of the global minimum cut algorithm stated above. Using randomization, the running time improves to $m^{1+o(1)}$ because of a faster maximum flow subroutine; this improves the best known randomized algorithm for the minimum Steiner cut problem as well. Our main technical contribution is a new tool that we call *isolating cuts*. Given a set of vertices $R$, this entails finding cuts of minimum weight that separate (or isolate) each individual vertex $v\in R$ from the rest of the vertices $R\setminus \{v\}$. Naïvely, this can be done using $|R|$ maximum flow calls, but we show that just $O(\log |R|)$ suffice for finding isolating cuts for any set of vertices $R$. We call this the *isolating cut lemma*.
EASE: Energy-Aware Job Scheduling for Vehicular Edge Networks With Renewable Energy Resources
Venue: arXiv cs.NI 2022
Year: 2022

The energy sustainability of multi-access edge computing (MEC) platforms is here addressed by developing Energy-Aware job Scheduling at the Edge (EASE), a computing resource scheduler for edge servers co-powered by renewable energy resources and the power grid. The scenario under study involves the optimal allocation and migration of time-sensitive computing tasks in a resource-constrained internet of vehicles (IoV) context. This is achieved by tackling, as the main objective, the minimization of the carbon footprint of the edge network, whilst delivering adequate quality of service (QoS) to the end users (e.g., meeting task execution deadlines). EASE integrates i) a centralized optimization step, solved through model predictive control (MPC), to manage the renewable energy that is locally collected at the edge servers and their local computing resources, estimating their future availability, and ii) a distributed consensus step, solved via dual ascent in closed form, to reach agreement on service migrations. EASE is compared with four existing migration strategies. Quantitative results demonstrate its greater energy efficiency, which often gets close to complete carbon neutrality, while also improving the QoS.
Origami-inspired soft twisting actuator
Venue: arXiv cs.RO 2022
Year: 2022

Soft actuators have shown great advantages in compliance and morphology matched for manipulation of delicate objects and inspection in a confined space. There is an unmet need for a soft actuator that can provide torsional motion to e.g. enlarge working space and increase degrees of freedom. Towards this goal, we present origami-inspired soft pneumatic actuators (OSPAs) made from silicone. The prototype can output a rotation of more than one revolution (up to 435°), more significant than its counterparts. Its rotation ratio (=rotation angle/ aspect ratio) is more than 136°, about twice the largest one in other literature. We describe the design and fabrication method, build the analytical model and simulation model, and analyze and optimize the parameters. Finally, we demonstrate the potentially extensive utility of the OSPAs through their integration into a gripper capable of simultaneously grasping and lifting fragile or flat objects, a versatile robot arm capable of picking and placing items at the right angle with the twisting actuators, and a soft snake robot capable of changing attitude and directions by torsion of the twisting actuators.
Physarum Inspired Dynamics to Solve Semi-Definite Programs
Venue: arXiv cs.DS 2022
Year: 2022

Physarum Polycephalum is a slime mold that can solve shortest path problems. A mathematical model based on Physarum's behavior, known as the Physarum Directed Dynamics, can solve positive linear programs. In this paper, we present a family of Physarum-based dynamics extending the previous work and introduce a new algorithm to solve positive Semi-Definite Programs (SDP). The Physarum dynamics are governed by orthogonal projections (w.r.t. time-dependent scalar products) on the affine subspace defined by the linear constraints. We present a natural generalization of the scalar products used in the LP case to the matrix space for SDPs, which boils down to the linear case when all matrices in the SDP are diagonal, thus, representing an LP. We investigate the behavior of the induced dynamics theoretically and experimentally, highlight challenges arising from the non-commutative nature of matrix products, and prove soundness and convergence under mild conditions. Moreover, we consider a more abstract view on the dynamics that suggests a slight variation to guarantee unconditional soundness and convergence-to-optimality. By simulating these dynamics using suitable discretizations, one obtains numerical algorithms for solving positive SDPs, which have applications in discrete optimization, e.g., for computing the Goemans-Williamson approximation for MaxCut or the Lovasz theta number for determining the clique/chromatic number in perfect graphs.
The Parameterized Complexity of the Survivable Network Design Problem
Venue: arXiv cs.DS 2022
Year: 2022

For the well-known Survivable Network Design Problem (SNDP) we are given an undirected graph $G$ with edge costs, a set $R$ of terminal vertices, and an integer demand $d_{s,t}$ for every terminal pair $s,t\in R$. The task is to compute a subgraph $H$ of $G$ of minimum cost, such that there are at least $d_{s,t}$ disjoint paths between $s$ and $t$ in $H$. If the paths are required to be edge-disjoint we obtain the edge-connectivity variant (EC-SNDP), while internally vertex-disjoint paths result in the vertex-connectivity variant (VC-SNDP). Another important case is the element-connectivity variant (LC-SNDP), where the paths are disjoint on edges and non-terminals. In this work we shed light on the parameterized complexity of the above problems. We consider several natural parameters, which include the solution size $\ell$, the sum of demands $D$, the number of terminals $k$, and the maximum demand $d_\max$. Using simple, elegant arguments, we prove the following results. - We give a complete picture of the parameterized tractability of the three variants w.r.t. parameter $\ell$: both EC-SNDP and LC-SNDP are FPT, while VC-SNDP is W[1]-hard. - We identify some special cases of VC-SNDP that are FPT: * when $d_\max\leq 3$ for parameter $\ell$, * on locally bounded treewidth graphs (e.g., planar graphs) for parameter $\ell$, and * on graphs of treewidth $tw$ for parameter $tw+D$. - The well-known Directed Steiner Tree (DST) problem can be seen as single-source EC-SNDP with $d_\max=1$ on directed graphs, and is FPT parameterized by $k$ [Dreyfus & Wagner 1971]. We show that in contrast, the 2-DST problem, where $d_\max=2$, is W[1]-hard, even when parameterized by $\ell$.
Nearly Tight Lower Bounds for Succinct Range Minimum Query
Venue: arXiv cs.DS 2022
Year: 2022

Given an array of distinct integers $A[1\ldots n]$, the Range Minimum Query (RMQ) problem requires us to construct a data structure from $A$, supporting the RMQ query: given an interval $[a,b]\subseteq[1,n]$, return the index of the minimum element in subarray $A[a\ldots b]$, i.e. return $\text{argmin}_{i\in[a,b]}A[i]$. The fundamental problem has a long history. The textbook solution which uses $O(n)$ words of space and $O(1)$ time by Gabow, Bentley, Tarjan (STOC 1984) and Harel, Tarjan (SICOMP 1984) dates back to 1980s. The state-of-the-art solution is presented by Fischer, Heun (SICOMP 2011) and Navarro, Sadakane (TALG 2014). The solution uses $2n-1.5\log n+n/\left(\frac{\log n}{t}\right)^t+\tilde{O}(n^{3/4})$ bits of space and $O(t)$ query time, where the additive $\tilde{O}(n^{3/4})$ is a pre-computed lookup table used in the RAM model, assuming the word-size is $Θ(\log n)$ bits. On the other hand, the only known lower bound is proved by Liu and Yu (STOC 2020). They show that any data structure which solves RMQ in $t$ query time must use $2n-1.5\log n+n/(\log n)^{O(t^2\log^2t)}$ bits of space, assuming the word-size is $Θ(\log n)$ bits. In this paper, we prove nearly tight lower bound for this problem. We show that, for any data structure which solves RMQ in $t$ query time, $2n-1.5\log n+n/(\log n)^{O(t\log^2t)}$ bits of space is necessary in the cell-probe model with word-size $Θ(\log n)$ bits. We emphasize that, in terms of time complexity, our lower bound is tight up to a polylogarithmic factor.
An Improved Algorithm for The $k$-Dyck Edit Distance Problem
Venue: arXiv cs.DS 2022
Year: 2022

A Dyck sequence is a sequence of opening and closing parentheses (of various types) that is balanced. The Dyck edit distance of a given sequence of parentheses $S$ is the smallest number of edit operations (insertions, deletions, and substitutions) needed to transform $S$ into a Dyck sequence. We consider the threshold Dyck edit distance problem, where the input is a sequence of parentheses $S$ and a positive integer $k$, and the goal is to compute the Dyck edit distance of $S$ only if the distance is at most $k$, and otherwise report that the distance is larger than $k$. Backurs and Onak [PODS'16] showed that the threshold Dyck edit distance problem can be solved in $O(n+k^{16})$ time. In this work, we design new algorithms for the threshold Dyck edit distance problem which costs $O(n+k^{4.544184})$ time with high probability or $O(n+k^{4.853059})$ deterministically. Our algorithms combine several new structural properties of the Dyck edit distance problem, a refined algorithm for fast $(\min,+)$ matrix product, and a careful modification of ideas used in Valiant's parsing algorithm.
Logically Sound Arguments for the Effectiveness of ML Safety Measures
Venue: arXiv cs.LO 2022
Year: 2022

We investigate the issues of achieving sufficient rigor in the arguments for the safety of machine learning functions. By considering the known weaknesses of DNN-based 2D bounding box detection algorithms, we sharpen the metric of imprecise pedestrian localization by associating it with the safety goal. The sharpening leads to introducing a conservative post-processor after the standard non-max-suppression as a counter-measure. We then propose a semi-formal assurance case for arguing the effectiveness of the post-processor, which is further translated into formal proof obligations for demonstrating the soundness of the arguments. Applying theorem proving not only discovers the need to introduce missing claims and mathematical concepts but also reveals the limitation of Dempster-Shafer's rules used in semi-formal argumentation.
A thread-safe Term Library
Venue: arXiv cs.DC 2022
Year: 2022

Terms are one of the fundamental mathematical concepts in computing. E.g. every expression characterisable by a context free grammar is a term. We developed a thread-safe Term Library. The biggest challenge is to implement hyper-efficient multi-reader/single-writer mutual exclusion for which we designed the new busy-forbidden protocol. Model checking is used to show both the correctness of the protocol and the Term Library. Benchmarks show this Term Library has little overhead compared to sequential versions and outperforms them already on two processors. Using the new library in an existing state space generation tool, very substantial speed ups can be obtained.
Big Data Testing Techniques: Taxonomy, Challenges and Future Trends
Venue: arXiv cs.AI 2022
Year: 2022

Big Data is reforming many industrial domains by providing decision support through analyzing large data volumes. Big Data testing aims to ensure that Big Data systems run smoothly and error-free while maintaining the performance and quality of data. However, because of the diversity and complexity of data, testing Big Data is challenging. Though numerous research efforts deal with Big Data testing, a comprehensive review to address testing techniques and challenges of Big Data is not available as yet. Therefore, we have systematically reviewed the Big Data testing techniques evidence occurring in the period 2010-2021. This paper discusses testing data processing by highlighting the techniques used in every processing phase. Furthermore, we discuss the challenges and future directions. Our findings show that diverse functional, non-functional and combined (functional and non-functional) testing techniques have been used to solve specific problems related to Big Data. At the same time, most of the testing challenges have been faced during the MapReduce validation phase. In addition, the combinatorial testing technique is one of the most applied techniques in combination with other techniques (i.e., random testing, mutation testing, input space partitioning and equivalence testing) to find various functional faults through Big Data testing.
Map-Assisted Constellation Design for mmWave WDM with OAM in Short-Range LOS Environment
Venue: arXiv cs.IT 2022
Year: 2022

We consider a system that integrates positioning and single-user millimeter wave (mmWave) communication, where the communication part adopts wavelength division multiplexing (WDM) and orbital angular momentum (OAM). This paper addresses the multi-dimensional constellation design in shortrange line-of-sight (LOS) environment, with stable communication links. We propose a map-assisted method to quantify the system parameters based on positions and reduce real-time computing overhead. We explore the possibility of using a few patterns in the maps, and investigate its performance loss. We first investigate the features of OAM beams, and find that the link gain ratio between any two sub-channels remains unchanged at some postions. Then, we prove that a fixed constellation can be adopted for the positions where the link gain matrices are sufficiently close to be proportional. Moreover, we prove that the system can adopt a fixed power vector to generate a multidimensional constellation if the difference between fixed power vector and optimal power vector is small. Finally, we figure out that the constellation design for all receiver locations can be represented by a few constellation sets.
Interpretable Personalized Experimentation
Venue: arXiv cs.LG 2022
Year: 2022

Black-box heterogeneous treatment effect (HTE) models are increasingly being used to create personalized policies that assign individuals to their optimal treatments. However, they are difficult to understand, and can be burdensome to maintain in a production environment. In this paper, we present a scalable, interpretable personalized experimentation system, implemented and deployed in production at Meta. The system works in a multiple treatment, multiple outcome setting typical at Meta to: (1) learn explanations for black-box HTE models; (2) generate interpretable personalized policies. We evaluate the methods used in the system on publicly available data and Meta use cases, and discuss lessons learnt during the development of the system.
IPAL: Breaking up Silos of Protocol-dependent and Domain-specific Industrial Intrusion Detection Systems
Venue: arXiv cs.CR 2022
Year: 2022

The increasing interconnection of industrial networks exposes them to an ever-growing risk of cyber attacks. To reveal such attacks early and prevent any damage, industrial intrusion detection searches for anomalies in otherwise predictable communication or process behavior. However, current efforts mostly focus on specific domains and protocols, leading to a research landscape broken up into isolated silos. Thus, existing approaches cannot be applied to other industries that would equally benefit from powerful detection. To better understand this issue, we survey 53 detection systems and find no fundamental reason for their narrow focus. Although they are often coupled to specific industrial protocols in practice, many approaches could generalize to new industrial scenarios in theory. To unlock this potential, we propose IPAL, our industrial protocol abstraction layer, to decouple intrusion detection from domain-specific industrial protocols. After proving IPAL's correctness in a reproducibility study of related work, we showcase its unique benefits by studying the generalizability of existing approaches to new datasets and conclude that they are indeed not restricted to specific domains or protocols and can perform outside their restricted silos.
Perturbational Complexity by Distribution Mismatch: A Systematic Analysis of Reinforcement Learning in Reproducing Kernel Hilbert Space
Venue: arXiv cs.LG 2022
Year: 2022

Most existing theoretical analysis of reinforcement learning (RL) is limited to the tabular setting or linear models due to the difficulty in dealing with function approximation in high dimensional space with an uncertain environment. This work offers a fresh perspective into this challenge by analyzing RL in a general reproducing kernel Hilbert space (RKHS). We consider a family of Markov decision processes $\mathcal{M}$ of which the reward functions lie in the unit ball of an RKHS and transition probabilities lie in a given arbitrary set. We define a quantity called perturbational complexity by distribution mismatch $Δ_{\mathcal{M}}(ε)$ to characterize the complexity of the admissible state-action distribution space in response to a perturbation in the RKHS with scale $ε$. We show that $Δ_{\mathcal{M}}(ε)$ gives both the lower bound of the error of all possible algorithms and the upper bound of two specific algorithms (fitted reward and fitted Q-iteration) for the RL problem. Hence, the decay of $Δ_\mathcal{M}(ε)$ with respect to $ε$ measures the difficulty of the RL problem on $\mathcal{M}$. We further provide some concrete examples and discuss whether $Δ_{\mathcal{M}}(ε)$ decays fast or not in these examples. As a byproduct, we show that when the reward functions lie in a high dimensional RKHS, even if the transition probability is known and the action space is finite, it is still possible for RL problems to suffer from the curse of dimensionality.
Data Selection for Efficient Model Update in Federated Learning
Venue: arXiv cs.LG 2022
Year: 2022

The Federated Learning (FL) workflow of training a centralized model with distributed data is growing in popularity. However, until recently, this was the realm of contributing clients with similar computing capability. The fast expanding IoT space and data being generated and processed at the edge are encouraging more effort into expanding federated learning to include heterogeneous systems. Previous approaches distribute light-weight models to clients are rely on knowledge transfer to distil the characteristic of local data in partitioned updates. However, their additional knowledge exchange transmitted through the network degrades the communication efficiency of FL. We propose to reduce the size of knowledge exchanged in these FL setups by clustering and selecting only the most representative bits of information from the clients. The partitioned global update adopted in our work splits the global deep neural network into a lower part for generic feature extraction and an upper part that is more sensitive to this selected client knowledge. Our experiments show that only 1.6% of the initially exchanged data can effectively transfer the characteristic of the client data to the global model in our FL approach, using split networks. These preliminary results evolve our understanding of federated learning by demonstrating efficient training using strategically selected training samples.
Asymptotically Good Quantum and Locally Testable Classical LDPC Codes
Venue: arXiv cs.IT 2022
Year: 2022

We study classical and quantum LDPC codes of constant rate obtained by the lifted product construction over non-abelian groups. We show that the obtained families of quantum LDPC codes are asymptotically good, which proves the qLDPC conjecture. Moreover, we show that the produced classical LDPC codes are also asymptotically good and locally testable with constant query and soundness parameters, which proves a well-known conjecture in the field of locally testable codes.