Differentially Private Decomposable Submodular Maximization

• URL: http://arxiv.org/abs/2005.14717v1
• Date: Fri, 29 May 2020 17:59:46 GMT
• Title: Differentially Private Decomposable Submodular Maximization
• Authors: Anamay Chaturvedi, Huy Nguyen, Lydia Zakynthinou
• Abstract summary: 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.
• Score: 12.835348339847762
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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 of maximizing a monotone, decomposable submodular function under cardinality constraints is known as the Combinatorial Public Projects (CPP) problem [Papadimitriou et al., 2008]. Previous work by Gupta et al. [2010] gave a differentially private algorithm for the CPP problem. We extend this work by designing differentially private algorithms for both monotone and non-monotone decomposable submodular maximization under general matroid constraints, with competitive utility guarantees. We complement our theoretical bounds with experiments demonstrating empirical performance, which improves over the differentially private algorithms for the general case of submodular maximization and is close to the performance of non-private algorithms.

Related papers

• Individualized Privacy Accounting via Subsampling with Applications in Combinatorial Optimization [55.81991984375959]
  In this work, we give a new technique for analyzing individualized privacy accounting via the following simple observation. We obtain several improved algorithms for private optimization problems, including decomposable submodular and set algorithm cover.
  arXiv  Detail & Related papers  (2024-05-28T19:02:30Z)
• Streaming Submodular Maximization with Differential Privacy [8.04779839951237]
  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.
  arXiv  Detail & Related papers  (2022-10-25T20:18:10Z)
• Using Partial Monotonicity in Submodular Maximization [13.23676270963484]
  We show that for many standard submodular algorithms one can prove new approximation guarantees that depend on the monotonicity ratio. This leads to improved approximation ratios for the common machine learning applications of movie recommendation, quadratic programming and image summarization.
  arXiv  Detail & Related papers  (2022-02-07T10:35:40Z)
• Randomized Algorithms for Monotone Submodular Function Maximization on the Integer Lattice [5.543220407902113]
  We consider the problem of maximizing a monotone submodular function on a bounded integer lattice subject to a cardinality constraint. In particular, we focus on maximizing DR-submodular functions, i.e., functions defined on the integer lattice that exhibit the diminishing returns property. Applying our proposed algorithm on the integer lattice is faster than the alternatives, including reducing a target problem to the set domain and then applying the fastest known set submodular algorithm.
  arXiv  Detail & Related papers  (2021-11-19T12:07:16Z)
• 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)
• Universal Online Convex Optimization Meets Second-order Bounds [74.0120666722487]
  We propose a simple strategy for universal online convex optimization. The key idea is to construct a set of experts to process the original online functions, and deploy a meta-algorithm over the linearized losses. In this way, we can plug in off-the-shelf online solvers as black-box experts to deliver problem-dependent regret bounds.
  arXiv  Detail & Related papers  (2021-05-08T11:43:49Z)
• Multi-objective Evolutionary Algorithms are Generally Good: Maximizing Monotone Submodular Functions over Sequences [44.11102526976392]
  This paper studies the problem class of maximizing monotone submodular functions over sequences. EAs can achieve good approximation guarantees for solving the problem classes of submodular optimization. Empirical studies on various applications, e.g., accomplishing tasks, maximizing information gain, search-and-tracking and recommender systems, show the excellent performance of the GSEMO.
  arXiv  Detail & Related papers  (2021-04-20T10:36:10Z)
• 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)

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.