OpenRaiser/Intern-Atlas huggingface dataset:
A Fundamental Tradeoff between Computation and Communication in Distributed Computing
Venue: arXiv cs.IT 2017
Year: 2017

How can we optimally trade extra computing power to reduce the communication load in distributed computing? We answer this question by characterizing a fundamental tradeoff between computation and communication in distributed computing, i.e., the two are inversely proportional to each other. More specifically, a general distributed computing framework, motivated by commonly used structures like MapReduce, is considered, where the overall computation is decomposed into computing a set of "Map" and "Reduce" functions distributedly across multiple computing nodes. A coded scheme, named "Coded Distributed Computing" (CDC), is proposed to demonstrate that increasing the computation load of the Map functions by a factor of $r$ (i.e., evaluating each function at $r$ carefully chosen nodes) can create novel coding opportunities that reduce the communication load by the same factor. An information-theoretic lower bound on the communication load is also provided, which matches the communication load achieved by the CDC scheme. As a result, the optimal computation-communication tradeoff in distributed computing is exactly characterized. Finally, the coding techniques of CDC is applied to the Hadoop TeraSort benchmark to develop a novel CodedTeraSort algorithm, which is empirically demonstrated to speed up the overall job execution by $1.97\times$ - $3.39\times$, for typical settings of interest.
Phase Retrieval Without Small-Ball Probability Assumptions
Venue: arXiv cs.IT 2017
Year: 2017

In the context of the phase retrieval problem, it is known that certain natural classes of measurements, such as Fourier measurements and random Bernoulli measurements, do not lead to the unique reconstruction of all possible signals, even in combination with certain practically feasible random masks. To avoid this difficulty, the analysis is often restricted to measurement ensembles (or masks) that satisfy a small-ball probability condition, in order to ensure that the reconstruction is unique. This paper shows a complementary result: for random Bernoulli measurements, there is still a large class of signals that can be reconstructed uniquely, namely those signals that are "non-peaky." In fact, this result is much more general: it holds for random measurements sampled from any subgaussian distribution D, without any small-ball conditions. This is demonstrated in two ways: first, a proof of stability and uniqueness, and second, a uniform recovery guarantee for the PhaseLift algorithm. In all of these cases, the number of measurements m approaches the information-theoretic lower bound. Finally, for random Bernoulli measurements with erasures, it is shown that PhaseLift achieves uniform recovery of all signals (including peaky ones).
EgoSampling: Wide View Hyperlapse from Egocentric Videos
Venue: arXiv cs.CV 2017
Year: 2017

The possibility of sharing one's point of view makes use of wearable cameras compelling. These videos are often long, boring and coupled with extreme shake, as the camera is worn on a moving person. Fast forwarding (i.e. frame sampling) is a natural choice for quick video browsing. However, this accentuates the shake caused by natural head motion in an egocentric video, making the fast forwarded video useless. We propose EgoSampling, an adaptive frame sampling that gives stable, fast forwarded, hyperlapse videos. Adaptive frame sampling is formulated as an energy minimization problem, whose optimal solution can be found in polynomial time. We further turn the camera shake from a drawback into a feature, enabling the increase in field-of-view of the output video. This is obtained when each output frame is mosaiced from several input frames. The proposed technique also enables the generation of a single hyperlapse video from multiple egocentric videos, allowing even faster video consumption.
Collective Stochastic Discrete Choice Problems: A Min-LQG Game Formulation
Venue: arXiv cs.SY 2017
Year: 2017

We consider a class of dynamic collective choice models with social interactions, whereby a large number of non-uniform agents have to individually settle on one of multiple discrete alternative choices, with the relevance of their would-be choices continuously impacted by noise and the unfolding group behavior. This class of problems is modeled here as a so-called Min-LQG game, i.e., a linear quadratic Gaussian dynamic and non-cooperative game, with an additional combinatorial aspect in that it includes a final choice-related minimization in its terminal cost. The presence of this minimization term is key to enforcing some specific discrete choice by each individual agent. The theory of mean field games is invoked to generate a class of decentralized agent feedback control strategies which are then shown to converge to an exact Nash equilibrium of the game as the number of players increases to infinity. A key building block in our approach is an explicit solution to the problem of computing the best response of a generic agent to some arbitrarily posited smooth mean field trajectory. Ultimately, an agent is shown to face a continuously revised discrete choice problem, where greedy choices dictated by current conditions must be constantly balanced against the risk of the future process noise upsetting the wisdom of such decisions.Even though an agent's ultimately chosen alternative is random and dictated by its entire noise history and initial state, the limiting infinite population macroscopic behavior can still be predicted. It is shown that any Nash equilibrium of the game is defined by an a priori computable probability matrix characterizing the manner in which the agent population ultimately splits among the available alternatives.
Classifying Options for Deep Reinforcement Learning
Venue: arXiv cs.LG 2017
Year: 2017

In this paper we combine one method for hierarchical reinforcement learning - the options framework - with deep Q-networks (DQNs) through the use of different "option heads" on the policy network, and a supervisory network for choosing between the different options. We utilise our setup to investigate the effects of architectural constraints in subtasks with positive and negative transfer, across a range of network capacities. We empirically show that our augmented DQN has lower sample complexity when simultaneously learning subtasks with negative transfer, without degrading performance when learning subtasks with positive transfer.
An Exact Algorithm for a Fuel-Constrained Autonomous Vehicle Path Planning Problem
Venue: arXiv cs.SY 2017
Year: 2017

This paper addresses a fuel-constrained, autonomous vehicle path planning problem in the presence of multiple refueling stations. We are given a set of targets, a set of refueling stations, and a depot where $m$ vehicles are stationed. The vehicles are allowed to refuel at any refueling station, and the objective of the problem is to determine a route for each vehicle starting and terminating at the depot, such that each target is visited by at least one vehicle, the vehicles never run out of fuel while traversing their routes, and the total travel cost of all the routes is a minimum. We present four new mixed-integer linear programming formulations for the problem. These formulations are compared both analytically and empirically, and a branch-and-cut algorithm is developed to compute an optimal solution. Extensive computational results on a large class of test instances that corroborate the effectiveness of the algorithm are also presented.
Fundamental Tradeoff between Storage and Latency in Cache-Aided Wireless Interference Networks
Venue: arXiv cs.IT 2017
Year: 2017

This paper studies the fundamental tradeoff between storage and latency in a general wireless interference network with caches equipped at all transmitters and receivers. The tradeoff is characterized by an information-theoretic metric, \emph{normalized delivery time} (NDT), which is the worst-case delivery time of the actual traffic load at a transmission rate specified by degrees of freedom (DoF) of a given channel. We obtain both an achievable upper bound and a theoretical lower bound of the minimum NDT for any number of transmitters, any number of receivers, and any feasible cache size tuple. We show that the achievable NDT is exactly optimal in certain cache size regions, and is within a bounded multiplicative gap to the theoretical lower bound in other regions. In the achievability analysis, we first propose a novel cooperative transmitter/receiver coded caching strategy. It offers the freedom to adjust file splitting ratios for NDT minimization. We then propose a delivery strategy which transforms the considered interference network into a new class of cooperative X-multicast channels. It leverages local caching gain, coded multicasting gain, and transmitter cooperation gain (via interference alignment and interference neutralization) opportunistically. Finally, the achievable NDT is obtained by solving a linear programming problem. This study reveals that with caching at both transmitter and receiver sides, the network can benefit simultaneously from traffic load reduction and transmission rate enhancement, thereby effectively reducing the content delivery latency.
Gaussian Process Autonomous Mapping and Exploration for Range Sensing Mobile Robots
Venue: arXiv cs.RO 2017
Year: 2017

Most of the existing robotic exploration schemes use occupancy grid representations and geometric targets known as frontiers. The occupancy grid representation relies on the assumption of independence between grid cells and ignores structural correlations present in the environment. We develop a Gaussian Processes (GPs) occupancy mapping technique that is computationally tractable for online map building due to its incremental formulation and provides a continuous model of uncertainty over the map spatial coordinates. The standard way to represent geometric frontiers extracted from occupancy maps is to assign binary values to each grid cell. We extend this notion to novel probabilistic frontier maps computed efficiently using the gradient of the GP occupancy map. We also propose a mutual information-based greedy exploration technique built on that representation that takes into account all possible future observations. A major advantage of high-dimensional map inference is the fact that such techniques require fewer observations, leading to a faster map entropy reduction during exploration for map building scenarios. Evaluations using the publicly available datasets show the effectiveness of the proposed framework for robotic mapping and exploration tasks.
On sampling theorem with sparse decimated samples: exploring branching spectrum degeneracy
Venue: arXiv cs.IT 2017
Year: 2017

The paper investigates possibility of recovery of sequences from their decimated subsequences. It is shown that this recoverability is associated with certain spectrum degeneracy of a new kind, and that a sequences of a general kind can be approximated by sequences featuring this degeneracy. This is applied to sparse sampling of continuous time band-limited functions. The paper shows that these functions allow an arbitrarily close approximation by functions that can be recovered from sparse equidistant samples with sampling distance larger than the distance defined by the critical Nyquist rate for the underlying function. This allows to bypass, in a certain sense, the restriction on the sampling rate defined by the Nyquist rate.
Coalition Formability Semantics with Conflict-Eliminable Sets of Arguments
Venue: arXiv cs.AI 2017
Year: 2017

We consider abstract-argumentation-theoretic coalition formability in this work. Taking a model from political alliance among political parties, we will contemplate profitability, and then formability, of a coalition. As is commonly understood, a group forms a coalition with another group for a greater good, the goodness measured against some criteria. As is also commonly understood, however, a coalition may deliver benefits to a group X at the sacrifice of something that X was able to do before coalition formation, which X may be no longer able to do under the coalition. Use of the typical conflict-free sets of arguments is not very fitting for accommodating this aspect of coalition, which prompts us to turn to a weaker notion, conflict-eliminability, as a property that a set of arguments should primarily satisfy. We require numerical quantification of attack strengths as well as of argument strengths for its characterisation. We will first analyse semantics of profitability of a given conflict-eliminable set forming a coalition with another conflict-eliminable set, and will then provide four coalition formability semantics, each of which formalises certain utility postulate(s) taking the coalition profitability into account.
Game-Theoretic Multi-Agent Control and Network Cost Allocation under Communication Constraints
Venue: arXiv cs.SY 2017
Year: 2017

Multi-agent networked linear dynamic systems have attracted attention of researchers in power systems, intelligent transportation, and industrial automation. The agents might cooperatively optimize a global performance objective, resulting in social optimization, or try to satisfy their own selfish objectives using a noncooperative differential game. However, in these solutions, large volumes of data must be sent from system states to possibly distant control inputs, thus resulting in high cost of the underlying communication network. To enable economically-viable communication, a game-theoretic framework is proposed under the \textit{communication cost}, or \textit{sparsity}, constraint, given by the number of communicating state/control input pairs. As this constraint tightens, the system transitions from dense to sparse communication, providing the trade-off between dynamic system performance and information exchange. Moreover, using the proposed sparsity-constrained distributed social optimization and noncooperative game algorithms, we develop a method to allocate the costs of the communication infrastructure fairly and according to the agents' diverse needs for feedback and cooperation. Numerical results illustrate utilization of the proposed algorithms to enable and ensure economic fairness of wide-area control among power companies.
Private Coded Caching
Venue: arXiv cs.IT 2017
Year: 2017

Recent work by Maddah-Ali and Niesen introduced coded caching which demonstrated the benefits of joint design of storage and transmission policies in content delivery networks. They studied a setup where a server communicates with a set of users, each equipped with a local cache, over a shared error-free link and proposed an order-optimal caching and delivery scheme. In this paper, we introduce the problem of secretive coded caching where we impose the additional constraint that a user should not be able to learn anything, from either the content stored in its cache or the server transmissions, about a file it did not request. We propose a feasible scheme for this setting and demonstrate its order-optimality with respect to information-theoretic lower bounds.
Maximal Ratio Combining Diversity Analysis of Underwater Acoustic Communications Subject to $κ-μ$ Shadowed Fading Channels
Venue: arXiv cs.IT 2017
Year: 2017

In this paper, a novel unified analytical expression for average bit error rates (ABER) and average channel capacity (ACC) is presented for the $κ-μ$ shadowed fading model. This new shadowed fading model has shown to be suitable for underwater wireless channel modeling for the measurements conducted by the Naval Research Laboratory, and is not so well covered in the public literature. Deploying the Maximal Ratio Combining (MRC) receiver, a new simple analytical expression for the probability density function (PDF) of the receiver output signal to noise ratio is presented. Based on this new PDF, the novel unified ABER and ACC expression derived. To further generalize the error rate analysis, the additive white generalized Gaussian noise model is assumed that models the different noise environments. The new unified expression is accurate, simple and generic, and is suitable for MRC analysis in this generalized shadowed fading and noise environment. Numerical techniques and published results from the technical literature corroborate the generality and accuracy of our analysis under the different test scenarios.
Rate-Distortion Bounds on Bayes Risk in Supervised Learning
Venue: arXiv cs.IT 2017
Year: 2017

We present an information-theoretic framework for bounding the number of labeled samples needed to train a classifier in a parametric Bayesian setting. We derive bounds on the average $L_p$ distance between the learned classifier and the true maximum a posteriori classifier, which are well-established surrogates for the excess classification error due to imperfect learning. We provide lower and upper bounds on the rate-distortion function, using $L_p$ loss as the distortion measure, of a maximum a priori classifier in terms of the differential entropy of the posterior distribution and a quantity called the interpolation dimension, which characterizes the complexity of the parametric distribution family. In addition to expressing the information content of a classifier in terms of lossy compression, the rate-distortion function also expresses the minimum number of bits a learning machine needs to extract from training data to learn a classifier to within a specified $L_p$ tolerance. We use results from universal source coding to express the information content in the training data in terms of the Fisher information of the parametric family and the number of training samples available. The result is a framework for computing lower bounds on the Bayes $L_p$ risk. This framework complements the well-known probably approximately correct (PAC) framework, which provides minimax risk bounds involving the Vapnik-Chervonenkis dimension or Rademacher complexity. Whereas the PAC framework provides upper bounds the risk for the worst-case data distribution, the proposed rate-distortion framework lower bounds the risk averaged over the data distribution. We evaluate the bounds for a variety of data models, including categorical, multinomial, and Gaussian models. In each case the bounds are provably tight orderwise, and in two cases we prove that the bounds are tight up to multiplicative constants.
Recurrent Human Pose Estimation
Venue: arXiv cs.CV 2017
Year: 2017

We propose a novel ConvNet model for predicting 2D human body poses in an image. The model regresses a heatmap representation for each body keypoint, and is able to learn and represent both the part appearances and the context of the part configuration. We make the following three contributions: (i) an architecture combining a feed forward module with a recurrent module, where the recurrent module can be run iteratively to improve the performance, (ii) the model can be trained end-to-end and from scratch, with auxiliary losses incorporated to improve performance, (iii) we investigate whether keypoint visibility can also be predicted. The model is evaluated on two benchmark datasets. The result is a simple architecture that achieves performance on par with the state of the art, but without the complexity of a graphical model stage (or layers).
ARRIVAL: A zero-player graph game in NP $\cap$ coNP
Venue: arXiv cs.CC 2017
Year: 2017

Suppose that a train is running along a railway network, starting from a designated origin, with the goal of reaching a designated destination. The network, however, is of a special nature: every time the train traverses a switch, the switch will change its position immediately afterwards. Hence, the next time the train traverses the same switch, the other direction will be taken, so that directions alternate with each traversal of the switch. Given a network with origin and destination, what is the complexity of deciding whether the train, starting at the origin, will eventually reach the destination? It is easy to see that this problem can be solved in exponential time, but we are not aware of any polynomial-time method. In this short paper, we prove that the problem is in NP $\cap$ coNP. This raises the question whether we have just failed to find a (simple) polynomial-time solution, or whether the complexity status is more subtle, as for some other well-known (two-player) graph games.
Adapting the Bron-Kerbosch Algorithm for Enumerating Maximal Cliques in Temporal Graphs
Venue: arXiv cs.DS 2017
Year: 2017

Dynamics of interactions play an increasingly important role in the analysis of complex networks. A modeling framework to capture this are temporal graphs which consist of a set of vertices (entities in the network) and a set of time-stamped binary interactions between the vertices. We focus on enumerating delta-cliques, an extension of the concept of cliques to temporal graphs: for a given time period delta, a delta-clique in a temporal graph is a set of vertices and a time interval such that all vertices interact with each other at least after every delta time steps within the time interval. Viard, Latapy, and Magnien [ASONAM 2015, TCS 2016] proposed a greedy algorithm for enumerating all maximal delta-cliques in temporal graphs. In contrast to this approach, we adapt the Bron-Kerbosch algorithm - an efficient, recursive backtracking algorithm which enumerates all maximal cliques in static graphs - to the temporal setting. We obtain encouraging results both in theory (concerning worst-case running time analysis based on the parameter "delta-slice degeneracy" of the underlying graph) as well as in practice with experiments on real-world data. The latter culminates in an improvement for most interesting delte-values concerning running time in comparison with the algorithm of Viard, Latapy, and Magnien.
Why is Deep Random suitable for cryptology
Venue: arXiv cs.IT 2017
Year: 2017

We present a new form of randomness, called Deep Randomness, generated in such a way that probability distribution of the output signal is made unknowledgeable for an observer. By limiting, thanks to Deep Randomness, the capacity of the opponent observer to perform bayesian inference over public information to estimate private information, we can design protocols, beyond Shannon limit, enabling two legitimate partners, sharing originally no common private information, to exchange secret information with accuracy as close as desired from perfection, and knowledge as close as desired from zero by any unlimitedly powered opponent. We discuss the theoretical foundation of Deep Randomness, which lies on Prior Probability theory, introduced and developped by authors like Laplace, Cox, Carnap, Jefferys and Jaynes ; and we introduce computational method to generate such Deep Randomness. V2: we add a commented example of Perfact Secrecy Protocol based on Deep Random assumption V3: we provide a major update of the article. The logic foundation of Deep Random assumption is highly strengthened by avoiding the inconsistency attached to rare events. Such inconsistency could lead to security flaws in previous proposition. At the same time, several variants of the protocol are commented with improved performances. V4: we correct an error due to lack of symmetry in the example of protocol given in annex. We also make some writing improvements in perspective of conference publication. V5: we introduce parallel with former article from Maurer presenting a model of Perfect security based on partially independent channels.