OpenRaiser/Intern-Atlas huggingface dataset:
Defending Against Saddle Point Attack in Byzantine-Robust Distributed Learning
Venue: arXiv cs.LG 2020
Year: 2020

We study robust distributed learning that involves minimizing a non-convex loss function with saddle points. We consider the Byzantine setting where some worker machines have abnormal or even arbitrary and adversarial behavior. In this setting, the Byzantine machines may create fake local minima near a saddle point that is far away from any true local minimum, even when robust gradient estimators are used. We develop ByzantinePGD, a robust first-order algorithm that can provably escape saddle points and fake local minima, and converge to an approximate true local minimizer with low iteration complexity. As a by-product, we give a simpler algorithm and analysis for escaping saddle points in the usual non-Byzantine setting. We further discuss three robust gradient estimators that can be used in ByzantinePGD, including median, trimmed mean, and iterative filtering. We characterize their performance in concrete statistical settings, and argue for their near-optimality in low and high dimensional regimes.
Real-time Monocular Visual Odometry for Turbid and Dynamic Underwater Environments
Venue: arXiv cs.RO 2020
Year: 2020

In the context of robotic underwater operations, the visual degradations induced by the medium properties make difficult the exclusive use of cameras for localization purpose. Hence, most localization methods are based on expensive navigational sensors associated with acoustic positioning. On the other hand, visual odometry and visual SLAM have been exhaustively studied for aerial or terrestrial applications, but state-of-the-art algorithms fail underwater. In this paper we tackle the problem of using a simple low-cost camera for underwater localization and propose a new monocular visual odometry method dedicated to the underwater environment. We evaluate different tracking methods and show that optical flow based tracking is more suited to underwater images than classical approaches based on descriptors. We also propose a keyframe-based visual odometry approach highly relying on nonlinear optimization. The proposed algorithm has been assessed on both simulated and real underwater datasets and outperforms state-of-the-art visual SLAM methods under many of the most challenging conditions. The main application of this work is the localization of Remotely Operated Vehicles (ROVs) used for underwater archaeological missions but the developed system can be used in any other applications as long as visual information is available.
Cliques and a new measure of clustering: with application to U.S. domestic airlines
Venue: arXiv cs.SI 2020
Year: 2020

We propose a higher-order generalization of the well-known overall clustering coefficient for triples $C(3)$ to any number of nodes. We give analytic formulae for the special cases of three, four, and five nodes and show that they have very fast runtime performance for small graphs. We discuss some theoretical properties and limitations of the new measure, and use it to provide insight into dynamic changes in the structure of U.S. airline networks.
An asynchronous and task-based implementation of Peridynamics utilizing HPX -- the C++ standard library for parallelism and concurrency
Venue: arXiv cs.DC 2020
Year: 2020

On modern supercomputers, asynchronous many task systems are emerging to address the new architecture of computational nodes. Through this shift of increasing cores per node, a new programming model with the focus on handle the fine-grain parallelism of this increasing amount of cores per computational node is needed. Asynchronous Many Task (AMT) run time systems represent an emerging paradigm for addressing fine-grain parallelism since they handle the increasing amount of threads per node and concurrency. HPX, a open source C++ standard library for parallelism and concurrency, is one AMT which is confirm with the C++ standard. Which means that HPX's Application Programming Interface (API) is confirm with its definition by the C++ standard committee. For example for the concept of futurization the hpx:future can be replaced by std::future without breaking the API. Peridynamics is a non-local generalization of continuum mechanics tailored to address discontinuous displacement fields arising in fracture mechanics. As many non-local approaches, peridynamics requires considerable computing resources to solve practical problems. This paper investigates the implementation of a peridynamics EMU nodal discretization in an asynchronous task-based fashion. The scalability of asynchronous task-based implementation is to be in agreement with theoretical estimations. In addition, to the scalabilty the code is convergent for implicit time integration and recovers theoretical solutions. Explicit time integration, convergence results are presented to showcase the agreement of results with theoretical claims in previous works.
Storage, Computation, and Communication: A Fundamental Tradeoff in Distributed Computing
Venue: arXiv cs.IT 2020
Year: 2020

We consider a MapReduce-like distributed computing system. We derive a lower bound on the communication cost for any given storage and computation costs. This lower bound matches the achievable bound we proposed recently. As a result, we completely characterize the optimal tradeoff between the storage, the computation, and the communication. Our result generalizes the previous one by Li et al. to also account for the number of computed intermediate values.
Neural Tangent Kernel: Convergence and Generalization in Neural Networks
Venue: arXiv cs.LG 2020
Year: 2020

At initialization, artificial neural networks (ANNs) are equivalent to Gaussian processes in the infinite-width limit, thus connecting them to kernel methods. We prove that the evolution of an ANN during training can also be described by a kernel: during gradient descent on the parameters of an ANN, the network function $f_θ$ (which maps input vectors to output vectors) follows the kernel gradient of the functional cost (which is convex, in contrast to the parameter cost) w.r.t. a new kernel: the Neural Tangent Kernel (NTK). This kernel is central to describe the generalization features of ANNs. While the NTK is random at initialization and varies during training, in the infinite-width limit it converges to an explicit limiting kernel and it stays constant during training. This makes it possible to study the training of ANNs in function space instead of parameter space. Convergence of the training can then be related to the positive-definiteness of the limiting NTK. We prove the positive-definiteness of the limiting NTK when the data is supported on the sphere and the non-linearity is non-polynomial. We then focus on the setting of least-squares regression and show that in the infinite-width limit, the network function $f_θ$ follows a linear differential equation during training. The convergence is fastest along the largest kernel principal components of the input data with respect to the NTK, hence suggesting a theoretical motivation for early stopping. Finally we study the NTK numerically, observe its behavior for wide networks, and compare it to the infinite-width limit.
Multimodal feature fusion for CNN-based gait recognition: an empirical comparison
Venue: arXiv cs.CV 2020
Year: 2020

People identification in video based on the way they walk (i.e. gait) is a relevant task in computer vision using a non-invasive approach. Standard and current approaches typically derive gait signatures from sequences of binary energy maps of subjects extracted from images, but this process introduces a large amount of non-stationary noise, thus, conditioning their efficacy. In contrast, in this paper we focus on the raw pixels, or simple functions derived from them, letting advanced learning techniques to extract relevant features. Therefore, we present a comparative study of different Convolutional Neural Network (CNN) architectures by using three different modalities (i.e. gray pixels, optical flow channels and depth maps) on two widely-adopted and challenging datasets: TUM-GAID and CASIA-B. In addition, we perform a comparative study between different early and late fusion methods used to combine the information obtained from each kind of modalities. Our experimental results suggest that (i) the raw pixel values represent a competitive input modality, compared to the traditional state-of-the-art silhouette-based features (e.g. GEI), since equivalent or better results are obtained; (ii) the fusion of the raw pixel information with information from optical flow and depth maps allows to obtain state-of-the-art results on the gait recognition task with an image resolution several times smaller than the previously reported results; and, (iii) the selection and the design of the CNN architecture are critical points that can make a difference between state-of-the-art results or poor ones.
Full Coded Caching Gains for Cache-less Users
Venue: arXiv cs.IT 2020
Year: 2020

Within the context of coded caching, the work reveals the interesting connection between having multiple transmitters and having heterogeneity in the cache sizes of the receivers. Our work effectively shows that having multiple transmit antennas -- while providing full multiplexing gains -- can also simultaneously completely remove the performance penalties that are typically associated to cache-size unevenness. Focusing on the multiple-input single-output Broadcast Channel, the work first identifies the performance limits of the extreme case where cache-aided users coincide with users that do not have caches, and then expands the analysis to the case where both user groups are cache-aided but with heterogeneous cache-sizes. In the first case, the main contribution is a new algorithm that employs perfect matchings on a bipartite graph to offer full multiplexing as well as full coded-caching gains to both cache-aided as well as cache-less users. An interesting conclusion is that, starting from a single-stream centralized coded caching setting with normalized cache size $γ$, then adding $L$ antennas allows for the addition of {up to} approximately $L/γ$ extra cache-less users, at no added delay costs. Similarly surprising is the finding that, {beginning} with a single-antenna hybrid system (with both cache-less and cache-aided users), then adding {$L-1$} antennas to the transmitter, as well as endowing the cache-less users with a cumulative normalized cache size $Γ_2$, increases the Degrees of Freedom by a \emph{multiplicative} factor of up to $Γ_{2}+L$.
On $r$-Simple $k$-Path and Related Problems Parameterized by $k/r$
Venue: arXiv cs.DS 2020
Year: 2020

Abasi et al. (2014) and Gabizon et al. (2015) studied the following problems. In the $r$-Simple $k$-Path problem, given a digraph $G$ on $n$ vertices and integers $r,k$, decide whether $G$ has an $r$-simple $k$-path, which is a walk where every vertex occurs at most $r$ times and the total number of vertex occurrences is $k$. In the $(r,k)$-Monomial Detection problem, given an arithmetic circuit that encodes some polynomial $P$ on $n$ variables and integers $k,r$, decide whether $P$ has a monomial of degree $k$ where the degree of each variable is at most~$r$. In the $p$-Set $(r,q)$-Packing problem, given a universe $V$, positive integers $p,q,r$, and a collection $\cal H$ of sets of size $p$ whose elements belong to $V$, decide whether there exists a subcollection ${\cal H}'$ of $\cal H$ of size $q$ where each element occurs in at most $r$ sets of ${\cal H}'$. Abasi et al. and Gabizon et al. proved that the three problems are single-exponentially fixed-parameter tractable (FPT) when parameterized by $(k/r)\log r$, where $k=pq$ for $p$-Set $(r,q)$-Packing and asked whether the $\log r$ factor in the exponent can be avoided. We consider their question from a wider perspective: are the above problems FPT when parameterized by $k/r$ only? We resolve the wider question by (a) obtaining a $2^{O((k/r)^2\log(k/r))} (n+\log k)^{O(1)}$-time algorithm for $r$-Simple $k$-Path on digraphs and a $2^{O(k/r)} (n+\log k)^{O(1)}$-time algorithm for $r$-Simple $k$-Path on undirected graphs (i.e., for undirected graphs we answer the original question in affirmative), (b) showing that $p$-Set $(r,q)$-Packing is FPT, and (c) proving that $(r,k)$-Monomial Detection is para-NP-hard. For $p$-Set $(r,q)$-Packing, we obtain a polynomial kernel for any fixed $p$, which resolves a question posed by Gabizon et al. regarding the existence of polynomial kernels for problems with relaxed disjointness constraints.
Fusion of complex networks and randomized neural networks for texture analysis
Venue: arXiv cs.CV 2020
Year: 2020

This paper presents a high discriminative texture analysis method based on the fusion of complex networks and randomized neural networks. In this approach, the input image is modeled as a complex networks and its topological properties as well as the image pixels are used to train randomized neural networks in order to create a signature that represents the deep characteristics of the texture. The results obtained surpassed the accuracies of many methods available in the literature. This performance demonstrates that our proposed approach opens a promising source of research, which consists of exploring the synergy of neural networks and complex networks in the texture analysis field.
Privacy-Cost Trade-offs in Smart Electricity Metering Systems
Venue: arXiv cs.IT 2020
Year: 2020

Trade-offs between privacy and cost are studied for a smart grid consumer, whose electricity consumption is monitored in almost real time by the utility provider (UP) through smart meter (SM) readings. It is assumed that an electrical battery is available to the consumer, which can be utilized both to achieve privacy and to reduce the energy cost by demand shaping. Privacy is measured via the mean squared distance between the SM readings and a target load profile, while time-of-use (ToU) pricing is considered to compute the cost incurred. The consumer can also sell electricity back to the UP to further improve the privacy-cost trade-off. Two privacy-preserving energy management policies (EMPs) are proposed, which differ in the way the target load profile is characterized. A more practical EMP, which optimizes the energy management less frequently, is also considered. Numerical results are presented to compare the privacy-cost trade-off of these EMPs, considering various privacy indicators.
Multi-Mapping Image-to-Image Translation with Central Biasing Normalization
Venue: arXiv cs.CV 2020
Year: 2020

Recent advances in image-to-image translation have seen a rise in approaches generating diverse images through a single network. To indicate the target domain for a one-to-many mapping, the latent code is injected into the generator network. However, we found that the injection method leads to mode collapse because of normalization strategies. Existing normalization strategies might either cause the inconsistency of feature distribution or eliminate the effect of the latent code. To solve these problems, we propose the consistency within diversity criteria for designing the multi-mapping model. Based on the criteria, we propose central biasing normalization to inject the latent code information. Experiments show that our method can improve the quality and diversity of existing image-to-image translation models, such as StarGAN, BicycleGAN, and pix2pix.
Complying with Data Handling Requirements in Cloud Storage Systems
Venue: arXiv cs.NI 2020
Year: 2020

In past years, cloud storage systems saw an enormous rise in usage. However, despite their popularity and importance as underlying infrastructure for more complex cloud services, today's cloud storage systems do not account for compliance with regulatory, organizational, or contractual data handling requirements by design. Since legislation increasingly responds to rising data protection and privacy concerns, complying with data handling requirements becomes a crucial property for cloud storage systems. We present PRADA, a practical approach to account for compliance with data handling requirements in key-value based cloud storage systems. To achieve this goal, PRADA introduces a transparent data handling layer, which empowers clients to request specific data handling requirements and enables operators of cloud storage systems to comply with them. We implement PRADA on top of the distributed database Cassandra and show in our evaluation that complying with data handling requirements in cloud storage systems is practical in real-world cloud deployments as used for microblogging, data sharing in the Internet of Things, and distributed email storage.
Using Reinforcement Learning with Partial Vehicle Detection for Intelligent Traffic Signal Control
Venue: arXiv cs.AI 2020
Year: 2020

Intelligent Transportation Systems (ITS) have attracted the attention of researchers and the general public alike as a means to alleviate traffic congestion. Recently, the maturity of wireless technology has enabled a cost-efficient way to achieve ITS by detecting vehicles using Vehicle to Infrastructure (V2I) communications. Traditional ITS algorithms, in most cases, assume that every vehicle is observed, such as by a camera or a loop detector, but a V2I implementation would detect only those vehicles with wireless communications capability. We examine a family of transportation systems, which we will refer to as `Partially Detected Intelligent Transportation Systems'. An algorithm that can act well under a small detection rate is highly desirable due to gradual penetration rates of the underlying wireless technologies such as Dedicated Short Range Communications (DSRC) technology. Artificial Intelligence (AI) techniques for Reinforcement Learning (RL) are suitable tools for finding such an algorithm due to utilizing varied inputs and not requiring explicit analytic understanding or modeling of the underlying system dynamics. In this paper, we report a RL algorithm for partially observable ITS based on DSRC. The performance of this system is studied under different car flows, detection rates, and topologies of the road network. Our system is able to efficiently reduce the average waiting time of vehicles at an intersection, even with a low detection rate.
Subgraphs and motifs in a dynamic airline network
Venue: arXiv cs.SI 2020
Year: 2020

How does the small-scale topological structure of an airline network behave as the network evolves? To address this question, we study the dynamic properties of small undirected subgraphs using 15 years of data on Southwest Airlines' domestic route service. We use exact enumeration formulae to identify statistically over- and under-represented subgraphs, known as motifs and anti-motifs. We discover substantial topology transitions in Southwest's network and provide evidence for time-varying power-law scaling between subgraph counts and the number of edges in the network. We also suggest a node-ranking measure that can identify important nodes relative to specific local topologies. Our results extend the toolkit of subgraph-based methods and provide new insight into transportation networks and the strategic behaviour of firms.
Hierarchical stochastic graphlet embedding for graph-based pattern recognition
Venue: arXiv cs.CV 2020
Year: 2020

Despite being very successful within the pattern recognition and machine learning community, graph-based methods are often unusable because of the lack of mathematical operations defined in graph domain. Graph embedding, which maps graphs to a vectorial space, has been proposed as a way to tackle these difficulties enabling the use of standard machine learning techniques. However, it is well known that graph embedding functions usually suffer from the loss of structural information. In this paper, we consider the hierarchical structure of a graph as a way to mitigate this loss of information. The hierarchical structure is constructed by topologically clustering the graph nodes, and considering each cluster as a node in the upper hierarchical level. Once this hierarchical structure is constructed, we consider several configurations to define the mapping into a vector space given a classical graph embedding, in particular, we propose to make use of the Stochastic Graphlet Embedding (SGE). Broadly speaking, SGE produces a distribution of uniformly sampled low to high order graphlets as a way to embed graphs into the vector space. In what follows, the coarse-to-fine structure of a graph hierarchy and the statistics fetched by the SGE complements each other and includes important structural information with varied contexts. Altogether, these two techniques substantially cope with the usual information loss involved in graph embedding techniques, obtaining a more robust graph representation. This fact has been corroborated through a detailed experimental evaluation on various benchmark graph datasets, where we outperform the state-of-the-art methods.
Multi-kernel unmixing and super-resolution using the Modified Matrix Pencil method
Venue: arXiv cs.IT 2020
Year: 2020

Consider $L$ groups of point sources or spike trains, with the $l^{\text{th}}$ group represented by $x_l(t)$. For a function $g:\mathbb{R} \rightarrow \mathbb{R}$, let $g_l(t) = g(t/μ_l)$ denote a point spread function with scale $μ_l > 0$, and with $μ_1 < \cdots < μ_L$. With $y(t) = \sum_{l=1}^{L} (g_l \star x_l)(t)$, our goal is to recover the source parameters given samples of $y$, or given the Fourier samples of $y$. This problem is a generalization of the usual super-resolution setup wherein $L = 1$; we call this the multi-kernel unmixing super-resolution problem. Assuming access to Fourier samples of $y$, we derive an algorithm for this problem for estimating the source parameters of each group, along with precise non-asymptotic guarantees. Our approach involves estimating the group parameters sequentially in the order of increasing scale parameters, i.e., from group $1$ to $L$. In particular, the estimation process at stage $1 \leq l \leq L$ involves (i) carefully sampling the tail of the Fourier transform of $y$, (ii) a \emph{deflation} step wherein we subtract the contribution of the groups processed thus far from the obtained Fourier samples, and (iii) applying Moitra's modified Matrix Pencil method on a deconvolved version of the samples in (ii).
On the Fundamental Limits of Coded Data Shuffling for Distributed Machine Learning
Venue: arXiv cs.IT 2020
Year: 2020

We consider the data shuffling problem in a distributed learning system, in which a master node is connected to a set of worker nodes, via a shared link, in order to communicate a set of files to the worker nodes. The master node has access to a database of files. In every shuffling iteration, each worker node processes a new subset of files, and has excess storage to partially cache the remaining files, assuming the cached files are uncoded. The caches of the worker nodes are updated every iteration, and they should be designed to satisfy any possible unknown permutation of the files in subsequent iterations. For this problem, we characterize the exact load-memory trade-off for worst-case shuffling by deriving the minimum communication load for a given storage capacity per worker node. As a byproduct, the exact load-memory trade-off for any shuffling is characterized when the number of files is equal to the number of worker nodes. We propose a novel deterministic coded shuffling scheme, which improves the state of the art, by exploiting the cache memories to create coded functions that can be decoded by several worker nodes. Then, we prove the optimality of our proposed scheme by deriving a matching lower bound and showing that the placement phase of the proposed coded shuffling scheme is optimal over all shuffles.