Working under a model of privacy in which data remains private even from the
statistician, we study the tradeoff between privacy guarantees and the risk of
the resulting statistical estimators. We develop private versions of classical
information-theoretic bounds, in particular those due to Le Cam, Fano, and
Assouad. These inequalities allow for a precise characterization of statistical
rates under local privacy constraints and the development of provably (minimax)
optimal estimation procedures. We provide a treatment of several canonical
families of problems: mean estimation and median estimation, generalized linear
models, and nonparametric density estimation. For all of these families, we
provide lower and upper bounds that match up to constant factors, and exhibit
new (optimal) privacy-preserving mechanisms and computationally efficient
estimators that achieve the bounds. Additionally, we present a variety of
experimental results for estimation problems involving sensitive data,
including salaries, censored blog posts and articles, and drug abuse; these
experiments demonstrate the importance of deriving optimal procedures.

本文研究数据保护与统计估计之间的平衡，开发了私有版本的信息熵界限，提出了一些新的基于隐私保护机制和计算效率估计，并给出了一些实验结果，证明了这些过程的重要性。

局部隐私估计的极小极大最优算法

Minimax Optimal Procedures for Locally Private Estimation

Differential entropy and log determinant of the covariance matrix of a
multivariate Gaussian distribution have many applications in coding,
communications, signal processing and statistical inference. In this paper we
consider in the high dimensional setting optimal estimation of the differential
entropy and the log-determinant of the covariance matrix. We first establish a
central limit theorem for the log determinant of the sample covariance matrix
in the high dimensional setting where the dimension $p(n)$ can grow with the
sample size $n$. An estimator of the differential entropy and the log
determinant is then considered. Optimal rate of convergence is obtained. It is
shown that in the case $p(n)/n \rightarrow 0$ the estimator is asymptotically
sharp minimax. The ultra-high dimensional setting where $p(n) > n$ is also
discussed.

本文研究了高维条件下多元高斯分布的差分熵、协方差矩阵的对数行列式的最优估计问题，建立了样本协方差矩阵对数行列式的中心极限定理，并给出了估计器的收敛率和局限性。

高维高斯分布样本协方差矩阵对数行列式定律与微分熵最优估计

Law of Log Determinant of Sample Covariance Matrix and Optimal  Estimation of Differential Entropy for High-Dimensional Gaussian  Distributions

We consider the problem of learning the optimal action-value function in the
discounted-reward Markov decision processes (MDPs). We prove a new PAC bound on
the sample-complexity of model-based value iteration algorithm in the presence
of the generative model, which indicates that for an MDP with N state-action
pairs and the discount factor \gamma\in[0,1) only
O(N\log(N/\delta)/((1-\gamma)^3\epsilon^2)) samples are required to find an
\epsilon-optimal estimation of the action-value function with the probability
1-\delta. We also prove a matching lower bound of \Theta
(N\log(N/\delta)/((1-\gamma)^3\epsilon^2)) on the sample complexity of
estimating the optimal action-value function by every RL algorithm. To the best
of our knowledge, this is the first matching result on the sample complexity of
estimating the optimal (action-) value function in which the upper bound
matches the lower bound of RL in terms of N, \epsilon, \delta and 1/(1-\gamma).
Also, both our lower bound and our upper bound significantly improve on the
state-of-the-art in terms of 1/(1-\gamma).

本文使用生成模型证明了在马尔可夫决策过程中，基于值迭代算法的样本复杂度 PAC 上限为 O (Nlog (N/δ)/((1-γ)³ε²))，其中 N 为状态 - 动作对的数量，γ 为折扣因子，ε 表示动作价值函数的 ε- 最优估计，δ 为概率。同时证明了在任何强化学习算法中，基于每个状态 - 动作对估计最优动作值函数的样本复杂度下限为 Θ(Nlog (N/δ)/((1-γ)³ε²))，该上限和下限在 N，ε、δ、1/(1-γ) 方面匹配。