Decomposable Submodular Maximization in Federated Setting
Akbar Rafiey
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.