We study the problem of private online learning, specifically, online
prediction from experts (OPE) and online convex optimization (OCO). We propose
a new transformation that transforms lazy online learning algorithms into
private algorithms. We apply our transformation for differentially private OPE
and OCO using existing lazy algorithms for these problems. Our final algorithms
obtain regret, which significantly improves the regret in the high privacy
regime $\varepsilon \ll 1$, obtaining $\sqrt{T \log d} + T^{1/3}
\log(d)/\varepsilon^{2/3}$ for DP-OPE and $\sqrt{T} + T^{1/3}
\sqrt{d}/\varepsilon^{2/3}$ for DP-OCO. We also complement our results with a
lower bound for DP-OPE, showing that these rates are optimal for a natural
family of low-switching private algorithms.

我们研究了私密在线学习的问题，特别是专家预测（OPE）和在线凸优化（OCO）。我们提出了一种将惰性在线学习算法转化为私密算法的新方法。我们通过使用现有的惰性算法解决这些问题，将我们的转化应用于差分隐私 OPE 和 OCO。我们的最终算法在高隐私水平 ε≪1 下获得显著改进的后悔，对于 DP-OPE 为√(Tlogd) + (T^(1/3) log (d))/ε^(2/3)，对于 DP-OCO 为√T + (T^(1/3)√d)/ε^(2/3)。我们通过对 DP-OPE 进行下界的研究，进一步补充了我们的结果，表明这些速率对于一类自然的低转换私密算法来说是最优的。

通过懒惰算法实现私密在线学习

Private Online Learning via Lazy Algorithms

One of the most basic problems for studying the "price of privacy over time"
is the so called private counter problem, introduced by Dwork et al. (2010) and
Chan et al. (2010). In this problem, we aim to track the number of events that
occur over time, while hiding the existence of every single event. More
specifically, in every time step $t\in[T]$ we learn (in an online fashion) that
$\Delta_t\geq 0$ new events have occurred, and must respond with an estimate
$n_t\approx\sum_{j=1}^t \Delta_j$. The privacy requirement is that all of the
outputs together, across all time steps, satisfy event level differential
privacy. The main question here is how our error needs to depend on the total
number of time steps $T$ and the total number of events $n$. Dwork et al.
(2015) showed an upper bound of $O\left(\log(T)+\log^2(n)\right)$, and
Henzinger et al. (2023) showed a lower bound of $\Omega\left(\min\{\log n, \log
T\}\right)$. We show a new lower bound of $\Omega\left(\min\{n,\log
T\}\right)$, which is tight w.r.t. the dependence on $T$, and is tight in the
sparse case where $\log^2 n=O(\log T)$. Our lower bound has the following
implications:
$\bullet$ We show that our lower bound extends to the "online thresholds
problem", where the goal is to privately answer many "quantile queries" when
these queries are presented one-by-one. This resolves an open question of Bun
et al. (2017).
$\bullet$ Our lower bound implies, for the first time, a separation between
the number of mistakes obtainable by a private online learner and a non-private
online learner. This partially resolves a COLT'22 open question published by
Sanyal and Ramponi.
$\bullet$ Our lower bound also yields the first separation between the
standard model of private online learning and a recently proposed relaxed
variant of it, called private online prediction.

研究了随时间推移的隐私价格问题，其中包括私有计数问题、事件级差分隐私、在线阈值问题和私有在线学习等主题，并提出了相应的下界。