Submodular functions, as well as the sub-class of decomposable submodular
functions, and their optimization appear in a wide range of applications in
machine learning, recommendation systems, and welfare maximization. However,
optimization of decomposable submodular functions with millions of component
functions is computationally prohibitive. Furthermore, the component functions
may be private (they might represent user preference function, for example) and
cannot be widely shared. To address these issues, we propose a {\em federated
optimization} setting for decomposable submodular optimization. In this
setting, clients have their own preference functions, and a weighted sum of
these preferences needs to be maximized. We implement the popular {\em
continuous greedy} algorithm in this setting where clients take parallel small
local steps towards the local solution and then the local changes are
aggregated at a central server. To address the large number of clients, the
aggregation is performed only on a subsampled set. Further, the aggregation is
performed only intermittently between stretches of parallel local steps, which
reduces communication cost significantly. We show that our federated algorithm
is guaranteed to provide a good approximate solution, even in the presence of
above cost-cutting measures. Finally, we show how the federated setting can be
incorporated in solving fundamental discrete submodular optimization problems
such as Maximum Coverage and Facility Location.

提出了一种联邦优化设置的分解可分模函数的优化方法，使用连续贪婪算法在客户端和中央服务器之间进行并行小步骤的局部优化，通过抽样和定期聚合来减少通信成本，并展示了如何与最大覆盖和设施位置等离散分解模最优化问题相结合。