  Consider statistical learning (e.g. discrete distribution estimation) with
local $\epsilon$-differential privacy, which preserves each data provider's
privacy locally, we aim to optimize statistical data utility under the privacy
constraints. Specifically, we study maximizing mutual information between a
provider's data and its private view, and give the exact mutual information
bound along with an attainable mechanism: $k$-subset mechanism as results. The
mutual information optimal mechanism randomly outputs a size $k$ subset of the
original data domain with delicate probability assignment, where $k$ varies
with the privacy level $\epsilon$ and the data domain size $d$. After analysing
the limitations of existing local private mechanisms from mutual information
perspective, we propose an efficient implementation of the $k$-subset mechanism
for discrete distribution estimation, and show its optimality guarantees over
existing approaches.
