Privacy-Conscious Algorithm Design Via PAC Privacy

As the use of algorithms for daily decision-making has grown, so has the need for provable privacy guarantees on their leakage of sensitive data. Classically, privatizing these algorithms is implemented by computing the minimal noise required for a given privacy budget and adding it post-hoc. We instead propose that the algorithm's hyperparameters and its privacy budget can be jointly optimized to improve overall privatized utility. In this work, we focus on designing privacyconscious algorithms; that is, designing near-optimal algorithms, in terms of utility, for a given privacy budget under PAC Privacy.

We integrate the noise required for PAC Privacy guarantees directly into our objective functions for classic algorithms like linear regression and gradient descent. To the best of our knowledge, we are the first to optimize for privatized performance under PAC Privacy. We demonstrate how to derive theoretically-optimal parameters to maximize utility under a provided privacy budget. These parameters correspond to regularization strength for linear regression and step sizes for gradient descent optimization of convex and smooth objective functions. We validate our theoretical results experimentally, showing the benefits of privacy-conscious design for ridge regression and regularized logistic regression. Our algorithms maintain near-optimal utility at relaxed privacy budgets and smoothly trade off utility and privacy in stricter settings.

is calibrated appropriately. That is, while the algorithm still uses instance-specific noise computations, it requires tracking 1. Note that Theorem 4.2 of [25], which allows for the harder adversarial setting is no longer black-box -specifically, this theorem requires a universal upper bound on divergence (similar to DP) making it difficult to integrate with privacy-conscious design.