Locally Differentially Private Distributed Online Learning with
  Guaranteed Optimality
Ziqin Chen Yongqiang Wang
Distributed online learning is gaining increased traction due to its unique
ability to process large-scale datasets and streaming data. To address the
growing public awareness and concern on privacy protection, plenty of private
distributed online learning algorithms have been proposed, mostly based on
differential privacy which has emerged as the ``gold standard" for privacy
protection. However, these algorithms often face the dilemma of trading
learning accuracy for privacy. By exploiting the unique characteristics of
online learning, this paper proposes an approach that tackles the dilemma and
ensures both differential privacy and learning accuracy in distributed online
learning. More specifically, while ensuring a diminishing expected
instantaneous regret, the approach can simultaneously ensure a finite
cumulative privacy budget, even on the infinite time horizon. To cater for the
fully distributed setting, we adopt the local differential-privacy framework
which avoids the reliance on a trusted data curator, and hence, provides
stronger protection than the classic ``centralized" (global) differential
privacy. To the best of our knowledge, this is the first algorithm that
successfully ensures both rigorous local differential privacy and learning
accuracy. The effectiveness of the proposed algorithm is evaluated using
machine learning tasks, including logistic regression on the ``Mushrooms" and
``Covtype" datasets and CNN based image classification on the ``MNIST" and
``CIFAR-10" datasets.