{"id":348,"date":"2023-02-15T21:32:50","date_gmt":"2023-02-15T21:32:50","guid":{"rendered":"https:\/\/todaysainews.com\/index.php\/2023\/02\/15\/a-novel-differentially-private-aggregation-framework-google-ai-blog\/"},"modified":"2025-04-27T07:34:18","modified_gmt":"2025-04-27T07:34:18","slug":"a-novel-differentially-private-aggregation-framework-google-ai-blog","status":"publish","type":"post","link":"https:\/\/todaysainews.com\/index.php\/2023\/02\/15\/a-novel-differentially-private-aggregation-framework-google-ai-blog\/","title":{"rendered":"A novel differentially private aggregation framework \u2013 Google AI Blog"},"content":{"rendered":"

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

\nPosted by Haim Kaplan and Yishay Mansour, Research Scientists, Google Research
\n<\/span><\/p>\n

<\/p>\n

\nDifferential privacy<\/a> (DP) machine learning algorithms protect user data by limiting the effect of each data point on an aggregated output with a mathematical guarantee. Intuitively the guarantee implies that changing a single user\u2019s contribution should not significantly change the output distribution of the DP algorithm.\n<\/p>\n

<\/p>\n

\nHowever, DP algorithms tend to be less accurate than their non-private counterparts because satisfying DP is a worst-case<\/em> requirement: one has to add noise to \u201chide\u201d changes in any potential<\/em> input point, including “unlikely points\u2019\u2019 that have a significant impact on the aggregation. For example, suppose we want to privately estimate the average of a dataset, and we know that a sphere of diameter, \u039b, contains all possible data points. The sensitivity of the average to a single point is bounded by \u039b, and therefore it suffices to add noise proportional to \u039b to each coordinate of the average to ensure DP.\n<\/p>\n\n\n\n\n
<\/a><\/td>\n<\/tr>\n
A sphere of diameter \u039b containing all possible data points.<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

\nNow assume that all the data points are “friendly,” meaning they are close together, and each affects the average by at most \ud835\udc5f, which is much smaller than \u039b. Still, the traditional way for ensuring DP requires adding noise proportional to \u039b to account for a neighboring dataset that contains one additional “unfriendly” point that is unlikely to be sampled.\n<\/p>\n\n\n\n\n
<\/a><\/td>\n<\/tr>\n
Two adjacent datasets that differ in a single outlier. A DP algorithm would have to add noise proportional to \u039b to each coordinate to hide this outlier.<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

\nIn \u201cFriendlyCore: Practical Differentially Private Aggregation<\/a>\u201d, presented at ICML 2022<\/a>, we introduce a general framework for computing differentially private aggregations. The FriendlyCore framework pre-processes data, extracting a \u201cfriendly\u201d subset (the core) and consequently reducing the private aggregation error seen with traditional DP algorithms. The private aggregation step adds less noise since we do not need to account for unfriendly points that negatively impact the aggregation.\n<\/p>\n

\nIn the averaging example, we first apply FriendlyCore<\/em> to remove outliers, and in the aggregation step, we add noise proportional to \ud835\udc5f (not \u039b). The challenge is to make our overall algorithm (outlier removal + aggregation) differentially private. This constrains our outlier removal scheme and stabilizes the algorithm so that two adjacent inputs that differ by a single point (outlier or not) should produce any (friendly) output with similar probabilities.\n<\/p>\n

FriendlyCore Framework<\/h2>\n

\nWe begin by formalizing when a dataset is considered friendly<\/em>, which depends on the type of aggregation needed and should capture datasets for which the sensitivity of the aggregate is small. For example, if the aggregate is averaging, the term friendly <\/em>should capture datasets with a small diameter.\n<\/p>\n

\nTo abstract away the particular application, we define friendliness using a predicate \ud835\udc53 that is positive on points \ud835\udc65 and \ud835\udc66 if they are \u201cclose\u201d to each other. For example,in the averaging application \ud835\udc65 and \ud835\udc66 are close if the distance between them is less than \ud835\udc5f. We say that a dataset is friendly (for this predicate) if every pair of points \ud835\udc65 and \ud835\udc66 are both close to a third point \ud835\udc67 (not necessarily in the data).\n<\/p>\n

\nOnce we have fixed \ud835\udc53 and defined when a dataset is friendly, two tasks remain. First,<\/strong> we construct the FriendlyCore algorithm <\/em>that extracts a large friendly subset (the core) of the input stably. FriendlyCore<\/em> is a filter satisfying two requirements: (1) It has to remove outliers to keep only elements that are close to many others in the core, and (2) for neighboring datasets that differ by a single element, \ud835\udc66, the filter outputs each element except \ud835\udc66 with almost the same probability. Furthermore, the union of the cores extracted from these neighboring datasets is friendly.\n<\/p>\n

\nThe idea underlying FriendlyCore<\/em> is simple: The probability that we add a point, \ud835\udc65, to the core is a monotonic and stable function of the number of elements close to \ud835\udc65. In particular, if \ud835\udc65 is close to all other points, it\u2019s not considered an outlier and can be kept in the core with probability 1.\n<\/p>\n

\nSecond, we develop the Friendly DP <\/em>algorithm that satisfies a weaker notion of privacy by adding less noise to the aggregate. This means that the outcomes of the aggregation are guaranteed to be similar only for neighboring datasets \ud835\udc36 and \ud835\udc36’ such that the union<\/a> of \ud835\udc36 and \ud835\udc36’ is friendly<\/em>.\n<\/p>\n

\nOur main theorem<\/a> states that if we apply a friendly DP aggregation algorithm to the core produced by a filter with the requirements listed above, then this composition is differentially private in the regular sense.\n<\/p>\n

Clustering and other applications<\/h2>\n

\nOther applications of our aggregation method are clustering<\/a> and learning the covariance matrix<\/a> of a Gaussian distribution<\/a>. Consider the use of FriendlyCore to develop a differentially private k-means clustering algorithm<\/a>. Given a database of points, we partition it into random equal-size smaller subsets and run a good non<\/i>-private k<\/em>-means clustering algorithm on each small set. If the original dataset contains k<\/em> large clusters then each smaller subset will contain a significant fraction of each of these k<\/em> clusters. It follows that the tuples (ordered sets) of k<\/em>-centers we get from the non-private algorithm for each small subset are similar. This dataset of tuples is expected to have a large friendly core (for an appropriate definition of closeness).\n<\/p>\n\n\n\n\n
<\/a><\/td>\n<\/tr>\n
<\/tr>\n<\/tbody>\n<\/table>\n

\nWe use our framework to aggregate the resulting tuples of k<\/em>-centers (k<\/em>-tuples). We define two such k<\/em>-tuples to be close if there is a matching between them such that a center is substantially closer to its mate than to any other center.\n<\/p>\n\n\n\n\n
<\/a><\/td>\n<\/tr>\n
In this picture, any pair of the red, blue, and green tuples are close to each other, but none of them is close to the pink tuple. So the pink tuple is removed by our filter and is not in the core.<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

\nWe then extract the core by our generic sampling scheme and aggregate it using the following steps:\n<\/p>\n

    \n
  1. Pick a random k<\/em>-tuple \ud835\udc47 from the core.\n<\/li>\n
  2. Partition the data by putting each point in a bucket according to its closest center in \ud835\udc47.\n<\/li>\n
  3. Privately average the points in each bucket to get our final k<\/em>-centers.\n<\/li>\n<\/ol>\n

    Empirical results<\/h2>\n

    \nBelow are the empirical results of our algorithms based on FriendlyCore<\/em>. We implemented them in the zero-Concentrated Differential Privacy<\/a> (zCDP) model, which gives improved accuracy in our setting (with similar privacy guarantees as the more well-known <\/a> (\ud835\udf16, \ud835\udeff)-DP<\/a>).\n<\/p>\n

    Averaging<\/h3>\n

    \nWe tested the mean estimation of 800 samples from a spherical Gaussian with an unknown<\/em> mean. We compared it to the algorithm CoinPress<\/a><\/em>. In contrast to FriendlyCore, CoinPress<\/em> requires an upper bound \ud835\udc45 on the norm of the mean. The figures below show the effect on accuracy when increasing \ud835\udc45 or the dimension \ud835\udc51. Our averaging algorithm performs better on large values of these parameters since it is independent of \ud835\udc45 and \ud835\udc51.<\/p>\n\n\n\n
    <\/a><\/td>\n<\/a><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

    <\/p>\n\n\n\n
    Left<\/strong>: Averaging in \ud835\udc51= 1000, varying \ud835\udc45. Right<\/strong>: Averaging with \ud835\udc45= \u221a\ud835\udc51, varying \ud835\udc51.<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

    <\/p>\n

    Clustering<\/h3>\n

    \nWe tested the performance of our private clustering algorithm for k<\/em>-means. We compared it to the Chung and Kamath<\/a> algorithm that is based on recursive locality-sensitive hashing<\/a> (LSH-clustering). For each experiment, we performed 30 repetitions and present the medians along with the 0.1 and 0.9 quantiles. In each repetition, we normalize the losses by the loss of k-means++<\/a> (where a smaller number is better).\n<\/p>\n

    \nThe left figure below compares the k<\/em>-means results on a uniform mixture of eight separated Gaussians in two dimensions. For small values of \ud835\udc5b (the number of samples from the mixture), FriendlyCore often fails and yields inaccurate results. Yet, increasing \ud835\udc5b increases the success probability of our algorithm (because the generated tuples become closer to each other) and yields very accurate results, while LSH-clustering lags behind.\n<\/p>\n\n\n\n\n
    <\/a><\/td>\n<\/tr>\n
    Left<\/strong>: k<\/em>-means results in \ud835\udc51= 2 and k<\/em>= 8, for varying \ud835\udc5b(number of samples). Right<\/strong>: A graphical illustration of the centers in one of the iterations for \ud835\udc5b= 2 X 105<\/sup>. Green points are the centers of our algorithm and the red points are the centers of LSH-clustering.<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

    \nFriendlyCore also performs well on large datasets, even without clear separation into clusters. We used the Fonollosa and Huerta<\/a> gas sensors dataset that contains 8M rows, consisting of a 16-dimensional point defined by 16 sensors’ measurements at a given point in time. We compared the clustering algorithms for varying k<\/em>. FriendlyCore performs well except for k<\/em>= 5 where it fails due to the instability of the non-private algorithm used by our method (there are two different solutions for k<\/em>= 5 with similar cost that makes our approach fail since we do not get one set of tuples that are close to each other).\n<\/p>\n\n\n\n\n
    <\/a><\/td>\n<\/tr>\n
    k<\/em>-means results on gas sensors’ measurements over time, varying k<\/em>.<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

    Conclusion<\/h2>\n

    \nFriendlyCore<\/em> is a general framework for filtering metric data before privately aggregating it. The filtered data is stable and makes the aggregation less sensitive, enabling us to increase its accuracy with DP. Our algorithms outperform private algorithms tailored for averaging and clustering, and we believe this technique can be useful for additional aggregation tasks. Initial results show that it can effectively reduce utility loss when we deploy DP aggregations. To learn more, and see how we apply it for estimating the covariance matrix of a Gaussian distribution, see our paper<\/a>.\n<\/p>\n

    Acknowledgements<\/h2>\n

    \nThis work was led by Eliad Tsfadia in collaboration with Edith Cohen, Haim Kaplan, Yishay Mansour, Uri Stemmer, Avinatan Hassidim and Yossi Matias.<\/em><\/p>\n<\/div>\n

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

    [ad_1] Posted by Haim Kaplan and Yishay Mansour, Research Scientists, Google Research Differential privacy (DP) machine learning algorithms<\/p>\n","protected":false},"author":2,"featured_media":349,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[20],"tags":[],"class_list":["post-348","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\/348","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=348"}],"version-history":[{"count":1,"href":"https:\/\/todaysainews.com\/index.php\/wp-json\/wp\/v2\/posts\/348\/revisions"}],"predecessor-version":[{"id":2898,"href":"https:\/\/todaysainews.com\/index.php\/wp-json\/wp\/v2\/posts\/348\/revisions\/2898"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/todaysainews.com\/index.php\/wp-json\/wp\/v2\/media\/349"}],"wp:attachment":[{"href":"https:\/\/todaysainews.com\/index.php\/wp-json\/wp\/v2\/media?parent=348"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/todaysainews.com\/index.php\/wp-json\/wp\/v2\/categories?post=348"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/todaysainews.com\/index.php\/wp-json\/wp\/v2\/tags?post=348"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}