Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userEstimating Sparse Discrete Distributions Under Local Privacy and Communication Constraints
53
0
0.0
(
0
)
Added by
Ziteng Sun
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We consider the problem of estimating sparse discrete distributions under local differential privacy (LDP) and communication constraints. We characterize the sample complexity for sparse estimation under LDP constraints up to a constant factor and the sample complexity under communication constraints up to a logarithmic factor. Our upper bounds under LDP are based on the Hadamard Response, a private coin scheme that requires only one bit of communication per user. Under communication constraints, we propose public coin schemes based on random hashing functions. Our tight lower bounds are based on the recently proposed method of chi squared contractions.
rate research
Read More
Much of the literature on differential privacy focuses on item-level privacy, where loosely speaking, the goal is to provide privacy per item or training example. However, recently many practical applications such as federated learning require preserving privacy for all items of a single user, which is much harder to achieve. Therefore understanding the theoretical limit of user-level privacy becomes crucial. We study the fundamental problem of learning discrete distributions over $k$ symbols with user-level differential privacy. If each user has $m$ samples, we show that straightforward applications of Laplace or Gaussian mechanisms require the number of users to be $mathcal{O}(k/(malpha^2) + k/epsilonalpha)$ to achieve an $ell_1$ distance of $alpha$ between the true and estimated distributions, with the privacy-induced penalty $k/epsilonalpha$ independent of the number of samples per user $m$. Moreover, we show that any mechanism that only operates on the final aggregate counts should require a user complexity of the same order. We then propose a mechanism such that the number of users scales as $tilde{mathcal{O}}(k/(malpha^2) + k/sqrt{m}epsilonalpha)$ and hence the privacy penalty is $tilde{Theta}(sqrt{m})$ times smaller compared to the standard mechanisms in certain settings of interest. We further show that the proposed mechanism is nearly-optimal under certain regimes. We also propose general techniques for obtaining lower bounds on restricted differentially private estimators and a lower bound on the total variation between binomial distributions, both of which might be of independent interest.
Intelligent reflection surface (IRS) is emerging as a promising technique for future wireless communications. Considering its excellent capability in customizing the channel conditions via energy-focusing and energy-nulling, it is an ideal technique for enhancing wireless communication security and privacy, through the theories of physical layer security and covert communications, respectively. In this article, we first present some results on applying IRS to improve the average secrecy rate in wiretap channels, to enable perfect communication covertness, and to deliberately create extra randomness in wireless propagations for hiding active wireless transmissions. Then, we identify multiple challenges for future research to fully unlock the benefits offered by IRS in the context of physical layer security and covert communications. With the aid of extensive numerical studies, we demonstrate the necessity of designing the amplitudes of the IRS elements in wireless communications with the consideration of security and privacy, where the optimal values are not always $1$ as commonly adopted in the literature. Furthermore, we reveal the tradeoff between the achievable secrecy performance and the estimation accuracy of the IRSs channel state information (CSI) at both the legitimate and malicious users, which presents the fundamental resource allocation challenge in the context of IRS-aided physical layer security. Finally, a passive channel estimation methodology exploiting deep neural networks and scene images is discussed as a potential solution to enabling CSI availability without utilizing resource-hungry pilots. This methodology serves as a visible pathway to significantly improving the covert communication rate in IRS-aided wireless networks.
In this paper, we propose a multiple-input multipleoutput (MIMO) transmission strategy that is closer to the Shannon limit than the existing strategies. Different from most existing strategies which only consider uniformly distributed discrete input signals, we present a unified framework to optimize the MIMO precoder and the discrete input signal distribution jointly. First, a general model of MIMO transmission under discrete input signals and its equivalent formulation are established. Next, in order to maximize the mutual information between the input and output signals, we provide an algorithm that jointly optimizes the precoder and the input distribution. Finally, we compare our strategy with other existing strategies in the simulation. Numerical results indicate that our strategy narrows the gap between the mutual information and Shannon limit, and shows a lower frame error rate in simulation.
Private collection of statistics from a large distributed population is an important problem, and has led to large scale deployments from several leading technology companies. The dominant approach requires each user to randomly perturb their input, leading to guarantees in the local differential privacy model. In this paper, we place the various approaches that have been suggested into a common framework, and perform an extensive series of experiments to understand the tradeoffs between different implementation choices. Our conclusion is that for the core problems of frequency estimation and heavy hitter identification, careful choice of algorithms can lead to very effective solutions that scale to millions of users
Sensitive statistics are often collected across sets of users, with repeated collection of reports done over time. For example, trends in users private preferences or software usage may be monitored via such reports. We study the collection of such statistics in the local differential privacy (LDP) model, and describe an algorithm whose privacy cost is polylogarithmic in the number of changes to a users value. More fundamentally---by building on anonymity of the users reports---we also demonstrate how the privacy cost of our LDP algorithm can actually be much lower when viewed in the central model of differential privacy. We show, via a new and general privacy amplification technique, that any permutation-invariant algorithm satisfying $varepsilon$-local differential privacy will satisfy $(O(varepsilon sqrt{log(1/delta)/n}), delta)$-central differential privacy. By this, we explain how the high noise and $sqrt{n}$ overhead of LDP protocols is a consequence of them being significantly more private in the central model. As a practical corollary, our results imply that several LDP-based industrial deployments may have much lower privacy cost than their advertised $varepsilon$ would indicate---at least if reports are anonymized.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
