Streaming Submodular Maximization with Differential Privacy
- URL: http://arxiv.org/abs/2210.14315v1
- Date: Tue, 25 Oct 2022 20:18:10 GMT
- Title: Streaming Submodular Maximization with Differential Privacy
- Authors: Anamay Chaturvedi, Huy L\^e Nguyen, Thy Nguyen
- Abstract summary: We study the problem of privately maximizing a submodular function in the streaming setting.
A submodular function is decomposable when it can be written as a sum of submodular functions.
- Score: 8.04779839951237
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: 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.
Related papers
- Maximizing Submodular Functions for Recommendation in the Presence of
Biases [25.081136190260015]
Subset selection tasks arise in systems and search engines and ask to select a subset of items that maximize the value for the user.
In many applications, inputs have been observed to have social biases that reduce the utility of the output subset.
We show that fairness constraint-based interventions can not only ensure proportional representation but also achieve near-optimal utility in the presence of biases.
arXiv Detail & Related papers (2023-05-03T15:20:00Z) - Neural Estimation of Submodular Functions with Applications to
Differentiable Subset Selection [50.14730810124592]
Submodular functions and variants, through their ability to characterize diversity and coverage, have emerged as a key tool for data selection and summarization.
We propose FLEXSUBNET, a family of flexible neural models for both monotone and non-monotone submodular functions.
arXiv Detail & Related papers (2022-10-20T06:00:45Z) - On Differential Privacy for Federated Learning in Wireless Systems with
Multiple Base Stations [90.53293906751747]
We consider a federated learning model in a wireless system with multiple base stations and inter-cell interference.
We show the convergence behavior of the learning process by deriving an upper bound on its optimality gap.
Our proposed scheduler improves the average accuracy of the predictions compared with a random scheduler.
arXiv Detail & Related papers (2022-08-25T03:37:11Z) - Sparsification of Decomposable Submodular Functions [27.070004659301162]
Submodular functions are at the core of many machine learning and data mining tasks.
The number of underlying submodular functions in the original function is so large that we need large amount of time to process it and/or it does not even fit in the main memory.
We introduce the notion of sparsification for decomposable submodular functions whose objective is to obtain an accurate approximation of the original function is a (weighted) sum of only a few submodular functions.
arXiv Detail & Related papers (2022-01-18T20:05:25Z) - Submodular + Concave [53.208470310734825]
It has been well established that first order optimization methods can converge to the maximal objective value of concave functions.
In this work, we initiate the determinant of the smooth functions convex body $$F(x) = G(x) +C(x)$.
This class of functions is an extension of both concave and continuous DR-submodular functions for which no guarantee is known.
arXiv Detail & Related papers (2021-06-09T01:59:55Z) - Planning with Submodular Objective Functions [118.0376288522372]
We study planning with submodular objective functions, where instead of maximizing cumulative reward, the goal is to maximize the value induced by a submodular function.
Our framework subsumes standard planning and submodular objective with cardinality constraints as special cases.
arXiv Detail & Related papers (2020-10-22T16:55:12Z) - Fast and Private Submodular and $k$-Submodular Functions Maximization
with Matroid Constraints [27.070004659301162]
We study the problem of maximizing monotone submodular functions subject to matroid constraints in the framework of differential privacy.
We give the first $frac12$-approximation algorithm that preserves $k$submodular functions subject to matroid constraints.
arXiv Detail & Related papers (2020-06-28T23:18:58Z) - Continuous Submodular Function Maximization [91.17492610120324]
Continuous submodularity is a class of functions with a wide spectrum of applications.
We identify several applications of continuous submodular optimization, ranging from influence, MAP for inferences to inferences to field field.
arXiv Detail & Related papers (2020-06-24T04:37:31Z) - From Sets to Multisets: Provable Variational Inference for Probabilistic
Integer Submodular Models [82.95892656532696]
Submodular functions have been studied extensively in machine learning and data mining.
In this work, we propose a continuous DR-submodular extension for integer submodular functions.
We formulate a new probabilistic model which is defined through integer submodular functions.
arXiv Detail & Related papers (2020-06-01T22:20:45Z) - Differentially Private Decomposable Submodular Maximization [12.835348339847762]
We study the problem of differentially private constrained of decomposable submodular functions.
A submodular function is decomposable if it takes the form of a sum of submodular functions.
We design differentially private algorithms for both monotone and non-monotone decomposable submodular under general matroid constraints.
arXiv Detail & Related papers (2020-05-29T17:59:46Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.