Private Online Prediction from Experts with Small Losses

Introduction

Online prediction from experts (OPE) is a fundamental problem in machine learning. In this problem, the learner receives a stream of $T$ loss functions $\ell_1,\ldots,\ell_T$. In each round $t$, the learner chooses an expert $i_t \in[N]$ before seeing $\ell_t$ and suffers loss $\ell_t(i_t)$. The learner aims to minimize its total loss, which is compared to that of the best expert in hindsight, denoted by $L^\star$. The difference between these two quantities is called the regret, which measures the learner’s performance for this problem.

A critical concern when deploying machine learning algorithms on sensitive data (e.g., financial or medical records) is privacy leakage. To address this, differential privacy (DP) [9, 8] has emerged as the de facto standard for formalizing the privacy guarantee provided by an algorithm. Informally, an algorithm is said to be differentially private if changing a single input data point alters its output distribution only negligibly. As a result, such a change in an individual’s information is unlikely to be detected, thereby protecting personal privacy.

Given the importance of OPE, studying it under DP has received significant attention. Previous work [3, 4] has developed algorithms that achieve regret $\widetilde{O}(\sqrt{T})$, which is nearly optimal because it matches the $\Omega(\sqrt{T\log N}+\log N)$ lower bound [6]—a bound that holds even without any privacy constraints. These results suggest that the cost of privacy in OPE is negligible in the worst case.

In many practical settings—such as financial forecasting, weather prediction, or personalized recommendations—domain experts are specifically selected for their accuracy, so their cumulative loss tends to be low over time. However, the $\widetilde{O}(\sqrt{T})$ regret becomes less meaningful when the loss of the best expert $L^\star$ is small because the regret itself can be substantially greater than $L^\star$, rendering the learner’s loss considerably higher than $L^\star$. As an illustration, suppose $L^\star=T^{1/4}$. An algorithm with regret $\sqrt{T}$ may incur a loss of $\sqrt{T}$, which is $T^{1/4}$ times larger than $L^\star$. In contrast, when $L^\star=T^{3/4}$ the total loss is only $(1+o(1))L^\star$. Thus, worst-case regret bounds are not suitable for OPE with small losses.

In the non-private setting, a natural remedy is to run the multiplicative weights method with a larger learning rate: increasing the learning rate from $\sqrt{\log N/T}$ to $\sqrt{\log N/L^\star}$ yields a regret bound of $O(\sqrt{L^\star\log N}+\log N)$ [19, 13]. Unfortunately, such a strategy cannot be directly applied under DP. This is because a large learning rate amplifies the algorithm’s sensitivity to individual data points, thereby violating privacy constraints. Indeed, all existing private OPE algorithms impose a strict upper bound on the learning rate to ensure DP, which prevents them from adapting to small $L^\star$. Consequently, it remains unclear whether an $\widetilde{O}(\sqrt{L^\star})$ regret bound is achievable in the private setting.

Our contribution

In this work, we assume that $\ell_1,\ldots,\ell_T$ are chosen by an oblivious adversary. That is, they are fixed in advance and independent of the outputs of the learner.

We propose the first differentially private algorithm that attains regret $\widetilde{O}(\sqrt{L^\star})$ for OPE. This nearly matches the optimal regret without privacy constraints, suggesting that the cost of privacy remains small in the low-loss regime. The results are formally stated in the theorems below.

Comparison with previous results. When $L^\star=0$, our results recover the bounds obtained by Asi et al. [2] for the realizable setting. When $L^\star$ grows, our algorithm yields a quadratic improvement over their $\widetilde{O}(L^\star)$ regret bound. Compared to the $\widetilde{O}(\sqrt{T})$ regret obtained by Asi et al. [3, 4], our results are significantly better when $L^\star$ is much smaller than $T$.

As shown by Asi et al. [3], the above improvement cannot be achieved against an adaptive adversary under pure DP: any OPE algorithm must incur an $\Omega(T)$ regret even if $L^\star=0$. We additionally prove that it remains impossible under approximate DP by providing an $\widetilde{\Omega}(\sqrt{T})$ lower bound, which also holds when $L^\star=0$.

Related work

In the non-private setting, the OPE problem has been extensively studied. The multiplicative weights algorithm [19, 23] was shown to achieve a data-dependent regret bound of $O(\sqrt{L^\star\log N}+\log N)$ with an appropriately tuned learning rate [13]. There are also other methods with the same regret bound, such as follow-the-perturbed-leader [15, 18, 16]. It was formally proved by Cesa-Bianchi et al. [6] that such a bound is asymptotically optimal.

The private version of OPE was first considered by Dwork et al. [11]. It is a folklore result that the multiplicative weights method preserves differential privacy, which follows from the exponential mechanism [20] and advanced composition [12]. A series of subsequent works [21, 17, 1, 2, 3, 4] further investigated the problem. In the oblivious adversarial setting considered in this paper, Asi et al. [3] proposed algorithms with regret $\widetilde{O}(\sqrt{T})$ under pure DP and $O(\sqrt{T\log N})+\widetilde{O}(T^{1/3})$ under approximate DP, demonstrating that the cost of privacy is negligible. The bound for approximate DP was later refined by Asi et al. [4], who further optimized the dependence on the privacy parameter $\varepsilon$. However, these results are unfavorable when $L^\star$ is much smaller than $T$. Asi et al. [2] studied the realizable setting, where $L^\star= 0$, and gave algorithms with $\widetilde{O}(1)$ regret. Their algorithms can be extended to the agnostic setting where $L^\star> 0$. Nevertheless, the resulting regret bound is $\widetilde{O}(L^\star)$, which is far from optimal.

Preliminaries

Online prediction from experts can be formulated as a $T$-round game played between a learner and an adversary. In this work, we assume an oblivious adversary who determines a sequence of loss functions $\ell_1,\ldots,\ell_T$ in advance and releases them to the learner one by one, where every $\ell_t : [N] \to[0,1]$ assigns each of the $N$ experts a loss in $[0,1]$. In round $t$, the learner chooses an expert $i_t \in[N]$ before receiving $\ell_t$ and incurs loss $\ell_t(i_t)$. The performance of the learner is assessed by the expected regret, defined as

For ease of notation, we write $L^\star$ to denote $\min_{i\in[N]}\sum_{t=1}^{T}\ell_t(i)$. Note that $L^\star$ is determined in advance because the adversary is oblivious. However, it is unknown to the learner until the end.

One common approach to solving OPE is the celebrated multiplicative weights method, which in each round $t$ samples $i_t$ such that

where $\eta$ is the learning rate. The following lemma provides an upper bound on its expected regret.

We then introduce the notion of differential privacy in the context of OPE.

When $\delta=0$, we usually omit $\delta$ and say $A$ is $\varepsilon$-differentially private. This case is referred to as pure DP, while the case where $\delta>0$ is referred to as approximate DP.

A key ingredient in our design is the AboveThreshold mechanism, which receives a sequence of queries and privately identifies the first one that exceeds a prespecified threshold.

Every step of the multiplicative weights method is exactly the exponential mechanism with privacy parameter $\varepsilon= 2\eta$. This property, combined with advanced composition, has been widely used in the literature to develop private OPE algorithms.

Algorithm and analysis

In this section, we present our algorithm and analyze its privacy and regret guarantees.

Our algorithm is built on the shrinking dartboard algorithm [14], which was also leveraged by Asi et al. [3] to develop algorithms with $\widetilde{O}(\sqrt{T})$ regret. The key insight is that the marginal distribution of the multiplicative weights method changes only slightly between consecutive rounds. Consequently, it suffices to update the output with only a small probability after each round. By reducing the number of updates, one can allocate a larger privacy budget for each update (i.e., use a larger learning rate $\eta$), thereby achieving smaller regret.

However, the shrinking dartboard algorithm is not inherently private because the probability of making an update depends on the underlying data (specifically, $\ell_t(i_t)$, i.e., the loss associated with the currently selected expert $i_t$). Asi et al. [3, 4] addressed this by forcing the algorithm to perform an additional update at each round with a probability independent of the data. However, to satisfy even approximate DP, this probability must be at least $\widetilde{\Omega}(T^{-1/3})$. By advanced composition, this imposes an $\widetilde{O}(1/T^{1/3})$ upper bound on the learning rate $\eta$, which in turn yields an $\widetilde{O}(T^{1/3})$ regret bound according to Lemma 2.1. This exceeds our desired $\widetilde{O}(\sqrt{L^\star})$ regret whenever $L^\star< T^{2/3}$.

We address this by delaying the update until the currently selected expert has incurred a sufficiently large loss, and then making an update with a probability that depends on the cumulative loss accumulated during the delay. Our key consideration here is that, while such a probability is data-dependent, performing an update with this probability preserves privacy. Moreover, the delay before an update can be implemented using the AboveThreshold mechanism, which is also differentially private. In addition, we impose a lower bound on the probability of updating and an upper bound on the number of updates, which are crucial for satisfying DP in the worst case. The overall algorithm is described in Algorithm 1. We formally prove its privacy guarantee in § 3.1 and regret bound in § 3.2.

Privacy analysis

Let $\operatorname{Comp}_{\delta}(k,\varepsilon_0)$ be the smallest $\varepsilon$ such that the composition of $k$ $\varepsilon_0$-differentially private algorithms is $(\varepsilon,\delta)$-differentially private. We prove the privacy guarantee of Algorithm 1 in the following lemma.

Proof. We analyze the augmented transcript consisting of the initial expert $i_1$, the outputs of all AboveThreshold instances, the $Z_u$'s, and the experts generated at the (at most $V$) resampling steps. The learner’s output sequence is a post-processing of this transcript.

We view the algorithm as the concurrent composition of three types of interactive mechanisms: the collection of AboveThreshold instances, the mechanism generating the $Z_u$'s, and the at most $V$ resampling mechanisms. Throughout the proof, when comparing two neighboring input sequences, we consider an arbitrary common prefix of the interaction transcript. Thus, all previously generated AboveThreshold outputs, $Z_u$'s, resampled experts, and the resulting termination time are fixed and identical on the two executions.

We first show that the collection of AboveThreshold instances is $\varepsilon_1$-differentially private. Let the two neighboring sequences $S$ and $S'$ differ at round $\tilde{t}$. Along any fixed common interaction transcript, there is at most one AboveThreshold instance whose query stream contains the differing loss. All earlier instances receive identical query streams and therefore have identical output distributions on $S$ and $S'$.

Consider the potentially affected instance. Conditioned on the common transcript up to its launch, its starting time and selected expert are fixed and identical on the two executions. Hence, every Algorithm 1: Private online prediction from experts

Input: privacy parameters $\varepsilon_1$ and $\varepsilon_2$, learning rate $\eta$, threshold $\tau$, limit on updates $V$

1. $u \leftarrow1$, $v \leftarrow0$, and $t_0 \leftarrow1$

2. Sample $i_1$ uniformly from $[N]$

3. Initiate an instance of AboveThreshold with privacy parameter $\varepsilon_1$ and threshold $\tau$

4. Observe $\ell_1$ and suffer loss $\ell_1(i_1)$

5. for $t = 2,\ldots,T$ do

   6. if $v < V$ then

      7. Define query $q_t \equiv\sum_{s=t_{u-1}}^{t-1}\ell_s(i_{t-1})$

      8. Feed $q_t$ to AboveThreshold and obtain outcome $\sigma_t$

      9. if $\sigma_t = \top$ then

         10. $r_u \leftarrow\max(1/(e^{\varepsilon_2}-1),\sum_{s=t_{u-1}}^{t-1}\ell_s(i_{t-1}))$

         11. Sample $Z_u$ from $\operatorname{Ber}(e^{-\eta r_u})$

         12. if $Z_u = 1$ then

             13. $i_t \leftarrow i_{t-1}$

         13. else

             15. Sample $i_t \leftarrow i$ with probability $\dfrac{e^{-\eta\sum_{s=1}^{t-1}\ell_s(i)}}{\sum_{i'\in[N]}e^{-\eta\sum_{s=1}^{t-1}\ell_s(i')}}$ for $i \in[N]$

         14. $v \leftarrow v + 1$

         15. end

         16. $t_u \leftarrow t$

         17. $u \leftarrow u + 1$

         18. Initiate an instance of AboveThreshold with privacy parameter $\varepsilon_1$ and threshold $\tau$

      10. else

          22. $i_t \leftarrow i_{t-1}$

      11. end

   7. else

      25. $i_t \leftarrow i_{t-1}$

   8. end

   9. Observe $\ell_t$ and suffer loss $\ell_t(i_t)$

6. end

query issued by this instance has sensitivity at most 1. By the privacy guarantee of AboveThreshold, the transcript generated by this instance is $\varepsilon_1$-differentially private. If this instance terminates, then conditioned on a common transcript through its termination, every subsequent AboveThreshold instance starts after round $\tilde{t}$. Consequently, all subsequent instances receive identical query streams on $S$ and $S'$. If the affected instance never terminates, there are no subsequent instances. Applying the chain rule to the conditional output distributions therefore shows that the collection of all AboveThreshold instances, viewed as one interactive mechanism, is $\varepsilon_1$-differentially private.

We next analyze the privacy loss from generating the $Z_u$'s. Let $Z_1,Z_2,\ldots$ and $Z'_1,Z'_2,\ldots$ denote the $Z_u$'s generated on neighboring sequences $S$ and $S'$, respectively. Similarly, let $r_u$'s and $r'_u$'s denote the $r_u$-values computed on $S$ and $S'$, respectively. As above, all probabilities involving $Z_u$'s are understood to be conditioned on the relevant fixed common transcript prefix.

Along any common transcript path, the intervals $[t_{u-1},t_u-1]$ corresponding to generated $Z_u$'s are disjoint. Hence, there is at most one index $j$ such that $S$ and $S'$ differ at round $\tilde{t}\in[t_{j-1},t_j-1]$. If such $j$ does not exist, then $r_u=r'_u$ for every $Z_u$, which implies that the two $Z_u$-transcripts have identical conditional distributions.

Otherwise, we have $r_u=r'_u$ for all $u<j$ and $|r_j-r'_j|\le1$. Therefore,

Moreover, since $\min(r_j,r'_j) \ge1/(e^{\varepsilon_2}-1)$, we have

where we use the fact that $\frac{1-e^{-y}}{1-e^{-x}}\le\frac{y}{x}$ for $0<x\le y$. For every later $u>j$, condition on an arbitrary common transcript prefix up to the generation of $Z_u$. The selected expert and the interval $[t_{u-1},t_u-1]$ are then fixed and identical on the two neighboring sequences. Since this interval occurs after the differing round, we have $r_u=r'_u$. Thus, $Z_u$ and $Z'_u$ have the same conditional distribution on the two executions. Therefore, by the chain rule, only $Z_j$ contributes privacy loss, and the generation of the $Z_u$'s is $\max(\eta,\varepsilon_2)$-differentially private.

Finally, by Lemma 2.4, each of the at most $V$ resampling steps is $2\eta$-differentially private conditioned on an arbitrary common transcript prefix. By the concurrent composition theorem [22], the adaptive interleaving of these mechanisms has the same composition guarantee as their non-interactive composition. Hence the augmented transcript, and therefore the learner’s output sequence by post-processing, is $(\varepsilon,\delta)$-differentially private. $\square$

Regret analysis

We proceed to analyze the regret. The following key lemma provides lower and upper bounds on the cumulative loss from round $t_{u-1}$ through round $t_u-1$.

Proof. By Theorem 2.3 and the union bound, with probability $1-\beta_1$ we have $q_t\ge\tau-\alpha$ if $\sigma_t=\top$ and $q_t\le\tau+\alpha$ if $\sigma_t=\bot$ for all $t\in[T]$, where $\alpha=8(\ln T+\ln(2T/\beta_1))/\varepsilon_1$. The lower bound follows directly from the fact that $\sigma_{t_u}=\top$. For the upper bound, the inequality trivially holds if $t_{u-1}=t_u-1$. When $t_{u-1}<t_u-1$, we have $\sigma_{t_{u-1}}=\bot$ and $i_{t_{u-2}}=i_{t_{u-1}}$. Hence,

$\square$

Next, we show that the number of updates is $\widetilde{O}(\eta L^\star)$ with high probability. As a consequence, the algorithm works normally (i.e., it won’t reach the update limit) if $V=\widetilde{O}(\eta L^\star)$. By the composition theorems, this allows us to set $\eta=\widetilde{\Theta}(1/\sqrt{L^\star})$, which minimizes the regret bound in Lemma 2.1.

Proof. Note that $v$ can increase by at most 1 in each round. Therefore, the condition $v<V$ is always met given that $V\ge T$. In what follows, we will prove the result assuming $V\ge T$ because $v_T$ can only be smaller if we decrease $V$.

Define a potential function

We have $N=\Phi_1\ge\cdots\ge\Phi_{T+1}\ge e^{-\eta L^\star}$. Let $s_j\in[T]$ be the largest index such that $\Phi_{s_j}\ge\Phi_1/e^j$ and let $m$ be the smallest positive integer such that $s_m=T$. Then $m\le\ln(\Phi_1/\Phi_{T+1})+1\le\ln N+\eta L^\star+1$. Suppose an update happens at round $t \in[s_{j-1}+1,s_j]$ (set $s_0=0$ for simplicity). Let $E$ denote the event that another update happens at some round $t' \in[t+1,s_j]$. Let

By Lemma 3.2, we have $\sum_{s=t_{u-1}}^{t_u-1}\ell_s(i_{t_{u-1}})\ge1/(e^{\epsilon^2}-1)$ for any $u\ge1$. This implies $r_u=\sum_{s=t_{u-1}}^{t_u-1}\ell_s(i_{t_{u-1}})$. Thus, for any $i\in S$, we have

Note that

Rearranging this yields

Therefore,

As a consequence, the probability that $v_T\ge n+m$ can be bounded by the probability that the sum of $n$ Bernoulli random variables with mean $0.03$ is less than $m$. By the Chernoff bound, this is at most $\exp(-0.03n/8)$ given that $0.03n\ge2m$. Thus, it suffices to set $n=70m+280\ln(1/\beta_2)$.

The most challenging task in our proof is to compare the output distribution of Algorithm 1 with that of the multiplicative weights method. To this end, we introduce Algorithm 2, which makes the following modifications to Algorithm 1:

• The limit $V$ on the number of updates and the lower bound on $r_u$ are removed.

• The AboveThreshold mechanisms are replaced by a delay function $d$.

• The learning process can start from an arbitrary round $T_s$.

• The update procedure at round $T_e$ is forced.

We first prove that the output distributions of Algorithm 2 and the multiplicative weights method are the same at round $T_e$.

Proof. We prove by backward induction on $T_s$. When $T_s=T_e$, the conclusion holds since we sample $i_{T_e}$ exactly according to the desired distribution. Now consider $T_s=t'\in[T_e-1]$ and suppose that the result holds for all $T_s\ge t'+1$. Fix some $i_{t'}=k\in[N]$. Define $t_0=t'$ and

Algorithm 2: An auxiliary algorithm
Input: starting point $T_s$, ending point $T_e$, learning rate $\eta$, delay function $d : \mathbb{Z}^{3} \to \mathbb{N}$
1  $u \leftarrow 1$ and $t_0 \leftarrow T_s$
2  Sample $i_{T_s} \leftarrow i$ with probability $\frac{e^{-\eta\sum_{s=1}^{T_s-1}\ell_s(i)}}{\sum_{j\in[N]}e^{-\eta\sum_{s=1}^{T_s-1}\ell_s(j)}}$ for $i\in[N]$
3  Observe $\ell_{T_s}$ and suffer loss $\ell_{T_s}(i_{T_s})$
4  for $t=T_s+1,\ldots,T_e$ do
5    if $t\ge d(t_{u-1},i_{t_{u-1}},u)$ or $t=T_e$ then
6      $r_u\leftarrow\sum_{s=t_{u-1}}^{t-1}\ell_s(i_{t-1})$
7      Sample $Z_u$ from $\operatorname{Ber}(e^{-\eta r_u})$
8      if $Z_u=1$ then
9        $i_t\leftarrow i_{t-1}$
10     else
11       Sample $i_t\leftarrow i$ with probability $\frac{e^{-\eta\sum_{s=1}^{t-1}\ell_s(i)}}{\sum_{j\in[N]}e^{-\eta\sum_{s=1}^{t-1}\ell_s(j)}}$ for $i\in[N]$
12     end
13     $t_u\leftarrow t$
14     $u\leftarrow u+1$
15   else
16     $i_t\leftarrow i_{t-1}$
17   end
18   Observe $\ell_t$ and suffer loss $\ell_t(i_t)$
19 end

These are exactly the $t_u$’s in Algorithm 2 on the event $i_{t'}=\cdots=i_{T_e-1}=k$. Let $m$ be the first index such that $t_m=T_e$. Note that

Moreover, by the induction hypothesis, we have

for any $j\in[m]$ since the learning process starting from $t_j$ can be seen as running Algorithm 2 with $d$ shifted by $j$ along the third dimension and $T_s=t_j$. For simplicity, write $w_t(i)=e^{-\eta\sum_{s=1}^{t-1}\ell_s(i)}$ and $\Phi_t=\sum_{i\in[N]}w_t(i)$ for $t\in[T_e]$. Note that $i_{T_e}\ne i_{t'}$ only if $Z_j=0$ for some $j$. Therefore, we have

for $i\ne k$ and

As a consequence, we have

as desired. ∎

We leverage the fact that Algorithm 2 behaves similarly to Algorithm 1 before round $T_e$ when $T_s = 1$: Lemma 3.2 and Lemma 3.3 suggest that the first modification has little impact, while the second modification can be seen as fixing the random coins used by the AboveThreshold mechanisms (see Appendix § 8 for a more detailed explanation). By analyzing their behavior at round $T_e$ and applying the above lemma, we can argue that with high probability, the output distribution of Algorithm 1 at each round is pointwise at most $e^{O(\eta(\tau+\log T/\varepsilon_1))} \approx1 + O(\eta\tau+ \eta\log T/\varepsilon_1)$ times that of the multiplicative weights mechanism. This leads to the following regret bound.

Proof. Let $\beta_1 = 1/T$. Since the regret cannot be larger than $T$, it suffices to prove the desired conclusion conditioned on the event in Lemma 3.2. As argued in the proof of Lemma 3.3, for any $u \ge1$ we have

By Lemma 3.2, there exists $\Delta=\tau+O(\log T/\varepsilon_1)+1=O(\tau)$ such that $r_u\le\Delta$ for all $u\ge1$.

We first prove the result under the condition that $V\ge T$. Fix a realization of the random coins used by the AboveThreshold mechanisms and let $\widehat Q_t(i)$ be the probability that Algorithm 1 outputs $i_t=i$. Since $V\ge T$, there is no restriction on the number of updates. Hence, this realization induces a delay function $d$ so that Algorithm 1 and Algorithm 2 (with this delay function $d$ and $T_s=1$) behave identically in the first $t-1$ rounds.

Let $P_t$ be as defined in Lemma 2.1 and consider any $i\in[N]$. By Lemma 3.4 with $1=T_s<T_e=t$, Algorithm 2 outputs $i_t=i$ with probability $P_t(i)$. Since it produces $i_{t-1}=i$ with probability $\widehat Q_{t-1}(i)$, we have $P_t(i)\ge\widehat Q_{t-1}(i)\cdot e^{-\eta\Delta}$. Now consider Algorithm 1. If it outputs $i_{t-1}\ne i$, then the probability that it outputs $i_t=i$ is at most $(1-e^{-\eta\Delta})P_t(i)$. As a consequence, we have

where the last inequality is due to the fact that $1+x-1/x\le x^2$ for $x\ge1$. Moreover, we have $\widehat Q_1(i)=P_1(i)$ since we sample $i_1$ uniformly at random. Thus, $\widehat Q_t(i)\le e^{2\eta\Delta}P_t(i)$ for all $t\in[T]$.

By Lemma 2.1, the expected regret of Algorithm 1 with $V\ge T$ is

because $\eta\Delta=O(\eta\tau)=O(1)$.

Let $Q_t(i)$ be the probability that Algorithm 1 outputs $i_t=i$ with $V$ as in the lemma statement. Applying Lemma 3.3 with $\beta_2=1/T$, we obtain $\Pr[v_T<V]\ge1-1/T$. We can decompose $Q_t(i)$ as $\Pr[v_T<V]Q_t^0(i)+\Pr[v_T\ge V]Q_t^1(i)$, where $Q_t^0(i)$ and $Q_t^1(i)$ are the probabilities of outputting $i_t=i$ conditioned on $v_T<V$ and $v_T\ge V$, respectively. We can also write $\widehat Q_t(i)=\Pr[v_T<V]\widehat Q_t^0(i)+\Pr[v_T\ge V]\widehat Q_t^1(i)$ in the same way. For any $t\in[T]$, we have

since $Q_t^0(i)=\widehat{Q}_t^0(i)$. Consequently,

Applying the triangle inequality leads to the desired result.

Choosing $\eta=\widetilde{\Theta}(1/\sqrt{L^\star})$ minimizes the regret bound in Lemma 3.5. However, we cannot do this directly since $L^\star$ is unknown at the beginning. This issue can be circumvented by applying the standard doubling trick, which starts by assuming that $L^\star$ is small and doubles the estimated value once the estimate becomes inaccurate. We defer the detailed implementation to Appendix § 7.

Lower bound for adaptive adversaries

In this section, we briefly discuss how we establish the lower bound for adaptive inputs. We utilize a lower bound in [3], which states that every adaptively $(\varepsilon,\delta)$-differentially private OPE algorithm with $N\geq2T$ experts must incur $\Omega(T)$ regret in the high-privacy regime where $\varepsilon=\widetilde{O}(1/\sqrt{T})$, even if $L^\star=0$. Now suppose $\mathcal{A}$ is an adaptively $(\varepsilon,\delta)$-differentially private OPE algorithm with $\varepsilon\leq1$ and regret at most $R_{\mathcal{A}}(T)$. We create an algorithm $\mathcal{A}_q$ that simulates $\mathcal{A}$, forwards $\mathcal{A}$’s outputs as its own, and feeds the loss function $\operatorname{Ber}(q)\ell_t$ to $\mathcal{A}$. This can be seen as an extension of the canonical “privacy amplification by subsampling” technique to the online setting. We prove that $\mathcal{A}_q$ has privacy parameter $O(q\varepsilon)$ and regret at most $R_{\mathcal{A}}(T)/q$. Applying the lower bound in [3] to $\mathcal{A}_q$ with $q=\widetilde{\Theta}(\min(1/\sqrt{T},1/(\varepsilon T)))$ yields $R_{\mathcal{A}}(T)/q=\Omega(T)$. Rearranging this gives $R_{\mathcal{A}}(T)=\Omega(qT)=\widetilde{\Omega}(\min(\sqrt{T},\sqrt{T}/\varepsilon))$.

The main technical challenge lies in proving the privacy amplification result in the adaptive setting, which requires a more sophisticated analysis than in the oblivious setting. We defer the formal proof to Appendix § 9.

Discussion and future work

In this work, we propose the first differentially private algorithm for OPE that achieves a data-dependent regret bound of $\widetilde{O}(\sqrt{L^\star})$, extending the previous $\widetilde{O}(\sqrt{T})$ bound to the low-loss regime. Our result matches the non-private lower bound $\Omega(\sqrt{L^\star\log N}+\log N)$ up to poly-logarithmic factors for constant privacy parameters, suggesting that the cost of privacy is mild for OPE with small losses. Our algorithm works against any oblivious adversary. We also show that $\widetilde{\Omega}(\sqrt{T})$ regret is necessary for adaptive inputs, demonstrating that such an improvement cannot be made against an adaptive adversary.

When $L^\star$ is large, our regret bounds are slightly worse than those in [3, 4] in certain parameter ranges. For example, suppose $L^\star=\Theta(T)$. Under pure DP, Asi et al. [3] gave an upper bound of $O(\sqrt{T}\log N/\varepsilon)$. Our bound in Theorem 1.1 is larger than theirs by a factor of $\sqrt{\varepsilon\log T/\log N}$ when this factor is greater than $1$ (when it is less than $1$, our bound is better). Under approximate DP, Asi et al. [4] proved an upper bound of $O(\sqrt{T\log N}+T^{1/3}\log N\log(T/\delta)/\varepsilon^{2/3})$. The first term in our bound in Theorem 1.2 is larger than that in their bound by a factor of $O(\sqrt{\log T/\varepsilon})$. An interesting future direction is to investigate whether our bounds can be further improved to match these results.

Acknowledgments and Disclosure of Funding

The research was supported in part by an NSFC grant 62432008, RGC RIF grant R6021-20, an RGC TRS grant T43-513/23N-2, RGC CRF grants C7004-22G, C1029-22G and C6015-23G, NSFC/RGC grant CRS_HKUST601/24 and RGC GRF grants 16207423, 16203824 and 16216725.

Algorithm without prior knowledge of $L^\star$

In this section, we show how to construct an algorithm without prior knowledge of $L^\star$. We first prove regret bounds when some estimate $L' \ge L^\star$ is given.

Proof. We run Algorithm 1 with $\varepsilon_1=\varepsilon_2=\varepsilon/3$, $\tau=8(\ln T+2\ln(2T))/\varepsilon_1+1/(e^{\varepsilon_2}-1)$,

and $V=\lceil71(\ln N+\eta L'+1)+280\ln T\rceil$. One can verify that $\eta\le\varepsilon/3$, $2\eta V\le\varepsilon/3$, and $\eta\tau\le1$. By Lemma 3.1 and basic composition, the overall algorithm is $\varepsilon$-differentially private. By Lemma 3.5 and the fact that $L^\star\le L'$, the expected regret is bounded by

Plugging in the value of $\eta$ yields the desired result. □

Proof. We run Algorithm 1 with $\varepsilon_1=\varepsilon_2=\varepsilon/3$, $\tau=8(\ln T+2\ln(2T))/\varepsilon_1+1/(e^{\varepsilon_2}-1)$,

and $V=\lceil71(\ln N+\eta L'+1)+280\ln T\rceil$, where

• $\eta_1=\max\left(\frac{\varepsilon}{18\cdot\lceil71\ln N+72\rceil},\frac{\varepsilon}{36\sqrt{2\cdot\lceil71\ln N+72\rceil\ln(3/\delta)}}\right)$.

• $\eta_2=\max\left(\frac{\varepsilon}{18\cdot\lceil280\ln T\rceil},\frac{\varepsilon}{36\sqrt{2\cdot\lceil280\ln T\rceil\ln(3/\delta)}}\right) \ldots

• $\eta_3 = \max\left(\sqrt{\varepsilon/(1278L')}, \varepsilon^{2/3}/(184032L'\ln(3/\delta))^{1/3}\right)$.

• $\eta_4 = \sqrt{\varepsilon\ln N/(L'\ln T)}$.

Note that $\lceil71(\ln N+\eta L'+1)+280\ln T\rceil\le\lceil71\ln N+72\rceil+\lfloor71\eta L'\rfloor+\lceil280\ln T\rceil$. By basic and advanced composition, we have

Applying Lemma 3.1 proves the privacy guarantee. Since $\eta\le1$, by Lemma 3.5 and the fact that $L^\star\le L'$, the expected regret is bounded by

Plugging in the value of $\eta$ yields the desired result.

Algorithm 3: Algorithm without prior knowledge of L^\star
1  k ← 1, b_1 ← 1, and α ← 16(ln T + 2 ln(2T))/ε
2  Initiate an instance of AboveThreshold with privacy parameter ε/2 and threshold 4α
3  Initiate an instance of Alg with L′ = 6α
4  for t = 1, . . . , T do
5      Obtain i_t from Alg
6      Observe ℓ_t and suffer loss ℓ_t(i_t)
7      Define query q_t ≡ min_{i∈[N]} ∑_{s=b_k}^{t} ℓ_s(i)
8      Feed q_t to AboveThreshold and obtain outcome σ_t
9      if σ_t = ⊤ then
10         k ← k + 1
11         b_k ← t + 1
12         Terminate the existing instance of Alg and initiate a new one with L′ = 3 · 2^kα
13         Initiate an instance of AboveThreshold with privacy parameter ε/2 and threshold (3 · 2^k − 2)α
14     end
15 end

The overall algorithm works as follows. We start with $L'=6\alpha$ and employ an AboveThreshold mechanism to test if the current cumulative loss of the best expert exceeds $L'$. Once this happens, we double the value of $L'$ and initiate new instances of both the learning algorithm and the AboveThreshold mechanism. This procedure is formalized in Algorithm 3 and the regret guarantee is established in the lemma below. Applying this framework to the two preceding theorems yields our main results in § 1.1.

Proof. We first prove the privacy guarantee. Consider the augmented transcript consisting of the termination times of all AboveThreshold instances together with the outputs of all instances of Alg. We first claim that the sequence of AboveThreshold termination times is $\varepsilon/2$-differentially private. Consider two neighboring loss sequences that differ at round $\tilde{t}$, and condition on an arbitrary common prefix of the termination-time transcript. There is at most one AboveThreshold instance whose queries contain the differing loss. All earlier instances receive identical query streams. For the affected instance, every query has sensitivity at most 1, so its termination time is $\varepsilon/2$-differentially private. Conditioned on a common termination time for this instance, every subsequent instance starts strictly after round $\tilde{t}$, and therefore receives identical query streams on the two neighboring sequences. By the chain rule, the entire sequence of termination times is $\varepsilon/2$-differentially private.

Now fix any sequence of termination times. This also fixes a partition of the loss sequence into disjoint subsequences. The instances of Alg are run independently on these disjoint subsequences, and at most one of them receives the differing loss. By parallel composition, their joint output is $(\varepsilon/2,\delta)$-differentially private. Applying basic composition to the termination-time transcript and the outputs of Alg, followed by post-processing, shows that Algorithm 3 is $(\varepsilon,\delta)$-differentially private.

We then prove utility. By Theorem 2.3 and the union bound, with probability $1-1/T$ all applications of AboveThreshold are $\alpha$-accurate. We first prove a regret bound conditioned on this event. Suppose $\sigma_t=\top$ at round $t$. Before increasing the value of $k$, we have

By our assumption, the algorithm Alg with $L'=3\cdot2^k\alpha$ incurs an expected regret of at most $R(3\cdot2^k\alpha)$ during $[b_k,t]=[b_k,b_{k+1}-1]$. Moreover, we have

This implies that

Hence, whenever a new bucket $k+1$ is initiated, we have $k+1\le K$. Since the algorithm starts with $k=1$, the total number of buckets is therefore at most $K$. For the final bucket, if no $\top$ is returned, the accuracy of AboveThreshold implies $q_T\le(3\cdot2^k-1)\alpha<3\cdot2^k\alpha$, so the same regret bound applies. Summing the regret over all buckets gives $\sum_{k=1}^{K}R(3\cdot2^k\alpha)$.

Since the regret can be at most $T$, the unconditional expected regret is at most

Construction of the delay function

In this section, we show how to construct the delay function when the randomness of the AboveThreshold mechanisms is fixed. Consider an AboveThreshold mechanism that is initiated at round $s$. It is implemented as in Algorithm 4.

Note that in each round $t\in[T]$ we always draw a random variable $\nu_t$. Hence, we can fix the values of $\nu_1,\ldots,\nu_T$ at the beginning. Additionally, we draw $\xi_1,\ldots,\xi_T$, where $\xi_u$ denotes the variable $\xi$ used by the $u$-th AboveThreshold mechanism.

Now suppose that in Algorithm 1 we initiate the $u$-th AboveThreshold mechanism at round $t_{u-1}$. Then it will return $\sigma_t=\top$ for the first $t$ satisfying

As a consequence, we can define $d(t_{u-1},i_{t_{u-1}},u)$ as this $t$ if such a $t$ exists, and as $T+1$ otherwise. Doing this for every tuple $(t_{u-1},i_{t_{u-1}},u)\in[T]\times[N]\times[T]$ constructs the delay function $d$.

Algorithm 4: AboveThreshold
Input: privacy parameter $\varepsilon$, threshold $\tau$
1 $\xi \leftarrow \operatorname{Lap}(2/\varepsilon)$
2 **for** $t=s+1,\ldots,T$ **do**
3 $\nu_t \leftarrow \operatorname{Lap}(4/\varepsilon)$
4 Receive $q_t$
5 **if** $q_t+\nu_t \ge \tau+\xi$ **then**
6 $\sigma_t \leftarrow \top$
7 **Halt.**
8 **else**
9 $\sigma_t \leftarrow \bot$
10 **end**
11 **end**

Lower bound for adaptive adversaries

Before presenting the proof, we first formally define differential privacy against an adaptive adversary. Let $\mathcal{A}$ be an online learner, $\mathcal{D}$ be an adversary, and $b \in\{0,1\}$ be a hidden bit that is unknown to both $\mathcal{A}$ and $\mathcal{D}$. Define the privacy game played between $\mathcal{A}$ and $\mathcal{D}$ as follows. At each round $t \in[T]$, the adversary $\mathcal{D}$ generates two loss functions $\ell_t^0$ and $\ell_t^1$ and the algorithm produces an output $i_t$, both based on the interaction history up to round $t-1$. After these choices are made, $\mathcal{A}$ receives $\ell_t^b$ while $\mathcal{D}$ observes $i_t$. During the entire game, the adversary $\mathcal{D}$ ensures that $\ell_t^0=\ell_t^1$ for all $t \in[T]\setminus\{\tilde{t}\}$, where $\tilde{t}$ is a special round that is chosen adaptively by $\mathcal{D}$ (i.e., the choice of $\tilde{t}$ can depend on the interaction history before round $\tilde{t}$). Let $\operatorname{View}_{\mathcal{A},\mathcal{D}}(b)$ denote the view of $\mathcal{D}$ in this privacy game, including the internal randomness of $\mathcal{D}$ and $(i_1,\ldots,i_T)$ produced by $\mathcal{A}$. Differential privacy against adaptive adversaries is defined as follows.

Our proof is based on the following lower bound from [3] that holds in the high-privacy regime.

Remark. The above lemma can be obtained by setting $\varepsilon\le1/(\sqrt{T}\ln T)$ and $\delta\le T^{-3}$ in Theorem 9 of [3]. While the theorem statement does not explicitly state that $L^\star=0$, the proof actually constructs a realizable input sequence.

Our idea can be seen as extending the privacy amplification technique to the online setting.

We first establish the privacy guarantee of $\mathcal{A}_q$. In the proof, we write $P\approx_{(\varepsilon,\delta)}Q$ to denote that distributions $P$ and $Q$ are $(\varepsilon,\delta)$-close, i.e., they satisfy the inequalities defining DP:

for any event $O$.

Proof. Let $\mathcal{D}$ be any adversary that interacts with $\mathcal{A}_q$. Write

for $b \in\{0,1\}$. Let $P_b$ be the distribution of $V_b$. Introduce the following three auxiliary view distributions:

• $P^{-}$: the distribution of $\mathcal{D}$’s view in an auxiliary privacy game where $Z_{\tilde{t}}$ is set deterministically to 0, while all other sampling coins are drawn as usual.

• $P_0^{+}$: the distribution of $\mathcal{D}$’s view in an auxiliary privacy game with $b=0$ where $Z_{\tilde{t}}$ is set deterministically to 1, while all other sampling coins are drawn as usual.

• $P_1^{+}$: the distribution of $\mathcal{D}$’s view in an auxiliary privacy game with $b=1$ where $Z_{\tilde{t}}$ is set deterministically to 1, while all other sampling coins are drawn as usual.

Since $\tilde{t}$ is chosen based on the interaction history before round $\tilde{t}$, while $Z_{\tilde{t}}$ is sampled independently at round $\tilde{t}$, we have

where the first term is due to the fact that $\mathcal{A}$ receives $\tilde{\ell}_{\tilde{t}} = Z_{\tilde{t}}\ell_{\tilde{t}}^b = 0$ whenever $Z_{\tilde{t}}=0$, regardless of the value of $b$.

Now we derive privacy relations among $P^{-}$, $P_0^{+}$, and $P_1^{+}$. We first consider $P_0^{+}$ and $P_1^{+}$. Construct an adversary $\mathcal{D}^{+}$ that simulates $\mathcal{D}$ and at each round $t \ne\tilde{t}$ draws $Z_t \sim\operatorname{Ber}(q)$ and generates

At round $\tilde{t}$, it generates

It is easy to check that $\mathcal{D}^{+}$ is a valid adversary in the privacy game with $\mathcal{A}$: it only generates different loss functions at round $\tilde{t}$. For $b \in\{0,1\}$, the resulting interaction is exactly the branch defining $P_b^{+}$. By the privacy guarantee of $\mathcal{A}$ and the fact that the view of $\mathcal{D}$ can be seen as a post-processing of $\mathcal{D}^{+}$’s view, we have $P_0^{+} \approx_{(\varepsilon,\delta)} P_1^{+}$.

Next we compare $P_0^{+}$ with $P^{-}$. Construct an adversary $\mathcal{D}^{-}$ that performs the same simulation as $\mathcal{D}^{+}$ at round $t \ne\tilde{t}$. At round $\tilde{t}$, it generates

For $b=0$, the interaction is again the branch defining $P_0^{+}$. For $b=1$, the interaction becomes the branch defining $P^{-}$. Therefore, we have $P_0^{+} \approx_{(\varepsilon,\delta)} P^{-}$. We can similarly prove that $P_1^{+} \approx_{(\varepsilon,\delta)} P^{-}$.

We now prove the final conclusion. For any measurable set $O$, write $x=P_0^{+}(O)$, $y=P_1^{+}(O)$, and $z=P^{-}(O)$. By the pairwise $(\varepsilon,\delta)$-closeness of $P_0^{+}$, $P_1^{+}$, and $P^{-}$, we have $x \le e^\varepsilon y+\delta$ and $x \le e^\varepsilon z+\delta$. Hence,

where the second inequality follows because

By symmetry, $P_1(O) \le(1+q(e^\varepsilon-1))P_0(O)+q\delta$. This proves the desired result.

Proof. Let $\ell_1,\ldots,\ell_T$ be a realizable sequence generated by an adaptive adversary. There exists $i^\star\in[N]$ such that $\ell_t(i^\star)=0$ for all $t \in[T]$. By definition, $\widetilde{\ell}_t(i^\star)=Z_t\ell_t(i^\star)=0$. This implies that the sequence $\widetilde{\ell}_1,\ldots,\widetilde{\ell}_T$ is also realizable. Therefore,

On the other hand, since $Z_t$ is independent of $i_t$ and $\ell_t$, we have

Summing over $t$ gives

Rearranging the inequality yields the desired conclusion. □

Proof. Suppose $\mathcal{A}$ is adaptively $(\varepsilon,\delta)$-DP and has expected cumulative loss at most $R_{\mathcal{A}}(T)$ on realizable input sequences. Consider $\mathcal{A}_q$ in Definition C.3 with

Lemma C.4 establishes that $\mathcal{A}_q$ is adaptively $(\ln(1+q(e^\varepsilon-1)),q\delta)$-differentially private. Since $\varepsilon\le1$, we have

Moreover,

Therefore, $\mathcal{A}_q$ is adaptively $(1/(\sqrt{T}\ln T),T^{-3})$-differentially private. By Lemma C.2, $\mathcal{A}_q$ must incur an expected cumulative loss of $\Omega(T)$. Lemma C.5 then yields

□