提升隐私统计估计效率，显著降低数据需求。
Privately Estimating Monotone Statistics in Polynomial Time
- 基于分块聚合改进隐私算法，可调参数平衡效率与精度。
- 相比传统方法，样本复杂度降低 t 倍，运行时间增加 e^t 倍。
- 适用于高维模型参数、特征值等隐私估计任务。
我们研究高效差分隐私算法用于估计单调统计量，即在新增观测时保持单调性的统计量。以分块聚合为起点，该经典框架将数据集划分为若干块，在每块上估计统计量，并私密聚合结果。尽管实用且通用，但此方法对数据量要求较高。针对单调统计量类别，我们改进该框架：相比分块聚合，新算法在样本复杂度上节省 t 倍，运行时间代价为 e^t 倍，其中 t > 0 为可调参数。我们进一步给出查询复杂度下界，证明算法在该任务中基本最优。作为应用，我们在隐私特征值估计、隐私损失估计及高维模型单参数估计（如线性回归）方面取得更优结果。
原文摘要 · Abstract (English)
We study efficient differentially private algorithms for estimating monotone statistics, i.e., statistics that are monotone under the addition of new observations. The starting point for our investigation is subsample-and-aggregate: a classical paradigm that partitions the dataset into blocks, estimates the statistic on each block, and then privately aggregates the estimates. While practical and generically applicable, this approach is quite data-hungry. We improve upon this framework for the class of monotone statistics -- compared to subsample-and-aggregate, our algorithms save a factor of $t$ in sample complexity and pay a factor of $e^t$ in running time, where $t>0$ is a tunable parameter. We complement our results with a query-complexity lower bound, showing that our algorithms are essentially optimal for this task. As an application, we obtain improved results for private eigenvalue estimation, private loss estimation, and privately estimating a single parameter of a high-dimensional model, e.g., in linear regression.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。