OpenRaiser/Intern-Atlas huggingface dataset:
Concentration bounds for temporal difference learning with linear function approximation: The case of batch data and uniform sampling
Venue: arXiv cs.LG 2020
Year: 2020

We propose a stochastic approximation (SA) based method with randomization of samples for policy evaluation using the least squares temporal difference (LSTD) algorithm. Our proposed scheme is equivalent to running regular temporal difference learning with linear function approximation, albeit with samples picked uniformly from a given dataset. Our method results in an $O(d)$ improvement in complexity in comparison to LSTD, where $d$ is the dimension of the data. We provide non-asymptotic bounds for our proposed method, both in high probability and in expectation, under the assumption that the matrix underlying the LSTD solution is positive definite. The latter assumption can be easily satisfied for the pathwise LSTD variant proposed in [23]. Moreover, we also establish that using our method in place of LSTD does not impact the rate of convergence of the approximate value function to the true value function. These rate results coupled with the low computational complexity of our method make it attractive for implementation in big data settings, where $d$ is large. A similar low-complexity alternative for least squares regression is well-known as the stochastic gradient descent (SGD) algorithm. We provide finite-time bounds for SGD. We demonstrate the practicality of our method as an efficient alternative for pathwise LSTD empirically by combining it with the least squares policy iteration (LSPI) algorithm in a traffic signal control application. We also conduct another set of experiments that combines the SA based low-complexity variant for least squares regression with the LinUCB algorithm for contextual bandits, using the large scale news recommendation dataset from Yahoo.
Segmentation of Encrypted data
Venue: arXiv cs.CR 2020
Year: 2020

The retrieval of data from computer hard drives that have been seized from police busts against suspected criminals are sometimes not straight forward. Typically the incriminating data, which may be important evidence in subsequent trials, is encrypted and quick deleted. The cryptanalysis of what can be recovered from such hard drives is then subject to time-consuming brute-forcing and password guessing. To this end methods for accurate classification of what is encrypted data and what is not is of the essence. Here a procedure for discriminating encrypted data from non-encrypted is derived. Several methods are suggested and their accuracy is evaluated in different ways. Two methods to detect where encrypted data is located in a hard disk drive are detailed using passive change-point detection. The measures of performance of such methods are discussed and a new property for evaluation is suggested. The methods are then evaluated and discussed according to the new performance measure as well as the standard measures.
On the Energy Self-Sustainability of IoT via Distributed Compressed Sensing
Venue: arXiv cs.IT 2020
Year: 2020

This paper advocates the use of the distributed compressed sensing (DCS) paradigm to deploy energy harvesting (EH) Internet of Thing (IoT) devices for energy self-sustainability. We consider networks with signal/energy models that capture the fact that both the collected signals and the harvested energy of different devices can exhibit correlation. We provide theoretical analysis on the performance of both the classical compressive sensing (CS) approach and the proposed distributed CS (DCS)-based approach to data acquisition for EH IoT. Moreover, we perform an in-depth comparison of the proposed DCS-based approach against the distributed source coding (DSC) system. These performance characterizations and comparisons embody the effect of various system phenomena and parameters including signal correlation, EH correlation, network size, and energy availability level. Our results unveil that, the proposed approach offers significant increase in data gathering capability with respect to the CS-based approach, and offers a substantial reduction of the mean-squared error distortion with respect to the DSC system.
Partial Strategyproofness: Relaxing Strategyproofness for the Random Assignment Problem
Venue: arXiv cs.GT 2020
Year: 2020

We present partial strategyproofness, a new, relaxed notion of strategyproofness for studying the incentive properties of non-strategyproof assignment mechanisms. Informally, a mechanism is partially strategyproof if it makes truthful reporting a dominant strategy for those agents whose preference intensities differ sufficiently between any two objects. We demonstrate that partial strategyproofness is axiomatically motivated and yields a parametric measure for "how strategyproof" an assignment mechanism is. We apply this new concept to derive novel insights about the incentive properties of the probabilistic serial mechanism and different variants of the Boston mechanism.
Adding Negative Prices to Priced Timed Games
Venue: arXiv cs.GT 2020
Year: 2020

Priced timed games (PTGs) are two-player zero-sum games played on the infinite graph of configurations of priced timed automata where two players take turns to choose transitions in order to optimize cost to reach target states. Bouyer et al. and Alur, Bernadsky, and Madhusudan independently proposed algorithms to solve PTGs with nonnegative prices under certain divergence restriction over prices. Brihaye, Bruyere, and Raskin later provided a justification for such a restriction by showing the undecidability of the optimal strategy synthesis problem in the absence of this divergence restriction. This problem for PTGs with one clock has long been conjectured to be in polynomial time, however the current best known algorithm, by Hansen, Ibsen-Jensen, and Miltersen, is exponential. We extend this picture by studying PTGs with both negative and positive prices. We refine the undecidability results for optimal strategy synthesis problem, and show undecidability for several variants of optimal reachability cost objectives including reachability cost, time-bounded reachability cost, and repeated reachability cost objectives. We also identify a subclass with bi-valued price-rates and give a pseudo-polynomial algorithm to partially answer the conjecture on the complexity of one-clock PTGs.
An improved analysis of the Mömke-Svensson algorithm for graph-TSP on subquartic graphs
Venue: arXiv cs.DS 2020
Year: 2020

Mömke and Svensson presented a beautiful new approach for the traveling salesman problem on a graph metric (graph-TSP), which yields a $4/3$-approximation guarantee on subcubic graphs as well as a substantial improvement over the $3/2$-approximation guarantee of Christofides' algorithm on general graphs. The crux of their approach is to compute an upper bound on the minimum cost of a circulation in a particular network, $C(G,T)$, where $G$ is the input graph and $T$ is a carefully chosen spanning tree. The cost of this circulation is directly related to the number of edges in a tour output by their algorithm. Mucha subsequently improved the analysis of the circulation cost, proving that Mömke and Svensson's algorithm for graph-TSP has an approximation ratio of at most $13/9$ on general graphs. This analysis of the circulation is local, and vertices with degree four and five can contribute the most to its cost. Thus, hypothetically, there could exist a subquartic graph (a graph with degree at most four at each vertex) for which Mucha's analysis of the Mömke-Svensson algorithm is tight. We show that this is not the case and that Mömke and Svensson's algorithm for graph-TSP has an approximation guarantee of at most $25/18$ on subquartic graphs. To prove this, we present different methods to upper bound the minimum cost of a circulation on the network $C(G,T)$. Our approximation guarantee holds for all graphs that have an optimal solution to a standard linear programming relaxation of graph-TSP with subquartic support.
Settling the Complexity of Arrow-Debreu Markets under Leontief and PLC Utilities, using the Classes FIXP and \Exists-R
Venue: arXiv cs.CC 2020
Year: 2020

This paper resolves two of the handful of remaining questions on the computability of market equilibria, a central theme within algorithmic game theory (AGT). Our results are as follows: 1. We show FIXP-hardness of computing equilibria in Arrow-Debreu markets under Leontief utility functions, and Arrow-Debreu markets under linear utility functions and Leontief production sets. We note that these are the first FIXP-hardness results ever since the introduction of the class FIXP and the hardness of 3-Nash established therein. 2. We note that for the problems stated above, the corresponding results showing membership in FIXP were established after imposing suitable sufficiency conditions to render the problems total, as is customary in economics. However, if all instances are under consideration, then in both cases we prove that the problem of deciding if a given instance admits an equilibrium is \Exists-R-complete, where \Exists-R is the class of decision problems which can be reduced in polynomial time to Existential Theory of the Reals. 3. For Arrow-Debreu markets under Leontief utility functions and a constant number of agents, we give a polynomial-time algorithm for computing an equilibrium. This settles part of an open problem of Devanur and Kannan (FOCS'08). We note that PLC utilities are about the most general utilities of interest in economics and several fundamental utility functions studied within AGT are special cases of it. Several important problems, which have been shown to be in FIXP, are waiting for proofs of FIXP-hardness. In this context, our technique of reducing from 3-Nash to Multivariate Polynomial Equations and then to the problem is likely to be useful in the future.
Augur: a decentralized oracle and prediction market platform
Venue: arXiv cs.CR 2020
Year: 2020

Augur is a trustless, decentralized oracle and platform for prediction markets. The outcomes of Augur's prediction markets are chosen by users that hold Augur's native Reputation token, who stake their tokens on the actual observed outcome and, in return, receive settlement fees from the markets. Augur's incentive structure is designed to ensure that honest, accurate reporting of outcomes is always the most profitable option for Reputation token holders. Token holders can post progressively-larger Reputation bonds to dispute proposed market outcomes. If the size of these bonds reaches a certain threshold, Reputation splits into multiple versions, one for each possible outcome of the disputed market; token holders must then exchange their Reputation tokens for one of these versions. Versions of Reputation which do not correspond to the real-world outcome will become worthless, as no one will participate in prediction markets unless they are confident that the markets will resolve correctly. Therefore, token holders will select the only version of Reputation which they know will continue to have value: the version that corresponds to reality.
Using Rank Aggregation for Expert Search in Academic Digital Libraries
Venue: arXiv cs.IR 2020
Year: 2020

The task of expert finding has been getting increasing attention in information retrieval literature. However, the current state-of-the-art is still lacking in principled approaches for combining different sources of evidence. This paper explores the usage of unsupervised rank aggregation methods as a principled approach for combining multiple estimators of expertise, derived from the textual contents, from the graph-structure of the citation patterns for the community of experts, and from profile information about the experts. We specifically experimented two unsupervised rank aggregation approaches well known in the information retrieval literature, namely CombSUM and CombMNZ. Experiments made over a dataset of academic publications for the area of Computer Science attest for the adequacy of these methods.
Random variate generation using only finitely many unbiased, independently and identically distributed random bits
Venue: arXiv cs.IT 2020
Year: 2020

For any discrete probability distributions with bounded entropy, we can generate exactly a random variate using only a finite expected number of perfect coin flips. A perfect coin flip is the outcome of an unbiased Bernoulli random variable. Coin flips are unbiased, independently and identically distributed in all our work. We survey well-known algorithms for the discrete case such as the one from Knuth and Yao as well as the one from Han and Hoshi. We also discuss briefly about a practical implementation for the algorithm proposed by Knuth and Yao. For the continuous case, only approximations can be hoped for. The freedom to choose the accuracy for the approximations matters, and, for that, we propose to measure accuracy in terms of the Wasserstein $L_\infty$-metric. We derive a universal lower bound for the expected number of perfect coin flips required to reach a desired accuracy. We also provide several algorithms for absolutely continuous distributions that come within our universal lower bound.
Web Similarity in Sets of Search Terms using Database Queries
Venue: arXiv cs.IR 2020
Year: 2020

Normalized web distance (NWD) is a similarity or normalized semantic distance based on the World Wide Web or another large electronic database, for instance Wikipedia, and a search engine that returns reliable aggregate page counts. For sets of search terms the NWD gives a common similarity (common semantics) on a scale from 0 (identical) to 1 (completely different). The NWD approximates the similarity of members of a set according to all (upper semi)computable properties. We develop the theory and give applications of classifying using Amazon, Wikipedia, and the NCBI website from the National Institutes of Health. The last gives new correlations between health hazards. A restriction of the NWD to a set of two yields the earlier normalized google distance (NGD) but no combination of the NGD's of pairs in a set can extract the information the NWD extracts from the set. The NWD enables a new contextual (different databases) learning approachbased on Kolmogorov complexity theory that incorporates knowledge from these databases.
Scale-discretised ridgelet transform on the sphere
Venue: arXiv cs.IT 2020
Year: 2020

We revisit the spherical Radon transform, also called the Funk-Radon transform, viewing it as an axisymmetric convolution on the sphere. Viewing the spherical Radon transform in this manner leads to a straightforward derivation of its spherical harmonic representation, from which we show the spherical Radon transform can be inverted exactly for signals exhibiting antipodal symmetry. We then construct a spherical ridgelet transform by composing the spherical Radon and scale-discretised wavelet transforms on the sphere. The resulting spherical ridgelet transform also admits exact inversion for antipodal signals. The restriction to antipodal signals is expected since the spherical Radon and ridgelet transforms themselves result in signals that exhibit antipodal symmetry. Our ridgelet transform is defined natively on the sphere, probes signal content globally along great circles, does not exhibit blocking artefacts, supports spin signals and exhibits an exact and explicit inverse transform. No alternative ridgelet construction on the sphere satisfies all of these properties. Our implementation of the spherical Radon and ridgelet transforms is made publicly available. Finally, we illustrate the effectiveness of spherical ridgelets for diffusion magnetic resonance imaging of white matter fibers in the brain.
A Study on Splay Trees
Venue: arXiv cs.DS 2020
Year: 2020

We study the dynamic optimality conjecture, which predicts that splay trees are a form of universally efficient binary search tree, for any access sequence. We reduce this claim to a regular access bound, which seems plausible and might be easier to prove. This approach may be useful to establish dynamic optimality.
A metric for sets of trajectories that is practical and mathematically consistent
Venue: arXiv cs.CV 2020
Year: 2020

Metrics on the space of sets of trajectories are important for scientists in the field of computer vision, machine learning, robotics, and general artificial intelligence. However, existing notions of closeness between sets of trajectories are either mathematically inconsistent or of limited practical use. In this paper, we outline the limitations in the current mathematically-consistent metrics, which are based on OSPA (Schuhmacher et al. 2008); and the inconsistencies in the heuristic notions of closeness used in practice, whose main ideas are common to the CLEAR MOT measures (Keni and Rainer 2008) widely used in computer vision. In two steps, we then propose a new intuitive metric between sets of trajectories and address these limitations. First, we explain a solution that leads to a metric that is hard to compute. Then we modify this formulation to obtain a metric that is easy to compute while keeping the useful properties of the previous metric. Our notion of closeness is the first demonstrating the following three features: the metric 1) can be quickly computed, 2) incorporates confusion of trajectories' identity in an optimal way, and 3) is a metric in the mathematical sense.
Spanners for Directed Transmission Graphs
Venue: arXiv cs.CG 2020
Year: 2020

Let $P \subset \mathbb{R}^2$ be a planar $n$-point set such that each point $p \in P$ has an associated radius $r_p > 0$. The transmission graph $G$ for $P$ is the directed graph with vertex set $P$ such that for any $p, q \in P$, there is an edge from $p$ to $q$ if and only if $d(p, q) \leq r_p$. Let $t > 1$ be a constant. A $t$-spanner for $G$ is a subgraph $H \subseteq G$ with vertex set $P$ so that for any two vertices $p,q \in P$, we have $d_H(p, q) \leq t d_G(p, q)$, where $d_H$ and $d_G$ denote the shortest path distance in $H$ and $G$, respectively (with Euclidean edge lengths). We show how to compute a $t$-spanner for $G$ with $O(n)$ edges in $O(n (\log n + \log Ψ))$ time, where $Ψ$ is the ratio of the largest and smallest radius of a point in $P$. Using more advanced data structures, we obtain a construction that runs in $O(n \log^5 n)$ time, independent of $Ψ$. We give two applications for our spanners. First, we show how to use our spanner to find a BFS tree in $G$ from any given start vertex in $O(n \log n)$ time (in addition to the time it takes to build the spanner). Second, we show how to use our spanner to extend a reachability oracle to answer geometric reachability queries. In a geometric reachability query we ask whether a vertex $p$ in $G$ can "reach" a target $q$ which is an arbitrary point in the plane (rather than restricted to be another vertex $q$ of $G$ in a standard reachability query). Our spanner allows the reachability oracle to answer geometric reachability queries with an additive overhead of $O(\log n\log Ψ)$ to the query time and $O(n \log Ψ)$ to the space.
Multiple instance learning for sequence data with across bag dependencies
Venue: arXiv cs.LG 2020
Year: 2020

In Multiple Instance Learning (MIL) problem for sequence data, the instances inside the bags are sequences. In some real world applications such as bioinformatics, comparing a random couple of sequences makes no sense. In fact, each instance may have structural and/or functional relations with instances of other bags. Thus, the classification task should take into account this across bag relation. In this work, we present two novel MIL approaches for sequence data classification named ABClass and ABSim. ABClass extracts motifs from related instances and use them to encode sequences. A discriminative classifier is then applied to compute a partial classification result for each set of related sequences. ABSim uses a similarity measure to discriminate the related instances and to compute a scores matrix. For both approaches, an aggregation method is applied in order to generate the final classification result. We applied both approaches to solve the problem of bacterial Ionizing Radiation Resistance prediction. The experimental results of the presented approaches are satisfactory.
Classification accuracy as a proxy for two sample testing
Venue: arXiv cs.LG 2020
Year: 2020

When data analysts train a classifier and check if its accuracy is significantly different from chance, they are implicitly performing a two-sample test. We investigate the statistical properties of this flexible approach in the high-dimensional setting. We prove two results that hold for all classifiers in any dimensions: if its true error remains $ε$-better than chance for some $ε>0$ as $d,n \to \infty$, then (a) the permutation-based test is consistent (has power approaching to one), (b) a computationally efficient test based on a Gaussian approximation of the null distribution is also consistent. To get a finer understanding of the rates of consistency, we study a specialized setting of distinguishing Gaussians with mean-difference $δ$ and common (known or unknown) covariance $Σ$, when $d/n \to c \in (0,\infty)$. We study variants of Fisher's linear discriminant analysis (LDA) such as "naive Bayes" in a nontrivial regime when $ε\to 0$ (the Bayes classifier has true accuracy approaching 1/2), and contrast their power with corresponding variants of Hotelling's test. Surprisingly, the expressions for their power match exactly in terms of $n,d,δ,Σ$, and the LDA approach is only worse by a constant factor, achieving an asymptotic relative efficiency (ARE) of $1/\sqrtπ$ for balanced samples. We also extend our results to high-dimensional elliptical distributions with finite kurtosis. Other results of independent interest include minimax lower bounds, and the optimality of Hotelling's test when $d=o(n)$. Simulation results validate our theory, and we present practical takeaway messages along with natural open problems.
Local sparsity and recovery of fusion frames structured signals
Venue: arXiv cs.IT 2020
Year: 2020

The problem of recovering signals of high complexity from low quality sensing devices is analyzed via a combination of tools from signal processing and harmonic analysis. By using the rich structure offered by the recent development in fusion frames, we introduce a compressed sensing framework in which we split the dense information into sub-channel or local pieces and then fuse the local estimations. Each piece of information is measured by potentially low quality sensors, modeled by linear matrices and recovered via compressed sensing -- when necessary. Finally, by a fusion process within the fusion frames, we are able to recover accurately the original signal. Using our new method, we show, and illustrate on simple numerical examples, that it is possible, and sometimes necessary, to split a signal via local projections and / or filtering for accurate, stable, and robust estimation. In particular, we show that by increasing the size of the fusion frame, a certain robustness to noise can also be achieved. While the computational complexity remains relatively low, we achieve stronger recovery performance compared to usual single-device compressed sensing systems.
New Strong Converse for Asymmetric Broadcast Channels
Venue: arXiv cs.IT 2020
Year: 2020

We consider the discrete memoryless asymmetric broadcast channels. We prove that the error probability of decoding tends to one exponentially for rates outside the capacity region and derive an explicit lower bound of this exponent function. We shall demonstrate that the information spectrum approach is quite useful for investigating this problem.
RHOG: A Refinement-Operator Library for Directed Labeled Graphs
Venue: arXiv cs.AI 2020
Year: 2020

This document provides the foundations behind the functionality provided by the $ρ$G library (https://github.com/santiontanon/RHOG), focusing on the basic operations the library provides: subsumption, refinement of directed labeled graphs, and distance/similarity assessment between directed labeled graphs. $ρ$G development was initially supported by the National Science Foundation, by the EAGER grant IIS-1551338.