As stated earlier, differentially private algorithms typically require specification of the global sensitivity of the
function whose outputs are being privatized (see Definition REF  and Lemma REF ).
This can become arbitrarily complex for complicated models even assuming a bounded input domain.
The Sample-Aggregate paradigm introduced in [1]} suggests that one way to deal with this is
to run the algorithm of interest non-privately over \(k\)  disjoint subsets of the data, bound
the outputs, and then aggregate the results using a function with a sensitivity that is
easier to reason about (e.g. the mean). Because each element in the original data
contributes to one subset of the partition, its effect on the aggregation is localized
to one of its \(k\)  inputs and we can treat this just like privatizing the mean of a data set with
\(k\)  elements.
