  Differentially private mechanisms achieving worst-case optimal error bounds
(e.g., the classical Laplace mechanism) are well-studied in the literature.
However, when typical data are far from the worst case,
\emph{instance-specific} error bounds -- which depend on the largest value in
the dataset -- are more meaningful. For example, consider the sum estimation
problem, where each user has an integer $x_i$ from the domain $\{0,1,\dots,U\}$
and we wish to estimate $\sum_i x_i$. This has a worst-case optimal error of
$O(U/\varepsilon)$, while recent work has shown that the clipping mechanism can
achieve an instance-optimal error of $O(\max_i x_i \cdot \log\log U
/\varepsilon)$. Under the shuffle model, known instance-optimal protocols are
less communication-efficient. The clipping mechanism also works in the shuffle
model, but requires two rounds: Round one finds the clipping threshold, and
round two does the clipping and computes the noisy sum of the clipped data. In
this paper, we show how these two seemingly sequential steps can be done
simultaneously in one round using just $1+o(1)$ messages per user, while
maintaining the instance-optimal error bound. We also extend our technique to
the high-dimensional sum estimation problem and sparse vector aggregation
(a.k.a. frequency estimation under user-level differential privacy). Our
experiments show order-of-magnitude improvements of our protocols in terms of
error compared with prior work.
