A private learner is trained on a sample of labeled points and generates a
hypothesis that can be used for predicting the labels of newly sampled points
while protecting the privacy of the training set [Kasiviswannathan et al., FOCS
2008]. Research uncovered that private learners may need to exhibit
significantly higher sample complexity than non-private learners as is the case
with, e.g., learning of one-dimensional threshold functions [Bun et al., FOCS
2015, Alon et al., STOC 2019].
We explore prediction as an alternative to learning. Instead of putting
forward a hypothesis, a predictor answers a stream of classification queries.
Earlier work has considered a private prediction model with just a single
classification query [Dwork and Feldman, COLT 2018]. We observe that when
answering a stream of queries, a predictor must modify the hypothesis it uses
over time, and, furthermore, that it must use the queries for this
modification, hence introducing potential privacy risks with respect to the
queries themselves.
We introduce private everlasting prediction taking into account the privacy
of both the training set and the (adaptively chosen) queries made to the
predictor. We then present a generic construction of private everlasting
predictors in the PAC model. The sample complexity of the initial training
sample in our construction is quadratic (up to polylog factors) in the VC
dimension of the concept class. Our construction allows prediction for all
concept classes with finite VC dimension, and in particular threshold functions
with constant size initial training sample, even when considered over infinite
domains, whereas it is known that the sample complexity of privately learning
threshold functions must grow as a function of the domain size and hence is
impossible for infinite domains.

本研究提出了一种私有永久预测模型来解决传统私有模型中样本复杂度高的问题，其中预测是替代假设的，用来回答一系列分类查询，并使用预测修改假设，同时考虑对训练集和 (自适应选择的) 查询的隐私保护，而在 PAC 模型中提供通用建设，有效预测所有具有有限 VC 维的概念类，无论是有限域还是无限域。

私密长存预测

Private Everlasting Prediction

We present a private learner for halfspaces over an arbitrary finite domain
$X\subset \mathbb{R}^d$ with sample complexity $mathrm{poly}(d,2^{\log^*|X|})$.
The building block for this learner is a differentially private algorithm for
locating an approximate center point of $m>\mathrm{poly}(d,2^{\log^*|X|})$
points -- a high dimensional generalization of the median function. Our
construction establishes a relationship between these two problems that is
reminiscent of the relation between the median and learning one-dimensional
thresholds [Bun et al.\ FOCS '15]. This relationship suggests that the problem
of privately locating a center point may have further applications in the
design of differentially private algorithms.
We also provide a lower bound on the sample complexity for privately finding
a point in the convex hull. For approximate differential privacy, we show a
lower bound of $m=\Omega(d+\log^*|X|)$, whereas for pure differential privacy
$m=\Omega(d\log|X|)$.

介绍了针对任意有限域的高维半空间私有学习器，其样本复杂度为 poly (d,2^log*|X|)。其构造是基于在 m 个点中找到近似中心点的差分隐私算法，可用于设计差分隐私算法，并提供了在凸包中查找点的样本复杂度的下界。