  Online prediction from experts is a fundamental problem in machine learning
and several works have studied this problem under privacy constraints. We
propose and analyze new algorithms for this problem that improve over the
regret bounds of the best existing algorithms for non-adaptive adversaries. For
approximate differential privacy, our algorithms achieve regret bounds of
$\tilde{O}(\sqrt{T \log d} + \log d/\varepsilon)$ for the stochastic setting
and $\tilde{O}(\sqrt{T \log d} + T^{1/3} \log d/\varepsilon)$ for oblivious
adversaries (where $d$ is the number of experts). For pure DP, our algorithms
are the first to obtain sub-linear regret for oblivious adversaries in the
high-dimensional regime $d \ge T$. Moreover, we prove new lower bounds for
adaptive adversaries. Our results imply that unlike the non-private setting,
there is a strong separation between the optimal regret for adaptive and
non-adaptive adversaries for this problem. Our lower bounds also show a
separation between pure and approximate differential privacy for adaptive
adversaries where the latter is necessary to achieve the non-private
$O(\sqrt{T})$ regret.
