  Sketching is an important tool for dealing with high-dimensional vectors that
are sparse (or well-approximated by a sparse vector), especially useful in
distributed, parallel, and streaming settings. It is known that sketches can be
made differentially private by adding noise according to the sensitivity of the
sketch, and this has been used in private analytics and federated learning
settings. The post-processing property of differential privacy implies that all
estimates computed from the sketch can be released within the given privacy
budget.
  In this paper we consider the classical CountSketch, made differentially
private with the Gaussian mechanism, and give an improved analysis of its
estimation error. Perhaps surprisingly, the privacy-utility trade-off is
essentially the best one could hope for, independent of the number of
repetitions in CountSketch: The error is almost identical to the error from
non-private CountSketch plus the noise needed to make the vector private in the
original, high-dimensional domain.
