  In this work, we study the problem of privately maximizing a submodular
function in the streaming setting. Extensive work has been done on privately
maximizing submodular functions in the general case when the function depends
upon the private data of individuals. However, when the size of the data stream
drawn from the domain of the objective function is large or arrives very fast,
one must privately optimize the objective within the constraints of the
streaming setting. We establish fundamental differentially private baselines
for this problem and then derive better trade-offs between privacy and utility
for the special case of decomposable submodular functions. A submodular
function is decomposable when it can be written as a sum of submodular
functions; this structure arises naturally when each summand function models
the utility of an individual and the goal is to study the total utility of the
whole population as in the well-known Combinatorial Public Projects Problem.
Finally, we complement our theoretical analysis with experimental
corroboration.
