Differentially Private Submodular Maximization with a Knapsack Constraint

Submodular maximization subject to a knapsack constraint (SMK) is a fundamental problem in discrete optimization, with wide-ranging applications in machine learning and related fields. As these applications increasingly involve sensitive individual data, there is a growing need for high-utility algorithms that provide formal privacy guarantees. In this work, we study the SMK problem under differential privacy, considering both monotone and non-monotone objective functions. For monotone objectives, we propose a differentially private algorithm that achieves the optimal $(1-1/e)$-approximation ratio while significantly improving both additive error and query complexity over prior work. We also present a more efficient algorithm for the same setting, achieving a $1/2$-approximation. For non-monotone objectives, we introduce, to our knowledge, the first differentially private algorithm with provable guarantees, achieving a $1/4$-approximation in expectation and an additive error comparable to the best known for monotone objective functions.

Many real-world systems must choose a small set of items from a large collection while respecting a budget. Examples include selecting medical tests for disease prediction, features for machine learning models, products for personalized recommendation, or locations for service placement in cities. These problems are challenging because the value of adding a new item often depends on what has already been selected, and each item also incurs a cost. At the same time, these applications increasingly rely on sensitive personal data. This creates an additional requirement: the selection process must protect individual privacy while still producing high-quality decisions. We study this problem from the perspective of differential privacy, a formal mathematical standard ensuring that the final output does not compromise any single individual’s data. Prior work on this problem is often not efficient enough for practical use and provides loose guarantees on solution quality. In addition, it is restricted to monotone settings, where adding more items can only improve the solution. However, in many applications, adding redundant items can in fact reduce quality. In the monotone setting, we present a differentially private algorithm with significantly improved utility guarantees and computational efficiency, along with an even faster variant that maintains strong guarantees. In the non-monotone setting, we present the first differentially private algorithm with provable guarantees for this problem. Overall, our results provide essential tools for privacy-preserving discrete optimization under budget constraints.