Higher utility methods for differentially private optimization
Anamay Chaturvedi · 2024
Advances in our ability to collect and analyze data at scale have introduced new risks to the privacy of individuals. Differential privacy (DP) provides a principled way of quantifying the privacy risk that occurs when we publish the outcome of data analyses that use as input private information. Further, basic properties of DP allow DP subroutines to be used in a modular manner in a data analysis pipeline and to bound the net privacy risk in terms of the privacy risk of the individual DP components. This means that DP solutions for fundamental optimization tasks lend themselves to be used as building blocks for privacy-preserving data analysis. On the other hand, DP also necessitates incurring a certain amount of error or loss in utility, which in some problem settings is necessary for meaningfully preserving privacy. This motivates the study of DP methods that achieve the best possible trade-offs between privacy and utility. Two problems of special focus for us in the DP setting are k-means and submodular maximization, both of which are used widely in applications that involve sensitive data. k-Means is a continuous optimization problem that serves as a widely used data clustering primitive. For just a couple of illustrative examples, it has been used in document classification, recommendation systems, and even tracking the COVID-19 infection spread. Formally, the solver is given some data set and a fixed number of cluster centers (called the k-means) that they can allocate. They must choose from the domain as many centers as in their budget such that the the squared distance between each data point and the closest center summed over all data points is minimized. This is a well-studied problem in the algorithms literature, and has received much interest in the past few years in the DP setting. Submodular maximization is a discrete optimization problem that asks the solver to maximize a submodular function subject to some constraint on permissible inputs. Submodular functions take as input subsets of some given ground set, and output real number values. They are defined by the diminishing returns property, i.e. that the increase in the function value when adding an element to a subset is smaller when the subset is larger. Submodular maximization has been used fruitfully in disparate fields such as electrical engineering, economics, and machine learning. It has been observed that some of the most compelling applications of submodular maximization such as feature selection involve the use of sensitive data, motivating the study of DP submodular maximization. We derive new upper and lower bounds on the best possible utility achievable under the constraints of DP for these optimization problems. The long-term goal of this line of work is to facilitate the adoption of DP methods and formally bound the privacy risk when giving algorithms access to private data.--Author's abstract