💻 computer science

Differentially Private Submodular Maximization with a Knapsack Constraint

This paper presents differentially private algorithms for submodular maximization under a knapsack constraint that achieve optimal or near-optimal approximation ratios for both monotone and non-monotone objectives while significantly improving additive error and query complexity compared to prior work.

Original authors: Ron Zadicario, Tova Milo

Published 2026-06-16

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Ron Zadicario, Tova Milo

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: The "Secret Recipe" Problem

Imagine you are a chef trying to create the perfect dish (the "optimal solution") using a limited set of ingredients.

The Ingredients: You have a huge pantry (the "ground set") with thousands of items.
The Rule of Diminishing Returns: This is the "submodular" part. It means the first onion you add adds a huge burst of flavor. The second onion adds a little more, but the tenth onion adds almost nothing. The value of adding an ingredient depends on what's already in the pot.
The Budget: You have a strict budget (the "knapsack constraint"). Some ingredients are cheap (like salt), while others are expensive (like saffron). You can't just buy everything; you have to pick the best combination that fits your wallet.

The Goal: Find the specific mix of ingredients that makes the tastiest dish possible without going over budget.

The Twist: Protecting the Secret Ingredient List

Now, imagine that your list of ingredients isn't just a grocery list; it's a secret medical record of your customers.

If you reveal which ingredients you picked, a hacker might figure out that a specific customer has a rare allergy or a specific disease.
Differential Privacy (DP): This is a mathematical "magic cloak." It ensures that when you show your final dish to the world, no one can tell if one specific customer's data was used to make it. The recipe looks almost the same whether Customer A is in the database or not.

The Problem: Usually, when you add this "magic cloak" to hide secrets, the dish tastes worse. The noise added to protect privacy ruins the flavor. Previous methods were either too slow (taking years to cook) or the resulting dish was barely edible (very low quality).

What This Paper Achieves

The authors, Ron Zadicario and Tova Milo, have cooked up new algorithms (recipes) that solve this problem much better than before. They tackled two types of cooking scenarios:

1. The "Always Better" Scenario (Monotone)

In this scenario, adding an ingredient never makes the dish worse. It might not add much flavor, but it won't ruin it.

The Old Way: Previous methods were like trying to guess the perfect recipe by tasting every possible combination of ingredients. It was slow and the privacy protection made the final dish taste terrible.
The New Way (Algorithm 2): They created a method that is optimal. It gets you 63% of the theoretical best taste (a famous benchmark in math called $1 - 1/e$ $1 - 1/ e$ ).
- The Analogy: Imagine you have a magic tasting spoon. Instead of tasting every single combination (which takes forever), this spoon intelligently samples the most promising combinations. It protects the customers' secrets so well that the "noise" added to the recipe is tiny. The result is a dish that tastes almost as good as the non-private version, but it's safe.
The Faster Way (Algorithm 7): They also made a "speedy" version. It's not quite as perfect (it gets 50% of the best taste), but it's incredibly fast and still keeps the secrets safe.

2. The "Sometimes Bad" Scenario (Non-Monotone)

In this scenario, adding an ingredient can ruin the dish. Maybe adding too much garlic overpowers the soup. This is harder to solve.

The Breakthrough: Before this paper, no one had a mathematically proven way to protect secrets in this tricky scenario while still getting a good dish.
The New Way (Algorithm 3): They introduced the first-ever method that guarantees a decent result (25% of the best taste) while protecting privacy.
- The Analogy: Think of this as a "toss-up" strategy. The algorithm picks a potential ingredient, flips a coin, and sometimes decides not to use it even if it looks good. This randomness helps hide the secrets. Then, at the end, it looks at all the "almost" dishes it made and picks the best one. It's a clever gamble that pays off.

Why This Matters (According to the Paper)

The paper doesn't claim these algorithms will cure diseases or run your business directly. Instead, it focuses on the math and efficiency:

Better Taste (Utility): Their algorithms produce results that are much closer to the "perfect dish" than previous privacy methods. The "error" (how much worse the dish tastes) is significantly smaller.
Faster Cooking (Query Complexity): They reduced the number of times the algorithm needs to "taste" the ingredients (query the data).
- Analogy: The old method might have needed to taste 1,000,000 combinations to find a good one. Their new method might only need 1,000. This makes it possible to use on massive datasets that were previously too slow to process.
First of Its Kind: For the tricky "non-monotone" case (where ingredients can ruin the dish), they are the first to provide a mathematically guaranteed solution that works under strict privacy rules.

Summary in a Nutshell

Think of this paper as a master chef who figured out how to cook a gourmet meal using a secret ingredient list without ever revealing who the customers are.

Before: You had to choose between a fast, unsafe meal or a slow, terrible-tasting safe meal.
Now: They offer a menu where you can get a meal that is both safe (mathematically proven privacy) and delicious (high quality), and it's cooked much faster than before. They even figured out how to do this for the most difficult, unpredictable recipes where ingredients can sometimes clash.

Technical Summary: Differentially Private Submodular Maximization with a Knapsack Constraint

1. Problem Definition

The paper addresses the Submodular Maximization subject to a Knapsack Constraint (SMK) problem under the framework of Differential Privacy (DP).

SMK Context: Given a ground set $N$ of $n$ elements, a submodular objective function $f: 2^N \to \mathbb{R}$ , a cost function $c: N \to \mathbb{R}_{>0}$ , and a budget $B$ , the goal is to find a subset $S \subseteq N$ such that $\sum_{v \in S} c(v) \leq B$ and $f(S)$ is maximized. This problem is NP-hard and ubiquitous in machine learning applications like feature selection, data summarization, and influence maximization.
Privacy Setting: The objective function $f_D$ depends on a sensitive dataset $D$ . The algorithm must output a solution $S$ while satisfying $(\epsilon, \delta)$ -differential privacy, ensuring that the output distribution changes negligibly when a single individual's data in $D$ is modified.
Scope: The work considers both monotone and non-monotone objective functions.

2. Methodology and Technical Challenges

The authors identify that standard techniques for DP submodular maximization (often designed for cardinality constraints) are suboptimal for knapsack constraints due to two primary challenges:

Varying Sensitivity of Density Scores: In knapsack settings, algorithms typically select elements based on "density" (marginal gain divided by cost). Unlike cardinality constraints where sensitivity is uniform, the sensitivity of a density score $f(u|S)/c(u)$ depends inversely on the element cost $c(u)$ . A naive application of standard selection mechanisms (like the Exponential Mechanism) would incur an additive error proportional to $\Delta f \cdot (B/c_{\min})$ , leading to a suboptimal dependence on the maximum feasible solution size $k$ .
- Resolution: The authors employ the Generalized Report Noisy Max (GRNM) mechanism (Raskhodnikova & Smith, 2016). This mechanism adapts to individual candidate sensitivities, ensuring the additive error scales with the specific sensitivity of the selected candidate rather than the worst-case bound.
Composition Bottleneck: State-of-the-art non-private algorithms for monotone SMK (e.g., Two-Guess-Greedy) require $O(n^2)$ iterations to guess optimal elements. Standard advanced composition theorems would result in an error term scaling polynomially with $n$ , negating the benefits of privacy.
- Resolution: The authors leverage the Generalized Private Selection framework (Cohen et al., 2023). By randomizing the number of times each enumeration step is invoked, they decouple the privacy loss from the total number of subroutines, achieving an additive error with polylogarithmic dependence on $n$ .

3. Key Contributions and Algorithms

A. Monotone Objective Functions

The paper proposes two algorithms for the monotone case:

DP-2GG (Algorithm 2): A differentially private adaptation of the "Two-Guess-Greedy" algorithm (Feldman et al., 2023).
- Mechanism: It iterates over all subsets $Y \subseteq N$ of size at most 2. For each $Y$ , it runs a privatized density-greedy subroutine (Algorithm 1) on the residual instance. The final solution is selected from the noisy outputs of these subroutines using the Generalized Selection framework.
- Guarantees: Achieves an optimal $(1 - 1/e)$ -approximation.
- Complexity: $O(\beta^{-1} n^3 k)$ oracle queries.
- Error: Additive error scales as $O(\frac{\Delta k^{1.5}}{\epsilon} \sqrt{\log n} \dots)$ , improving upon prior work by removing polynomial dependence on $n$ and $1/c_{\min}$ .
DP-DG+ (Algorithm 7): A faster, single-pass algorithm based on Density-Greedy+.
- Mechanism: Executes a privatized density-greedy pass once and selects the best solution among the partial solutions and their feasible single-element extensions using Report Noisy Max (RNM).
- Guarantees: Achieves a $1/2$ -approximation.
- Complexity: $O(nk)$ oracle queries.
- Error: Improved additive error comparable to the monotone case.

B. Non-Monotone Objective Functions

The paper introduces the first differentially private algorithm with provable guarantees for non-monotone SMK.

Algorithm: DP-SDG (Algorithm 3), a privatized adaptation of the non-private SmkRan algorithm (Han et al., 2021).
Mechanism: It performs density-based selections using GRNM. Selected elements are added to the solution with probability $1/2$ (randomized discarding) to handle non-monotonicity. Crucially, it continues iterating even if marginal gains become negative (due to noise) and uses RNM to select the best observed solution from all partial solutions and their extensions.
Privacy Analysis: To handle the uncertainty in the number of selection steps, the authors derive a concentration bound showing the total iterations are stochastically dominated by a sum of geometric random variables, concentrating around $O(k)$ .
Guarantees: Achieves a $1/4$ -approximation in expectation.
Complexity: $O(nk)$ oracle queries.
Error: Additive error is comparable to the monotone case.

4. Results and Empirical Evaluation

Theoretical Results

The authors compare their results against prior work (specifically Sadeghi & Fazel, 2021) in Table 1. Key improvements include:

Approximation Ratios: Matching the best known non-private ratios ( $(1-1/e)$ for monotone, $1/4$ for non-monotone).
Additive Error: Significantly improved dependence on the ground set size $n$ (polylogarithmic vs. polynomial) and the maximum feasible solution size $k$ (scaling with $k^{1.5}$ vs. $k$ or worse in prior work).
Query Complexity: Polynomial in $n$ and $k$ , whereas prior work for monotone SMK relied on exact evaluation of the multilinear extension requiring $O(2^n)$ queries.

Empirical Results

The algorithms were evaluated on a ride-sharing optimization task using a dataset of 100,000 Uber pickup locations in Manhattan.

Utility: For $\epsilon \geq 0.1$ , the DP algorithms (DP-2GG, DP-DG+, DP-SDG) achieve utility comparable to their non-private counterparts (2GG, DG+, SmkRan), substantially outperforming a random baseline. At $\epsilon=0.2$ , DP-2GG is within 2% of the non-private 2GG.
Scalability: DP-DG+ and DP-SDG exhibit linear growth in oracle queries with respect to the ground set size $n$ , confirming their practical efficiency compared to the more query-intensive DP-2GG.

5. Significance and Claims

The paper claims to bridge critical gaps in the literature regarding differentially private combinatorial optimization:

First Provable Non-Monotone SMK: It establishes the first provable guarantees for non-monotone SMK under differential privacy.
Improved Monotone Bounds: It improves both the utility (additive error) and query complexity of monotone SMK algorithms, moving away from the exponential query complexity of previous approaches.
Handling Knapsack Constraints: It demonstrates that the specific challenges of knapsack constraints (varying sensitivities and composition bottlenecks) can be overcome using generalized selection mechanisms and concentration bounds, achieving results that match the efficiency of cardinality-constrained settings.

The authors note that while their additive error dependence on $k$ matches the best known for polynomial-time algorithms in cardinality-constrained settings, the question of whether a better dependence on $k$ is achievable under bounded sensitivity remains open. They also suggest extending these techniques to combined knapsack and matroid constraints as a direction for future work.