OpenRaiser/Intern-Atlas huggingface dataset:
Tropes in films: an initial analysis
Venue: arXiv cs.DL 2021
Year: 2021

TVTropes is a wiki that describes tropes and which ones are used in which artistic work. We are mostly interested in films, so after releasing the TropeScraper Python module that extracts data from this site, in this report we use scraped information to describe statistically how tropes and films are related to each other and how these relations evolve in time. In order to do so, we generated a dataset through the tool TropeScraper in April 2020. We have compared it to the latest snapshot of DB Tropes, a dataset covering the same site and published in July 2016, providing descriptive analysis, studying the fundamental differences and addressing the evolution of the wiki in terms of the number of tropes, the number of films and connections. The results show that the number of tropes and films doubled their value and quadrupled their relations, and films are, at large, better described in terms of tropes. However, while the types of films with the most tropes has not changed significantly in years, the list of most popular tropes has. This outcome can help on shedding some light on how popular tropes evolve, which ones become more popular or fade away, and in general how a set of tropes represents a film and might be a key to its success. The dataset generated, the information extracted, and the summaries provided are useful resources for any research involving films and tropes. They can provide proper context and explanations about the behaviour of models built on top of the dataset, including the generation of new content or its use in machine learning.
Privacy For Free: Wireless Federated Learning Via Uncoded Transmission With Adaptive Power Control
Venue: arXiv cs.IT 2021
Year: 2021

Federated Learning (FL) refers to distributed protocols that avoid direct raw data exchange among the participating devices while training for a common learning task. This way, FL can potentially reduce the information on the local data sets that is leaked via communications. In order to provide formal privacy guarantees, however, it is generally necessary to put in place additional masking mechanisms. When FL is implemented in wireless systems via uncoded transmission, the channel noise can directly act as a privacy-inducing mechanism. This paper demonstrates that, as long as the privacy constraint level, measured via differential privacy (DP), is below a threshold that decreases with the signal-to-noise ratio (SNR), uncoded transmission achieves privacy "for free", i.e., without affecting the learning performance. More generally, this work studies adaptive power allocation (PA) for decentralized gradient descent in wireless FL with the aim of minimizing the learning optimality gap under privacy and power constraints. Both orthogonal multiple access (OMA) and non-orthogonal multiple access (NOMA) transmission with "over-the-air-computing" are studied, and solutions are obtained in closed form for an offline optimization setting. Furthermore, heuristic online methods are proposed that leverage iterative one-step-ahead optimization. The importance of dynamic PA and the potential benefits of NOMA versus OMA are demonstrated through extensive simulations.
The Max k-Cut Game: On Stable Optimal Colorings
Venue: arXiv cs.GT 2021
Year: 2021

We study the max k-cut game on an undirected and unweighted graph in order to find out whether an optimal solution is also a strong equilibrium. While we do fail to show that, by proving an alternate formula for computing the cut value difference for a strong deviation, we show that optimal solutions are 7-stable equilibria. Furthermore, we prove some properties of minimal subsets with respect to a strong deviation, showing that each of their nodes will deviate towards the color of one of their neighbors and that those subsets induce connected subgraphs.
Locally Private Graph Neural Networks
Venue: arXiv cs.LG 2021
Year: 2021

Graph Neural Networks (GNNs) have demonstrated superior performance in learning node representations for various graph inference tasks. However, learning over graph data can raise privacy concerns when nodes represent people or human-related variables that involve sensitive or personal information. While numerous techniques have been proposed for privacy-preserving deep learning over non-relational data, there is less work addressing the privacy issues pertained to applying deep learning algorithms on graphs. In this paper, we study the problem of node data privacy, where graph nodes have potentially sensitive data that is kept private, but they could be beneficial for a central server for training a GNN over the graph. To address this problem, we develop a privacy-preserving, architecture-agnostic GNN learning algorithm with formal privacy guarantees based on Local Differential Privacy (LDP). Specifically, we propose an LDP encoder and an unbiased rectifier, by which the server can communicate with the graph nodes to privately collect their data and approximate the GNN's first layer. To further reduce the effect of the injected noise, we propose to prepend a simple graph convolution layer, called KProp, which is based on the multi-hop aggregation of the nodes' features acting as a denoising mechanism. Finally, we propose a robust training framework, in which we benefit from KProp's denoising capability to increase the accuracy of inference in the presence of noisy labels. Extensive experiments conducted over real-world datasets demonstrate that our method can maintain a satisfying level of accuracy with low privacy loss.
Improved Analysis for Dynamic Regret of Strongly Convex and Smooth Functions
Venue: arXiv cs.LG 2021
Year: 2021

In this paper, we present an improved analysis for dynamic regret of strongly convex and smooth functions. Specifically, we investigate the Online Multiple Gradient Descent (OMGD) algorithm proposed by Zhang et al. (2017). The original analysis shows that the dynamic regret of OMGD is at most $\mathcal{O}(\min\{\mathcal{P}_T,\mathcal{S}_T\})$, where $\mathcal{P}_T$ and $\mathcal{S}_T$ are path-length and squared path-length that measures the cumulative movement of minimizers of the online functions. We demonstrate that by an improved analysis, the dynamic regret of OMGD can be improved to $\mathcal{O}(\min\{\mathcal{P}_T,\mathcal{S}_T,\mathcal{V}_T\})$, where $\mathcal{V}_T$ is the function variation of the online functions. Note that the quantities of $\mathcal{P}_T, \mathcal{S}_T, \mathcal{V}_T$ essentially reflect different aspects of environmental non-stationarity -- they are not comparable in general and are favored in different scenarios. Therefore, the dynamic regret presented in this paper actually achieves a \emph{best-of-three-worlds} guarantee and is strictly tighter than previous results.
A Probabilistic Model for Discriminative and Neuro-Symbolic Semi-Supervised Learning
Venue: arXiv cs.LG 2021
Year: 2021

Much progress has been made in semi-supervised learning (SSL) by combining methods that exploit different aspects of the data distribution, e.g. consistency regularisation relies on properties of $p(x)$, whereas entropy minimisation pertains to the label distribution $p(y|x)$. Focusing on the latter, we present a probabilistic model for discriminative SSL, that mirrors its classical generative counterpart. Under the assumption $y|x$ is deterministic, the prior over latent variables becomes discrete. We show that several well-known SSL methods can be interpreted as approximating this prior, and can be improved upon. We extend the discriminative model to neuro-symbolic SSL, where label features satisfy logical rules, by showing such rules relate directly to the above prior, thus justifying a family of methods that link statistical learning and logical reasoning, and unifying them with regular SSL.
Quantum Channel State Masking
Venue: arXiv cs.IT 2021
Year: 2021

Communication over a quantum channel that depends on a quantum state is considered when the encoder has channel side information (CSI) and is required to mask information on the quantum channel state from the decoder. A full characterization is established for the entanglement-assisted masking equivocation region, and a regularized formula is given for the quantum capacity-leakage function without assistance. For Hadamard channels without assistance, we derive single-letter inner and outer bounds, which coincide in the standard case of a channel that does not depend on a state.
When is Particle Filtering Efficient for Planning in Partially Observed Linear Dynamical Systems?
Venue: arXiv cs.LG 2021
Year: 2021

Particle filtering is a popular method for inferring latent states in stochastic dynamical systems, whose theoretical properties have been well studied in machine learning and statistics communities. In many control problems, e.g., partially observed linear dynamical systems (POLDS), oftentimes the inferred latent state is further used for planning at each step. This paper initiates a rigorous study on the efficiency of particle filtering for sequential planning, and gives the first particle complexity bounds. Though errors in past actions may affect the future, we are able to bound the number of particles needed so that the long-run reward of the policy based on particle filtering is close to that based on exact inference. In particular, we show that, in stable systems, polynomially many particles suffice. Key in our proof is a coupling of the ideal sequence based on the exact planning and the sequence generated by approximate planning based on particle filtering. We believe this technique can be useful in other sequential decision-making problems.
Revisiting visual-inertial structure from motion for odometry and SLAM initialization
Venue: arXiv cs.CV 2021
Year: 2021

In this paper, an efficient closed-form solution for the state initialization in visual-inertial odometry (VIO) and simultaneous localization and mapping (SLAM) is presented. Unlike the state-of-the-art, we do not derive linear equations from triangulating pairs of point observations. Instead, we build on a direct triangulation of the unknown $3D$ point paired with each of its observations. We show and validate the high impact of such a simple difference. The resulting linear system has a simpler structure and the solution through analytic elimination only requires solving a $6\times 6$ linear system (or $9 \times 9$ when accelerometer bias is included). In addition, all the observations of every scene point are jointly related, thereby leading to a less biased and more robust solution. The proposed formulation attains up to $50$ percent decreased velocity and point reconstruction error compared to the standard closed-form solver, while it is $4\times$ faster for a $7$-frame set. Apart from the inherent efficiency, fewer iterations are needed by any further non-linear refinement thanks to better parameter initialization. In this context, we provide the analytic Jacobians for a non-linear optimizer that optionally refines the initial parameters. The superior performance of the proposed solver is established by quantitative comparisons with the state-of-the-art solver.
Empirical Time Complexity of Generic Dijkstra Algorithm
Venue: arXiv cs.NI 2021
Year: 2021

Generic Dijkstra is a novel algorithm for finding the optimal shortest path in both wavelength-division multiplexed networks (WDM) and elastic optical networks (EON), claimed to outperform known algorithms considerably. Because of its novelty, it has not been independently implemented and verified. Its time complexity also remains unknown. In this paper, we perform run-time analysis and show that Generic Dijkstra running time grows quadratically with the number of graph vertices and logarithmically with the number of edge units. We also discover that the running time of the Generic Dijkstra algorithm in the function of network utilization is not monotonic, as peak running time is at approximately 0.25 network utilization. Additionally, we provide an independent open source implementation of Generic Dijkstra in the Python language. We confirm the correctness of the algorithm and its superior performance. In comparison to the Filtered Graphs algorithm, Generic Dijkstra is approximately 2.3 times faster in networks with 25 to 500 nodes, and in 90% of calls its computation takes less time.
Sample-Efficient Low Rank Phase Retrieval
Venue: arXiv cs.IT 2021
Year: 2021

This work studies the Low Rank Phase Retrieval (LRPR) problem: recover an $n \times q$ rank-$r$ matrix $X^*$ from $y_k = |A_k^\top x^*_k|$, $k=1, 2,..., q$, when each $y_k$ is an m-length vector containing independent phaseless linear projections of $x^*_k$. The different matrices $A_k$ are i.i.d. and each contains i.i.d. standard Gaussian entries. We obtain an improved guarantee for AltMinLowRaP, which is an Alternating Minimization solution to LRPR that was introduced and studied in our recent work. As long as the right singular vectors of $X^*$ satisfy the incoherence assumption, we can show that the AltMinLowRaP estimate converges geometrically to $X^*$ if the total number of measurements $mq \gtrsim nr^2 (r + \log(1/ε))$. In addition, we also need $m \gtrsim max(r, \log q, \log n)$ because of the specific asymmetric nature of our problem. Compared to our recent work, we improve the sample complexity of the AltMin iterations by a factor of $r^2$, and that of the initialization by a factor of $r$. We also extend our result to the noisy case; we prove stability to corruption by small additive noise.
EMOGI: Efficient Memory-access for Out-of-memory Graph-traversal In GPUs
Venue: arXiv cs.DC 2021
Year: 2021

Modern analytics and recommendation systems are increasingly based on graph data that capture the relations between entities being analyzed. Practical graphs come in huge sizes, offer massive parallelism, and are stored in sparse-matrix formats such as CSR. To exploit the massive parallelism, developers are increasingly interested in using GPUs for graph traversal. However, due to their sizes, graphs often do not fit into the GPU memory. Prior works have either used input data pre-processing/partitioning or UVM to migrate chunks of data from the host memory to the GPU memory. However, the large, multi-dimensional, and sparse nature of graph data presents a major challenge to these schemes and results in significant amplification of data movement and reduced effective data throughput. In this work, we propose EMOGI, an alternative approach to traverse graphs that do not fit in GPU memory using direct cacheline-sized access to data stored in host memory. This paper addresses the open question of whether a sufficiently large number of overlapping cacheline-sized accesses can be sustained to 1) tolerate the long latency to host memory, 2) fully utilize the available bandwidth, and 3) achieve favorable execution performance. We analyze the data access patterns of several graph traversal applications in GPU over PCIe using an FPGA to understand the cause of poor external bandwidth utilization. By carefully coalescing and aligning external memory requests, we show that we can minimize the number of PCIe transactions and nearly fully utilize the PCIe bandwidth even with direct cache-line accesses to the host memory. EMOGI achieves 2.92$\times$ speedup on average compared to the optimized UVM implementations in various graph traversal applications. We also show that EMOGI scales better than a UVM-based solution when the system uses higher bandwidth interconnects such as PCIe 4.0.
Needle in a Haystack: Label-Efficient Evaluation under Extreme Class Imbalance
Venue: arXiv cs.LG 2021
Year: 2021

Important tasks like record linkage and extreme classification demonstrate extreme class imbalance, with 1 minority instance to every 1 million or more majority instances. Obtaining a sufficient sample of all classes, even just to achieve statistically-significant evaluation, is so challenging that most current approaches yield poor estimates or incur impractical cost. Where importance sampling has been levied against this challenge, restrictive constraints are placed on performance metrics, estimates do not come with appropriate guarantees, or evaluations cannot adapt to incoming labels. This paper develops a framework for online evaluation based on adaptive importance sampling. Given a target performance metric and model for $p(y|x)$, the framework adapts a distribution over items to label in order to maximize statistical precision. We establish strong consistency and a central limit theorem for the resulting performance estimates, and instantiate our framework with worked examples that leverage Dirichlet-tree models. Experiments demonstrate an average MSE superior to state-of-the-art on fixed label budgets.
Federated and continual learning for classification tasks in a society of devices
Venue: arXiv cs.LG 2021
Year: 2021

Today we live in a context in which devices are increasingly interconnected and sensorized and are almost ubiquitous. Deep learning has become in recent years a popular way to extract knowledge from the huge amount of data that these devices are able to collect. Nevertheless, centralized state-of-the-art learning methods have a number of drawbacks when facing real distributed problems, in which the available information is usually private, partial, biased and evolving over time. Federated learning is a popular framework that allows multiple distributed devices to train models remotely, collaboratively, and preserving data privacy. However, the current proposals in federated learning focus on deep architectures that in many cases are not feasible to implement in non-dedicated devices such as smartphones. Also, little research has been done regarding the scenario where data distribution changes over time in unforeseen ways, causing what is known as concept drift. Therefore, in this work we want to present Light Federated and Continual Consensus (LFedCon2), a new federated and continual architecture that uses light, traditional learners. Our method allows powerless devices (such as smartphones or robots) to learn in real time, locally, continuously, autonomously and from users, but also improving models globally, in the cloud, combining what is learned locally, in the devices. In order to test our proposal, we have applied it in a heterogeneous community of smartphone users to solve the problem of walking recognition. The results show the advantages that LFedCon2 provides with respect to other state-of-the-art methods.
D-square-B: Deep Distribution Bound for Natural-looking Adversarial Attack
Venue: arXiv cs.LG 2021
Year: 2021

We propose a novel technique that can generate natural-looking adversarial examples by bounding the variations induced for internal activation values in some deep layer(s), through a distribution quantile bound and a polynomial barrier loss function. By bounding model internals instead of individual pixels, our attack admits perturbations closely coupled with the existing features of the original input, allowing the generated examples to be natural-looking while having diverse and often substantial pixel distances from the original input. Enforcing per-neuron distribution quantile bounds allows addressing the non-uniformity of internal activation values. Our evaluation on ImageNet and five different model architecture demonstrates that our attack is quite effective. Compared to the state-of-the-art pixel space attack, semantic attack, and feature space attack, our attack can achieve the same attack success/confidence level while having much more natural-looking adversarial perturbations. These perturbations piggy-back on existing local features and do not have any fixed pixel bounds.
Leakage of Dataset Properties in Multi-Party Machine Learning
Venue: arXiv cs.LG 2021
Year: 2021

Secure multi-party machine learning allows several parties to build a model on their pooled data to increase utility while not explicitly sharing data with each other. We show that such multi-party computation can cause leakage of global dataset properties between the parties even when parties obtain only black-box access to the final model. In particular, a ``curious'' party can infer the distribution of sensitive attributes in other parties' data with high accuracy. This raises concerns regarding the confidentiality of properties pertaining to the whole dataset as opposed to individual data records. We show that our attack can leak population-level properties in datasets of different types, including tabular, text, and graph data. To understand and measure the source of leakage, we consider several models of correlation between a sensitive attribute and the rest of the data. Using multiple machine learning models, we show that leakage occurs even if the sensitive attribute is not included in the training data and has a low correlation with other attributes or the target variable.
Robust Baggage Detection and Classification Based on Local Tri-directional Pattern
Venue: arXiv cs.CV 2021
Year: 2021

In recent decades, the automatic video surveillance system has gained significant importance in computer vision community. The crucial objective of surveillance is monitoring and security in public places. In the traditional Local Binary Pattern, the feature description is somehow inaccurate, and the feature size is large enough. Therefore, to overcome these shortcomings, our research proposed a detection algorithm for a human with or without carrying baggage. The Local tri-directional pattern descriptor is exhibited to extract features of different human body parts including head, trunk, and limbs. Then with the help of support vector machine, extracted features are trained and evaluated. Experimental results on INRIA and MSMT17 V1 datasets show that LtriDP outperforms several state-of-the-art feature descriptors and validate its effectiveness.
Self-Imitation Learning via Generalized Lower Bound Q-learning
Venue: arXiv cs.LG 2021
Year: 2021

Self-imitation learning motivated by lower-bound Q-learning is a novel and effective approach for off-policy learning. In this work, we propose a n-step lower bound which generalizes the original return-based lower-bound Q-learning, and introduce a new family of self-imitation learning algorithms. To provide a formal motivation for the potential performance gains provided by self-imitation learning, we show that n-step lower bound Q-learning achieves a trade-off between fixed point bias and contraction rate, drawing close connections to the popular uncorrected n-step Q-learning. We finally show that n-step lower bound Q-learning is a more robust alternative to return-based self-imitation learning and uncorrected n-step, over a wide range of continuous control benchmark tasks.
Algorithm for Computing Approximate Nash Equilibrium in Continuous Games with Application to Continuous Blotto
Venue: arXiv cs.GT 2021
Year: 2021

Successful algorithms have been developed for computing Nash equilibrium in a variety of finite game classes. However, solving continuous games -- in which the pure strategy space is (potentially uncountably) infinite -- is far more challenging. Nonetheless, many real-world domains have continuous action spaces, e.g., where actions refer to an amount of time, money, or other resource that is naturally modeled as being real-valued as opposed to integral. We present a new algorithm for {approximating} Nash equilibrium strategies in continuous games. In addition to two-player zero-sum games, our algorithm also applies to multiplayer games and games with imperfect information. We experiment with our algorithm on a continuous imperfect-information Blotto game, in which two players distribute resources over multiple battlefields. Blotto games have frequently been used to model national security scenarios and have also been applied to electoral competition and auction theory. Experiments show that our algorithm is able to quickly compute close approximations of Nash equilibrium strategies for this game.