Federated learning involves training statistical models over remote devices
or siloed data centers, such as mobile phones or hospitals, while keeping data
localized. Training in heterogeneous and potentially massive networks
introduces novel challenges that require a fundamental departure from standard
approaches for large-scale machine learning, distributed optimization, and
privacy-preserving data analysis. In this article, we discuss the unique
characteristics and challenges of federated learning, provide a broad overview
of current approaches, and outline several directions of future work that are
relevant to a wide range of research communities.

本文介绍联邦学习的独特特征和挑战，提供当前方法的概述，并概述了与各种研究社区相关的几个未来方向。

联邦学习：挑战、方法和未来方向

Federated Learning: Challenges, Methods, and Future Directions

Privacy-preserving data analysis is a rising challenge in contemporary
statistics, as the privacy guarantees of statistical methods are often achieved
at the expense of accuracy. In this paper, we investigate the tradeoff between
statistical accuracy and privacy in mean estimation and linear regression,
under both the classical low-dimensional and modern high-dimensional settings.
A primary focus is to establish minimax optimality for statistical estimation
with the $(\varepsilon,\delta)$-differential privacy constraint. To this end,
we find that classical lower bound arguments fail to yield sharp results, and
new technical tools are called for.
By refining the "tracing adversary" technique for lower bounds in the
theoretical computer science literature, we formulate a general lower bound
argument for minimax risks with differential privacy constraints, and apply
this argument to high-dimensional mean estimation and linear regression
problems. We also design computationally efficient algorithms that attain the
minimax lower bounds up to a logarithmic factor. In particular, for the
high-dimensional linear regression, a novel private iterative hard thresholding
pursuit algorithm is proposed, based on a privately truncated version of
stochastic gradient descent. The numerical performance of these algorithms is
demonstrated by simulation studies and applications to real data containing
sensitive information, for which privacy-preserving statistical methods are
necessary.

探讨平衡标准误差和隐私保护之间的关系，提出了最小化极限风险下的差分隐私约束的算法，包括隐私迭代硬阈值追踪，以及在实际数据集中表现出的数值表现。

隐私成本：具有差分隐私的参数估计的最佳收敛速率

The Cost of Privacy: Optimal Rates of Convergence for Parameter  Estimation with Differential Privacy

This paper aims at answering the following two questions in
privacy-preserving data analysis and publishing: What formal privacy guarantee
(if any) does $k$-anonymization provide? How to benefit from the adversary's
uncertainty about the data? We have found that random sampling provides a
connection that helps answer these two questions, as sampling can create
uncertainty. The main result of the paper is that $k$-anonymization, when done
"safely", and when preceded with a random sampling step, satisfies
$(\epsilon,\delta)$-differential privacy with reasonable parameters. This
result illustrates that "hiding in a crowd of $k$" indeed offers some privacy
guarantees. This result also suggests an alternative approach to output
perturbation for satisfying differential privacy: namely, adding a random
sampling step in the beginning and pruning results that are too sensitive to
change of a single tuple. Regarding the second question, we provide both
positive and negative results. On the positive side, we show that adding a
random-sampling pre-processing step to a differentially-private algorithm can
greatly amplify the level of privacy protection. Hence, when given a dataset
resulted from sampling, one can utilize a much large privacy budget. On the
negative side, any privacy notion that takes advantage of the adversary's
uncertainty likely does not compose. We discuss what these results imply in
practice.

本文研究在隐私保护数据分析和发布中，K - 匿名提供了怎样的形式隐私保证，并探索了如何从对方的数据不确定性中受益。结果表明，随机采样可以提供帮助，具有很好的隐私保护。通过在 K - 匿名之前添加随机采样步骤，可以以合理的参数满足差分隐私，从而为数据提供更好保护。同时，对于给定的采样数据集，可以利用更大的隐私预算。

关于抽样、匿名化和差分隐私：或者，k - 匿名遇上差分隐私

On Sampling, Anonymization, and Differential Privacy: Or,  k-Anonymization Meets Differential Privacy

Suppose we would like to know all answers to a set of statistical queries C
on a data set up to small error, but we can only access the data itself using
statistical queries. A trivial solution is to exhaustively ask all queries in
C. Can we do any better?
+ We show that the number of statistical queries necessary and sufficient for
this task is---up to polynomial factors---equal to the agnostic learning
complexity of C in Kearns' statistical query (SQ) model. This gives a complete
answer to the question when running time is not a concern.
+ We then show that the problem can be solved efficiently (allowing arbitrary
error on a small fraction of queries) whenever the answers to C can be
described by a submodular function. This includes many natural concept classes,
such as graph cuts and Boolean disjunctions and conjunctions.
While interesting from a learning theoretic point of view, our main
applications are in privacy-preserving data analysis:
Here, our second result leads to the first algorithm that efficiently
releases differentially private answers to of all Boolean conjunctions with 1%
average error. This presents significant progress on a key open problem in
privacy-preserving data analysis.
Our first result on the other hand gives unconditional lower bounds on any
differentially private algorithm that admits a (potentially
non-privacy-preserving) implementation using only statistical queries. Not only
our algorithms, but also most known private algorithms can be implemented using
only statistical queries, and hence are constrained by these lower bounds. Our
result therefore isolates the complexity of agnostic learning in the SQ-model
as a new barrier in the design of differentially private algorithms.

本研究提出了两个结果，第一个结果说明了在 Kearns' SQ 模型中，对一组统计查询 C 生成错误率较小的所有答案需要的统计查询次数是对偶学习复杂度；第二个结果能高效地解决问题，只要能够通过子模函数描述 C 的答案集。这两个结果对隐私保护数据分析产生了积极的应用，使其得到了重大进展。