Differentially Private Submodular Maximization: Data Summarization in Disguise
Many data summarization applications are captured by the general framework of submodular maximization. As a consequence, a wide range of efficient approximation algorithms have been developed. However, when such applications involve sensitive data about individuals, their privacy concerns are not automatically addressed. To remedy this problem, we propose a general and systematic study of differentially private submodular maximization. We present privacy-preserving algorithms for both monotone and non-monotone submodular maximization under cardinality, matroid, and p-extendible system constraints, with guarantees that are competitive with optimal. Along the way, we analyze a new algorithm for non-monotone submodular maximization, which is the first (even non-privately) to achieve a constant approximation ratio while running in linear time. We additionally provide two concrete experiments to validate the efficacy of these algorithms.
Code (0)
등록된 구현이 없습니다.
Tasks
Data SummarizationPrivacy PreservingSimilar Papers 제목 키워드 기반
Differentially Private Decomposable Submodular Maximization
We study the problem of differentially private constrained maximization of decomposable submodular functions. A submodular function is decomposable if it takes the form of a sum of submodular functions. The special case …
Streaming Submodular Maximization with Differential Privacy
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 d…
Streaming Submodular Maximization under a k-Set System Constraint
In this paper, we propose a novel framework that converts streaming algorithms for monotone submodular maximization into streaming algorithms for non-monotone submodular maximization. This reduction readily leads to the …
Data SummarizationMovie RecommendationStreaming Submodular Maximization under a $k$-Set System Constraint
In this paper, we propose a novel framework that converts streaming algorithms for monotone submodular maximization into streaming algorithms for non-monotone submodular maximization. This reduction readily leads to the …
Data SummarizationMovie RecommendationFast and Private Submodular and $k$-Submodular Functions Maximization with Matroid Constraints
The problem of maximizing nonnegative monotone submodular functions under a certain constraint has been intensively studied in the last decade, and a wide range of efficient approximation algorithms have been developed f…
Data Summarization