OpenRaiser/Intern-Atlas huggingface dataset:
Self-Directed Online Machine Learning for Topology Optimization
Venue: arXiv cs.CE 2022
Year: 2022

Topology optimization by optimally distributing materials in a given domain requires non-gradient optimizers to solve highly complicated problems. However, with hundreds of design variables or more involved, solving such problems would require millions of Finite Element Method (FEM) calculations whose computational cost is huge and impractical. Here we report Self-directed Online Learning Optimization (SOLO) which integrates Deep Neural Network (DNN) with FEM calculations. A DNN learns and substitutes the objective as a function of design variables. A small number of training data is generated dynamically based on the DNN's prediction of the optimum. The DNN adapts to the new training data and gives better prediction in the region of interest until convergence. The optimum predicted by the DNN is proved to converge to the true global optimum through iterations. Our algorithm was tested by four types of problems including compliance minimization, fluid-structure optimization, heat transfer enhancement and truss optimization. It reduced the computational time by 2 ~ 5 orders of magnitude compared with directly using heuristic methods, and outperformed all state-of-the-art algorithms tested in our experiments. This approach enables solving large multi-dimensional optimization problems.
A simple certifying algorithm for 3-edge-connectivity
Venue: arXiv cs.DS 2022
Year: 2022

A linear-time certifying algorithm for 3-edge-connectivity is presented. Given an undirected graph G, if G is 3-edge-connected, the algorithm generates a construction sequence as a positive certificate for G. Otherwise, the algorithm decomposes G into its 3-edge-connected components and at the same time generates a construction sequence for each connected component as well as the bridges and a cactus representation of the cut-pairs in G. All of these are done by making only one pass over G using an innovative graph contraction technique. Moreover, the graph need not be 2-edge-connected.
To Split or Not to Split: The Impact of Disparate Treatment in Classification
Venue: arXiv cs.LG 2022
Year: 2022

Disparate treatment occurs when a machine learning model yields different decisions for individuals based on a sensitive attribute (e.g., age, sex). In domains where prediction accuracy is paramount, it could potentially be acceptable to fit a model which exhibits disparate treatment. To evaluate the effect of disparate treatment, we compare the performance of split classifiers (i.e., classifiers trained and deployed separately on each group) with group-blind classifiers (i.e., classifiers which do not use a sensitive attribute). We introduce the benefit-of-splitting for quantifying the performance improvement by splitting classifiers. Computing the benefit-of-splitting directly from its definition could be intractable since it involves solving optimization problems over an infinite-dimensional functional space. Under different performance measures, we (i) prove an equivalent expression for the benefit-of-splitting which can be efficiently computed by solving small-scale convex programs; (ii) provide sharp upper and lower bounds for the benefit-of-splitting which reveal precise conditions where a group-blind classifier will always suffer from a non-trivial performance gap from the split classifiers. In the finite sample regime, splitting is not necessarily beneficial and we provide data-dependent bounds to understand this effect. Finally, we validate our theoretical results through numerical experiments on both synthetic and real-world datasets.
HPIM-DM: a fast and reliable dense-mode multicast routing protocol (extended version)
Venue: arXiv cs.NI 2022
Year: 2022

This paper proposes the HPIM-DM (Hard-state Protocol Independent Multicast - Dense Mode) multicast routing protocol. HPIM-DM is a hard-state version of PIM-DM that keeps its main characteristics but has faster convergence and better resilience to replay attacks. Like PIM-DM, HPIM-DM is meant for dense networks and supports its operation on a unicast routing protocol and reverse path forwarding checks. However, routers maintain sense of the multicast trees at all times, allowing fast reconfiguration in the presence of network failures or unicast route changes. This is achieved by (i) keeping information on all upstream neighbors from which multicast data can be received, (ii) ensuring the reliable transmission and sequencing of control messages, and (iii) synchronizing the routing information immediately when a new router joins the network. The protocol was fully implemented in Python, and the implementation is publicly available. Finally, the correctness of the protocol was extensively validated using model checking, logical reasoning and tests performed over the protocol implementation.
Multi-item Non-truthful Auctions Achieve Good Revenue
Venue: arXiv cs.GT 2022
Year: 2022

We present a general framework for designing approximately revenue-optimal mechanisms for multi-item additive auctions, which applies to both truthful and non-truthful auctions. Given a (not necessarily truthful) single-item auction format $A$ satisfying certain technical conditions, we run simultaneous item auctions augmented with a personalized entry fee for each bidder that must be paid before the auction can be accessed. These entry fees depend only on the prior distribution of bidder types, and in particular are independent of realized bids. We bound the revenue of the resulting two-part tariff mechanism using a novel geometric technique that enables revenue guarantees for many common non-truthful auctions that previously had none. Our approach adapts and extends the duality framework of Cai et al [CDW16] beyond truthful auctions. Our framework can be used with many common auction formats, such as simultaneous first-price, simultaneous second-price, and simultaneous all-pay auctions. Our results for first price and all-pay are the first revenue guarantees of non-truthful mechanisms in multi-dimensional environments, addressing an open question in the literature [RST17]. If all-pay auctions are used, we prove that the resulting mechanism is also credible in the sense that the auctioneer cannot benefit by deviating from the stated mechanism after observing agent bids. This is the first static credible mechanism for multi-item additive auctions that achieves a constant factor of the optimal revenue. If second-price auctions are used, we obtain a truthful $O(1)$-approximate mechanism with fixed entry fees that are amenable to tuning via online learning techniques.
Stratified Rule-Aware Network for Abstract Visual Reasoning
Venue: arXiv cs.CV 2022
Year: 2022

Abstract reasoning refers to the ability to analyze information, discover rules at an intangible level, and solve problems in innovative ways. Raven's Progressive Matrices (RPM) test is typically used to examine the capability of abstract reasoning. The subject is asked to identify the correct choice from the answer set to fill the missing panel at the bottom right of RPM (e.g., a 3$\times$3 matrix), following the underlying rules inside the matrix. Recent studies, taking advantage of Convolutional Neural Networks (CNNs), have achieved encouraging progress to accomplish the RPM test. However, they partly ignore necessary inductive biases of RPM solver, such as order sensitivity within each row/column and incremental rule induction. To address this problem, in this paper we propose a Stratified Rule-Aware Network (SRAN) to generate the rule embeddings for two input sequences. Our SRAN learns multiple granularity rule embeddings at different levels, and incrementally integrates the stratified embedding flows through a gated fusion module. With the help of embeddings, a rule similarity metric is applied to guarantee that SRAN can not only be trained using a tuplet loss but also infer the best answer efficiently. We further point out the severe defects existing in the popular RAVEN dataset for RPM test, which prevent from the fair evaluation of the abstract reasoning ability. To fix the defects, we propose an answer set generation algorithm called Attribute Bisection Tree (ABT), forming an improved dataset named Impartial-RAVEN (I-RAVEN for short). Extensive experiments are conducted on both PGM and I-RAVEN datasets, showing that our SRAN outperforms the state-of-the-art models by a considerable margin.
$π$VAE: a stochastic process prior for Bayesian deep learning with MCMC
Venue: arXiv cs.LG 2022
Year: 2022

Stochastic processes provide a mathematically elegant way model complex data. In theory, they provide flexible priors over function classes that can encode a wide range of interesting assumptions. In practice, however, efficient inference by optimisation or marginalisation is difficult, a problem further exacerbated with big data and high dimensional input spaces. We propose a novel variational autoencoder (VAE) called the prior encoding variational autoencoder ($π$VAE). The $π$VAE is finitely exchangeable and Kolmogorov consistent, and thus is a continuous stochastic process. We use $π$VAE to learn low dimensional embeddings of function classes. We show that our framework can accurately learn expressive function classes such as Gaussian processes, but also properties of functions to enable statistical inference (such as the integral of a log Gaussian process). For popular tasks, such as spatial interpolation, $π$VAE achieves state-of-the-art performance both in terms of accuracy and computational efficiency. Perhaps most usefully, we demonstrate that the low dimensional independently distributed latent space representation learnt provides an elegant and scalable means of performing Bayesian inference for stochastic processes within probabilistic programming languages such as Stan.
Hypergraph Isomorphism for Groups with Restricted Composition Factors
Venue: arXiv cs.DS 2022
Year: 2022

We consider the isomorphism problem for hypergraphs taking as input two hypergraphs over the same set of vertices $V$ and a permutation group $Γ$ over domain $V$, and asking whether there is a permutation $γ\in Γ$ that proves the two hypergraphs to be isomorphic. We show that for input groups, all of whose composition factors are isomorphic to a subgroup of the symmetric group on $d$ points, this problem can be solved in time $(n+m)^{O((\log d)^{c})}$ for some absolute constant $c$ where $n$ denotes the number of vertices and $m$ the number of hyperedges. In particular, this gives the currently fastest isomorphism test for hypergraphs in general. The previous best algorithm for this problem due to Schweitzer and Wiebking (STOC 2019) runs in time $n^{O(d)}m^{O(1)}$. As an application of this result, we obtain, for example, an algorithm testing isomorphism of graphs excluding $K_{3,h}$ ($h \geq 3$) as a minor in time $n^{O((\log h)^{c})}$. In particular, this gives an isomorphism test for graphs of Euler genus at most $g$ running in time $n^{O((\log g)^{c})}$.
A Model to Measure the Spread Power of Rumors
Venue: arXiv cs.SI 2022
Year: 2022

With technologies that have democratized the production and reproduction of information, a significant portion of daily interacted posts in social media has been infected by rumors. Despite the extensive research on rumor detection and verification, so far, the problem of calculating the spread power of rumors has not been considered. To address this research gap, the present study seeks a model to calculate the Spread Power of Rumor (SPR) as the function of content-based features in two categories: False Rumor (FR) and True Rumor (TR). For this purpose, the theory of Allport and Postman will be adopted, which it claims that importance and ambiguity are the key variables in rumor-mongering and the power of rumor. Totally 42 content features in two categories "importance" (28 features) and "ambiguity" (14 features) are introduced to compute SPR. The proposed model is evaluated on two datasets, Twitter and Telegram. The results showed that (i) the spread power of False Rumor documents is rarely more than True Rumors. (ii) there is a significant difference between the SPR means of two groups False Rumor and True Rumor. (iii) SPR as a criterion can have a positive impact on distinguishing False Rumors and True Rumors.
The Sum of Its Parts: Analysis of Federated Byzantine Agreement Systems
Venue: arXiv cs.DC 2022
Year: 2022

Federated Byzantine Agreement Systems (FBASs) are a fascinating new paradigm in the context of consensus protocols. Originally proposed for powering the Stellar payment network, FBASs can instantiate Byzantine quorum systems without requiring out-of-band agreement on a common set of validators; every node is free to decide for itself with whom it requires agreement. Sybil-resistant and yet energy-efficient consensus protocols can therefore be built upon FBASs, and the "decentrality" possible with the FBAS paradigm might be sufficient to reduce the use of environmentally unsustainable proof-of-work protocols. In this paper, we first demonstrate how the robustness of individual FBASs can be determined, by precisely determining their safety and liveness buffers and therefore enabling a comparison with threshold-based quorum systems. Using simulations and example node configuration strategies, we then empirically investigate the hypothesis that while FBASs can be bootstrapped in a bottom-up fashion from individual preferences, strategic considerations should additionally be applied by node operators in order to arrive at FBASs that are robust and amenable to monitoring. Finally, we investigate the reported "open-membership" property of FBASs. We observe that an often small group of nodes is exclusively relevant for determining liveness buffers and prove that membership in this top tier is conditional on the approval by current top tier nodes if maintaining safety is a core requirement.
CoLES: Contrastive Learning for Event Sequences with Self-Supervision
Venue: arXiv cs.LG 2022
Year: 2022

We address the problem of self-supervised learning on discrete event sequences generated by real-world users. Self-supervised learning incorporates complex information from the raw data in low-dimensional fixed-length vector representations that could be easily applied in various downstream machine learning tasks. In this paper, we propose a new method "CoLES", which adapts contrastive learning, previously used for audio and computer vision domains, to the discrete event sequences domain in a self-supervised setting. We deployed CoLES embeddings based on sequences of transactions at the large European financial services company. Usage of CoLES embeddings significantly improves the performance of the pre-existing models on downstream tasks and produces significant financial gains, measured in hundreds of millions of dollars yearly. We also evaluated CoLES on several public event sequences datasets and showed that CoLES representations consistently outperform other methods on different downstream tasks.
On the Decision Boundaries of Neural Networks: A Tropical Geometry Perspective
Venue: arXiv cs.LG 2022
Year: 2022

This work tackles the problem of characterizing and understanding the decision boundaries of neural networks with piecewise linear non-linearity activations. We use tropical geometry, a new development in the area of algebraic geometry, to characterize the decision boundaries of a simple network of the form (Affine, ReLU, Affine). Our main finding is that the decision boundaries are a subset of a tropical hypersurface, which is intimately related to a polytope formed by the convex hull of two zonotopes. The generators of these zonotopes are functions of the network parameters. This geometric characterization provides new perspectives to three tasks. (i) We propose a new tropical perspective to the lottery ticket hypothesis, where we view the effect of different initializations on the tropical geometric representation of a network's decision boundaries. (ii) Moreover, we propose new tropical based optimization reformulations that directly influence the decision boundaries of the network for the task of network pruning. (iii) At last, we discuss the reformulation of the generation of adversarial attacks in a tropical sense. We demonstrate that one can construct adversaries in a new tropical setting by perturbing a specific set of decision boundaries by perturbing a set of parameters in the network.
Taurus: A Data Plane Architecture for Per-Packet ML
Venue: arXiv cs.NI 2022
Year: 2022

Emerging applications -- cloud computing, the internet of things, and augmented/virtual reality -- demand responsive, secure, and scalable datacenter networks. These networks currently implement simple, per-packet, data-plane heuristics (e.g., ECMP and sketches) under a slow, millisecond-latency control plane that runs data-driven performance and security policies. However, to meet applications' service-level objectives (SLOs) in a modern data center, networks must bridge the gap between line-rate, per-packet execution and complex decision making. In this work, we present the design and implementation of Taurus, a data plane for line-rate inference. Taurus adds custom hardware based on a flexible, parallel-patterns (MapReduce) abstraction to programmable network devices, such as switches and NICs; this new hardware uses pipelined SIMD parallelism to enable per-packet MapReduce operations (e.g., inference). Our evaluation of a Taurus switch ASIC -- supporting several real-world models -- shows that Taurus operates orders of magnitude faster than a server-based control plane while increasing area by 3.8% and latency for line-rate ML models by up to 221 ns. Furthermore, our Taurus FPGA prototype achieves full model accuracy and detects two orders of magnitude more events than a state-of-the-art control-plane anomaly-detection system.
A Hardware Architecture for Reconfigurable Intelligent Surfaces with Minimal Active Elements for Explicit Channel Estimation
Venue: arXiv cs.IT 2022
Year: 2022

Intelligent surfaces comprising of cost effective, nearly passive, and reconfigurable unit elements are lately gaining increasing interest due to their potential in enabling fully programmable wireless environments. They are envisioned to offer environmental intelligence for diverse communication objectives, when coated on various objects of the deployment area of interest. To achieve this overarching goal, the channels where the Reconfigurable Intelligent Surfaces (RISs) are involved need to be in principle estimated. However, this is a challenging task with the currently available hardware RIS architectures requiring lengthy training periods among the network nodes utilizing RIS-assisted wireless communication. In this paper, we present a novel RIS architecture comprising of any number of passive reflecting elements, a simple controller for their adjustable configuration, and a single Radio Frequency (RF) chain for baseband measurements. Capitalizing on this architecture and assuming sparse wireless channels in the beamspace domain, we present an alternating optimization approach for explicit estimation of the channel gains at the RIS elements attached to the single RF chain. Representative simulation results demonstrate the channel estimation accuracy and achievable end-to-end performance for various training lengths and numbers of reflecting unit elements.
Learning in Markov Decision Processes under Constraints
Venue: arXiv cs.LG 2022
Year: 2022

We consider reinforcement learning (RL) in Markov Decision Processes in which an agent repeatedly interacts with an environment that is modeled by a controlled Markov process. At each time step $t$, it earns a reward, and also incurs a cost-vector consisting of $M$ costs. We design model-based RL algorithms that maximize the cumulative reward earned over a time horizon of $T$ time-steps, while simultaneously ensuring that the average values of the $M$ cost expenditures are bounded by agent-specified thresholds $c^{ub}_i,i=1,2,\ldots,M$. In order to measure the performance of a reinforcement learning algorithm that satisfies the average cost constraints, we define an $M+1$ dimensional regret vector that is composed of its reward regret, and $M$ cost regrets. The reward regret measures the sub-optimality in the cumulative reward, while the $i$-th component of the cost regret vector is the difference between its $i$-th cumulative cost expense and the expected cost expenditures $Tc^{ub}_i$. We prove that the expected value of the regret vector of UCRL-CMDP, is upper-bounded as $\tilde{O}\left(T^{2\slash 3}\right)$, where $T$ is the time horizon. We further show how to reduce the regret of a desired subset of the $M$ costs, at the expense of increasing the regrets of rewards and the remaining costs. To the best of our knowledge, ours is the only work that considers non-episodic RL under average cost constraints, and derive algorithms that can~\emph{tune the regret vector} according to the agent's requirements on its cost regrets.
Time Series Data Augmentation for Deep Learning: A Survey
Venue: arXiv cs.LG 2022
Year: 2022

Deep learning performs remarkably well on many time series analysis tasks recently. The superior performance of deep neural networks relies heavily on a large number of training data to avoid overfitting. However, the labeled data of many real-world time series applications may be limited such as classification in medical time series and anomaly detection in AIOps. As an effective way to enhance the size and quality of the training data, data augmentation is crucial to the successful application of deep learning models on time series data. In this paper, we systematically review different data augmentation methods for time series. We propose a taxonomy for the reviewed methods, and then provide a structured review for these methods by highlighting their strengths and limitations. We also empirically compare different data augmentation methods for different tasks including time series classification, anomaly detection, and forecasting. Finally, we discuss and highlight five future directions to provide useful research guidance.
On the Hardness of the Lee Syndrome Decoding Problem
Venue: arXiv cs.IT 2022
Year: 2022

In this paper we study the hardness of the syndrome decoding problem over finite rings endowed with the Lee metric. We first prove that the decisional version of the problem is NP-complete, by a reduction from the $3$-dimensional matching problem. Then, we study the complexity of solving the problem, by translating the best known solvers in the Hamming metric over finite fields to the Lee metric over finite rings, as well as proposing some novel solutions. For the analyzed algorithms, we assess the computational complexity in the asymptotic regime and compare it to the corresponding algorithms in the Hamming metric.