💻 computer science

Fast and Private Max-Sum Diversification

This paper introduces the first differentially private algorithms for the max-sum diversification problem under cardinality and matroid constraints, achieving nearly optimal utility while offering execution speeds that surpass existing non-private methods.

Original authors: Ron Zadicario, Tova Milo

Published 2026-07-21

📖 4 min read☕ Coffee break read

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

Imagine you are the curator of a massive, chaotic library. Every day, thousands of people walk in asking for book recommendations. If you just hand them the ten most popular books, you might satisfy the biggest crowd, but you'd miss out on the unique tastes of the quiet readers, and the list would feel repetitive. This is the art of diversification: picking a group of items that are not only good (relevant) but also different from each other (diverse), so the whole collection feels fresh and useful.

Now, imagine that the library's records contain secret details about what every single person bought or read. If you try to pick the "perfect" diverse list by crunching the numbers, you might accidentally reveal that a specific person bought a very rare, sensitive item. This is where privacy comes in. Scientists use a strict rule called differential privacy to protect these secrets. Think of it like adding a tiny bit of "static" or "noise" to your calculations, like a gentle fog that blurs the details of any single person's data just enough to hide them, while still letting you see the big picture. The challenge is: how do you find that perfect, diverse list without peeking at the secrets, and without taking forever to do the math?

This is exactly the puzzle tackled by Ron Zadicario and Tova Milo in their paper, "Fast and Private Max-Sum Diversification." They focus on a specific mathematical recipe called Max-Sum Diversification (MSD). In simple terms, this recipe tries to pick a group of items that maximizes two things at once: how relevant they are to the user's needs, and how far apart they are from each other (like picking fruits that are different colors and flavors, rather than just three red apples).

The authors discovered that the standard ways to solve this problem are either too slow or too risky for privacy. So, they invented new algorithms that act like a "smart, privacy-preserving scout." Instead of checking every single item in the library (which takes forever), their method takes quick, random samples and uses a special privacy tool called the Exponential Mechanism to pick the best candidates. This tool is like a magical dice that is weighted to roll higher numbers for better items, but it's designed so that the roll doesn't reveal which specific item caused the weight.

The paper shows that these new methods are not only safe but surprisingly fast. In fact, they are faster than the old, non-private methods that don't worry about secrets at all. When the researchers tested their ideas on real-world data—like picking the best Uber pickup spots in New York City or selecting a diverse set of health products from Amazon—they found that their private algorithms produced lists almost as good as the non-private ones. Even with a very strict privacy setting (where the "fog" is thick), their methods stayed within about 1% of the quality of the best possible non-private list.

Perhaps the most exciting finding is that these privacy-preserving tricks actually speed things up. One of their algorithms, called DP-OSG, is so efficient that it can handle huge lists of items without slowing down, making it a great choice even if you don't care about privacy. Another method, DP-SLS, handles more complex rules (like "pick 5 items from each price range") and still beats the old methods in speed while keeping the results high-quality.

In short, the paper proves that you don't have to choose between privacy, speed, and quality. By using clever sampling and noise, you can get a diverse, useful summary of data that respects individual secrets and gets the job done faster than ever before. The authors suggest that while their current methods are excellent, there might be even faster ways to do this in the future, but for now, they have shown that a fast, private, and diverse solution is definitely possible.

Technical Summary: Fast and Private Max-Sum Diversification

Problem Formulation

The paper addresses the Max-Sum Diversification (MSD) problem under the constraints of Differential Privacy (DP). MSD is a fundamental problem in data summarization and query result diversification, aiming to select a subset of items that balances relevance and diversity.

Given a ground set $V$ of $n$ items, a sensitive dataset $D$ , a monotone submodular relevance function $f_D$ , and a pseudometric distance function $d_D$ , the objective is to find a feasible subset $S$ (subject to constraints) that maximizes:
$\phi_D(S) = f_D(S) + \lambda \cdot d_D(S)$
where $\lambda \geq 0$ controls the trade-off between relevance and diversity. The term $d_D(S)$ represents the sum of pairwise distances between items in $S$ .

The challenge arises because the objective function $\phi_D$ is not submodular (as the sum of pairwise distances is supermodular), rendering standard DP submodular maximization techniques inapplicable. Furthermore, the underlying data $D$ (e.g., user purchase histories or location logs) is sensitive, requiring the selection algorithm to provide formal privacy guarantees (specifically $(\varepsilon, \delta)$ -DP) to prevent the leakage of individual information.

The paper considers two primary constraint types:

Cardinality Constraints: Selecting a subset of size at most $k$ .
Matroid Constraints: A generalization capturing more complex feasibility criteria (e.g., partition constraints).

Methodology

The authors propose a suite of differentially private algorithms tailored to these constraints, leveraging the Exponential Mechanism (EM) for private selection and Subset Sampling to improve efficiency.

1. Greedy Algorithms for Cardinality Constraints

DP-Greedy (Algorithm 1): A direct adaptation of the non-oblivious greedy algorithm by Borodin et al. [8]. It iteratively selects elements using the Exponential Mechanism based on an auxiliary function $\phi'(S) = \frac{1}{2}f_D(S) + \lambda d_D(S)$ $ϕ^{'} (S) = \frac{1}{2} f_{D} (S) + λ d_{D} (S)$ .
- Complexity: $O(nk)$ oracle calls.
- Guarantee: Achieves a $1/2$ -approximation (in expectation) with additive error dependent on sensitivity and privacy parameters.
DP-NOSG (Algorithm 2 - Non-Oblivious Sample Greedy): To address the $O(nk)$ bottleneck, this algorithm employs a "sample greedy" approach. In each iteration, it samples a smaller subset of candidates rather than evaluating the entire ground set.
- Complexity: $O(n \log k \log \gamma^{-1})$ oracle calls.
- Guarantee: Achieves a $(1/2 - \gamma)$ -approximation.
DP-OSG (Algorithm 2 - Oblivious Sample Greedy): A variant using an oblivious objective function and a different sampling strategy to achieve linear time complexity.
- Complexity: $O(n \log \gamma^{-1})$ oracle calls (independent of $k$ ).
- Guarantee: Achieves a $(1 - 2/e - \gamma - 1/k)$ -approximation.

Privacy Enhancements: For decomposable objectives (where the function can be expressed as a sum of functions depending on single records), the authors extend techniques from Gupta et al. [33] to provide stronger privacy guarantees. Specifically, for decomposable functions, the privacy loss does not scale linearly with $k$ in the same manner as general composition, allowing for tighter noise injection and better utility.

2. Local Search for Matroid Constraints

DP-SLS (Algorithm 3 - Sample Local Search): Since greedy approaches fail to provide constant-factor approximations for MSD under matroid constraints, the authors propose a private local search algorithm.
- Mechanism: The algorithm performs a fixed number of iterations ( $T'$ ). In each step, it subsamples a set of candidate swaps (adding an element and removing another) and uses the Exponential Mechanism to select a swap. It includes a "dummy swap" to allow the solution to remain unchanged if no improving swap is found. Finally, it privately selects the best solution observed across all iterations.
- Complexity: $O(\gamma^{-1} n k \log k)$ oracle calls, a significant improvement over the $O(n^2 + \gamma^{-1} n k^2 \log k)$ of the non-private baseline.
- Guarantee: Achieves a $(1/2 - \gamma)$ -approximation in expectation.

Key Contributions

Initiation of DP-MSD Study: This work is the first to formally study the Max-Sum Diversification problem under differential privacy, addressing the gap where existing DP submodular methods cannot be directly applied due to the non-submodular nature of the diversity term.
Near-Optimal Utility Guarantees: The proposed algorithms achieve approximation ratios that match or nearly match the theoretical lower bounds for non-private MSD (e.g., $1/2$ for cardinality constraints) while satisfying strict privacy guarantees.
Improved Efficiency: The authors design algorithms that are not only private but also faster than existing non-private methods.
- For cardinality constraints, the sample-based approaches reduce oracle calls from $O(nk)$ to $O(n \log k)$ or even $O(n)$ .
- For matroid constraints, the local search approach reduces complexity from $O(n^2)$ to $O(nk \log k)$ .
Decomposable Privacy Analysis: The paper extends privacy analysis techniques for decomposable objectives to the MSD setting, providing tighter additive error bounds and improved privacy parameters compared to general composition.

Experimental Results

The authors evaluated their algorithms on two real-world datasets: Uber pickup locations in Manhattan and Amazon product reviews (Health Care category).

Utility: Under strong privacy budgets (e.g., $\varepsilon = 0.1$ $ε = 0.1$ ), the proposed DP algorithms achieve utility comparable to non-private baselines.
- For cardinality constraints, DP-Greedy and DP-NOSG stay within 1% of the non-private greedy baseline.
- For matroid constraints, DP-SLS stays within 1% of the non-private local search baseline.
- In contrast, baselines that ignore diversity (DP-RelG) or rely on random selection perform significantly worse (17–30% lower utility).
Efficiency:
- Cardinality: DP-NOSG and DP-OSG demonstrated speedups of 14x and 50x respectively compared to the non-private greedy algorithm at $k=100$ , due to reduced oracle calls.
- Matroid: While DP-SLS reduces the total number of oracle calls compared to the non-private baseline, the fixed iteration count and overhead of the Exponential Mechanism result in execution times up to 2.2x slower in some regimes. However, it exhibits better scaling with ground set size $n$ .

Significance and Claims

The paper claims that result diversification is crucial for informative data summaries but often involves sensitive data, necessitating privacy-preserving methods. The authors assert that their work:

Bridges a critical gap: It provides the first formal framework for private MSD, enabling applications like privacy-preserving product recommendations and location summarization.
Offers dual value: The proposed algorithms are valuable even in non-private settings because they offer improved time complexity (faster execution) compared to state-of-the-art non-private methods.
Achieves near-optimal trade-offs: The algorithms successfully balance the "trilemma" of privacy, utility, and efficiency, achieving utility comparable to non-private methods while significantly reducing computational overhead for large datasets.

The authors acknowledge limitations, noting that their matroid constraints currently apply to general $\Delta$ -sensitive functions rather than exploiting decomposability for tighter bounds, and that the fastest linear-time algorithm ( $O(n)$ ) does not yet achieve the tight $1/2$ approximation ratio. They identify extending these guarantees and accelerating practical execution as directions for future work.