Decomposable submodular maximization in federated setting
Article No.: 1702, Pages 41841 - 41866
Abstract
Submodular functions, as well as the subclass 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 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 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.
References
[1]
Agarwal, N., Suresh, A. T., Yu, F. X., Kumar, S., and McMahan, B. cpsgd: Communication-efficient and differentially-private distributed SGD. In NeurIPS 2018, pp. 7575-7586, 2018.
[2]
Agarwal, N., Kairouz, P., and Liu, Z. The skellam mechanism for differentially private federated learning. In NeurIPS 2021, pp. 5052-5064, 2021.
[3]
Barbosa, R. D. P., Ene, A., Nguyen, H. L., and Ward, J. The power of randomization: Distributed submodular maximization on massive datasets. In ICML, volume 37, pp. 1236-1244. JMLR.org, 2015.
[4]
Bell, J. H., Bonawitz, K. A., Gascón, A., Lepoint, T., and Raykova, M. Secure single-server aggregation with (poly)logarithmic overhead. In CCS, pp. 1253-1269. ACM, 2020.
[5]
Bonawitz, K. A., Ivanov, V., Kreuter, B., Marcedone, A., McMahan, H. B., Patel, S., Ramage, D., Segal, A., and Seth, K. Practical secure aggregation for federated learning on user-held data. CoRR, abs/1611.04482, 2016.
[6]
Călinescu, G., Chekuri, C., Pál, M., and Vondrák, J. Maximizing a monotone submodular function subject to a matroid constraint. SIAM J. Comput., 40(6):1740-1766, 2011.
[7]
Chaturvedi, A., Nguyen, H. L., and Zakynthinou, L. Differentially private decomposable submodular maximization. In AAAI, pp. 6984-6992, 2021.
[8]
Chekuri, C., Vondrák, J., and Zenklusen, R. Dependent randomized rounding via exchange properties of combinatorial structures. In FOCS, pp. 575-584. IEEE Computer Society, 2010.
[9]
Chen, W., Choquette-Choo, C. A., Kairouz, P., and Suresh, A. T. The fundamental price of secure aggregation in differentially private federated learning. In ICML, volume 162, pp. 3056-3089. PMLR, 2022a.
[10]
Chen, W., Horváth, S., and Richtárik, P. Optimal client sampling for federated learning. Transactions on Machine Learning Research, 2022b. ISSN 2835-8856.
[11]
Dadras, A., Prakhya, K., and Yurtsever, A. Federated frank-wolfe algorithm. In Workshop on Federated Learning: Recent Advances and New Challenges (in Conjunction with NeurIPS), 2022.
[12]
Dobzinski, S. and Schapira, M. An improved approximation algorithm for combinatorial auctions with submodular bidders. In SODA, pp. 1064-1073, 2006.
[13]
Dueck, D. and Frey, B. J. Non-metric affinity propagation for unsupervised image categorization. In ICCV, pp. 1-8, 2007.
[14]
Edmonds, J. Submodular functions, matroids, and certain polyhedra. In Combinatorial Optimization - Eureka, You Shrink!, pp. 11-26, 2001.
[15]
Feige, U. A threshold of ln n for approximating set cover. J. ACM, 45(4):634-652, 1998.
[16]
Feige, U. On maximizing welfare when utility functions are subadditive. In STOC, pp. 41-50, 2006.
[17]
Feige, U. and Vondrák, J. Approximation algorithms for allocation problems: Improving the factor of 1 - 1/e. In FOCS, pp. 667-676, 2006.
[18]
Frank, M. and Wolfe, P. An algorithm for quadratic programming. Naval research logistics quarterly, 3(1-2): 95-110, 1956.
[19]
Gomes, R. and Krause, A. Budgeted nonparametric learning from data streams. In ICML, pp. 391-398, 2010.
[20]
Gorbunov, E., Hanzely, F., and Richtárik, P. Local SGD: unified theory and new efficient methods. In AISTATS, volume 130, pp. 3556-3564. PMLR, 2021.
[21]
Gupta, A., Ligett, K., McSherry, F., Roth, A., and Talwar, K. Differentially private combinatorial optimization. In SODA, pp. 1106-1125. SIAM, 2010.
[22]
Hassani, S. H., Soltanolkotabi, M., and Karbasi, A. Gradient methods for submodular maximization. In NeurIPS, pp. 5841-5851, 2017.
[23]
Kairouz, P., Liu, Z., and Steinke, T. The distributed discrete gaussian mechanism for federated learning with secure aggregation. In ICML, volume 139, pp. 5201-5212. PMLR, 2021.
[24]
Karimireddy, S. P., Kale, S., Mohri, M., Reddi, S. J., Stich, S. U., and Suresh, A. T. SCAFFOLD: stochastic controlled averaging for federated learning. In ICML, volume 119, pp. 5132-5143. PMLR, 2020.
[25]
Kenneth, Y. and Krauthgamer, R. Cut sparsification and succinct representation of submodular hypergraphs. CoRR, abs/2307.09110, 2023.
[26]
Khot, S., Lipton, R. J., Markakis, E., and Mehta, A. In-approximability results for combinatorial auctions with submodular utility functions. Algorithmica, 52(1):3-18, 2008.
[27]
Konečnỳ, J., McMahan, H. B., Ramage, D., and Richtárik, P. Federated optimization: distributed machine learning for on-device intelligence. arXiv preprint arXiv:1610.02527, 2016.
[28]
Krause, A. and Guestrin, C. Near-optimal nonmyopic value of information in graphical models. In UAI, pp. 324-331, 2005.
[29]
Kumar, R., Moseley, B., Vassilvitskii, S., and Vattani, A. Fast greedy algorithms in mapreduce and streaming. ACM Trans. Parallel Comput., 2(3):14:1-14:22, 2015.
[30]
Lehmann, B., Lehmann, D., and Nisan, N. Combinatorial auctions with decreasing marginal utilities. Games Econ. Behav., 55(2):270-296, 2006.
[31]
Li, X., Huang, K., Yang, W., Wang, S., and Zhang, Z. On the convergence of fedavg on non-iid data. In ICLR. OpenReview.net, 2020.
[32]
Lin, H. and Bilmes, J. A. A class of submodular functions for document summarization. In HLT, pp. 510-520, 2011.
[33]
McMahan, B., Moore, E., Ramage, D., Hampson, S., and y Arcas, B. A. Communication-efficient learning of deep networks from decentralized data. In AISTATS, volume 54, pp. 1273-1282. PMLR, 2017.
[34]
Mirrokni, V. S., Schapira, M., and Vondrák, J. Tight information-theoretic lower bounds for welfare maximization in combinatorial auctions. In EC, pp. 70-77. ACM, 2008.
[35]
Mirzasoleiman, B. Big Data Summarization Using Sub-modular Functions. PhD thesis, ETH Zurich, Zürich, Switzerland, 2017.
[36]
Mirzasoleiman, B., Badanidiyuru, A., and Karbasi, A. Fast constrained submodular maximization: Personalized data summarization. In ICML, volume 48, pp. 1358-1367, 2016a.
[37]
Mirzasoleiman, B., Karbasi, A., Sarkar, R., and Krause, A. Distributed submodular maximization. J. Mach. Learn. Res., 17:238:1-238:44, 2016b.
[38]
Mitrovic, M., Bun, M., Krause, A., and Karbasi, A. Differentially private submodular maximization: Data summarization in disguise. In ICML, pp. 2478-2487, 2017.
[39]
Mokhtari, A., Hassani, H., and Karbasi, A. Conditional gradient method for stochastic submodular maximization: Closing the gap. In AISTATS, volume 84, pp. 1886-1895. PMLR, 2018a.
[40]
Mokhtari, A., Hassani, H., and Karbasi, A. Decentralized submodular maximization: Bridging discrete and continuous settings. In ICML, volume 80, pp. 3613-3622. PMLR, 2018b.
[41]
Nemhauser, G. L., Wolsey, L. A., and Fisher, M. L. An analysis of approximations for maximizing submodular set functions - I. Math. Program., 14(1):265-294, 1978.
[42]
Papadimitriou, C. H., Schapira, M., and Singer, Y. On the hardness of being truthful. In FOCS, pp. 250-259. IEEE Computer Society, 2008.
[43]
Pathak, R. and Wainwright, M. J. Fedsplit: an algorithmic framework for fast federated optimization. In NeurIPS, volume 33, pp. 7057-7066, 2020.
[44]
Rafiey, A. and Yoshida, Y. Fast and private submodular and k-submodular functions maximization with matroid constraints. In ICML, pp. 7887-7897, 2020.
[45]
Rafiey, A. and Yoshida, Y. Sparsification of decomposable submodular functions. In AAAI, pp. 10336-10344. AAAI Press, 2022.
[46]
Stan, S., Zadimoghaddam, M., Krause, A., and Karbasi, A. Probabilistic submodular maximization in sublinear time. In ICML, volume 70, pp. 3241-3250. PMLR, 2017.
[47]
Stich, S. U. Local SGD converges fast and communicates little. In ICLR. OpenReview.net, 2019.
[48]
Tschiatschek, S., Iyer, R. K., Wei, H., and Bilmes, J. A. Learning mixtures of submodular functions for image collection summarization. In NeurIPS, pp. 1413-1421, 2014.
[49]
Vondrák, J. Optimal approximation for the submodular welfare problem in the value oracle model. In STOC, pp. 67-74, 2008.
[50]
Wang, J. and Joshi, G. Cooperative SGD: A unified framework for the design and analysis of local-update SGD algorithms. J. Mach. Learn. Res., 22:213:1-213:50, 2021.
[51]
Wang, S., Tuor, T., Salonidis, T., Leung, K. K., Makaya, C., He, T., and Chan, K. Adaptive federated learning in resource constrained edge computing systems. IEEE J. Sel. Areas Commun., 37(6):1205-1221, 2019.
[52]
Wang, Y., Zhou, T., Chen, C., and Wang, Y. Federated submodular maximization with differential privacy. IEEE Internet of Things Journal, 2023.
[53]
Woodworth, B. E., Patel, K. K., Stich, S. U., Dai, Z., Bullins, B., McMahan, H. B., Shamir, O., and Srebro, N. Is local SGD better than minibatch sgd? In ICML, volume 119, pp. 10334-10343. PMLR, 2020.
[54]
Yu, H., Yang, S., and Zhu, S. Parallel restarted SGD with faster convergence and less communication: Demystifying why model averaging works for deep learning. In AAAI, pp. 5693-5700. AAAI Press, 2019.
[55]
Zhang, M., Zhou, Y., Ge, Q., Zheng, R., and Wu, Q. Decentralized randomized block-coordinate frank-wolfe algorithms for submodular maximization over networks. IEEE Trans. Syst. Man Cybern. Syst., 52(8):5081-5091, 2022.
[56]
Zhang, X., Hong, M., Dhople, S. V., Yin, W., and Liu, Y. Fedpd: A federated learning framework with optimal rates and adaptivity to non-iid data. CoRR, abs/2005.11418, 2020.
Index Terms
- Decomposable submodular maximization in federated setting
Index terms have been assigned to the content through auto-classification.
Recommendations
Efficient minimization of decomposable submodular functions
NIPS'10: Proceedings of the 24th International Conference on Neural Information Processing Systems - Volume 2Many combinatorial problems arising in machine learning can be reduced to the problem of minimizing a submodular function. Submodular functions are a natural discrete analog of convex functions, and can be minimized in strongly polynomial time. ...
Differentiable submodular maximization
IJCAI'18: Proceedings of the 27th International Joint Conference on Artificial IntelligenceWe consider learning of submodular functions from data. These functions are important in machine learning and have a wide range of applications, e.g. data summarization, feature selection and active learning. Despite their combinatorial nature, ...
Non-submodular maximization with a decomposable objective function
AbstractWe study the non-submodular maximization problem, whose objective function can be expressed as the Difference between two Set (DS) functions or the Ratio between two Set (RS) functions. For the cardinality-constrained and unconstrained DS ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
July 2024
63010 pages
Copyright © 2024.
Publisher
JMLR.org
Publication History
Published: 21 July 2024
Qualifiers
- Research-article
- Research
- Refereed limited
Acceptance Rates
Overall Acceptance Rate 140 of 548 submissions, 26%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 05 Mar 2025