OpenRaiser/Intern-Atlas huggingface dataset:
Expander Decomposition and Pruning: Faster, Stronger, and Simpler
Venue: arXiv cs.DS 2021
Year: 2021

We study the problem of graph clustering where the goal is to partition a graph into clusters, i.e. disjoint subsets of vertices, such that each cluster is well connected internally while sparsely connected to the rest of the graph. In particular, we use a natural bicriteria notion motivated by Kannan, Vempala, and Vetta which we refer to as {\em expander decomposition}. Expander decomposition has become one of the building blocks in the design of fast graph algorithms, most notably in the nearly linear time Laplacian solver by Spielman and Teng, and it also has wide applications in practice. We design algorithm for the parametrized version of expander decomposition, where given a graph $G$ of $m$ edges and a parameter $ϕ$, our algorithm finds a partition of the vertices into clusters such that each cluster induces a subgraph of conductance at least $ϕ$ (i.e. a $ϕ$ expander), and only a $\widetilde{O}(ϕ)$ fraction of the edges in $G$ have endpoints across different clusters. Our algorithm runs in $\widetilde{O}(m/ϕ)$ time, and is the first nearly linear time algorithm when $ϕ$ is at least $1/\log^{O(1)} m$, which is the case in most practical settings and theoretical applications. Previous results either take $Ω(m^{1+o(1)})$ time, or attain nearly linear time but with a weaker expansion guarantee where each output cluster is guaranteed to be contained inside some unknown $ϕ$ expander. Our result achieve both nearly linear running time and the strong expander guarantee for clusters. Moreover, a main technique we develop for our result can be applied to obtain a much better \emph{expander pruning} algorithm, which is the key tool for maintaining an expander decomposition on dynamic graphs. Finally, we note that our algorithm is developed from first principles based on relatively simple and basic techniques, thus making it very likely to be practical.
GM-PHD Filter for Searching and Tracking an Unknown Number of Targets with a Mobile Sensor with Limited FOV
Venue: arXiv cs.RO 2021
Year: 2021

We study the problem of searching for and tracking a collection of moving targets using a robot with a limited Field-Of-View (FOV) sensor. The actual number of targets present in the environment is not known a priori. We propose a search and tracking framework based on the concept of Bayesian Random Finite Sets (RFSs). Specifically, we generalize the Gaussian Mixture Probability Hypothesis Density (GM-PHD) filter which was previously applied for tracking problems to allow for simultaneous search and tracking with a limited FOV sensor. The proposed framework can extract individual target tracks as well as estimate the number and the spatial density of targets. We also show how to use the Gaussian Process (GP) regression to extract and predict non-linear target trajectories in this framework. We demonstrate the efficacy of our techniques through representative simulations and a real data collected from an aerial robot.
CodedSketch: A Coding Scheme for Distributed Computation of Approximated Matrix Multiplication
Venue: arXiv cs.IT 2021
Year: 2021

In this paper, we propose CodedSketch, as a distributed straggler-resistant scheme to compute an approximation of the multiplication of two massive matrices. The objective is to reduce the recovery threshold, defined as the total number of worker nodes that we need to wait for to be able to recover the final result. To exploit the fact that only an approximated result is required, in reducing the recovery threshold, some sorts of pre-compression are required. However, compression inherently involves some randomness that would lose the structure of the matrices. On the other hand, considering the structure of the matrices is crucial to reduce the recovery threshold. In CodedSketch, we use count--sketch, as a hash-based compression scheme, on the rows of the first and columns of the second matrix, and a structured polynomial code on the columns of the first and rows of the second matrix. This arrangement allows us to exploit the gain of both in reducing the recovery threshold. To increase the accuracy of computation, multiple independent count--sketches are needed. This independency allows us to theoretically characterize the accuracy of the result and establish the recovery threshold achieved by the proposed scheme. To guarantee the independency of resulting count--sketches in the output, while keeping its cost on the recovery threshold minimum, we use another layer of structured codes.
On the Benefit of Width for Neural Networks: Disappearance of Bad Basins
Venue: arXiv cs.LG 2021
Year: 2021

Wide networks are often believed to have a nice optimization landscape, but what rigorous results can we prove? To understand the benefit of width, it is important to identify the difference between wide and narrow networks. In this work, we prove that from narrow to wide networks, there is a phase transition from having sub-optimal basins to no sub-optimal basins. Specifically, we prove two results: on the positive side, for any continuous activation functions, the loss surface of a class of wide networks has no sub-optimal basins, where "basin" is defined as the set-wise strict local minimum; on the negative side, for a large class of networks with width below a threshold, we construct strict local minima that are not global. These two results together show the phase transition from narrow to wide networks.
Approximate Nearest Neighbors in the Space of Persistence Diagrams
Venue: arXiv cs.CG 2021
Year: 2021

Persistence diagrams are important tools in the field of topological data analysis that describe the presence and magnitude of features in a filtered topological space. However, current approaches for comparing a persistence diagram to a set of other persistence diagrams is linear in the number of diagrams or do not offer performance guarantees. In this paper, we apply concepts from locality-sensitive hashing to support approximate nearest neighbor search in the space of persistence diagrams. Given a set $Γ$ of $n$ $(M,m)$-bounded persistence diagrams, each with at most $m$ points, we snap-round the points of each diagram to points on a cubical lattice and produce a key for each possible snap-rounding. Specifically, we fix a grid over each diagram at several resolutions and consider the snap-roundings of each diagram to the four nearest lattice points. Then, we propose a data structure with $τ$ levels $\mathbb{D}_τ$ that stores all snap-roundings of each persistence diagram in $Γ$ at each resolution. This data structure has size $O(n5^mτ)$ to account for varying lattice resolutions as well as snap-roundings and the deletion of points with low persistence. To search for a persistence diagram, we compute a key for a query diagram by snapping each point to a lattice and deleting points of low persistence. Furthermore, as the lattice parameter decreases, searching our data structure yields a six-approximation of the nearest diagram in $Γ$ in $O((m\log{n}+m^2)\logτ)$ time and a constant factor approximation of the $k$th nearest diagram in $O((m\log{n}+m^2+k)\logτ)$ time.
Dynamic and Application-Aware Provisioning of Chained Virtual Security Network Functions
Venue: arXiv cs.NI 2021
Year: 2021

A promising area of application for Network Function Virtualization is in network security, where chains of Virtual Security Network Functions (VSNFs), i.e., security-specific virtual functions such as firewalls or Intrusion Prevention Systems, can be dynamically created and configured to inspect, filter or monitor the network traffic. However, the traffic handled by VSNFs could be sensitive to specific network requirements, such as minimum bandwidth or maximum end-to-end latency. Therefore, the decision on which VSNFs should apply for a given application, where to place them and how to connect them, should take such requirements into consideration. Otherwise, security services could affect the quality of service experienced by customers. In this paper we propose PESS (Progressive Embedding of Security Services), a solution to efficiently deploy chains of virtualised security functions based on the security requirements of individual applications and operators' policies, while optimizing resource utilization. We provide the PESS mathematical model and heuristic solution. Simulation results show that, compared to state-of-the-art application-agnostic VSNF provisioning models, PESS reduces computational resource utilization by up to 50%, in different network scenarios. This result ultimately leads to a higher number of provisioned security services and to up to a 40% reduction in end-to-end latency of application traffic.
On Coded Caching with Correlated Files
Venue: arXiv cs.IT 2021
Year: 2021

This paper studies the fundamental limits of the shared-link coded caching problem with correlated files, where a server with a library of $N$ files communicates with $K$ users who can locally cache $M$ files. Given an integer $r \in [N]$, correlation is modeled as follows: each r-subset of files contains a unique common block. The tradeoff between the cache size and the average transmitted load is considered. First, a converse bound under the constraint of uncoded cache placement (i.e., each user directly stores a subset of the library bits) is derived. Then, a caching scheme for the case where every user demands a distinct file (possible for $N \geq K$) is shown to be optimal under the constraint of uncoded cache placement. This caching scheme is further proved to be decodable and optimal under the constraint of uncoded cache placement when (i) $KrM \leq 2N$ or $KrM \geq (K - 1)N $or $r \in \{1,2,N- 1,N\}$ for every demand type (i.e., when the demanded file are not necessarily distinct), and (ii) when the number of distinct demanded files is no larger than four. Finally, a two-phase delivery scheme based on interference alignment is shown to be optimal to within a factor of 2 under the constraint of uncoded cache placement for every possible demands. As a by-product, the proposed interference alignment scheme is shown to reduce the (worst-case or average) load of state-of-the-art schemes for the coded caching problem where the users can request multiple files.
On Efficient Optimal Transport: An Analysis of Greedy and Accelerated Mirror Descent Algorithms
Venue: arXiv cs.DS 2021
Year: 2021

We provide theoretical analyses for two algorithms that solve the regularized optimal transport (OT) problem between two discrete probability measures with at most $n$ atoms. We show that a greedy variant of the classical Sinkhorn algorithm, known as the \emph{Greenkhorn algorithm}, can be improved to $\widetilde{\mathcal{O}}(n^2\varepsilon^{-2})$, improving on the best known complexity bound of $\widetilde{\mathcal{O}}(n^2\varepsilon^{-3})$. Notably, this matches the best known complexity bound for the Sinkhorn algorithm and helps explain why the Greenkhorn algorithm can outperform the Sinkhorn algorithm in practice. Our proof technique, which is based on a primal-dual formulation and a novel upper bound for the dual solution, also leads to a new class of algorithms that we refer to as \emph{adaptive primal-dual accelerated mirror descent} (APDAMD) algorithms. We prove that the complexity of these algorithms is $\widetilde{\mathcal{O}}(n^2\sqrtδ\varepsilon^{-1})$, where $δ> 0$ refers to the inverse of the strong convexity module of Bregman divergence with respect to $\|\cdot\|_\infty$. This implies that the APDAMD algorithm is faster than the Sinkhorn and Greenkhorn algorithms in terms of $\varepsilon$. Experimental results on synthetic and real datasets demonstrate the favorable performance of the Greenkhorn and APDAMD algorithms in practice.
CAMR: Coded Aggregated MapReduce
Venue: arXiv cs.DC 2021
Year: 2021

Many big data algorithms executed on MapReduce-like systems have a shuffle phase that often dominates the overall job execution time. Recent work has demonstrated schemes where the communication load in the shuffle phase can be traded off for the computation load in the map phase. In this work, we focus on a class of distributed algorithms, broadly used in deep learning, where intermediate computations of the same task can be combined. Even though prior techniques reduce the communication load significantly, they require a number of jobs that grows exponentially in the system parameters. This limitation is crucial and may diminish the load gains as the algorithm scales. We propose a new scheme which achieves the same load as the state-of-the-art while ensuring that the number of jobs as well as the number of subfiles that the data set needs to be split into remain small.
Double-Auction Mechanisms for Resource Trading Markets
Venue: arXiv cs.NI 2021
Year: 2021

We consider a double-auction mechanism, which was recently proposed in the context of rate allocation in mobile data-offloading markets. Network operators (users) derive benefit from offloading their traffic to third party WiFi or femtocell networks (link-suppliers). Link-suppliers experience costs for the additional capacity that they provide. Users and link-suppliers (collectively referred to as agents) have their pay-offs and cost functions as private knowledge. A network-manager decomposes the problem into a network problem and agent problems. The surrogate pay-offs and cost functions are modulated by the agents' bids. Agents' payoffs and costs are then determined by the allocations and prices set by the network-manager. Under this design, so long as the agents do not anticipate the effect of their actions on the prices set by the network-manager (i.e., price-taking agents), a competitive equilibrium exists as a solution to the network and agent problems, and this equilibrium optimizes the sum utility of all agents. However, this design fails when the agents are all strategic (price-anticipating). Specifically, the presence of a strategic link-supplier drives the system to an undesirable equilibrium with zero participation resulting in an efficiency loss of 100%. This is in stark contrast to an earlier setting where the users alone are strategic but the link-supplier is not - the efficiency loss is known to be at most 34%. The paper then proposes a Stackelberg game modification where the efficiency loss can be characterized in terms of the link-supplier's cost function when the users' pay-off functions are linear. Specifically, when the link-supplier's cost function is quadratic, the worst case efficiency loss is 25%. Further, the loss in efficiency improves for polynomial cost functions of higher degree.
Capacity Optimality of AMP in Coded Systems
Venue: arXiv cs.IT 2021
Year: 2021

This paper studies a large random matrix system (LRMS) model involving an arbitrary signal distribution and forward error control (FEC) coding. We establish an area property based on the so-called Turbo approximate message passing (Turbo-AMP) algorithm. Under the assumption that the state evolution for AMP is correct for the coded system, the achievable rate of Turbo-AMP is analyzed. We prove that Turbo-AMP achieves the constraint capacity of the LRMS with an arbitrary signal distribution provided that a matching condition is satisfied. As a byproduct, we provide an alternative derivation for the constraint capacity of an LRMS using a proved property of AMP. We discuss realization techniques for the matching principle of binary signaling using irregular low-density parity-check (LDPC) codes and provide related numerical results. We show that optimized codes demonstrate significantly better performance over un-matched ones under Turbo-AMP. For quadrature phase shift keying (QPSK) modulation, bit error rate (BER) performance within 1 dB from the constrained capacity limit is observed.
Leveraging Outdoor Webcams for Local Descriptor Learning
Venue: arXiv cs.CV 2021
Year: 2021

We present AMOS Patches, a large set of image cut-outs, intended primarily for the robustification of trainable local feature descriptors to illumination and appearance changes. Images contributing to AMOS Patches originate from the AMOS dataset of recordings from a large set of outdoor webcams. The semiautomatic method used to generate AMOS Patches is described. It includes camera selection, viewpoint clustering and patch selection. For training, we provide both the registered full source images as well as the patches. A new descriptor, trained on the AMOS Patches and 6Brown datasets, is introduced. It achieves state-of-the-art in matching under illumination changes on standard benchmarks.
Reconstruction of 3D Porous Media From 2D Slices
Venue: arXiv cs.CV 2021
Year: 2021

In many branches of earth sciences, the problem of rock study on the micro-level arises. However, a significant number of representative samples is not always feasible. Thus the problem of the generation of samples with similar properties becomes actual. In this paper, we propose a novel deep learning architecture for three-dimensional porous media reconstruction from two-dimensional slices. We fit a distribution on all possible three-dimensional structures of a specific type based on the given dataset of samples. Then, given partial information (central slices), we recover the three-dimensional structure around such slices as the most probable one according to that constructed distribution. Technically, we implement this in the form of a deep neural network with encoder, generator and discriminator modules. Numerical experiments show that this method provides a good reconstruction in terms of Minkowski functionals.
Generalized Dirichlet-process-means for $f$-separable distortion measures
Venue: arXiv cs.LG 2021
Year: 2021

DP-means clustering was obtained as an extension of $K$-means clustering. While it is implemented with a simple and efficient algorithm, it can estimate the number of clusters simultaneously. However, DP-means is specifically designed for the average distortion measure. Therefore, it is vulnerable to outliers in data, and can cause large maximum distortion in clusters. In this work, we extend the objective function of the DP-means to $f$-separable distortion measures and propose a unified learning algorithm to overcome the above problems by selecting the function $f$. Further, the influence function of the estimated cluster center is analyzed to evaluate the robustness against outliers. We demonstrate the performance of the generalized method by numerical experiments using real datasets.
OODIDA: On-board/Off-board Distributed Real-Time Data Analytics for Connected Vehicles
Venue: arXiv cs.PL 2021
Year: 2021

A fleet of connected vehicles easily produces many gigabytes of data per hour, making centralized (off-board) data processing impractical. In addition, there is the issue of distributing tasks to on-board units in vehicles and processing them efficiently. Our solution to this problem is OODIDA (On-board/Off-board Distributed Data Analytics), which is a platform that tackles both task distribution to connected vehicles as well as concurrent execution of tasks on arbitrary subsets of edge clients. Its message-passing infrastructure has been implemented in Erlang/OTP, while the end points use a language-independent JSON interface. Computations can be carried out in arbitrary programming languages. The message-passing infrastructure of OODIDA is highly scalable, facilitating the execution of large numbers of concurrent tasks.
Exact Markov Chain-based Runtime Analysis of a Discrete Particle Swarm Optimization Algorithm on Sorting and OneMax
Venue: arXiv cs.DM 2021
Year: 2021

Meta-heuristics are powerful tools for solving optimization problems whose structural properties are unknown or cannot be exploited algorithmically. We propose such a meta-heuristic for a large class of optimization problems over discrete domains based on the particle swarm optimization (PSO) paradigm. We provide a comprehensive formal analysis of the performance of this algorithm on certain "easy" reference problems in a black-box setting, namely the sorting problem and the problem OneMax. In our analysis we use a Markov model of the proposed algorithm to obtain upper and lower bounds on its expected optimization time. Our bounds are essentially tight with respect to the Markov model. We show that for a suitable choice of algorithm parameters the expected optimization time is comparable to that of known algorithms and, furthermore, for other parameter regimes, the algorithm behaves less greedy and more explorative, which can be desirable in practice in order to escape local optima. Our analysis provides a precise insight on the tradeoff between optimization time and exploration. To obtain our results we introduce the notion of indistinguishability of states of a Markov chain and provide bounds on the solution of a recurrence equation with non-constant coefficients by integration.
Attention in Natural Language Processing
Venue: arXiv cs.CL 2021
Year: 2021

Attention is an increasingly popular mechanism used in a wide range of neural architectures. The mechanism itself has been realized in a variety of formats. However, because of the fast-paced advances in this domain, a systematic overview of attention is still missing. In this article, we define a unified model for attention architectures in natural language processing, with a focus on those designed to work with vector representations of the textual data. We propose a taxonomy of attention models according to four dimensions: the representation of the input, the compatibility function, the distribution function, and the multiplicity of the input and/or output. We present the examples of how prior information can be exploited in attention models and discuss ongoing research efforts and open challenges in the area, providing the first extensive categorization of the vast body of literature in this exciting domain.
Sampling and Remote Estimation for the Ornstein-Uhlenbeck Process through Queues: Age of Information and Beyond
Venue: arXiv cs.IT 2021
Year: 2021

The age of information, as a metric for evaluating information freshness, has received a lot of attention. Recently, an interesting connection between the age of information and remote estimation error was found in a sampling problem of Wiener processes: If the sampler has no knowledge of the signal being sampled, the optimal sampling strategy is to minimize the age of information; however, by exploiting causal knowledge of the signal values, it is possible to achieve a smaller estimation error. In this paper, we extend a previous study by investigating a problem of sampling a stationary Gauss-Markov process, namely the Ornstein-Uhlenbeck (OU) process. The optimal sampling problem is formulated as a constrained continuous-time Markov decision process (MDP) with an uncountable state space. We provide an exact solution to this MDP: The optimal sampling policy is a threshold policy on instantaneous estimation error and the threshold is found. Further, if the sampler has no knowledge of the OU process, the optimal sampling problem reduces to an MDP for minimizing a nonlinear age of information metric. The age-optimal sampling policy is a threshold policy on expected estimation error and the threshold is found. These results hold for (i) general service time distributions of the queueing server and (ii) sampling problems both with and without a sampling rate constraint. Numerical results are provided to compare different sampling policies.