{"id":82,"date":"2023-01-24T16:12:59","date_gmt":"2023-01-24T16:12:59","guid":{"rendered":"https:\/\/todaysainews.com\/index.php\/2023\/01\/24\/differential-privacy-accounting-by-connecting-the-dots-google-ai-blog\/"},"modified":"2025-04-27T07:36:13","modified_gmt":"2025-04-27T07:36:13","slug":"differential-privacy-accounting-by-connecting-the-dots-google-ai-blog","status":"publish","type":"post","link":"https:\/\/todaysainews.com\/index.php\/2023\/01\/24\/differential-privacy-accounting-by-connecting-the-dots-google-ai-blog\/","title":{"rendered":"Differential Privacy Accounting by Connecting the Dots \u2013 Google AI Blog"},"content":{"rendered":"

[ad_1]
\n<\/p>\n

\nPosted by Pritish Kamath and Pasin Manurangsi, Research Scientists, Google Research<\/span><\/p>\n

<\/p>\n

\nDifferential privacy<\/a> (DP) is an approach that enables data analytics and machine learning (ML) with a mathematical guarantee on the privacy of user data. DP quantifies the \u201cprivacy cost\u201d of an algorithm, i.e., the level of guarantee that the algorithm\u2019s output distribution for a given dataset will not change significantly if a single user\u2019s data is added to or removed from it. The algorithm is characterized by two parameters, \u03b5 and \u03b4, where smaller values of both indicate \u201cmore private\u201d. There is a natural tension between the privacy budget (\u03b5, \u03b4) and the utility of the algorithm: a smaller privacy budget requires the output to be more \u201cnoisy\u201d, often leading to less utility. Thus, a fundamental goal of DP is to attain as much utility as possible for a desired privacy budget.\n<\/p>\n

<\/p>\n

\nA key property of DP that often plays a central role in understanding privacy costs is that of composition<\/em>, which reflects the net privacy cost of a combination of DP algorithms, viewed together as a single algorithm. A notable example is the differentially-private stochastic gradient descent<\/a> (DP-SGD) algorithm. This algorithm trains ML models over multiple iterations \u2014 each of which is differentially private \u2014 and therefore requires an application of the composition property of DP. A basic composition theorem in DP says that the privacy cost of a collection of algorithms is, at most, the sum of the privacy cost of each. However, in many cases, this can be a gross overestimate, and several improved composition theorems provide better estimates of the privacy cost of composition.<\/p>\n

\nIn 2019, we released an open-source library<\/a> (on GitHub<\/a>) to enable developers to use analytic techniques based on DP. Today, we announce the addition<\/a> to this library of Connect-the-Dots<\/em>, a new privacy accounting algorithm based on a novel approach for discretizing privacy loss distributions<\/a> that is a useful tool for understanding the privacy cost of composition. This algorithm is based on the paper \u201cConnect the Dots: Tighter Discrete Approximations of Privacy Loss Distributions<\/a>\u201d, presented at PETS 2022<\/a>. The main novelty of this accounting algorithm is that it uses an indirect approach to construct more accurate discretizations of privacy loss distributions. We find that Connect-the-Dots provides significant gains over other privacy accounting methods in literature in terms of accuracy and running time. This algorithm was also recently applied for the privacy accounting of DP-SGD in training Ads prediction models<\/a>.\n<\/p>\n

Differential Privacy and Privacy Loss Distributions<\/h2>\n

\nA randomized algorithm is said to satisfy DP guarantees if its output \u201cdoes not depend significantly\u201d on any one entry in its training dataset, quantified mathematically with parameters (\u03b5, \u03b4). For example, consider the motivating example of DP-SGD. When trained with (non-private) SGD, a neural network could, in principle, be encoding the entire training dataset within its weights, thereby allowing one to reconstruct some training examples from a trained model<\/a>. On the other hand, when trained with DP-SGD, we have a formal guarantee that if one were able to reconstruct a training example with non-trivial probability then one would also be able to reconstruct the same example even if it was not included in the training dataset.\n<\/p>\n

\nThe hockey stick divergence<\/a>, parameterized by \u03b5, is a measure of distance between two probability distributions, as illustrated in the figure below. The privacy cost of most DP algorithms is dictated by the hockey stick divergence between two associated probability distributions P and Q. The algorithm satisfies DP with parameters (\u03b5, \u03b4), if the value of the hockey stick divergence for \u03b5 between P and Q is at most \u03b4. The hockey stick divergence between (P, Q), denoted \u03b4P||Q<\/sub>(\u03b5) is in turn completely characterized by it associated privacy loss distribution, denoted by PLDP||Q<\/sub>.\n<\/p>\n\n\n\n\n
<\/a><\/td>\n<\/tr>\n
Illustration of hockey stick divergence \u03b4P||Q<\/sub>(\u03b5) between distributions P and Q (left<\/b>), which corresponds to the probability mass<\/a> of P that is above e\u03b5<\/sup>Q, where e\u03b5<\/sup>Q is an e\u03b5<\/sup> scaling of the probability mass of Q (right<\/b>).<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

\nThe main advantage of dealing with PLDs is that compositions of algorithms correspond to the convolution<\/a> of the corresponding PLDs. Exploiting this fact, prior work<\/a> has designed efficient algorithms to compute the PLD corresponding to the composition of individual algorithms by simply performing convolution of the individual PLDs using the fast Fourier transform<\/a> algorithm.\n<\/p>\n

\nHowever, one challenge when dealing with many PLDs is that they often are continuous distributions, which make the convolution operations intractable in practice. Thus, researchers often apply various discretization approaches to approximate the PLDs using equally spaced points. For example, the basic version of the Privacy Buckets algorithm<\/a> assigns the probability mass of the interval between two discretization points entirely to the higher end of the interval.<\/p>\n\n\n\n\n
<\/a><\/td>\n<\/tr>\n
Illustration of discretization by rounding up probability masses. Here a continuous PLD (in blue) is discretized to a discrete PLD (in red), by rounding up the probability mass between consecutive points.<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

Connect-the-Dots : A New Algorithm<\/h2>\n

\nOur new Connect-the-Dots algorithm provides a better way to discretize PLDs towards the goal of estimating hockey stick divergences. This approach works indirectly by first discretizing the hockey stick divergence function and then mapping it back to a discrete PLD supported on equally spaced points.\n<\/p>\n\n\n\n\n
<\/a><\/td>\n<\/tr>\n
Illustration of high-level steps in the Connect-the-Dots algorithm.<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

\nThis approach relies on the notion of a \u201cdominating PLD<\/a>\u201d, namely, PLDP\u2019||Q\u2019<\/sub> dominates over PLDP||Q<\/sub> if the hockey stick divergence of the former is greater or equal to the hockey stick divergence of the latter for all values of \u03b5. The key property of dominating PLDs is that they remain dominating after compositions. Thus for purposes of privacy accounting, it suffices to work with a dominating PLD, which gives us an upper bound on the exact privacy cost.\n<\/p>\n

\nOur main insight behind the Connect-the-Dots algorithm is a characterization of discrete PLD, namely that a PLD is supported on a given finite set of \u03b5 values if and only if the corresponding hockey stick divergence as a function of e\u03b5<\/sup> is linear between consecutive e\u03b5<\/sup> values. This allows us to discretize the hockey stick divergence by simply connecting the dots to get a piecewise linear function that precisely equals the hockey stick divergence function at the given e\u03b5<\/sup> values. See a more detailed explanation<\/a> of the algorithm.\n<\/p>\n\n\n\n\n
<\/a><\/td>\n<\/tr>\n
Comparison of the discretizations of hockey stick divergence by Connect-the-Dots vs Privacy Buckets.<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

Experimental Evaluation<\/h2>\n

\nThe DP-SGD algorithm involves a noise multiplier<\/em> parameter, which controls the magnitude of noise added in each gradient step, and a sampling probability<\/em>, which controls how many examples are included in each mini-batch. We compare Connect-the-Dots against the algorithms listed below on the task of privacy accounting DP-SGD with a noise multiplier = 0.5, sampling probability = 0.2 x 10-4<\/sup> and \u03b4 = 10-8<\/sup>.\n<\/p>\n

\nWe plot the value of the \u03b5 computed by each of the algorithms against the number of composition steps, and additionally, we plot the running time of the implementations. As shown in the plots below, privacy accounting using Renyi DP provides a loose estimate of the privacy loss. However, when comparing the approaches using PLD, we find that in this example, the implementation of Connect-the-Dots achieves a tighter estimate of the privacy loss, with a running time that is 5x faster than the Microsoft PRV Accountant and >200x faster than the previous approach of Privacy Buckets in the Google-DP library.\n<\/p>\n\n\n\n\n
<\/a><\/td>\n<\/tr>\n
Left:<\/b> Upper bounds on the privacy parameter \u03b5 for varying number of steps of DP-SGD, as returned by different algorithms (for fixed \u03b4 = 10-8<\/sup>). Right:<\/b> Running time of the different algorithms.<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

Conclusion & Future Directions<\/h2>\n

\nThis work proposes Connect-the-Dots<\/a>, a new algorithm for computing optimal privacy parameters for compositions of differentially private algorithms. When evaluated on the DP-SGD task, we find that this algorithm gives tighter estimates on the privacy loss with a significantly faster running time.\n<\/p>\n

\nSo far, the library only supports the pessimistic estimate version of Connect-the-Dots algorithm, which provides an upper bound on the privacy loss of DP-algorithms. However, the paper<\/a> also introduces a variant of the algorithm that provides an \u201coptimistic\u201d estimate of the PLD, which can be used to derive lower bounds<\/em> on the privacy cost of DP-algorithms (provided those admit a \u201cworst case\u201d PLD). Currently, the library does support optimistic estimates as given by the Privacy Buckets algorithm, and we hope to incorporate the Connect-the-Dots version as well.\n<\/p>\n

Acknowledgements<\/h2>\n

\nThis work was carried out in collaboration with Vadym Doroshenko, Badih Ghazi, Ravi Kumar. We thank Galen Andrew, Stan Bashtavenko, Steve Chien, Christoph Dibak, Miguel Guevara, Peter Kairouz, Sasha Kulankhina, Stefan Mellem, Jodi Spacek, Yurii Sushko and Andreas Terzis for their help.<\/em>\n<\/p>\n<\/div>\n

[ad_2]
\n
Source link <\/a><\/p>\n","protected":false},"excerpt":{"rendered":"

[ad_1] Posted by Pritish Kamath and Pasin Manurangsi, Research Scientists, Google Research Differential privacy (DP) is an approach<\/p>\n","protected":false},"author":2,"featured_media":83,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[20],"tags":[],"class_list":["post-82","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-google-ai"],"_links":{"self":[{"href":"https:\/\/todaysainews.com\/index.php\/wp-json\/wp\/v2\/posts\/82","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/todaysainews.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/todaysainews.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/todaysainews.com\/index.php\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/todaysainews.com\/index.php\/wp-json\/wp\/v2\/comments?post=82"}],"version-history":[{"count":1,"href":"https:\/\/todaysainews.com\/index.php\/wp-json\/wp\/v2\/posts\/82\/revisions"}],"predecessor-version":[{"id":3020,"href":"https:\/\/todaysainews.com\/index.php\/wp-json\/wp\/v2\/posts\/82\/revisions\/3020"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/todaysainews.com\/index.php\/wp-json\/wp\/v2\/media\/83"}],"wp:attachment":[{"href":"https:\/\/todaysainews.com\/index.php\/wp-json\/wp\/v2\/media?parent=82"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/todaysainews.com\/index.php\/wp-json\/wp\/v2\/categories?post=82"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/todaysainews.com\/index.php\/wp-json\/wp\/v2\/tags?post=82"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}