私有随机决策理论在线学习中的最优间隔依赖遗憾

# 具有最优间隙依赖遗憾的私有随机决策理论在线学习
来源：https://arxiv.org/html/2605.29148
Tommaso Cesari 渥太华大学电气工程与计算机科学学院 加拿大渥太华 tcesari@uottawa\.ca Roberto Colomboni 布里斯托大学数学学院 英国布里斯托 roberto\.colomboni@bristol\.ac\.uk

###### 摘要

我们研究具有完全信息的事件级纯差分隐私的随机决策理论在线学习。一个 COLT 开放问题 [6 (https://arxiv.org/html/2605.29148#bib.bib9)] 要求确定在纯事件级差分隐私下，随机决策理论在线学习的最优间隙依赖遗憾率。对于 KK 个动作，损失在 [0,1][0,1] 中，并且存在一个唯一的最优动作，其与次优动作的间隔为 Δmin\Delta_{\min}，已知的下界阶数为 log⁡Kmin⁡{Δmin,ε}，\frac{\log K}{\min\{\Delta_{\min},\varepsilon\}}，或者等价地，在通用常数范围内，阶数为

log⁡KΔmin+log⁡Kε。\frac{\log K}{\Delta_{\min}}+\frac{\log K}{\varepsilon}.我们给出一个与时间范围无关的纯差分隐私算法，并证明明确的遗憾界

Reg_T≤1000⋅(log⁡KΔmin+log⁡Kε)\operatorname{Reg}_{T}\leq 1000\cdot\left(\frac{\log K}{\Delta_{\min}}+\frac{\log K}{\varepsilon}\right)对于任意时间范围 TT。数值常数未优化。该算法将时间划分为指数增长的区块，每个区块内执行单一动作，并通过指数机制基于前一个区块的数据无关随机前缀来选择下一个动作。随机前缀将区块遗憾转化为对所有前缀长度的 softmax 选择误差之和。一个单一的熵势能论证以 log⁡K/ε\log K/\varepsilon 的成本控制所有隐私主导的大间隙动作。

## 1 引言

具有随机完全信息反馈的决策理论在线学习 [3 (https://arxiv.org/html/2605.29148#bib.bib5)] 是研究在线决策统计成本最简洁的模型之一。有 KK 个动作。每一轮，学习器选择一个动作，遭受其损失，并观察完整的损失向量。当损失向量是独立同分布的，且最优动作与其他动作之间存在间隔时，非私有情况下最优间隙依赖遗憾率为 Θ(log⁡K/Δmin)\Theta(\log K/\Delta_{\min}) [7 (https://arxiv.org/html/2605.29148#bib.bib6), 9 (https://arxiv.org/html/2605.29148#bib.bib7)]。

差分隐私版本更为微妙。Hu 等人 (https://arxiv.org/html/2605.29148#bib.bib8) [5 (https://arxiv.org/html/2605.29148#bib.bib8)] 证明了一个阶数为

log⁡Kmin⁡{Δmin,ε}，\frac{\log K}{\min\{\Delta_{\min},\varepsilon\}},的下界，这等价于 log⁡K/Δmin+log⁡K/ε\log K/\Delta_{\min}+\log K/\varepsilon 在通用常数范围内。Hu 和 Mehta (https://arxiv.org/html/2605.29148#bib.bib9) [6 (https://arxiv.org/html/2605.29148#bib.bib9)] 将剩余问题提炼为一个 COLT 开放问题：确定在纯事件级差分隐私下的最优实例依赖遗憾率。Wu 和 Wang (https://arxiv.org/html/2605.29148#bib.bib10) [10 (https://arxiv.org/html/2605.29148#bib.bib10)] 最近取得了实质性进展，通过消除时间范围依赖并证明

O(log⁡KΔmin+log2⁡Kε)O\left(\frac{\log K}{\Delta_{\min}}+\frac{\log^{2}K}{\varepsilon}\right)对于随机问题，并在一个确定性的特例中给出了紧致的 Θ(log⁡K/ε)\Theta(\log K/\varepsilon) 分析，部分解决了该开放问题。

我们填补了随机问题中剩余的对数差距。我们的算法是一个随机前缀版本的私有“跟随领先者”。时间被划分为二进区块。在一个区块内，学习器重复一个动作。在区块结束时，学习器从区块的后半部分采样一个随机前缀长度，并将指数机制应用于该前缀上的累积损失。所选动作随后用于下一个区块。由于每个事件仅用于私有选择下一个区块，隐私性通过输出律的直接分解得到保证。我们给出直接分解证明，而非依赖并行组合。

证明包含两个要素。首先，随机化前缀长度从分析中消除了二进时钟：所有区块上的遗憾被一个常数乘以

∑m≥1E[∑j=1KΔjPm,j]，\sum_{m\geq 1}\mathbb{E}\left[\sum_{j=1}^{K}\Delta_{j}P_{m,j}\right],所界，其中 Pm,jP_{m,j} 是在 mm 个独立同分布样本后动作 jj 的随机 softmax 概率。其次，这个前缀长度 softmax 误差和分解为小间隙和大间隙项。小间隙部分由 Hoeffding 不等式和二进分组控制，得到 log⁡K/Δmin\log K/\Delta_{\min}。大间隙部分无需分别对每个动作求和即可控制：一个受限的 softmax 势能呈 telescoping 形式，其成本仅为其初始熵 log⁡K\log K 除以隐私尺度。这一步消除了额外的对数。

*因此，该证明也为最优率中的两项提供了概念性解释。*项 log⁡K/Δmin\log K/\Delta_{\min} 是在接近最优的竞争者中识别最佳动作的统计成本。项 log⁡K/ε\log K/\varepsilon 是私有地消除明显次优动作的隐私成本：一旦间隙很大，集中性不再是瓶颈，唯一剩余的资源是初始的 softmax 熵。*在这个意义上，该证明不仅匹配下界；它分离了统计价格和隐私价格，并精确显示了每一项进入的位置。*

#### 贡献。

我们为随机 DTOL 给出一个构造性的与时间范围无关的 ε\varepsilon-差分隐私算法，并证明明确的遗憾界

Reg_T≤1000⋅(log⁡KΔmin+log⁡Kε)。\operatorname{Reg}_{T}\leq 1000\cdot\left(\frac{\log K}{\Delta_{\min}}+\frac{\log K}{\varepsilon}\right)。结合 [5 (https://arxiv.org/html/2605.29148#bib.bib8)] 的下界，这解决了 [6 (https://arxiv.org/html/2605.29148#bib.bib9)] 提出的间隙依赖纯差分隐私率问题。虽然开放问题是对通常的积-动作随机模型提出的，我们的证明仅使用了时间上的独立性。因此它适用于损失向量在每一轮内坐标间任意依赖的独立同分布情况；积-动作模型是一个特例。

## 2 相关工作

#### 决策理论在线学习。

决策理论在线学习由 Freund 和 Schapire (https://arxiv.org/html/2605.29148#bib.bib5) [3 (https://arxiv.org/html/2605.29148#bib.bib5)] 引入，作为一个通用的完全信息在线决策模型。在随机机制下，“跟随领先者”和指数加权算法表现出由最佳和次佳动作之间间隔决定的间隙依赖行为。明确的非私有率为 Θ(log⁡K/Δmin)\Theta(\log K/\Delta_{\min})；例如，参见 Kotłowski (https://arxiv.org/html/2605.29148#bib.bib6) [7 (https://arxiv.org/html/2605.29148#bib.bib6)] 的“跟随领先者”上界和 Mourtada 与 Gaïffas (https://arxiv.org/html/2605.29148#bib.bib7) [9 (https://arxiv.org/html/2605.29148#bib.bib7)] 的最优性结果。我们的结果保留了这一统计项，并识别出纯事件级差分隐私强加的额外成本。

#### 差分隐私与私有选择。

差分隐私由 Dwork (https://arxiv.org/html/2605.29148#bib.bib3) [2 (https://arxiv.org/html/2605.29148#bib.bib3)] 引入。我们的算法使用 McSherry 和 Talwar (https://arxiv.org/html/2605.29148#bib.bib4) [8 (https://arxiv.org/html/2605.29148#bib.bib4)] 的指数机制在每个区块后选择下一个动作，通过从累积损失上的 softmax 分布中采样。与标准的一次性私有选择不同，在线设置要求整个发布动作前缀是私有的。我们的区块构造旨在使每个事件仅影响一次私有选择。随后区块内执行的动作是该选择的确定性后处理。

#### 私有随机在线学习。

Hu 等人 (https://arxiv.org/html/2605.29148#bib.bib8) [5 (https://arxiv.org/html/2605.29148#bib.bib8)] 研究了与此最相关的差分隐私随机在线学习设置，包括完全信息随机 DTOL 问题。对于完全信息随机 DTOL，他们的下界阶数为

log⁡Kmin⁡{Δmin,ε}。\frac{\log K}{\min\{\Delta_{\min},\varepsilon\}}。这等价于 log⁡K/Δmin+log⁡K/ε\log K/\Delta_{\min}+\log K/\varepsilon 在通用常数范围内。他们的上界匹配了统计项，但在隐私项中可能支付一个额外的 log⁡T\log T 因子。Hu 和 Mehta (https://arxiv.org/html/2605.29148#bib.bib9) [6 (https://arxiv.org/html/2605.29148#bib.bib9)] 随后将剩余差距表述为一个 COLT 开放问题：确定纯差分隐私下随机 DTOL 的最优间隙依赖遗憾率。

#### 关于开放问题的部分进展。

Wu 和 Wang (https://arxiv.org/html/2605.29148#bib.bib10) [10 (https://arxiv.org/html/2605.29148#bib.bib10)] 部分解决了该开放问题。他们消除了随机上界中的时间范围依赖，并得到

O(log⁡KΔmin+log2⁡Kε)，O\left(\frac{\log K}{\Delta_{\min}}+\frac{\log^{2}K}{\varepsilon}\right)，并在一个确定性的特例中证明了紧致的 Θ(log⁡K/ε)\Theta(\log K/\varepsilon) 率。他们的随机分析在隐私项中仍付出一个额外的 log⁡K\log K。在技术层面，他们的证明使用了伯努利重采样和单调性性质，随后对动作求和，这产生了额外的对数。

#### 本工作。

当前算法仍保持在 [6 (https://arxiv.org/html/2605.29148#bib.bib9), 10 (https://arxiv.org/html/2605.29148#bib.bib10)] 的纯差分隐私、随机、完全信息 DTOL 设置中。新增的要素是在每个二进区块中引入一个数据无关随机前缀。这种随机化将区块遗憾转化为前缀长度 softmax 选择误差之和。对于大间隙动作，该和通过单一 softmax 势能直接控制，其初始值至多为 log⁡K\log K。这消除了剩余的对数因子，并得到匹配的隐私项 log⁡K/ε\log K/\varepsilon。

## 3 模型

固定一个整数 K≥2K\geq 2，并记 [K]={1,...,K}[K]=\{1,\ldots,K\}。所有随机变量定义在一个概率空间 (Ω,F,P)(\Omega,\mathcal{F},\mathbb{P}) 上。损失过程是一个独立同分布随机变量序列 (Xt)t≥1(X_{t})_{t\geq 1}，取值于 [0,1]K[0,1]^{K}。我们记

Xt=(Xt,1,...,Xt,K)。X_{t}=(X_{t,1},\ldots,X_{t,K})。XtX_{t} 的各坐标可能是相关的。仅使用不同时间之间的独立性。

在第 tt 轮，学习器在观察到 XtX_{t} 之前选择一个动作 It∈[K]I_{t}\in[K]，遭受损失 Xt,ItX_{t,I_{t}}，然后观察整个向量 XtX_{t}。因此动作 ItI_{t} 关于学习器的内部随机化和过去的损失向量 X1,...,Xt−1X_{1},\ldots,X_{t-1} 是可测的。完全信息假设在此很重要：未来的观察不依赖于执行了哪个动作。

令

μj=E[X1,j]，j∈[K]。\mu_{j}=\mathbb{E}[X_{1,j}],\qquad j\in[K]。在重新标记动作后，假设

μ1<μ2≤⋯≤μK。\mu_{1}<\mu_{2}\leq\cdots\leq\mu_{K}。定义逐点期望损失间隙

Δ1=0，Δj=μj−μ1 (j∈{2,...,K})，\Delta_{1}=0,\qquad\Delta_{j}=\mu_{j}-\mu_{1}\quad(j\in\{2,\ldots,K\})，并定义

Δmin=Δ2。\Delta_{\min}=\Delta_{2}。由于损失属于 [0,1][0,1]，有 0<Δmin≤10<\Delta_{\min}\leq 1 且对所有 jj 有 0≤Δj≤10\leq\Delta_{j}\leq 1。

到时间范围 TT 的期望伪遗憾为

Reg_T=E[∑t=1T(Xt,It−Xt,1)]=∑t=1TE[ΔIt]。\operatorname{Reg}_{T}=\mathbb{E}\left[\sum_{t=1}^{T}\bigl(X_{t,I_{t}}-X_{t,1}\bigr)\right]=\sum_{t=1}^{T}\mathbb{E}[\Delta_{I_{t}}]。
###### 定义 1 (事件级纯差分隐私)。

固定 t≥1t\geq 1。两个确定性前缀 x1:t,x1:t′∈([0,1]K)tx_{1:t},x^{\prime}_{1:t}\in([0,1]^{K})^{t} 被称为相邻的，如果它们最多在一个完整的损失向量上不同。一个随机在线算法是 ε\varepsilon-差分隐私的，如果对于每个 t≥1t\geq 1，每对相邻的 x1:t,x1:t′x_{1:t},x^{\prime}_{1:t}，以及每个子集 S⊆[K]tS\subseteq[K]^{t}，

P((I1,...,It)∈S∣x1:t)≤eεP((I1,...,It)∈S∣x1:t′)。\mathbb{P}\bigl((I_{1},\ldots,I_{t})\in S\mid x_{1:t}\bigr)\leq e^{\varepsilon}\mathbb{P}\bigl((I_{1},\ldots,I_{t})\in S\mid x^{\prime}_{1:t}\bigr)。等价地，对于每个固定的输入前缀，算法定义了一个在 [K]t[K]^{t} 上的概率测度，且与相邻前缀相关联的两个测度在每个事件上都在乘法因子 eεe^{\varepsilon} 之内。

## 4 算法与主要结果

所有涉及条件期望的等式都被理解为 P\mathbb{P}-几乎必然成立。

固定 ε>0\varepsilon>0，并设定

η=min{ε/2,1/8}。\eta=\min\{\varepsilon/2,1/8\}。对于每个 r≥0r\geq 0，定义二进区块

Br={2r,2r+1,...,2r+1−1}。B_{r}=\{2^{r},2^{r}+1,\ldots,2^{r+1}-1\}。因此 |Br|=2r|B_{r}|=2^{r}。算法在每个区块内执行一个动作。令 ArA_{r} 是在 BrB_{r} 的每一轮上执行的动作。初始动作 A0A_{0} 从 [K][K] 上的任意分布中采样，该分布不依赖于损失序列。为具体起见，可以取 A0A_{0} 在 [K][K] 上均匀分布。

在观察到区块 BrB_{r} 之后，算法采样用于下一个区块的动作 Ar+1A_{r+1}。对于 r=0r=0，设定 M0=1M_{0}=1。对于 r≥1r\geq 1，学习器采样一个内部随机索引

Mr∼Unif{2r−1+1,...,2r}，M_{r}\sim\operatorname{Unif}\{2^{r-1}+1,\ldots,2^{r}\}，独立于损失向量和所有其他随机化。对于 s∈{1,...,2r}s\in\{1,\ldots,2^{r}\}，记

X(r,s)=X2r−1+s。X^{(r,s)}=X_{2^{r}-1+s}。这是区块 BrB_{r} 中的第 ss 个损失向量。对于 j∈[K]j\in[K] 和 m∈{1,...,2r}m\in\{1,\ldots,2^{r}\}，定义累积区块前缀损失

Lr,j(m)=∑s=1mXj(r,s)。L_{r,j}(m)=\sum_{s=1}^{m}X^{(r,s)}_{j}。给定 MrM_{r} 以及观察到的前缀 X(r,1),...,X(r,Mr)X^{(r,1)},\ldots,X^{(r,M_{r})}，下一个动作根据指数加权分布采样：

P(Ar+1=j∣Mr,X(r,1),...,X(r,Mr))=exp⁡(−ηLr,j(Mr))∑i=1Kexp⁡(−ηLr,i(Mr))。\mathbb{P}(A_{r+1}=j\mid M_{r},X^{(r,1)},\ldots,X^{(r,M_{r})})=\frac{\exp(-\eta L_{r,j}(M_{r}))}{\sum_{i=1}^{K}\exp(-\eta L_{r,i}(M_{r}))}。等价地，这是负累积损失 −Lr,j(Mr)-L_{r,j}(M_{r}) 的 softmax，其逆温度参数为 η\eta。

###### 定理 1 (显式间隙依赖私有遗憾)。

对于每个 K≥2K\geq 2，每个 ε>0\varepsilon>0，每个时间范围 T≥1T\geq 1，以及每个具有支撑在 [0,1]K[0,1]^{K} 上的边际分布且存在唯一最优动作的独立同分布损失过程，随机前缀 softmax 算法是 ε\varepsilon-差分隐私的，并满足

Reg_T≤1+800log⁡KΔm