OpenRaiser/Intern-Atlas huggingface dataset:
Learning Stationary Correlated Equilibria in Constrained General-Sum Stochastic Games
Venue: arXiv cs.GT 2015
Year: 2015

We study constrained general-sum stochastic games with unknown Markovian dynamics. A distributed constrained no-regret Q-learning scheme (CNRQ) is presented to guarantee convergence to the set of stationary correlated equilibria of the game. Prior art addresses the unconstrained case only, is structured with nested control loops, and has no convergence result. CNRQ is cast as a single-loop three-timescale asynchronous stochastic approximation algorithm with set-valued update increments. A rigorous convergence analysis with differential inclusion arguments is given which draws on recent extensions of the theory of stochastic approximation to the case of asynchronous recursive inclusions with set-valued mean fields. Numerical results are given for the exemplary application of CNRQ to decentralized resource control in heterogeneous wireless networks (HetNets).
Dual Query: Practical Private Query Release for High Dimensional Data
Venue: arXiv cs.DS 2015
Year: 2015

We present a practical, differentially private algorithm for answering a large number of queries on high dimensional datasets. Like all algorithms for this task, ours necessarily has worst-case complexity exponential in the dimension of the data. However, our algorithm packages the computationally hard step into a concisely defined integer program, which can be solved non-privately using standard solvers. We prove accuracy and privacy theorems for our algorithm, and then demonstrate experimentally that our algorithm performs well in practice. For example, our algorithm can efficiently and accurately answer millions of queries on the Netflix dataset, which has over 17,000 attributes; this is an improvement on the state of the art by multiple orders of magnitude.
Nonlinear Kalman filter based on duality relations between continuous and discrete-state stochastic processes
Venue: arXiv cs.SY 2015
Year: 2015

A new application of duality relations of stochastic processes is demonstrated. Although conventional usages of the duality relations need analytical solutions for the dual processes, we here employ numerical solutions of the dual processes and investigate the usefulness. As a demonstration, estimation problems of hidden variables in stochastic differential equations are discussed. Employing algebraic probability theory, a little complicated birth-death process is derived from the stochastic differential equations, and an estimation method based on the ensemble Kalman filter is proposed. As a result, the possibility for making faster computational algorithms based on the duality concepts is shown.
Scalable Positional Analysis for Studying Evolution of Nodes in Networks
Venue: arXiv cs.SI 2015
Year: 2015

In social network analysis, the fundamental idea behind the notion of position is to discover actors who have similar structural signatures. Positional analysis of social networks involves partitioning the actors into disjoint sets using a notion of equivalence which captures the structure of relationships among actors. Classical approaches to Positional Analysis, such as Regular equivalence and Equitable Partitions, are too strict in grouping actors and often lead to trivial partitioning of actors in real world networks. An Epsilon Equitable Partition (EEP) of a graph, which is similar in spirit to Stochastic Blockmodels, is a useful relaxation to the notion of structural equivalence which results in meaningful partitioning of actors. In this paper we propose and implement a new scalable distributed algorithm based on MapReduce methodology to find EEP of a graph. Empirical studies on random power-law graphs show that our algorithm is highly scalable for sparse graphs, thereby giving us the ability to study positional analysis on very large scale networks. We also present the results of our algorithm on time evolving snapshots of the facebook and flickr social graphs. Results show the importance of positional analysis on large dynamic networks.
Estimation with Strategic Sensors
Venue: arXiv cs.GT 2015
Year: 2015

We introduce a model of estimation in the presence of strategic, self-interested sensors. We employ a game-theoretic setup to model the interaction between the sensors and the receiver. The cost function of the receiver is equal to the estimation error variance while the cost function of the sensor contains an extra term which is determined by its private information. We start by the single sensor case in which the receiver has access to a noisy but honest side information in addition to the message transmitted by a strategic sensor. We study both static and dynamic estimation problems. For both these problems, we characterize a family of equilibria in which the sensor and the receiver employ simple strategies. Interestingly, for the dynamic estimation problem, we find an equilibrium for which the strategic sensor uses a memory-less policy. We generalize the static estimation setup to multiple sensors with synchronous communication structure (i.e., all the sensors transmit their messages simultaneously). We prove the maybe surprising fact that, for the constructed equilibrium in affine strategies, the estimation quality degrades as the number of sensors increases. However, if the sensors are herding (i.e., copying each other policies), the quality of the receiver's estimation improves as the number of sensors increases. Finally, we consider the asynchronous communication structure (i.e., the sensors transmit their messages sequentially).
Near-Linear Query Complexity for Graph Inference
Venue: arXiv cs.DS 2015
Year: 2015

How efficiently can we find an unknown graph using distance or shortest path queries between its vertices? Let $G = (V,E)$ be an unweighted, connected graph of bounded degree. The edge set $E$ is initially unknown, and the graph can be accessed using a \emph{distance oracle}, which receives a pair of vertices $(u,v)$ and returns the distance between $u$ and $v$. In the \emph{verification} problem, we are given a hypothetical graph $\hat G = (V,\hat E)$ and want to check whether $G$ is equal to $\hat G$. We analyze a natural greedy algorithm and prove that it uses $n^{1+o(1)}$ distance queries. In the more difficult \emph{reconstruction} problem, $\hat G$ is not given, and the goal is to find the graph $G$. If the graph can be accessed using a \emph{shortest path oracle}, which returns not just the distance but an actual shortest path between $u$ and $v$, we show that extending the idea of greedy gives a reconstruction algorithm that uses $n^{1+o(1)}$ shortest path queries. When the graph has bounded treewidth, we further bound the query complexity of the greedy algorithms for both problems by $\tilde O(n)$. When the graph is chordal, we provide a randomized algorithm for reconstruction using $\tilde O(n)$ distance queries.
A Bayesian Model of node interaction in networks
Venue: arXiv cs.LG 2015
Year: 2015

We are concerned with modeling the strength of links in networks by taking into account how often those links are used. Link usage is a strong indicator of how closely two nodes are related, but existing network models in Bayesian Statistics and Machine Learning are able to predict only wether a link exists at all. As priors for latent attributes of network nodes we explore the Chinese Restaurant Process (CRP) and a multivariate Gaussian with fixed dimensionality. The model is applied to a social network dataset and a word coocurrence dataset.
On the Isomorphism Problem for Helly Circular-Arc Graphs
Venue: arXiv cs.CC 2015
Year: 2015

The isomorphism problem is known to be efficiently solvable for interval graphs, while for the larger class of circular-arc graphs its complexity status stays open. We consider the intermediate class of intersection graphs for families of circular arcs that satisfy the Helly property. We solve the isomorphism problem for this class in logarithmic space. If an input graph has a Helly circular-arc model, our algorithm constructs it canonically, which means that the models constructed for isomorphic graphs are equal.
Multi-Step Stochastic ADMM in High Dimensions: Applications to Sparse Optimization and Noisy Matrix Decomposition
Venue: arXiv cs.LG 2015
Year: 2015

We propose an efficient ADMM method with guarantees for high-dimensional problems. We provide explicit bounds for the sparse optimization problem and the noisy matrix decomposition problem. For sparse optimization, we establish that the modified ADMM method has an optimal convergence rate of $\mathcal{O}(s\log d/T)$, where $s$ is the sparsity level, $d$ is the data dimension and $T$ is the number of steps. This matches with the minimax lower bounds for sparse estimation. For matrix decomposition into sparse and low rank components, we provide the first guarantees for any online method, and prove a convergence rate of $\tilde{\mathcal{O}}((s+r)β^2(p) /T) + \mathcal{O}(1/p)$ for a $p\times p$ matrix, where $s$ is the sparsity level, $r$ is the rank and $Θ(\sqrt{p})\leq β(p)\leq Θ(p)$. Our guarantees match the minimax lower bound with respect to $s,r$ and $T$. In addition, we match the minimax lower bound with respect to the matrix dimension $p$, i.e. $β(p)=Θ(\sqrt{p})$, for many important statistical models including the independent noise model, the linear Bayesian network and the latent Gaussian graphical model under some conditions. Our ADMM method is based on epoch-based annealing and consists of inexpensive steps which involve projections on to simple norm balls. Experiments show that for both sparse optimization and matrix decomposition problems, our algorithm outperforms the state-of-the-art methods. In particular, we reach higher accuracy with same time complexity.
On Asymptotic Incoherence and its Implications for Compressed Sensing of Inverse Problems
Venue: arXiv cs.IT 2015
Year: 2015

Recently, it has been shown that incoherence is an unrealistic assumption for compressed sensing when applied to many inverse problems. Instead, the key property that permits efficient recovery in such problems is so-called local incoherence. Similarly, the standard notion of sparsity is also inadequate for many real world problems. In particular, in many applications, the optimal sampling strategy depends on asymptotic incoherence and the signal sparsity structure. The purpose of this paper is to study asymptotic incoherence and its implications towards the design of optimal sampling strategies and efficient sparsity bases. It is determined how fast asymptotic incoherence can decay in general for isometries. Furthermore it is shown that Fourier sampling and wavelet sparsity, whilst globally coherent, yield optimal asymptotic incoherence as a power law up to a constant factor. Sharp bounds on the asymptotic incoherence for Fourier sampling with polynomial bases are also provided. A numerical experiment is also presented to demonstrate the role of asymptotic incoherence in finding good subsampling strategies.
The challenges of unbounded treewidth in parameterised subgraph counting problems
Venue: arXiv cs.CC 2015
Year: 2015

Parameterised subgraph counting problems are the most thoroughly studied topic in the theory of parameterised counting, and there has been significant recent progress in this area. Many of the existing tractability results for parameterised problems which involve finding or counting subgraphs with particular properties rely on bounding the treewidth of these subgraphs in some sense; here, we prove a number of hardness results for the situation in which this bounded treewidth condition does not hold, resulting in dichotomies for some special cases of the general subgraph counting problem. The paper also gives a thorough survey of known results on this subject and the methods used, as well as discussing the relationships both between multicolour and uncoloured versions of subgraph counting problems, and between exact counting, approximate counting and the corresponding decision problems.
Similarity Decomposition Approach to Oscillatory Synchronization for Multiple Mechanical Systems With a Virtual Leader
Venue: arXiv cs.SY 2015
Year: 2015

This paper addresses the oscillatory synchronization problem for multiple uncertain mechanical systems with a virtual leader, and the interaction topology among them is assumed to contain a directed spanning tree. We propose an adaptive control scheme to achieve the goal of oscillatory synchronization. Using the similarity decomposition approach, we show that the position and velocity synchronization errors between each mechanical system (or follower) and the virtual leader converge to zero. The performance of the proposed adaptive scheme is shown by numerical simulation results.
Algebraic Properties of Valued Constraint Satisfaction Problem
Venue: arXiv cs.CC 2015
Year: 2015

The paper presents an algebraic framework for optimization problems expressible as Valued Constraint Satisfaction Problems. Our results generalize the algebraic framework for the decision version (CSPs) provided by Bulatov et al. [SICOMP 2005]. We introduce the notions of weighted algebras and varieties and use the Galois connection due to Cohen et al. [SICOMP 2013] to link VCSP languages to weighted algebras. We show that the difficulty of VCSP depends only on the weighted variety generated by the associated weighted algebra. Paralleling the results for CSPs we exhibit a reduction to cores and rigid cores which allows us to focus on idempotent weighted varieties. Further, we propose an analogue of the Algebraic CSP Dichotomy Conjecture; prove the hardness direction and verify that it agrees with known results for VCSPs on two-element sets [Cohen et al. 2006], finite-valued VCSPs [Thapper and Zivny 2013] and conservative VCSPs [Kolmogorov and Zivny 2013].
A Fast Block Low-Rank Dense Solver with Applications to Finite-Element Matrices
Venue: arXiv cs.NA 2015
Year: 2015

This article presents a fast solver for the dense "frontal" matrices that arise from the multifrontal sparse elimination process of 3D elliptic PDEs. The solver relies on the fact that these matrices can be efficiently represented as a hierarchically off-diagonal low-rank (HODLR) matrix. To construct the low-rank approximation of the off-diagonal blocks, we propose a new pseudo-skeleton scheme, the boundary distance low-rank approximation, that picks rows and columns based on the location of their corresponding vertices in the sparse matrix graph. We compare this new low-rank approximation method to the adaptive cross approximation (ACA) algorithm and show that it achieves betters speedup specially for unstructured meshes. Using the HODLR direct solver as a preconditioner (with a low tolerance) to the GMRES iterative scheme, we can reach machine accuracy much faster than a conventional LU solver. Numerical benchmarks are provided for frontal matrices arising from 3D finite element problems corresponding to a wide range of applications.
Adversarial Wiretap Channel with Public Discussion
Venue: arXiv cs.CR 2015
Year: 2015

Wyner's elegant model of wiretap channel exploits noise in the communication channel to provide perfect secrecy against a computationally unlimited eavesdropper without requiring a shared key. We consider an adversarial model of wiretap channel proposed in [18,19] where the adversary is active: it selects a fraction $ρ_r$ of the transmitted codeword to eavesdrop and a fraction $ρ_w$ of the codeword to corrupt by "adding" adversarial error. It was shown that this model also captures network adversaries in the setting of 1-round Secure Message Transmission [8]. It was proved that secure communication (1-round) is possible if and only if $ρ_r + ρ_w <1$. In this paper we show that by allowing communicants to have access to a public discussion channel (authentic communication without secrecy) secure communication becomes possible even if $ρ_r + ρ_w >1$. We formalize the model of \awtppd protocol and for two efficiency measures, {\em information rate } and {\em message round complexity} derive tight bounds. We also construct a rate optimal protocol family with minimum number of message rounds. We show application of these results to Secure Message Transmission with Public Discussion (SMT-PD), and in particular show a new lower bound on transmission rate of these protocols together with a new construction of an optimal SMT-PD protocol.
Partitioning a Graph into Disjoint Cliques and a Triangle-free Graph
Venue: arXiv cs.CC 2015
Year: 2015

A graph $G = (V, E)$ is \emph{partitionable} if there exists a partition $\{A, B\}$ of $V$ such that $A$ induces a disjoint union of cliques and $B$ induces a triangle-free graph. In this paper we investigate the computational complexity of deciding whether a graph is partitionable. The problem is known to be $\NP$-complete on arbitrary graphs. Here it is proved that if a graph $G$ is bull-free, planar, perfect, $K_4$-free or does not contain certain holes then deciding whether $G$ is partitionable is $\NP$-complete. This answers an open question posed by Thomass{é}, Trotignon and Vuškovi{ć}. In contrast a finite list of forbidden induced subgraphs is given for partitionable cographs.
Knightian Analysis of the Vickrey Mechanism
Venue: arXiv cs.GT 2015
Year: 2015

We analyze the Vickrey mechanism for auctions of multiple identical goods when the players have both Knightian uncertainty over their own valuations and incomplete preferences. In this model, the Vickrey mechanism is no longer dominant-strategy, and we prove that all dominant-strategy mechanisms are inadequate. However, we also prove that, in undominated strategies, the social welfare produced by the Vickrey mechanism in the worst case is not only very good, but also essentially optimal.
The UK-DALE dataset, domestic appliance-level electricity demand and whole-house demand from five UK homes
Venue: arXiv cs.OH 2015
Year: 2015

Many countries are rolling out smart electricity meters. These measure a home's total power demand. However, research into consumer behaviour suggests that consumers are best able to improve their energy efficiency when provided with itemised, appliance-by-appliance consumption information. Energy disaggregation is a computational technique for estimating appliance-by-appliance energy consumption from a whole-house meter signal. To conduct research on disaggregation algorithms, researchers require data describing not just the aggregate demand per building but also the `ground truth' demand of individual appliances. In this context, we present UK-DALE: an open-access dataset from the UK recording Domestic Appliance-Level Electricity at a sample rate of 16 kHz for the whole-house and at 1/6 Hz for individual appliances. This is the first open access UK dataset at this temporal resolution. We recorded from five houses, one of which was recorded for 655 days, the longest duration we are aware of for any energy dataset at this sample rate. We also describe the low-cost, open-source, wireless system we built for collecting our dataset.
A directed isoperimetric inequality with application to Bregman near neighbor lower bounds
Venue: arXiv cs.CG 2015
Year: 2015

Bregman divergences $D_ϕ$ are a class of divergences parametrized by a convex function $ϕ$ and include well known distance functions like $\ell_2^2$ and the Kullback-Leibler divergence. There has been extensive research on algorithms for problems like clustering and near neighbor search with respect to Bregman divergences, in all cases, the algorithms depend not just on the data size $n$ and dimensionality $d$, but also on a structure constant $μ\ge 1$ that depends solely on $ϕ$ and can grow without bound independently. In this paper, we provide the first evidence that this dependence on $μ$ might be intrinsic. We focus on the problem of approximate near neighbor search for Bregman divergences. We show that under the cell probe model, any non-adaptive data structure (like locality-sensitive hashing) for $c$-approximate near-neighbor search that admits $r$ probes must use space $Ω(n^{1 + \fracμ{c r}})$. In contrast, for LSH under $\ell_1$ the best bound is $Ω(n^{1+\frac{1}{cr}})$. Our new tool is a directed variant of the standard boolean noise operator. We show that a generalization of the Bonami-Beckner hypercontractivity inequality exists "in expectation" or upon restriction to certain subsets of the Hamming cube, and that this is sufficient to prove the desired isoperimetric inequality that we use in our data structure lower bound. We also present a structural result reducing the Hamming cube to a Bregman cube. This structure allows us to obtain lower bounds for problems under Bregman divergences from their $\ell_1$ analog. In particular, we get a (weaker) lower bound for approximate near neighbor search of the form $Ω(n^{1 + \frac{1}{cr}})$ for an $r$-query non-adaptive data structure, and new cell probe lower bounds for a number of other near neighbor questions in Bregman space.
Detecting Possible Manipulators in Elections
Venue: arXiv cs.MA 2015
Year: 2015

Manipulation is a problem of fundamental importance in the context of voting in which the voters exercise their votes strategically instead of voting honestly to prevent selection of an alternative that is less preferred. The Gibbard-Satterthwaite theorem shows that there is no strategy-proof voting rule that simultaneously satisfies certain combinations of desirable properties. Researchers have attempted to get around the impossibility results in several ways such as domain restriction and computational hardness of manipulation. However these approaches have been shown to have limitations. Since prevention of manipulation seems to be elusive, an interesting research direction therefore is detection of manipulation. Motivated by this, we initiate the study of detection of possible manipulators in an election. We formulate two pertinent computational problems - Coalitional Possible Manipulators (CPM) and Coalitional Possible Manipulators given Winner (CPMW), where a suspect group of voters is provided as input to compute whether they can be a potential coalition of possible manipulators. In the absence of any suspect group, we formulate two more computational problems namely Coalitional Possible Manipulators Search (CPMS), and Coalitional Possible Manipulators Search given Winner (CPMSW). We provide polynomial time algorithms for these problems, for several popular voting rules. For a few other voting rules, we show that these problems are in NP-complete. We observe that detecting manipulation maybe easy even when manipulation is hard, as seen for example, in the case of the Borda voting rule.
A Distributed Frank-Wolfe Algorithm for Communication-Efficient Sparse Learning
Venue: arXiv cs.DC 2015
Year: 2015

Learning sparse combinations is a frequent theme in machine learning. In this paper, we study its associated optimization problem in the distributed setting where the elements to be combined are not centrally located but spread over a network. We address the key challenges of balancing communication costs and optimization errors. To this end, we propose a distributed Frank-Wolfe (dFW) algorithm. We obtain theoretical guarantees on the optimization error $ε$ and communication cost that do not depend on the total number of combining elements. We further show that the communication cost of dFW is optimal by deriving a lower-bound on the communication cost required to construct an $ε$-approximate solution. We validate our theoretical analysis with empirical studies on synthetic and real-world data, which demonstrate that dFW outperforms both baselines and competing methods. We also study the performance of dFW when the conditions of our analysis are relaxed, and show that dFW is fairly robust.