提出隐私保护下统计决策的量化风险下界,精准刻画罕见但严重失败。
Minimax Quantile Lower Bounds for Interactive Statistical Decision Making with Privacy
- 构建量化极小极大理论,连接分位数与期望,给出高概率下界工具。
- 在私有化均值估计和多臂赌博机中,得到含隐私因子的显式下界。
- 适合研究隐私机器学习、统计推断中鲁棒性与探索成本的学者。
极小极大风险和遗憾是基于期望的准则,无法捕捉罕见但后果严重的失败。为解决此问题,我们为交互式统计决策(ISDM)构建了δ-显式的极小极大分位数理论。首先建立极小极大分位数、下极小极大分位数与极小极大风险之间的结构关系,包括分位数到期望的转换,以及在可数个置信水平外严格与下极小极大分位数的等价性。随后,推导出两个交互式反向工具:高概率交互式Fano方法和高概率交互式Le Cam方法。通过限制可接受的决策类,该框架可处理互信息(MI)隐私。针对坐标系高斯私有化,导出一个两点模板,分离出隐私导致的方差膨胀。将该模板应用于高斯均值估计,并直接用于两臂高斯赌博机。进一步,推导出K臂高斯赌博机的极小极大分位数下界,表明交互式Fano方法能捕捉多个可能最优臂的探索代价。所得下界在置信水平δ和隐私预算上显式表达,平方误差均值估计呈现log(1/δ)/n缩放,两臂有界均值赌博机为√(T log(1/δ)),K臂情形为√(KT log(1/δ))型缩放,隐私通过高斯方差膨胀因子体现于私有问题中。
原文摘要 · Abstract (English)
Minimax risk and regret are expectation-based criteria and do not capture rare but consequential failures. To address this concern, we develop a $δ$-explicit minimax-quantile theory for interactive statistical decision making (ISDM). We first provide structural relations between minimax quantiles, lower minimax quantiles, and minimax risk. This includes a quantile-to-expectation conversion and an equivalence between strict and lower minimax quantiles outside a countable set of confidence levels. We then derive two converse tools for ISDM: a high-probability interactive Fano's method and a high-probability interactive Le Cam's method. Then, we show that mutual-information (MI) privacy can be handled in the same framework by restricting the admissible decision class. For coordinatewise Gaussian privatization, we derive a two-point template that isolates the privacy-induced variance inflation. We instantiate this template for Gaussian mean estimation, and use the same two-point strategy directly for two-armed Gaussian bandits. We then derive a minimax quantile lower bound for the $K$-armed Gaussian bandit problem, showing that the interactive Fano method captures the exploration cost over multiple possible best arms. The resulting lower bounds are explicit in the confidence level $δ$ and in the privacy budget for the private problems. They yield $\log(1/δ)/n$ scaling for squared-error Gaussian mean estimation, $\sqrt{T\log(1/δ)}$ scaling for two-armed bounded-mean Gaussian bandits, and $\sqrt{KT\log(1/δ)}$-type scaling for the $K$-armed bandits, with privacy appearing through a Gaussian variance-inflation factor for the private problems.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。