OpenRaiser/Intern-Atlas huggingface dataset:
Dynamic Frame skip Deep Q Network
Venue: arXiv cs.LG 2020
Year: 2020

Deep Reinforcement Learning methods have achieved state of the art performance in learning control policies for the games in the Atari 2600 domain. One of the important parameters in the Arcade Learning Environment (ALE) is the frame skip rate. It decides the granularity at which agents can control game play. A frame skip value of $k$ allows the agent to repeat a selected action $k$ number of times. The current state of the art architectures like Deep Q-Network (DQN) and Dueling Network Architectures (DuDQN) consist of a framework with a static frame skip rate, where the action output from the network is repeated for a fixed number of frames regardless of the current state. In this paper, we propose a new architecture, Dynamic Frame skip Deep Q-Network (DFDQN) which makes the frame skip rate a dynamic learnable parameter. This allows us to choose the number of times an action is to be repeated based on the current state. We show empirically that such a setting improves the performance on relatively harder games like Seaquest.
Optimal Inference for Distributed Detection
Venue: arXiv cs.IT 2020
Year: 2020

In distributed detection, there does not exist an automatic way of generating optimal decision strategies for non-affine decision functions. Consequently, in a detection problem based on a non-affine decision function, establishing optimality of a given decision strategy, such as a generalized likelihood ratio test, is often difficult or even impossible. In this thesis we develop a novel detection network optimization technique that can be used to determine necessary and sufficient conditions for optimality in distributed detection for which the underlying objective function is monotonic and convex in probabilistic decision strategies. Our developed approach leverages on basic concepts of optimization and statistical inference which are provided in sufficient detail. These basic concepts are combined to form the basis of an optimal inference technique for signal detection. We prove a central theorem that characterizes optimality in a variety of distributed detection architectures. We discuss three applications of this result in distributed signal detection. These applications include interactive distributed detection, optimal tandem fusion architecture, and distributed detection by acyclic graph networks. In the conclusion we indicate several future research directions, which include possible generalizations of our optimization method and new research problems arising from each of the three applications considered.
Multiple target tracking based on sets of trajectories
Venue: arXiv cs.CV 2020
Year: 2020

We propose a solution of the multiple target tracking (MTT) problem based on sets of trajectories and the random finite set framework. A full Bayesian approach to MTT should characterise the distribution of the trajectories given the measurements, as it contains all information about the trajectories. We attain this by considering multi-object density functions in which objects are trajectories. For the standard tracking models, we also describe a conjugate family of multitrajectory density functions.
Applications of Probabilistic Programming (Master's thesis, 2015)
Venue: arXiv cs.AI 2020
Year: 2020

This thesis describes work on two applications of probabilistic programming: the learning of probabilistic program code given specifications, in particular program code of one-dimensional samplers; and the facilitation of sequential Monte Carlo inference with help of data-driven proposals. The latter is presented with experimental results on a linear Gaussian model and a non-parametric dependent Dirichlet process mixture of objects model for object recognition and tracking. In Chapter 1 we provide a brief introduction to probabilistic programming. In Chapter 2 we present an approach to automatic discovery of samplers in the form of probabilistic programs. We formulate a Bayesian approach to this problem by specifying a grammar-based prior over probabilistic program code. We use an approximate Bayesian computation method to learn the programs, whose executions generate samples that statistically match observed data or analytical characteristics of distributions of interest. In our experiments we leverage different probabilistic programming systems to perform Markov chain Monte Carlo sampling over the space of programs. Experimental results have demonstrated that, using the proposed methodology, we can learn approximate and even some exact samplers. Finally, we show that our results are competitive with regard to genetic programming methods. In Chapter 3, we describe a way to facilitate sequential Monte Carlo inference in probabilistic programming using data-driven proposals. In particular, we develop a distance-based proposal for the non-parametric dependent Dirichlet process mixture of objects model. We implement this approach in the probabilistic programming system Anglican, and show that for that model data-driven proposals provide significant performance improvements. We also explore the possibility of using neural networks to improve data-driven proposals.
Persuasion with Limited Communication
Venue: arXiv cs.GT 2020
Year: 2020

We examine information structure design, also called "persuasion" or "signaling", in the presence of a constraint on the amount of communication. We focus on the fundamental setting of bilateral trade, which in its simplest form involves a seller with a single item to price, a buyer whose value for the item is drawn from a common prior distribution over $n$ different possible values, and a take-it-or-leave-it-offer protocol. A mediator with access to the buyer's type may partially reveal such information to the seller in order to further some objective such as the social welfare or the seller's revenue. In the setting of maximizing welfare under bilateral trade, we show that $O(\log(n) \log \frac{1}ε)$ signals suffice for a $1-ε$ approximation to the optimal welfare, and this bound is tight. As our main result, we exhibit an efficient algorithm for computing a $\frac{M-1}{M} \cdot (1-1/e)$-approximation to the welfare-maximizing scheme with at most M signals. For the revenue objective, we show that $Ω(n)$ signals are needed for a constant factor approximation to the revenue of a fully informed seller. From a computational perspective, however, the problem gets easier: we show that a simple dynamic program computes the signaling scheme with M signals maximizing the seller's revenue. Observing that the signaling problem in bilateral trade is a special case of the fundamental Bayesian Persuasion model of Kamenica and Gentzkow, we also examine the question of communication-constrained signaling more generally. In this model there is a sender (the mediator), a receiver (the seller) looking to take an action (setting the price), and a state of nature (the buyer's type) drawn from a common prior. We show that it is NP-hard to approximate the optimal sender's utility to within any constant factor in the presence of communication constraints.
Blockchain-based Proof of Location
Venue: arXiv cs.DC 2020
Year: 2020

Location-Based Services (LBSs) build upon geographic information to provide users with location-dependent functionalities. In such a context, it is particularly important that geographic locations claimed by users are trustworthy. Centralized verification approaches proposed in the last few years are not satisfactory, as they entail a high risk to the privacy of users. In this paper, we present and evaluate a novel decentralized, infrastructure-independent proof-of-location scheme based on blockchain technology. Our scheme guarantees both location trustworthiness and user privacy preservation.
Secure Group Testing
Venue: arXiv cs.IT 2020
Year: 2020

The principal goal of Group Testing (GT) is to identify a small subset of "defective" items from a large population, by grouping items into as few test pools as possible. The test outcome of a pool is positive if it contains at least one defective item, and is negative otherwise. GT algorithms are utilized in numerous applications, and in many of them maintaining the privacy of the tested items, namely, keeping secret whether they are defective or not, is critical. In this paper, we consider a scenario where there is an eavesdropper (Eve) who is able to observe a subset of the GT outcomes (pools). We propose a new non-adaptive Secure Group Testing (SGT) scheme based on information-theoretic principles. The new proposed test design keeps the eavesdropper ignorant regarding the items' status. Specifically, when the fraction of tests observed by Eve is $0 \leq δ<1$, we prove that with the naive Maximum Likelihood (ML) decoding algorithm the number of tests required for both correct reconstruction at the legitimate user (with high probability) and negligible information leakage to Eve is $\frac{1}{1-δ}$ times the number of tests required with no secrecy constraint for the fixed $K$ regime. By a matching converse, we completely characterize the Secure GT capacity. Moreover, we consider the Definitely Non-Defective (DND) computationally efficient decoding algorithm, proposed in the literature for non-secure GT. We prove that with the new secure test design, for $δ< 1/2$, the number of tests required, without any constraint on $K$, is at most $\frac{1}{1/2-δ}$ times the number of tests required with no secrecy constraint.
Dynamic Time Warping and Geometric Edit Distance: Breaking the Quadratic Barrier
Venue: arXiv cs.DS 2020
Year: 2020

Dynamic Time Warping (DTW) and Geometric Edit Distance (GED) are basic similarity measures between curves or general temporal sequences (e.g., time series) that are represented as sequences of points in some metric space $(X, \mathrm{dist})$. The DTW and GED measures are massively used in various fields of computer science, computational biology, and engineering. Consequently, the tasks of computing these measures are among the core problems in P. Despite extensive efforts to find more efficient algorithms, the best-known algorithms for computing the DTW or GED between two sequences of points in $X = \mathbb{R}^d$ are long-standing dynamic programming algorithms that require quadratic runtime, even for the one-dimensional case $d = 1$, which is perhaps one of the most used in practice. In this paper, we break the nearly 50 years old quadratic time bound for computing DTW or GED between two sequences of $n$ points in $\mathbb{R}$, by presenting deterministic algorithms that run in $O\left( n^2 / \log\log n \right)$ time. Our algorithms can be extended to work also for higher dimensional spaces $\mathbb{R}^d$, for any constant $d$, when the underlying distance-metric $\mathrm{dist}$ is polyhedral (e.g., $L_1, L_\infty$).
Bi-Arc Digraphs and Conservative Polymorphisms
Venue: arXiv cs.DS 2020
Year: 2020

In this paper we study the class of bi-arc digraphs, important from two seemingly unrelated perspectives. On the one hand, they are precisely the digraphs that admit certain polymorphisms of interest in the study of constraint satisfaction problems; on the other hand, they are a very broad generalization of interval graphs. Bi-arc digraphs is the class of digraphs that admit conservative semilattice polymorphisms. There is much interest in understanding structures that admit particular types of polymorphisms, and especially in their recognition algorithms. (Such problems are referred to as metaproblems.) Surprisingly, the class of bi-arc digraphs also describes the class of digraphs that admit certain other kinds of conservative polymorphisms. Thus solving the recognition problem for bi-arc digraphs solves the metaproblem for digraphs for several types of conservative polymorphisms. The complexity of the recognition problem for digraphs with conservative semilattice polymorphisms was an open problem, while it was known to be NP-complete for certain more complex relational structures. We complement our result by providing a complete dichotomy classification of which general relational structures have polynomial or NP-complete recognition problems for the existence of conservative semilattice polymorphisms. Bi-arc digraphs also generalizes the class of interval graphs; in fact it reduces to the class of interval graphs for symmetric and reflexive digraphs. It is much broader than interval graphs and includes other generalizations of interval graphs such as co-threshold tolerance graphs and adjusted interval digraphs. Yet, it is still a reasonable extension of interval graphs, in the sense that it keeps much of the appeal of interval graphs. Our main result is a forbidden obstruction characterization of, and a polynomial recognition for, the class of bi-arc digraphs.
Logical Induction
Venue: arXiv cs.AI 2020
Year: 2020

We present a computable algorithm that assigns probabilities to every logical statement in a given formal language, and refines those probabilities over time. For instance, if the language is Peano arithmetic, it assigns probabilities to all arithmetical statements, including claims about the twin prime conjecture, the outputs of long-running computations, and its own probabilities. We show that our algorithm, an instance of what we call a logical inductor, satisfies a number of intuitive desiderata, including: (1) it learns to predict patterns of truth and falsehood in logical statements, often long before having the resources to evaluate the statements, so long as the patterns can be written down in polynomial time; (2) it learns to use appropriate statistical summaries to predict sequences of statements whose truth values appear pseudorandom; and (3) it learns to have accurate beliefs about its own current beliefs, in a manner that avoids the standard paradoxes of self-reference. For example, if a given computer program only ever produces outputs in a certain range, a logical inductor learns this fact in a timely manner; and if late digits in the decimal expansion of $π$ are difficult to predict, then a logical inductor learns to assign $\approx 10\%$ probability to "the $n$th digit of $π$ is a 7" for large $n$. Logical inductors also learn to trust their future beliefs more than their current beliefs, and their beliefs are coherent in the limit (whenever $ϕ\implies ψ$, $\mathbb{P}_\infty(ϕ) \le \mathbb{P}_\infty(ψ)$, and so on); and logical inductors strictly dominate the universal semimeasure in the limit. These properties and many others all follow from a single logical induction criterion, which is motivated by a series of stock trading analogies. Roughly speaking, each logical sentence $ϕ$ is associated with a stock that is worth \$1 per share if [...]
(Bandit) Convex Optimization with Biased Noisy Gradient Oracles
Venue: arXiv cs.LG 2020
Year: 2020

Algorithms for bandit convex optimization and online learning often rely on constructing noisy gradient estimates, which are then used in appropriately adjusted first-order algorithms, replacing actual gradients. Depending on the properties of the function to be optimized and the nature of ``noise'' in the bandit feedback, the bias and variance of gradient estimates exhibit various tradeoffs. In this paper we propose a novel framework that replaces the specific gradient estimation methods with an abstract oracle. With the help of the new framework we unify previous works, reproducing their results in a clean and concise fashion, while, perhaps more importantly, the framework also allows us to formally show that to achieve the optimal root-$n$ rate either the algorithms that use existing gradient estimators, or the proof techniques used to analyze them have to go beyond what exists today.
Asynchronous Stochastic Gradient Descent with Delay Compensation
Venue: arXiv cs.LG 2020
Year: 2020

With the fast development of deep learning, it has become common to learn big neural networks using massive training data. Asynchronous Stochastic Gradient Descent (ASGD) is widely adopted to fulfill this task for its efficiency, which is, however, known to suffer from the problem of delayed gradients. That is, when a local worker adds its gradient to the global model, the global model may have been updated by other workers and this gradient becomes "delayed". We propose a novel technology to compensate this delay, so as to make the optimization behavior of ASGD closer to that of sequential SGD. This is achieved by leveraging Taylor expansion of the gradient function and efficient approximation to the Hessian matrix of the loss function. We call the new algorithm Delay Compensated ASGD (DC-ASGD). We evaluated the proposed algorithm on CIFAR-10 and ImageNet datasets, and the experimental results demonstrate that DC-ASGD outperforms both synchronous SGD and asynchronous SGD, and nearly approaches the performance of sequential SGD.
Fast Core Pricing for Rich Advertising Auctions
Venue: arXiv cs.GT 2020
Year: 2020

Standard ad auction formats do not immediately extend to settings where multiple size configurations and layouts are available to advertisers. In these settings, the sale of web advertising space increasingly resembles a combinatorial auction with complementarities, where truthful auctions such as the Vickrey-Clarke-Groves (VCG) can yield unacceptably low revenue. We therefore study core selecting auctions, which boost revenue by setting payments so that no group of agents, including the auctioneer, can jointly improve their utilities by switching to a different outcome. Our main result is a combinatorial algorithm that finds an approximate bidder optimal core point with almost linear number of calls to the welfare maximization oracle. Our algorithm is faster than previously-proposed heuristics in the literature and has theoretical guarantees. We conclude that core pricing is implementable even for very time sensitive practical use cases such as realtime auctions for online advertising and can yield more revenue. We justify this claim experimentally using the Microsoft Bing Ad Auction data, through which we show our core pricing algorithm generates almost 26% more revenue than VCG on average, about 9% more revenue than other core pricing rules known in the literature, and almost matches the revenue of the standard Generalized Second Price (GSP) auction.
Depth-Width Tradeoffs in Approximating Natural Functions with Neural Networks
Venue: arXiv cs.LG 2020
Year: 2020

We provide several new depth-based separation results for feed-forward neural networks, proving that various types of simple and natural functions can be better approximated using deeper networks than shallower ones, even if the shallower networks are much larger. This includes indicators of balls and ellipses; non-linear functions which are radial with respect to the $L_1$ norm; and smooth non-linear functions. We also show that these gaps can be observed experimentally: Increasing the depth indeed allows better learning than increasing width, when training neural networks to learn an indicator of a unit ball.
RECOME: a New Density-Based Clustering Algorithm Using Relative KNN Kernel Density
Venue: arXiv cs.DB 2020
Year: 2020

Discovering clusters from a dataset with different shapes, densities, and scales is a known challenging problem in data clustering. In this paper, we propose the RElative COre MErge (RECOME) clustering algorithm. The core of RECOME is a novel density measure, i.e., Relative $K$ nearest Neighbor Kernel Density (RNKD). RECOME identifies core objects with unit RNKD, and {partitions} non-core objects into atom clusters by successively following higher-density neighbor relations toward core objects. Core objects and their corresponding atom clusters are then merged through $α$-reachable paths on a KNN graph. We discover that the number of clusters computed by RECOME is a step function of the $α$ parameter with jump discontinuity on a small collection of values. A fast jump discontinuity discovery (FJDD) method is proposed based on graph theory. RECOME is evaluated on both synthetic datasets and real datasets. Experimental results indicate that RECOME is able to discover clusters with different shapes, densities, and scales. It outperforms six baseline methods on both synthetic datasets and real datasets. Moreover, FJDD is shown to be effective to extract the jump discontinuity set of parameter $α$ for all tested datasets, which can ease the task of data exploration and parameter tuning.
A Simpler and Faster Strongly Polynomial Algorithm for Generalized Flow Maximization
Venue: arXiv cs.DS 2020
Year: 2020

We present a new strongly polynomial algorithm for generalized flow maximization that is significantly simpler and faster than the previous strongly polynomial algorithm [Végh16]. For the uncapacitated problem formulation, the complexity bound $O(mn(m+n\log n)\log (n^2/m))$ improves on the previous estimate by almost a factor $O(n^2)$. Even for small numerical parameter values, our running time bound is comparable to the best weakly polynomial algorithms. The key new technical idea is relaxing the primal feasibility conditions. This allows us to work almost exclusively with integral flows, in contrast to all previous algorithms for the problem.
Polar Coding for Non-Stationary Channels
Venue: arXiv cs.IT 2020
Year: 2020

The problem of polar coding for an arbitrary sequence of independent binary-input memoryless symmetric (BMS) channels $\left\{W_i\right\}_{i=1}^{N}$ is considered. The sequence of channels is assumed to be completely known to both the transmitter and the receiver (a coherent scenario). Also, at each code block transmission, each of the channels is used only once. In other words, a codeword of length $N$ is constructed and then the $i$-th encoded bit is transmitted over $W_i$. The goal is to operate at a rate $R$ close to the average of the symmetric capacities of $W_i$'s, denoted by $\overline{I}_N$. To this end, we construct a polar coding scheme using Arikan's channel polarization transform in combination with certain permutations at each polarization level and certain skipped operations. In particular, given a non-stationary sequence of BMS channels $\left\{W_i\right\}_{i=1}^{N}$ and $P_e$, where $0 < P_e <1$, we construct a polar code of length $N$ and rate $R$ guaranteeing a block error probability of at most $P_e$ for transmission over $\left\{W_i\right\}_{i=1}^{N}$ such that $$ N \leq \fracκ{(\overline{I}_N - R)^μ}, $$ where $μ$ is a constant and $κ$ is a constant depending on $P_e$ and $μ$. We further show a numerical upper bound on $μ$ that is: $μ\leq 7.34$ for non-stationary binary erasure channels and $μ\leq 8.54$ for general non-stationary BMS channels. The encoding and decoding complexities of the constructed polar code preserve $O(N \log N)$ complexity of Arikan's polar codes. In an asymptotic sense, when coded bits are transmitted over a non-stationary sequence of BMS channels $\left\{W_i\right\}_{i=1}^{\infty}$, our proposed scheme achieves the average symmetric capacity $$ \overline{I}(\left\{W_i\right\}_{i=1}^{\infty}) := \lim_{N\rightarrow \infty} \frac{1}{N}\sum_{i=1}^N I(W_i), $$ assuming that the limit exists.