A privacy-constrained information extraction problem is considered where for a pair of correlated discrete random variables (X,Y) governed by a given joint distribution, an agent observes Y and wants to convey to a potentially public user as much information about Y as possible while limiting the amount of information revealed about X. To this end, the so-called rate-privacy function is investigated to quantify the maximal amount of information (measured in terms of mutual information) that can be extracted from Y under a privacy constraint between X and the extracted information, where privacy is measured using either mutual information or maximal correlation. Properties of the rate-privacy function are analyzed and its information-theoretic and estimation-theoretic interpretations are presented for both the mutual information and maximal correlation privacy measures. It is also shown that the rate-privacy function admits a closed-form expression for a large family of joint distributions of (X,Y). Finally, the rate-privacy function under the mutual information privacy measure is considered for the case where (X,Y) has a joint probability density function by studying the problem where the extracted information is a uniform quantization of Y corrupted by additive Gaussian noise. The asymptotic behavior of the rate-privacy function is studied as the quantization resolution grows without bound and it is observed that not all of the properties of the rate-privacy function carry over from the discrete to the continuous case.
16 August 2018 in IEEE Transactions on Information Theory
We investigate the problem of estimating a random variable Y under a privacy constraint dictated by another correlated random variable X. When X and Y are discrete, we express the underlying privacy-utility tradeoff in terms of the privacy-constrained guessing probability h(PXY , ε), the maximum probability Pc(Y|Z) of correctly guessing Y given an auxiliary random variable Z, where the maximization is taken over all PZ|Y ensuring that Pc(X|Z) ≤ ε for a given privacy threshold ε ≥ 0. We prove that h(PXY , ·) is concave and piecewise linear, which allows us to derive its expression in closed form for any ε when X and Y are binary. In the non-binary case, we derive h(PXY , ε) in the high utility regime (i.e., for sufficiently large, but nontrivial, values of ε) under the assumption that Y and Z have the same alphabets. We also analyze the privacyconstrained guessing probability for two scenarios in which X, Y and Z are binary vectors. When X and Y are continuous random variables, we formulate the corresponding privacy-utility tradeoff in terms of sENSR(PXY , ε), the smallest normalized minimum mean squared-error (mmse) incurred in estimating Y from a Gaussian perturbation Z. Here the minimization is taken over a family of Gaussian perturbations Z for which the mmse of f(X) given Z is within a factor 1 – ε from the variance of f(X) for any non-constant real-valued function f. We derive tight upper and lower bounds for sENSR when Y is Gaussian. For general absolutely continuous random variables, we obtain a tight lower bound for sENSR(PXY , ε) in the high privacy regime, i.e., for small ε.
25 March 2019 in IEEE Transactions on Automatic Control
We consider finite model approximations of discrete-time partially observed Markov decision processes (POMDPs) under the discounted cost criterion. After converting the original partially observed stochastic control problem to a fully observed one on the belief space, the finite models are obtained through the uniform quantization of the state and action spaces of the belief space Markov decision process (MDP). Under mild assumptions on the components of the original model, it is established that the policies obtained from these finite models are nearly optimal for the belief space MDP, and so, for the original partially observed problem. The assumptions essentially require that the belief space MDP satisfies a mild weak continuity condition. We provide examples and introduce explicit approximation procedures for the quantization of the set of probability measures on the state space of POMDP (i.e., belief space).
27 July 2018 in IEEE Transactions on Automatic Control
We consider a distributed online optimization problem where, at each time, a group of agents choose their individual states, after which an individual cost function is revealed to each of them. The whole network then faces a regret according to the cumulative sum of costs incurred by the agents' chosen states, and each agent faces an individual regret according to the cumulative sum of costs incurred by the agent's state estimation, perceived as the whole network's chosen state. In order to tackle the minimization of the individual regret using only local information, we assume that the group of agents communicate over a fixed undirected connected graph. We then propose an online version of the Alternating Direction Method of Multipliers (ADMM) algorithm, distributed over the communication graph, that allows each agent to drive its individual average regret over time to zero.
7 April 2017 in IEEE Transactions on Information Theory
The optimal zero delay coding of a finite-state Markov source is considered. The existence and structure of optimal codes are studied using a stochastic control formulation. Prior results in the literature established the optimality of deterministic Markov (Walrand–Varaiya-type) coding policies for the finite time horizon problem, and the optimality of both deterministic nonstationary and randomized stationary policies for the infinite time horizon problem. Our main result here shows that for any irreducible and aperiodic Markov source with a finite alphabet, deterministic and stationary Markov coding policies are optimal for the infinite horizon problem. In addition, the finite block length (time horizon) performance of an optimal (stationary and Markov) coding policy is shown to approach the infinite time horizon optimum at a rate $O(1/T)$ . The results are extended to systems, where zero delay communication takes place across a noisy channel with noiseless feedback.
17 July 2019 in IEEE Transactions on Automatic Control
In this paper, we study the problem of achieving average consensus over a random time-varying sequence of directed graphs by extending the class of so-called push-sum algorithms to such random scenarios. Provided that an ergodicity notion, which we term the directed infinite flow property, holds and the auxiliary states of agents are uniformly bounded away from zero infinitely often, we prove the almost sure convergence of the evolutions of this class of algorithms to the average of initial states. Moreover, for a random sequence of graphs generated using a so-called time-varying B-irreducible probability matrix, we establish convergence rates for the proposed push-sum algorithm.