OpenRaiser/Intern-Atlas huggingface dataset:
Building Efficient CNNs Using Depthwise Convolutional Eigen-Filters (DeCEF)
Venue: arXiv cs.LG 2022
Year: 2022

Deep Convolutional Neural Networks (CNNs) have been widely used in various domains due to their impressive capabilities. These models are typically composed of a large number of 2D convolutional (Conv2D) layers with numerous trainable parameters. To reduce the complexity of a network, compression techniques can be applied. These methods typically rely on the analysis of trained deep learning models. However, in some applications, due to reasons such as particular data or system specifications and licensing restrictions, a pre-trained network may not be available. This would require the user to train a CNN from scratch. In this paper, we aim to find an alternative parameterization to Conv2D filters without relying on a pre-trained convolutional network. During the analysis, we observe that the effective rank of the vectorized Conv2D filters decreases with respect to the increasing depth in the network, which then leads to the implementation of the Depthwise Convolutional Eigen-Filter (DeCEF) layer. Essentially, a DeCEF layer is a low rank version of the Conv2D layer with significantly fewer trainable parameters and floating point operations (FLOPs). The way we define the effective rank is different from the previous work and it is easy to implement in any deep learning frameworks. To evaluate the effectiveness of DeCEF, experiments are conducted on the benchmark datasets CIFAR-10 and ImageNet using various network architectures. The results have shown a similar or higher accuracy and robustness using about 2/3 of the original parameters and reducing the number of FLOPs to 2/3 of the base network, which is then compared to the state-of-the-art techniques.
Clock Tree Generation by Abutment in Synchoros VLSI Design
Venue: arXiv cs.AR 2022
Year: 2022

Synchoros VLSI design style has been proposed as an alternative to standard cell-based design. Standard cells are replaced by synchoros, large grain, VLSI design objects called SiLago (Silicon Lego) blocks. This new design style eliminates the need to synthesise ad hoc wires of any type: functional and infrastructural. SiLago blocks are organised into region instances. In a region instance, communication among SiLago blocks is synchronous and happens over a regional network on chip (NoC), whose fragments are also absorbed into SiLago blocks. Consequently, the regional NoCs get created by the abutment of SiLago blocks. The clock tree used in a region is called regional clock tree (RCT). The synchoros VLSI design style requires that the RCT, like the regional NoCs, is also created by abutting its fragments. The RCT fragments are absorbed within the SiLago blocks. The RCT created by abutment is not an ad-hoc clock tree but a structured and predictable design with known cost metrics. The design of such an RCT is the focus of this paper. The scheme is scalable, and we demonstrate that the proposed RCT can be generated for valid VLSI designs of ~1.5 million gates. The RCT created by abutment is correct by construction, and its properties are predictable. We have validated the generated RCTs with static timing analysis to validate the correct-by-construction claim. Finally, we show that the cost metrics of the SiLago RCT
Optimal Bound on the Combinatorial Complexity of Approximating Polytopes
Venue: arXiv cs.CG 2022
Year: 2022

This paper considers the question of how to succinctly approximate a multidimensional convex body by a polytope. Given a convex body $K$ of unit diameter in Euclidean $d$-dimensional space (where $d$ is a constant) and an error parameter $\varepsilon > 0$, the objective is to determine a convex polytope of low combinatorial complexity whose Hausdorff distance from $K$ is at most $\varepsilon$. By combinatorial complexity we mean the total number of faces of all dimensions. Classical constructions by Dudley and Bronshteyn/Ivanov show that $O(1/\varepsilon^{(d-1)/2})$ facets or vertices are possible, respectively, but neither achieves both bounds simultaneously. In this paper, we show that it is possible to construct a polytope with $O(1/\varepsilon^{(d-1)/2})$ combinatorial complexity, which is optimal in the worst case. Our result is based on a new relationship between $\varepsilon$-width caps of a convex body and its polar body. Using this relationship, we are able to obtain a volume-sensitive bound on the number of approximating caps that are "essentially different." We achieve our main result by combining this with a variant of the witness-collector method and a novel variable-thickness layered construction of the economical cap covering.
Persistent Homology as Stopping-Criterion for Voronoi Interpolation
Venue: arXiv cs.CG 2022
Year: 2022

In this study the Voronoi interpolation is used to interpolate a set of points drawn from a topological space with higher homology groups on its filtration. The technique is based on Voronoi tessellation, which induces a natural dual map to the Delaunay triangulation. Advantage is taken from this fact calculating the persistent homology on it after each iteration to capture the changing topology of the data. The boundary points are identified as critical. The Bottleneck and Wasserstein distance serve as a measure of quality between the original point set and the interpolation. If the norm of two distances exceeds a heuristically determined threshold, the algorithm terminates. We give the theoretical basis for this approach and justify its validity with numerical experiments.
Bunch theory: working notes on applications, axioms and models
Venue: arXiv cs.LO 2022
Year: 2022

In his book A Practical Theory of Programming, Eric Hehner proposes and applies a remarkably radical reformulation of set theory, in which the collection and packaging of elements are seen as separate activities. This provides for unpackaged collections, referred to as bunches. Bunches allow us to reason about non-determinism at the level of terms, and, very remarkably, allow us to reason about the conceptual entity nothing, which is just an empty bunch (and very different from an empty set). This eliminates mathematical gaps caused by undefined terms. We compare the use of bunches with other approaches to this problem, and we illustrate the use of Bunch Theory in formulating program semantics combining non-deterministic, preferential, and probabilistic choice to provide a guarded command language whose exceptional expressivity we illustrate with a short case study. We show how an existing axiomatisation of set theory can be extended to incorporate bunches, and we provide and validate a model.
On the Maximum Number of Non-Confusable Strings Evolving Under Short Tandem Duplications
Venue: arXiv cs.IT 2022
Year: 2022

The set of all $ q $-ary strings that do not contain repeated substrings of length $ \leqslant\! 3 $ (i.e., that do not contain substrings of the form $ a a $, $ a b a b $, and $ a b c a b c $) constitutes a code correcting an arbitrary number of tandem-duplication mutations of length $ \leqslant\! 3 $. In other words, any two such strings are non-confusable in the sense that they cannot produce the same string while evolving under tandem duplications of length $ \leqslant\! 3 $. We demonstrate that this code is asymptotically optimal in terms of rate, meaning that it represents the largest set of non-confusable strings up to subexponential factors. This result settles the zero-error capacity problem for the last remaining case of tandem-duplication channels satisfying the "root-uniqueness" property.
Adaptive Greedy versus Non-adaptive Greedy for Influence Maximization
Venue: arXiv cs.SI 2022
Year: 2022

We consider the *adaptive influence maximization problem*: given a network and a budget $k$, iteratively select $k$ seeds in the network to maximize the expected number of adopters. In the *full-adoption feedback model*, after selecting each seed, the seed-picker observes all the resulting adoptions. In the *myopic feedback model*, the seed-picker only observes whether each neighbor of the chosen seed adopts. Motivated by the extreme success of greedy-based algorithms/heuristics for influence maximization, we propose the concept of *greedy adaptivity gap*, which compares the performance of the adaptive greedy algorithm to its non-adaptive counterpart. Our first result shows that, for submodular influence maximization, the adaptive greedy algorithm can perform up to a $(1-1/e)$-fraction worse than the non-adaptive greedy algorithm, and that this ratio is tight. More specifically, on one side we provide examples where the performance of the adaptive greedy algorithm is only a $(1-1/e)$ fraction of the performance of the non-adaptive greedy algorithm in four settings: for both feedback models and both the *independent cascade model* and the *linear threshold model*. On the other side, we prove that in any submodular cascade, the adaptive greedy algorithm always outputs a $(1-1/e)$-approximation to the expected number of adoptions in the optimal non-adaptive seed choice. Our second result shows that, for the general submodular diffusion model with full-adoption feedback, the adaptive greedy algorithm can outperform the non-adaptive greedy algorithm by an unbounded factor. Finally, we propose a risk-free variant of the adaptive greedy algorithm that always performs no worse than the non-adaptive greedy algorithm.
Learning Hierarchy-Aware Knowledge Graph Embeddings for Link Prediction
Venue: arXiv cs.LG 2022
Year: 2022

Knowledge graph embedding, which aims to represent entities and relations as low dimensional vectors (or matrices, tensors, etc.), has been shown to be a powerful technique for predicting missing links in knowledge graphs. Existing knowledge graph embedding models mainly focus on modeling relation patterns such as symmetry/antisymmetry, inversion, and composition. However, many existing approaches fail to model semantic hierarchies, which are common in real-world applications. To address this challenge, we propose a novel knowledge graph embedding model -- namely, Hierarchy-Aware Knowledge Graph Embedding (HAKE) -- which maps entities into the polar coordinate system. HAKE is inspired by the fact that concentric circles in the polar coordinate system can naturally reflect the hierarchy. Specifically, the radial coordinate aims to model entities at different levels of the hierarchy, and entities with smaller radii are expected to be at higher levels; the angular coordinate aims to distinguish entities at the same level of the hierarchy, and these entities are expected to have roughly the same radii but different angles. Experiments demonstrate that HAKE can effectively model the semantic hierarchies in knowledge graphs, and significantly outperforms existing state-of-the-art methods on benchmark datasets for the link prediction task.
Financial Event Extraction Using Wikipedia-Based Weak Supervision
Venue: arXiv cs.CL 2022
Year: 2022

Extraction of financial and economic events from text has previously been done mostly using rule-based methods, with more recent works employing machine learning techniques. This work is in line with this latter approach, leveraging relevant Wikipedia sections to extract weak labels for sentences describing economic events. Whereas previous weakly supervised approaches required a knowledge-base of such events, or corresponding financial figures, our approach requires no such additional data, and can be employed to extract economic events related to companies which are not even mentioned in the training data.
Contextual Combinatorial Conservative Bandits
Venue: arXiv cs.LG 2022
Year: 2022

The problem of multi-armed bandits (MAB) asks to make sequential decisions while balancing between exploitation and exploration, and have been successfully applied to a wide range of practical scenarios. Various algorithms have been designed to achieve a high reward in a long term. However, its short-term performance might be rather low, which is injurious in risk sensitive applications. Building on previous work of conservative bandits, we bring up a framework of contextual combinatorial conservative bandits. An algorithm is presented and a regret bound of $\tilde O(d^2+d\sqrt{T})$ is proven, where $d$ is the dimension of the feature vectors, and $T$ is the total number of time steps. We further provide an algorithm as well as regret analysis for the case when the conservative reward is unknown. Experiments are conducted, and the results validate the effectiveness of our algorithm.
Proportionality and the Limits of Welfarism
Venue: arXiv cs.GT 2022
Year: 2022

We study two influential voting rules proposed in the 1890s by Phragmén and Thiele, which elect a committee or parliament of k candidates which proportionally represents the voters. Voters provide their preferences by approving an arbitrary number of candidates. Previous work has proposed proportionality axioms satisfied by Thiele's rule (now known as Proportional Approval Voting, PAV) but not by Phragmén's rule. By proposing two new proportionality axioms (laminar proportionality and priceability) satisfied by Phragmén but not Thiele, we show that the two rules achieve two distinct forms of proportional representation. Phragmén's rule ensures that all voters have a similar amount of influence on the committee, and Thiele's rule ensures a fair utility distribution. Thiele's rule is a welfarist voting rule (one that maximizes a function of voter utilities). We show that no welfarist rule can satisfy our new axioms, and we prove that no such rule can satisfy the core. Conversely, some welfarist fairness properties cannot be guaranteed by Phragmén-type rules. This formalizes the difference between the two types of proportionality. We then introduce an attractive committee rule, the Method of Equal Shares, which satisfies a property intermediate between the core and extended justified representation (EJR). It satisfies laminar proportionality, priceability, and is computable in polynomial time. We show that our new rule provides a logarithmic approximation to the core. On the other hand, PAV provides a factor-2 approximation to the core, and this factor is optimal for rules that are fair in the sense of the Pigou--Dalton principle.
Age of Information in Random Access Channels
Venue: arXiv cs.NI 2022
Year: 2022

In applications of remote sensing, estimation, and control, timely communication is not always ensured by high-rate communication. This work proposes distributed age-efficient transmission policies for random access channels with $M$ transmitters. In the first part of this work, we analyze the age performance of stationary randomized policies by relating the problem of finding age to the absorption time of a related Markov chain. In the second part of this work, we propose the notion of \emph{age-gain} of a packet to quantify how much the packet will reduce the instantaneous age of information at the receiver side upon successful delivery. We then utilize this notion to propose a transmission policy in which transmitters act in a distributed manner based on the age-gain of their available packets. In particular, each transmitter sends its latest packet only if its corresponding age-gain is beyond a certain threshold which could be computed adaptively using the collision feedback or found as a fixed value analytically in advance. Both methods improve age of information significantly compared to the state of the art. In the limit of large $M$, we prove that when the arrival rate is small (below $\frac{1}{eM}$), slotted ALOHA-type algorithms are asymptotically optimal. As the arrival rate increases beyond $\frac{1}{eM}$, while age increases under slotted ALOHA, it decreases significantly under the proposed age-based policies. For arrival rates $θ$, $θ=\frac{1}{o(M)}$, the proposed algorithms provide a multiplicative factor of at least two compared to the minimum age under slotted ALOHA (minimum over all arrival rates). We conclude that, as opposed to the common practice, it is beneficial to increase the sampling rate (and hence the arrival rate) and transmit packets selectively based on their age-gain.
Sometimes Reliable Spanners of Almost Linear Size
Venue: arXiv cs.CG 2022
Year: 2022

Reliable spanners can withstand huge failures, even when a linear number of vertices are deleted from the network. In case of failures, a reliable spanner may have some additional vertices for which the spanner property no longer holds, but this collateral damage is bounded by a fraction of the size of the attack. It is known that $Ω(n\log n)$ edges are needed to achieve this strong property, where $n$ is the number of vertices in the network, even in one dimension. Constructions of reliable geometric $(1+\varepsilon)$-spanners, for $n$ points in $\Re^d$, are known, where the resulting graph has $O( n \log n \log \log^{6}n )$ edges. Here, we show randomized constructions of smaller size spanners that have the desired reliability property in expectation or with good probability. The new construction is simple, and potentially practical -- replacing a hierarchical usage of expanders (which renders the previous constructions impractical) by a simple skip-list like construction. This results in a $1$-spanner, on the line, that has linear number of edges. Using this, we present a construction of a reliable spanner in $\Re^d$ with $O( n \log \log^{2} n \log \log \log n )$ edges.
Scalable Group Secret Key Generation over Wireless Channels
Venue: arXiv cs.CR 2022
Year: 2022

In this paper, we consider the problem of secret key generation for multiple parties. Multi-user networks usually require a trusted party to efficiently distribute keys to the legitimate users and this process is a weakness against eavesdroppers. With the help of the physical layer security techniques, users can securely decide on a secret key without a trusted party by exploiting the unique properties of the channel. In this context, we develop a physical layer group key generation scheme that is also based on the ideas of the analog function computation studies. We firstly consider the key generation as a function to be computed over the wireless channel and propose two novel methods depending on the users transmission capability (i.e. half-duplex and full-duplex transmissions). Secondly, we exploit the uniqueness of the prime integers in order to enable the simultaneous transmission of the users for key generation. As a result, our approach contributes to the scalability of the existing physical layer key generation algorithms since all users transmit simultaneously rather than using pairwise communications. We prove that our half-duplex network model reduces the required number of communications for group key generation down to a linear scale. Furthermore, the full-duplex network model reduces to a constant scale.
Putting Ridesharing to the Test: Efficient and Scalable Solutions and the Power of Dynamic Vehicle Relocation
Venue: arXiv cs.MA 2022
Year: 2022

We study the optimization of large-scale, real-time ridesharing systems and propose a modular design methodology, Component Algorithms for Ridesharing (CAR). We evaluate a diverse set of CARs (14 in total), focusing on the key algorithmic components of ridesharing. We take a multi-objective approach, evaluating 12 metrics related to global efficiency, complexity, passenger, driver, and platform incentives, in settings designed to closely resemble reality in every aspect, focusing on vehicles of capacity two. To the best of our knowledge, this is the largest and most comprehensive evaluation to date. We (i) identify CARs that perform well on global, passenger, driver or platform metrics, (ii) demonstrate that lightweight relocation schemes can significantly improve the Quality of Service by up to $50\%$, and (iii) highlight a practical, scalable, on-device CAR that works well across all metrics.
Waiting but not Aging: Optimizing Information Freshness Under the Pull Model
Venue: arXiv cs.NI 2022
Year: 2022

The Age-of-Information is an important metric for investigating the timeliness performance in information-update systems. In this paper, we study the AoI minimization problem under a new Pull model with replication schemes, where a user proactively sends a replicated request to multiple servers to "pull" the information of interest. Interestingly, we find that under this new Pull model, replication schemes capture a novel tradeoff between different values of the AoI across the servers (due to the random updating processes) and different response times across the servers, which can be exploited to minimize the expected AoI at the user's side. Specifically, assuming Poisson updating process for the servers and exponentially distributed response time, we derive a closed-form formula for computing the expected AoI and obtain the optimal number of responses to wait for to minimize the expected AoI. Then, we extend our analysis to the setting where the user aims to maximize the AoI-based utility, which represents the user's satisfaction level with respect to the freshness of the received information. Furthermore, we consider a more realistic scenario where the user has no prior knowledge of the system. In this case, we reformulate the utility maximization problem as a stochastic Multi-Armed Bandit problem with side observations and leverage a special linear structure of side observations to design learning algorithms with improved performance guarantees. Finally, we conduct extensive simulations to elucidate our theoretical results and compare the performance of different algorithms. Our findings reveal that under the Pull model, waiting does not necessarily lead to aging; waiting for more than one response can often significantly reduce the AoI and improve the AoI-based utility in most scenarios.
Adaptive Granularity in Tensors: A Quest for Interpretable Structure
Venue: arXiv cs.LG 2022
Year: 2022

Data collected at very frequent intervals is usually extremely sparse and has no structure that is exploitable by modern tensor decomposition algorithms. Thus the utility of such tensors is low, in terms of the amount of interpretable and exploitable structure that one can extract from them. In this paper, we introduce the problem of finding a tensor of adaptive aggregated granularity that can be decomposed to reveal meaningful latent concepts (structures) from datasets that, in their original form, are not amenable to tensor analysis. Such datasets fall under the broad category of sparse point processes that evolve over space and/or time. To the best of our knowledge, this is the first work that explores adaptive granularity aggregation in tensors. Furthermore, we formally define the problem and discuss what different definitions of "good structure" can be in practice, and show that optimal solution is of prohibitive combinatorial complexity. Subsequently, we propose an efficient and effective greedy algorithm called IceBreaker, which follows a number of intuitive decision criteria that locally maximize the "goodness of structure", resulting in high-quality tensors. We evaluate our method on synthetic, semi-synthetic and real datasets. In all the cases, our proposed method constructs tensors that have very high structure quality.