Differential Privacy with Dependent Data

具有依賴數(shù)據(jù)的差分隱私

https://arxiv.org/pdf/2511.18583

摘要
依賴數(shù)據(jù)是社會(huì)科學(xué)和健康科學(xué)中許多統(tǒng)計(jì)研究的基礎(chǔ)，而這些研究通常涉及敏感或私密信息。差分隱私（DP），特別是用戶級(jí)差分隱私（user-level DP），為處理依賴數(shù)據(jù)提供了一種自然的隱私需求形式化方法，其中每個(gè)個(gè)體向數(shù)據(jù)集中提供多個(gè)觀測(cè)值。然而，例如通過重復(fù)測(cè)量引入的依賴性，對(duì)現(xiàn)有在DP約束下的統(tǒng)計(jì)理論構(gòu)成了挑戰(zhàn)。在獨(dú)立同分布（i.i.d.）設(shè)定下，帶噪聲的Winsorized均值估計(jì)器已被證明在標(biāo)準(zhǔn)（項(xiàng)級(jí)）和用戶級(jí)DP下對(duì)均值 μ ∈ ?? 的估計(jì)具有極小極大最優(yōu)性。然而，其在潛在依賴觀測(cè)值上的行為此前尚未被研究。我們填補(bǔ)了這一空白，證明Winsorized均值估計(jì)器在弱依賴條件下同樣適用于有界和無(wú)界數(shù)據(jù)，并可獲得類似于其i.i.d.情形下的漸近與有限樣本保證。為此，我們通過觀測(cè)值聯(lián)合分布上的對(duì)數(shù)Sobolev不等式（log-Sobolev inequalities）來形式化依賴結(jié)構(gòu)。這使我們能夠?qū)arwa與Vadhan（2018）提出的穩(wěn)定直方圖方法推廣至非i.i.d.設(shè)定，并用于估計(jì)Winsorized估計(jì)器的私有投影區(qū)間。我們所提出的項(xiàng)級(jí)均值估計(jì)器的保證可進(jìn)一步推廣至用戶級(jí)均值估計(jì)，并通過隨機(jī)響應(yīng)直方圖遷移至本地模型（local model）。以這些均值估計(jì)器為基礎(chǔ)，我們進(jìn)一步將其擴(kuò)展至隨機(jī)效應(yīng)模型、縱向線性回歸和非參數(shù)回歸。因此，本工作構(gòu)成了對(duì)依賴數(shù)據(jù)下差分隱私系統(tǒng)性研究的第一步。

1 引言
差分隱私（DP）工具已在工業(yè)界和政府機(jī)構(gòu)的眾多應(yīng)用中大規(guī)模部署（Erlingsson等，2014；Ding等，2017；Tang等，2017；Garfinkel等，2019）。標(biāo)準(zhǔn)DP框架旨在發(fā)布統(tǒng)計(jì)量的同時(shí)保護(hù)單個(gè)數(shù)據(jù)點(diǎn)，其假設(shè)每個(gè)個(gè)體僅向大小為n的數(shù)據(jù)集貢獻(xiàn)一個(gè)數(shù)據(jù)點(diǎn)。我們將遵循文獻(xiàn)，稱這種標(biāo)準(zhǔn)方法為項(xiàng)級(jí)DP（item-level DP）。在此框架下，隱私通過發(fā)布經(jīng)過校準(zhǔn)的隨機(jī)化輸出來實(shí)現(xiàn)，使得任何單個(gè)數(shù)據(jù)點(diǎn)對(duì)輸出計(jì)算的影響被隨機(jī)化所掩蓋（Dwork等，2006；Dwork與Roth，2014）。

近期被稱為用戶級(jí)差分隱私（user-level differential privacy, uDP）的一系列工作研究了每個(gè)用戶向數(shù)據(jù)集貢獻(xiàn)多個(gè)觀測(cè)值的情形（Liu等，2020；Levy等，2021；Narayanan等，2022；Acharya等，2023；Bassily與Sun，2023；Ghazi等，2023；Asi與Liu，2024）。為簡(jiǎn)化起見，我們假設(shè)每位用戶貢獻(xiàn)T個(gè)數(shù)據(jù)點(diǎn)。此時(shí)，自然目標(biāo)是保護(hù)某用戶貢獻(xiàn)的所有T個(gè)數(shù)據(jù)點(diǎn)。挑戰(zhàn)在于，標(biāo)準(zhǔn)DP技術(shù)僅保護(hù)單個(gè)數(shù)據(jù)點(diǎn)，若直接應(yīng)用，要么導(dǎo)致隱私保證隨用戶貢獻(xiàn)點(diǎn)數(shù)增加而退化，要么在利用DP的群組性質(zhì)（group property）構(gòu)建算法時(shí)，為獲得正確隱私保證而添加過多噪聲（Dwork與Roth，2014，定理2.2）。

本文引入了適用于依賴數(shù)據(jù)的DP工具，特別關(guān)注縱向數(shù)據(jù)（也常稱為面板數(shù)據(jù)），即在一段時(shí)間內(nèi)從相同個(gè)體收集的多個(gè)依賴觀測(cè)值�？v向數(shù)據(jù)在社會(huì)科學(xué)和醫(yī)學(xué)應(yīng)用中極為重要（Diggle，2002；Baltagi，2008；Fitzmaurice等，2012；Hsiao，2022）。盡管用戶級(jí)DP似乎是縱向數(shù)據(jù)的自然隱私定義，但這一聯(lián)系在文獻(xiàn)中尚未被充分挖掘。事實(shí)上，在差分隱私約束下對(duì)依賴數(shù)據(jù)建模的研究相對(duì)較少。

我們的工作主要受Karwa與Vadhan（2018）的啟發(fā)，他們的算法構(gòu)成了我們所有方法的基礎(chǔ)，同時(shí)也受到新興uDP領(lǐng)域近期工作的激勵(lì)，特別是Levy等（2021）和Kent等（2024）的研究。

我們的主要貢獻(xiàn)可概括為以下關(guān)鍵點(diǎn)：

(a) 依賴且無(wú)界數(shù)據(jù)的DP：我們的工作似乎是首個(gè)研究多個(gè)DP算法在依賴觀測(cè)值上表現(xiàn)的工作。具體而言，我們引入了“對(duì)數(shù)Sobolev依賴”（log-Sobolev dependence）——一種通過對(duì)觀測(cè)值聯(lián)合分布施加對(duì)數(shù)Sobolev不等式來刻畫依賴性的概念，用以替代典型的i.i.d.假設(shè)。我們方法的核心是一個(gè)受Karwa與Vadhan（2018）啟發(fā)的Winsorized均值估計(jì)算法，該算法最初為高斯i.i.d.數(shù)據(jù)設(shè)計(jì)。在額外處理依賴性的同時(shí)，我們的算法繼承了其兩項(xiàng)優(yōu)點(diǎn)：支持無(wú)界觀測(cè)值的估計(jì)，且無(wú)需事先了解未知均值。

(b) 縱向數(shù)據(jù)的DP：我們提出了多種適用于依賴數(shù)據(jù)（尤其是縱向數(shù)據(jù)）的用戶級(jí)DP估計(jì)算法，允許用戶之間及時(shí)間維度上的依賴。這顯著偏離了絕大多數(shù)DP算法理論分析所依賴的i.i.d.假設(shè)，即便在uDP設(shè)定下亦如此（Levy等，2021；Kent等，2024；Agarwal等，2025）。在對(duì)數(shù)Sobolev依賴條件下，我們的算法被證明能達(dá)到最優(yōu)的有限樣本誤差率。該條件足夠通用，涵蓋了一系列此前文獻(xiàn)中未被研究的有趣統(tǒng)計(jì)模型，包括非參數(shù)回歸、簡(jiǎn)單隨機(jī)效應(yīng)模型，以及具有依賴誤差項(xiàng)的縱向線性回歸。

(c) 直方圖學(xué)習(xí)：我們利用Bobkov與G?tze（2010）提出的Dvoretzky–Kiefer–Wolfowitz型不等式，將Vadhan（2017）的直方圖估計(jì)器分析擴(kuò)展至對(duì)數(shù)Sobolev依賴數(shù)據(jù)。這是構(gòu)建我們均值估計(jì)的關(guān)鍵中間結(jié)果，因?yàn)樵赪insorized均值估計(jì)器中，需首先粗略估計(jì)一個(gè)長(zhǎng)度為O(log n)的私有投影區(qū)間的中點(diǎn)，而該步驟調(diào)用了私有直方圖。這一微小調(diào)整顯著拓展了Vadhan（2017）所引入技術(shù)的適用范圍，使其不僅限于i.i.d.高斯數(shù)據(jù)，甚至在項(xiàng)級(jí)設(shè)定下也能處理依賴數(shù)據(jù)。

(d) 項(xiàng)級(jí)與用戶級(jí)DP：一個(gè)概念上有趣的貢獻(xiàn)在于闡明了所有現(xiàn)有uDP算法均基于某個(gè)已知的項(xiàng)級(jí)DP算法構(gòu)建。這一聯(lián)系使我們能更深入地理解現(xiàn)有的期望意義下的極小極大DP與uDP下界。為此，我們對(duì)Karwa–Vadhan型投影估計(jì)器進(jìn)行了期望分析，該分析即使對(duì)i.i.d.高斯數(shù)據(jù)而言似乎也是新穎的。該界表明，uDP中一個(gè)不可能性結(jié)果（即當(dāng)每位用戶的觀測(cè)數(shù)T → ∞時(shí)無(wú)法學(xué)習(xí)，Levy等，2021，定理8）與項(xiàng)級(jí)設(shè)定下當(dāng)方差過快趨于零時(shí)的學(xué)習(xí)不可能性相關(guān)聯(lián)。由此，我們識(shí)別出現(xiàn)有項(xiàng)級(jí)與用戶級(jí)下界之間的脫節(jié)（Cai等，2021；Levy等，2021）。

(e) 本地DP（Local DP）：盡管本文主要聚焦于假設(shè)存在可信數(shù)據(jù)管理者的中心化DP模型，我們將所有結(jié)果擴(kuò)展至本地DP模型——在此模型中，中央服務(wù)器不可信，隱私機(jī)制在數(shù)據(jù)收集階段即被強(qiáng)制執(zhí)行（Kasiviswanathan等，2011；Duchi等，2018）。具體而言，我們展示了如何將中心化DP算法中的直方圖替換為其本地對(duì)應(yīng)版本，從而在本地模型下獲得近似最優(yōu)的估計(jì)器，同時(shí)保留前述所有優(yōu)良性質(zhì)。這意味著，在用戶級(jí)本地DP（uLDP）框架下，我們?nèi)钥商幚頍o(wú)界觀測(cè)值，以及用戶間及其觀測(cè)值之間的依賴關(guān)系。

1.1 相關(guān)工作

對(duì)均值、中位數(shù)等位置參數(shù)的私有估計(jì)是差分隱私（DP）文獻(xiàn)中頻繁研究的核心統(tǒng)計(jì)問題。首個(gè)DP均值估計(jì)器可追溯至Dwork等（2006）中對(duì)帶噪聲求和的應(yīng)用，而Dwork與Lei（2009）則獲得了私有截尾均值和中位數(shù)估計(jì)器的漸近保證。Smith（2011）似乎是最早提出并研究一種帶噪聲的兩階段Winsorized均值估計(jì)器漸近性質(zhì)的工作，該估計(jì)器與我們所考慮的類似：即首先粗略估計(jì)均值，將數(shù)據(jù)投影到圍繞該估計(jì)值的一個(gè)區(qū)間內(nèi)，然后添加與所得有限敏感度相匹配的噪聲以實(shí)現(xiàn)隱私保護(hù)。Bun等（2013）、Steinke與Ullman（2017）、Foygel Barber與Duchi（2014）、Bun與Steinke（2019）以及Cai等（2021）推導(dǎo)了均值估計(jì)的下界。特別是，Cai等（2021）針對(duì)一種缺乏數(shù)據(jù)驅(qū)動(dòng)投影區(qū)間的Winsorized均值估計(jì)器，給出了期望意義下的極小極大上下界，其收斂速率與Steinke與Ullman（2017）的結(jié)果一致。相比之下，Karwa與Vadhan（2018）開啟了一條研究Winsorized均值估計(jì)器“概率意義下”（in-probability）保證的新方向，該方法既不要求觀測(cè)值有界，也不要求均值有界。他們的算法基于一個(gè)(ε, δ)-DP的“穩(wěn)定”直方圖估計(jì)器，用于為一維高斯分布的均值尋找一個(gè)私有置信區(qū)間。隨后，Kamath等（2019）將該方法推廣至協(xié)方差矩陣未知的多元高斯分布，Kamath等（2020）進(jìn)一步將其擴(kuò)展至重尾分布。

我們注意到，還有大量其他工作研究私有均值和中位數(shù)估計(jì)問題，尤其致力于避免假設(shè)樣本空間有界，并在許多情況下與統(tǒng)計(jì)學(xué)界關(guān)于魯棒性的研究建立聯(lián)系（Avella-Medina與Brunel，2020；Avella-Medina，2020，2021；Avella-Medina等，2023；Li等，2023；Yu等，2024；Ramsay等，2022），以及計(jì)算機(jī)科學(xué)領(lǐng)域的相關(guān)研究（Tzamos等，2020；Liu等，2021，2022；Hopkins等，2023；Alabi等，2023；Chhor與Sentenac，2023）。這些構(gòu)造與我們的工作關(guān)聯(lián)較弱。

用戶級(jí)DP最早由McMahan等（2017）提出，用于保障聯(lián)邦學(xué)習(xí)中語(yǔ)言模型訓(xùn)練的隱私。此后，該定義被推廣至該背景下的其他工作（Wang等，2019；Augenstein等，2020）以及SQL數(shù)據(jù)庫(kù)中的用戶級(jí)私有數(shù)據(jù)聚合（Wilson等，2020）。在經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化背景下，Amin等（2019）、Epasto等（2020）、Levy等（2021）、Narayanan等（2022）以及Kent等（2024）研究了用戶數(shù)量n、每位用戶的觀測(cè)數(shù)T與實(shí)現(xiàn)用戶級(jí)隱私所需噪聲量之間的相互作用，并得出了相應(yīng)的統(tǒng)計(jì)結(jié)果。近期，Agarwal等（2025）和Zhao等（2024）在中心化模型中首次提出了適用于獨(dú)立用戶且具有獨(dú)立無(wú)界觀測(cè)值的用戶級(jí)均值估計(jì)器。

本地差分隱私（local differential privacy）下的估計(jì)問題已在廣泛的統(tǒng)計(jì)任務(wù)中被探索，包括均值估計(jì)、密度估計(jì)、非參數(shù)回歸和假設(shè)檢驗(yàn)等（僅舉幾例：Wasserman與Zhou，2010；Duchi等，2018；Gaboardi與Rogers，2018；Butucea等，2020；Berrett與Butucea，2020；Berrett等，2021；Sart，2023；Pensia等，2024）。特別是，用戶級(jí)本地差分隱私近期在Girgis等（2022）、Acharya等（2023）以及Kent等（2024）的研究中得到了探討。

最后，我們注意到已有一些初步文獻(xiàn)研究具有特定時(shí)間結(jié)構(gòu)的差分隱私問題。這包括變點(diǎn)檢測(cè)（Zhang等，2021；Berrett與Yu，2021；Li等，2022）和多臂老虎機(jī)（Mishra與Thakurta，2015；Sajed與Sheffet，2019；Hu與Hegde，2022；Ou等，2024）等問題，這些問題通常在項(xiàng)級(jí)DP和獨(dú)立觀測(cè)假設(shè)下進(jìn)行研究。此外，也有一些關(guān)于時(shí)間序列的DP初步工作，同樣從項(xiàng)級(jí)DP視角切入。例如，Zhang等（2022）考慮了具有序列AR(1)結(jié)構(gòu)的參數(shù)化方法，Amorino等（2025）研究了擴(kuò)散過程，而Kroll（2024）及Butucea等（2025）則探討了非參數(shù)譜密度估計(jì)問題。

2 預(yù)備知識(shí)
我們首先介紹本文通篇所使用的記號(hào)，并給出差分隱私與對(duì)數(shù)Sobolev不等式的基本背景。在本節(jié)末尾，我們將引入用于建模依賴數(shù)據(jù)（尤其是縱向數(shù)據(jù)）的主要依賴性假設(shè)。

2.1 記號(hào)

2.2 差分隱私

存在若干種相互競(jìng)爭(zhēng)的差分隱私（DP）定義（參見 Mironov (2017)；Dong 等 (2022)；Dwork 和 Rothblum (2016)；Bun 和 Steinke (2016)；Dwork 等 (2006)），但我們將采用最常用的定義——由 Dwork 等 (2006) 引入的 (ε, δ)-DP。在下文的定義中，我們用 (??) 表示 ?? 上的 Borel σ-代數(shù)。

上述拉普拉斯機(jī)制以及Dwork和Roth（2014）中提出的其他機(jī)制構(gòu)成了差分隱私（DP）的基礎(chǔ)。它們可以通過組合簡(jiǎn)單DP算法的輸出，構(gòu)建出更復(fù)雜的DP算法。一個(gè)輸出多個(gè)DP算法組合結(jié)果的算法，其有效隱私預(yù)算可通過以下組合定理進(jìn)行量化。

2.3 對(duì)數(shù)Sobolev不等式

建立對(duì)數(shù)Sobolev不等式的一種通用方法是通過其與概率測(cè)度密度（相對(duì)于Lebesgue測(cè)度）的曲率之間的關(guān)系。具體而言，強(qiáng)對(duì)數(shù)凹性（strong log-concavity）通過Bakry–émery準(zhǔn)則可直接推出對(duì)數(shù)Sobolev不等式，該準(zhǔn)則見附錄A；參見定理A.1。

以下的Lipschitz集中不等式將成為我們?cè)谝蕾囆詶l件下推導(dǎo)算法的主要概率工具。

2.4 對(duì)數(shù)Sobolev依賴性

據(jù)我們所知，現(xiàn)有所有針對(duì)項(xiàng)級(jí)差分隱私估計(jì)器的理論分析均依賴于簡(jiǎn)化版的獨(dú)立同分布（i.i.d.）假設(shè)，該假設(shè)與我們接下來將陳述的假設(shè)類似或更強(qiáng)。

請(qǐng)注意，假設(shè)2.7并未像差分隱私文獻(xiàn)中常見的那樣，要求數(shù)據(jù)具有已知的有界定義域。我們將看到，我們的估計(jì)器允許這種放寬后的i.i.d.假設(shè)，并表明對(duì)現(xiàn)有方法稍作修改即可在無(wú)界數(shù)據(jù)域下表現(xiàn)良好。這是本分析的一個(gè)有趣的副產(chǎn)品。然而，我們的主要貢獻(xiàn)在于明確允許數(shù)據(jù)存在依賴性。

3 直方圖估計(jì)器

3.1 隱私性與效用性保證

我們注意到，盡管算法2的隱私性在文獻(xiàn)中已有記載，但為完整性起見，我們?cè)谶B續(xù)設(shè)定下提供了該結(jié)果的證明；參見引理C.1。事實(shí)上，這一情形并未被Vadhan（2017）的定理7.3.5正式涵蓋。

Karwa與Vadhan（2018）似乎是最早將穩(wěn)定直方圖用于差分隱私均值估計(jì)的作者。更具體地說，他們利用這一思想對(duì)獨(dú)立同分布高斯隨機(jī)變量的均值和方差進(jìn)行私有估計(jì)。他們的結(jié)果依賴于以下直方圖效用性保證。

我們對(duì)基于穩(wěn)定性的直方圖估計(jì)器的分析，將Karwa和Vadhan（2018）的工作推廣至依賴觀測(cè)值的情形。具體而言，我們沿用其證明策略，將他們的引理2.3擴(kuò)展至滿足對(duì)數(shù)Sobolev不等式的觀測(cè)值 X n ∈ R n 。這導(dǎo)出了以下引理3.2，其證明見附錄C。

3.2 尋找私有的數(shù)據(jù)驅(qū)動(dòng)投影區(qū)間

我們直方圖學(xué)習(xí)算法的主要應(yīng)用是找到數(shù)據(jù)驅(qū)動(dòng)的投影區(qū)間，供我們的主均值估計(jì)器使用。其思路是尋找一個(gè)緩慢發(fā)散的區(qū)間，以高概率包含所有觀測(cè)值。這一方法遵循Karwa和Vadhan（2018）的設(shè)計(jì)藍(lán)圖。投影區(qū)間將由包含大部分質(zhì)量的區(qū)間及其兩個(gè)相鄰區(qū)間組成。這一簡(jiǎn)單算法屬于更廣泛的私有中點(diǎn)算法家族，此類算法廣泛應(yīng)用于中心化與本地化的項(xiàng)級(jí)及用戶級(jí)DP均值估計(jì)文獻(xiàn)中（Smith, 2011; Kamath等, 2020; Levy等, 2021; Kent等, 2024; Agarwal等, 2025）。

算法3返回一個(gè)區(qū)間，其區(qū)間中點(diǎn)是具有最大估計(jì)質(zhì)量的穩(wěn)定直方圖區(qū)間的中心（參見Karwa和Vadhan（2018），算法1）。我們的創(chuàng)新之處在于對(duì)該算法的分析，這導(dǎo)致了以下引理3.4（證明見附錄C.2）。該引理利用 ( τ , γ ) ∞ ∞ -集中性和由Bobkov與G?tze（2010）提出的DKW型不等式所支持的引理3.2，推廣了Karwa和Vadhan（2018）的定理3.1。最重要的是，這允許在對(duì)數(shù)Sobolev依賴模型內(nèi)存在觀測(cè)值之間的依賴關(guān)系，同時(shí)也允許觀測(cè)值非同分布。此外，若使用原始的DKW不等式，我們的證明策略還可將Karwa和Vadhan（2018）針對(duì)獨(dú)立同分布高斯數(shù)據(jù)的分析推廣至一般的獨(dú)立同分布及 ( τ , γ ) ∞ -集中觀測(cè)值。

4 依賴數(shù)據(jù)下的項(xiàng)級(jí)差分隱私估計(jì)

我們已準(zhǔn)備好介紹我們的主要算法。我們的方案遵循私有均值估計(jì)中一種流行的思想：計(jì)算一個(gè)Winsorized均值估計(jì)器，并通過拉普拉斯機(jī)制使其滿足隱私性。這一方法在項(xiàng)級(jí)和用戶級(jí)均值估計(jì)的文獻(xiàn)中都很常見（參見，例如，Smith (2011)；Karwa 和 Vadhan (2018)；Levy 等 (2021)；Kent 等 (2024)；Agarwal 等 (2025)）。

我們的主要理論結(jié)果是定理4.2和4.3中給出的有限樣本誤差界與期望意義下的均方誤差（MSE）界。這些主要結(jié)果以及為中間算法推導(dǎo)出的所有保證，均是在對(duì)數(shù)Sobolev依賴性假設(shè)下獲得的。我們分析的一個(gè)有趣副產(chǎn)品是：即使在獨(dú)立同分布（i.i.d.）設(shè)定下，我們也推廣了一些已知結(jié)果，允許數(shù)據(jù)域和參數(shù)空間均為無(wú)界。

4.1 均值估計(jì)器

算法4展示了我們的主要均值估計(jì)流程。它是一個(gè)一維的帶噪聲Winsorized均值估計(jì)器，在對(duì)數(shù)Sobolev依賴性下被證明表現(xiàn)良好。該估計(jì)器依賴于算法3提供的私有范圍
對(duì)數(shù)據(jù)進(jìn)行投影。

4.2 理論保證
4.2.1 高概率界

我們將定理D.1中的效用性保證轉(zhuǎn)化為算法5中估計(jì)器均方誤差（MSE）的有限樣本上界。以下定理4.2中的估計(jì)誤差由兩項(xiàng)之和來刻畫：統(tǒng)計(jì)誤差與隱私代價(jià)。該定理的證明見附錄D.1.1。

4.2.2 期望意義下的分析

雖然本工作的主要關(guān)注點(diǎn)在于非漸近界（如定理4.2的有限樣本保證及其在第5節(jié)中的具體應(yīng)用），我們也在定理4.3中提供了一個(gè)期望意義下的MSE上界。這樣做的目的是為了使我們的估計(jì)器分析能夠與現(xiàn)有文獻(xiàn)中的上下界相比較，特別是用戶級(jí)DP文獻(xiàn)中的推論5（Levy等，2021），以及項(xiàng)級(jí)DP文獻(xiàn)中的定理3.1或定理3.2（Cai等，2021）。這使得我們可以直接與已知的獨(dú)立同分布情形下的結(jié)果進(jìn)行比較；特別地，如定理4.3所示，在弱依賴條件下，我們能夠匹配獨(dú)立同分布情形下的收斂速率。

4.3 極小極大最優(yōu)性

為評(píng)估我們均值估計(jì)器的最優(yōu)性，我們將我們的上界與Cai等（2021）給出的統(tǒng)計(jì)極小極大下界進(jìn)行比較。他們的結(jié)果是在項(xiàng)級(jí)DP設(shè)定下針對(duì)每個(gè)元素均為獨(dú)立同分布ρ-次高斯變量的觀測(cè)值
得到的。為便于闡述，我們?cè)谙路街厥鏊麄兊亩ɡ�。我們將看到，該下界意味著我們的均值估�?jì)器在項(xiàng)級(jí)DP的獨(dú)立同分布設(shè)定下是極小極大最優(yōu)的。

4.4 非參數(shù)回歸的擴(kuò)展

我們注意到，私有非參數(shù)回歸問題已在中心化DP模型下針對(duì)獨(dú)立同分布數(shù)據(jù)被研究過（參見Awan等，2020；Golowich，2021；Cai等，2023），也在本地DP模型下被研究過（參見Berrett等，2021；Gy?rfi與Kroll，2025）。我們?cè)试S觀測(cè)值之間存在相關(guān)性，并希望關(guān)注其對(duì)估計(jì)的影響。為簡(jiǎn)化起見，我們將函數(shù)空間 F F 限制為有界利普希茨函數(shù)空間。該設(shè)定在定義4.7中形式化給出。

給定觀測(cè)值后，底層函數(shù) f f 通常使用經(jīng)典的核方法估計(jì)器進(jìn)行估計(jì)，例如最近鄰法、Priestley-Chao法、Nadaraya-Watson法、Gasser-Müller法或局部多項(xiàng)式估計(jì)器�；蛘�，該任務(wù)也可轉(zhuǎn)化為利用傅里葉變換或小波變換進(jìn)行均值估計(jì)，或通過光滑樣條進(jìn)行線性回歸（參見Tsybakov，2008）。在差分隱私下的非參數(shù)估計(jì)主要依賴于這些重新表述方法，這可見于Duchi等（2018）第5.2.2節(jié)、Cai等（2025）或Cai等（2023）第6節(jié)。在此，我們表明，在我們的固定設(shè)計(jì)設(shè)定下，可以基于經(jīng)典非參數(shù)Priestley-Chao回歸估計(jì)器（定義4.8中引入，由Priestley與Chao于1972年提出）構(gòu)建最優(yōu)逐點(diǎn)DP估計(jì)器。

5 依賴數(shù)據(jù)下的用戶級(jí)差分隱私估計(jì)器

請(qǐng)記住，在用戶級(jí)差分隱私（DP）設(shè)定中，每個(gè) n n 名用戶貢獻(xiàn)的 T T 個(gè)觀測(cè)值需作為一個(gè)整體受到保護(hù)。盡管我們所知的所有用戶級(jí)DP理論工作均假設(shè)用戶間及時(shí)間維度上的數(shù)據(jù)獨(dú)立且有界，但我們的結(jié)果同時(shí)覆蓋無(wú)界觀測(cè)值，并允許在 n n 名用戶及其各自的 T T 個(gè)觀測(cè)值之間存在依賴性。

5.1 用戶級(jí)均值估計(jì)

5.1.1 期望意義下的分析

5.2 隨機(jī)效應(yīng)位置模型

隨機(jī)效應(yīng)模型常用于聚類數(shù)據(jù)或相關(guān)數(shù)據(jù)的分析（Pinheiro 和 Bates，2000；Fahrmeir 和 Tutz，2001；Demidenko，2013）。在此，我們將討論限定于定義5.8中所給出的一維用戶級(jí)隨機(jī)效應(yīng)位置模型。我們這樣做是為了完全聚焦于由隨機(jī)效應(yīng)所引入的用戶之間的依賴性，并考察這種依賴性對(duì)我們Winsorized均值估計(jì)器收斂速率的影響。然而需要注意的是，第4節(jié)中的理論保證足夠強(qiáng)大，也能夠處理如第5.3小節(jié)所述線性回歸設(shè)定中的隨機(jī)效應(yīng)。

除了在同組 g g 內(nèi)用戶之間引入依賴性的隨機(jī)效應(yīng)外，定義5.8中的模型還包含用戶之間相互獨(dú)立、但在同一用戶隨時(shí)間變化的觀測(cè)值之間存在相關(guān)性的噪聲。因此，該模型同時(shí)包含了用戶間（inter-user）和用戶內(nèi)（intra-user）的依賴性。
盡管如此，我們將看到定義5.8中模型的分析是簡(jiǎn)單的，因?yàn)樗杀灰暈榈?.1小節(jié)所涵蓋的用戶級(jí)均值估計(jì)問題的一個(gè)特例。因此，我們只需證明由此得到的用戶級(jí)數(shù)據(jù)矩陣滿足對(duì)數(shù)Sobolev依賴性。我們?cè)谝韵乱碇型瓿蛇@一證明。

5.3 面向縱向數(shù)據(jù)的用戶級(jí)差分隱私線性回歸

盡管關(guān)于項(xiàng)級(jí)差分隱私線性回歸的文獻(xiàn)正在不斷增長(zhǎng)（Wang, 2018；Alabi 等, 2020；Liu 等, 2023；Avella-Medina 等, 2023；Brown 等, 2024；Bombari 等, 2025），但極少有工作涉及用戶級(jí)DP下的線性回歸問題，且尚未有任何研究針對(duì)依賴型縱向數(shù)據(jù)。在此，我們應(yīng)用我們的Winsorized均值估計(jì)器，證明其可用于估計(jì)定義5.13中所形式化的用戶級(jí)線性回歸模型中的回歸系數(shù)
。

由于我們所考慮的uDP估計(jì)器的非私有對(duì)應(yīng)版本已不再是標(biāo)準(zhǔn)最小二乘估計(jì)器，因此很自然會(huì)思考該估計(jì)器相對(duì)于標(biāo)準(zhǔn)最小二乘和廣義最小二乘方法的效率如何。下一個(gè)引理澄清了這一點(diǎn)，其證明見附錄E.3。

6 本地差分隱私的擴(kuò)展

截至目前所討論的中心化DP模型要求數(shù)據(jù)項(xiàng)/用戶信任一個(gè)中央服務(wù)器來聚合并私有化他們的數(shù)據(jù)。當(dāng)這種信任不存在時(shí)，數(shù)據(jù)項(xiàng)或用戶自身必須對(duì)數(shù)據(jù)進(jìn)行私有化處理。這種設(shè)定被稱為本地差分隱私（local model of DP）（Kasiviswanathan 等，2011；Duchi 等，2018）。

算法6中的隨機(jī)響應(yīng)機(jī)制是首個(gè)用于確保這種本地?cái)?shù)據(jù)隱私概念的隨機(jī)化算法。它早在本地DP被形式化之前，就由 Warner（1965）在調(diào)查抽樣背景下提出。眾所周知，隨機(jī)響應(yīng)機(jī)制是 (ε, 0)-LDP；參見 Dwork 和 Roth（2014，第3.2節(jié)）。

在本節(jié)其余部分，我們將隨機(jī)響應(yīng)機(jī)制與算法1中的拉普拉斯機(jī)制結(jié)合使用，將迄今為止所發(fā)展的依賴數(shù)據(jù)下Winsorized均值估計(jì)理論推廣至本地模型——盡管需在稍強(qiáng)一些的假設(shè)下進(jìn)行。除了要求數(shù)據(jù)滿足 ( τ , γ ) ∞
-集中性以及數(shù)據(jù)矩陣滿足對(duì)數(shù)Sobolev依賴性或行獨(dú)立同分布（i.i.d.）之外，我們還需假設(shè) ∥ μ ∥ ∞ ≤ B 。這是因?yàn)槲覀儗⒃扔糜跇?gòu)建私有中點(diǎn)的穩(wěn)定直方圖替換為基于隨機(jī)響應(yīng)的直方圖估計(jì)器，而后者無(wú)法處理無(wú)限多個(gè)區(qū)間（bins）。除這一替換外，我們的方法保持不變，因此相較于現(xiàn)有技術(shù)具有顯著更強(qiáng)的通用性，因?yàn)槲覀冊(cè)试S無(wú)界且依賴的數(shù)據(jù)。特別地，在有界獨(dú)立同分布觀測(cè)的情形下，我們可復(fù)現(xiàn)Kent等（2024）定理6中的上界。除了直方圖估計(jì)部分外，我們?cè)谥行幕Ｐ秃捅镜啬Ｐ拖碌慕Y(jié)果證明均基于一系列通用陳述，這些陳述隨后被分別實(shí)例化到兩種情形中。

6.1 直方圖估計(jì)器

我們的本地直方圖估計(jì)器同樣適用于依賴觀測(cè)值。算法7中的估計(jì)器是一種直方圖估計(jì)器，它在本地模型中也通過隨機(jī)響應(yīng)機(jī)制來保障隱私。該直方圖的構(gòu)造與Kent等（2024）所采用的方法類似。然而，我們無(wú)需合并多個(gè)相鄰的區(qū)間，并且引入了一個(gè)去偏步驟以確保其一致性。與專為中心化模型設(shè)計(jì)的算法2不同，該直方圖僅能處理有限多個(gè)不相交的區(qū)間，但它是 ( ε , 0 )LDP 的。需注意，穩(wěn)定直方圖是 ( ε , δ ) ) -DP 的，其中 δ > 0 。

6.2 均值估計(jì)器

我們的本地均值估計(jì)器的構(gòu)造與第4節(jié)中的中心化模型對(duì)應(yīng)版本類似。此處唯一的不同在于：我們?cè)诠烙?jì)投影區(qū)間的私有中點(diǎn)時(shí)使用隨機(jī)化直方圖，并且每個(gè)數(shù)據(jù)項(xiàng)或用戶在將投影后的觀測(cè)值發(fā)送至中央服務(wù)器之前，需添加拉普拉斯噪聲以實(shí)現(xiàn)隱私保護(hù)。算法8形式化了這一協(xié)議。請(qǐng)注意，隨機(jī)化直方圖僅能處理有限個(gè)區(qū)間，因此該算法要求輸入一個(gè) B ∈ ( 0 , ∞ ) ，使得 ∥ μ ∥ ∞ ≤ B 。

6.2.1 超出項(xiàng)級(jí)均值估計(jì)的擴(kuò)展

實(shí)例化定理6.4可立即得到項(xiàng)級(jí)非參數(shù)回歸、用戶級(jí)均值估計(jì)、隨機(jī)效應(yīng)位置估計(jì)以及縱向數(shù)據(jù)線性回歸的有限樣本風(fēng)險(xiǎn)界。以下簡(jiǎn)要概述這些結(jié)果，從非參數(shù)回歸開始（見推論6.7）。該結(jié)果是推論4.11的本地DP對(duì)應(yīng)版本。

附錄F.6中推論6.7所示的逐點(diǎn)誤差率，與Gy?rfi和Kroll（2025）利用基變換估計(jì)器所獲得的定理3.1和定理4.1中近乎最優(yōu)的期望意義下積分誤差率相似。我們的結(jié)果對(duì)定義4.8中的Priestley-Chao回歸估計(jì)器進(jìn)行了私有化，從而補(bǔ)充了他們的方法（另見Kent等（2024）第2.2.3小節(jié)）。

接下來的三個(gè)結(jié)果涉及用戶級(jí)估計(jì)，分別針對(duì)均值估計(jì)、位置隨機(jī)效應(yīng)模型和縱向回歸。我們首先給出一個(gè)通用的用戶級(jí)均值估計(jì)結(jié)果，該結(jié)果是推論5.4在本地模型下的對(duì)應(yīng)版本。

7 仿真

我們通過實(shí)證方法檢驗(yàn)我們帶噪聲的Winsorized均值估計(jì)器的有限樣本保證。雖然我們的仿真主要關(guān)注中心化模型下的項(xiàng)級(jí)均值估計(jì)，但我們也會(huì)簡(jiǎn)要討論用戶級(jí)均值估計(jì)以及本地差分隱私（DP）模型下的均值估計(jì)。

7.1 項(xiàng)級(jí)均值估計(jì)

7.1.1 小樣本下的隱私代價(jià)

7.1.2 理論與實(shí)證改進(jìn)常數(shù)

7.1.3 小樣本下的依賴代價(jià)

7.1.4中央與地方模式

7.1.5 插入式方差估計(jì)

7.2 用戶級(jí)均值估計(jì)

8 結(jié)論

我們?yōu)橐蕾嚁?shù)據(jù)提供了一些初步的差分隱私估計(jì)工具。核心方法是一種基于帶噪聲Winsorized均值的均值估計(jì)算法，該算法最初由Karwa和Vadhan（2018）在單變量獨(dú)立同分布高斯數(shù)據(jù)的項(xiàng)級(jí)差分隱私背景下提出。我們的工作表明，該算法的簡(jiǎn)單變體不僅能夠處理依賴數(shù)據(jù)，而且在用戶級(jí)DP和本地DP框架下，針對(duì)非參數(shù)回歸、隨機(jī)效應(yīng)模型和縱向線性回歸等多種估計(jì)問題，均可實(shí)現(xiàn)最優(yōu)的估計(jì)速率。從這個(gè)意義上說，我們的工作也為一系列通常被分別研究的差分隱私問題提供了一個(gè)簡(jiǎn)潔而統(tǒng)一的估計(jì)框架。

從技術(shù)角度看，允許對(duì)數(shù)Sobolev依賴觀測(cè)值的關(guān)鍵工具是Bobkov與G?tze（2010）提出的DKW型不等式。它使我們能夠控制中間直方圖估計(jì)器的性能——這些估計(jì)器對(duì)于自適應(yīng)地確定Winsorized均值估計(jì)器所需的投影區(qū)間至關(guān)重要。若要進(jìn)一步放松對(duì)數(shù)Sobolev依賴性假設(shè)，則需要在更弱條件下成立的DKW型不等式。

本工作開啟了諸多自然的未來研究方向。其中在實(shí)踐中最緊迫的問題或許是開發(fā)適用于中等樣本量且在依賴性條件下具有良好表現(xiàn)的統(tǒng)計(jì)推斷工具。為此，開發(fā)優(yōu)良的私有方差估計(jì)器將至關(guān)重要，我們認(rèn)為基于Biswas等（2020）提出的CoinPress方法的思想頗具前景。最后，許多重要的統(tǒng)計(jì)問題天然涉及依賴數(shù)據(jù)，包括多臂老虎機(jī)、在線學(xué)習(xí)、聯(lián)邦學(xué)習(xí)，以及一般的含噪差分隱私優(yōu)化過程。我們希望在未來的工作中探討其中部分問題。

原文鏈接： https://arxiv.org/pdf/2511.18583