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.
翻译:在这项工作中,我们研究了在流成环境中私人最大限度地增加子模块功能的问题;在一般情况下,该功能取决于个人的私人数据时,已经就私人最大限度地增加子模块功能做了大量工作;然而,当从目标功能领域提取的数据流规模很大或到达非常快时,人们必须在流成环境的限制范围内私下优化目标;我们为该问题建立基本的差别私人基线,然后为分解子模块功能的特殊案例的隐私和实用性作出更好的权衡。当子模块函数可以写成子模块功能的总和时,该子模块函数是可分解的;当每个组合和功能模拟个人效用时,这种结构自然产生,目标是研究众所周知的组合公共项目问题中的全体人口的总体效用。最后,我们用实验性确证来补充我们的理论分析。