{"id":3645,"date":"2024-02-16T01:32:27","date_gmt":"2024-02-15T16:32:27","guid":{"rendered":"https:\/\/saraheee.com\/?p=3645"},"modified":"2024-03-15T21:11:26","modified_gmt":"2024-03-15T12:11:26","slug":"algorithmic-foundations-4-useful-probabilistic-tools","status":"publish","type":"post","link":"https:\/\/saraheee.com\/ko\/2024\/02\/algorithmic-foundations-4-useful-probabilistic-tools\/","title":{"rendered":"[Algorithmic Foundations] #4. useful probabilistic tools"},"content":{"rendered":"

real (vector) valued queries \ub300\ud55c \ucc28\ub4f1 \ud504\ub77c\uc774\ubc84\uc2dc\ub97c \uc81c\uacf5\ud558\ub294 Laplace mechanism\uc744 \uc81c\uc2dc\ud55c\ub2e4.
\uc774\ub294 exponential mechanism\uc73c\ub85c \uc774\uc5b4\uc9c0\uba70, \uac1c\ubcc4\uc801\uc778 \ud6c4\ubcf4 \ucd9c\ub825 \uc138\ud2b8\uc5d0\uc11c \ucc28\ub4f1\uc801\uc73c\ub85c \uc0ac\uc801\uc778 \uc120\ud0dd\uc744 \uc704\ud55c \ubc29\ubc95\uc774\ub2e4.<\/p>\n\n\n\n

\uc5ec\ub7ec \ucc28\ub4f1 \uac1c\uc778 \uba54\ucee4\ub2c8\uc998\uc744 \uad6c\uc131\ud558\uc5ec \ubc1c\uc0dd\ud558\ub294 \uac1c\uc778 \uc815\ubcf4 \ubcf4\ud638 \uc190\uc2e4\uc744 \ubd84\uc11d\ud55c\ub2e4.
\ucc28\ub4f1 \uac1c\uc778 \uc815\ubcf4 \ubcf4\ud638 \uba54\ucee4\ub2c8\uc998\uc758 \ud6a8\uacfc\ub97c \uc774\ud574\ud558\uace0 \uc99d\uba85\ud558\ub294 \ub370 \ud544\uc218\uc801\uc778 \uae30\ubcf8 \ud655\ub960 \ub3c4\uad6c\ub97c \uc81c\uacf5\ud55c\ub2e4.<\/p>\n\n\n\n

3.1 Useful probabilistic tools<\/h4>\n\n\n\n

\ud655\ub960 \uc774\ub860\uc5d0\uc11c, Chernoff \uacbd\uacc4\ub294 \ubb34\uc791\uc704 \ubcc0\uc218\uc758 \ud3c9\uade0\uc5d0\uc11c \ud655\ub960\uc758 \uc0c1\ud55c\uc744 \uad6c\ud560 \uc218 \uc788\uac8c \ud558\ub294 \uac83\uc744 \ubaa9\ud45c\ub85c \ud55c\ub2e4.<\/p>\n\n\n\n

Theorem 3.1<\/mark> (Additive Chernoff Bound). <\/p>\n\n\n

\n
\"\"<\/figure><\/div>\n\n\n

\ub3c5\ub9bd\uc801\uc778 \ud655\ub960 \ubcc0\uc218 X\uc758 \ud569\uc5d0 \ub300\ud574, \uac01 \ubcc0\uc218\uac00 0 \uc774\uc0c1 1 \uc774\ud558\ub85c \uc81c\ud55c\ub418\uace0 \uae30\ub300 \ud569\uc774 \u03bc\uc778 \uacbd\uc6b0, \ud569\uc774 \uadf8 \uae30\ub300\uac12\uc5d0\uc11c \u2206 (\u03b5) \ub9cc\ud07c \ubc97\uc5b4\ub0a0 \ud655\ub960\uc774 \uc9c0\uc218\uc801\uc73c\ub85c \uc791\ub2e4\ub294 \uac83\uc744 \uc124\uba85\ud55c\ub2e4.<\/p>\n\n\n\n

\uac01 \ubcc0\uc218\ub294 \\(0 \\leq X_i \\leq 1\\)\ub85c \uc81c\ud55c\ub41c\ub2e4.
\uc774 \ub3c5\ub9bd\uc801\uc778 \ud655\ub960 \ubcc0\uc218\ub4e4\uc758 \ud3c9\uade0 \\(S=\\frac{1}{m}\\sum_{i=1}^m X_i\\), \uae30\ub300\uac12 \\(\\mu = \\mathbb{E}[S] = \\sum_{i=1}^{m} \\mathbb{E}[X_i]\\)<\/p>\n\n\n\n

\\(\\mathbb{E}[X_i]\\): \ub2e8\uc77c \ubb34\uc791\uc704 \ubcc0\uc218 \\(X_i\\)\uc758 \uae30\ub300\uac12
\\(\\mu\\): S\uac00 \ucde8\ud560 \uc218 \uc788\ub294 \uac12\ub4e4\uc758 \uac00\uc911 \ud3c9\uade0
– S\uac00 \uadf8 \uae30\ub300\uac12\uc5d0\uc11c \u2206 \uc774\uc0c1 \ucc28\uc774 \ub098\ub294 \ud655\ub960\uc774 \uc9c0\uc218\uc801\uc73c\ub85c \uac10\uc18c\ud55c\ub2e4.
– S\uc758 \uc2e4\uc81c \uac12\uc774 \uadf8 \uae30\ub300\uac12(\u03bc\ub85c\ubd80\ud130\u00a0\u0394\ub9cc\ud07c \uc704\ub098 \uc544\ub798\uc5d0\uc11c \uc5bc\ub9c8\ub098 \uba40\ub9ac \ub5a8\uc5b4\uc9c8 \uc218 \uc788\ub294\uc9c0 \uce21\uc815)<\/p>\n\n\n\n

\uc0c1\ubc29(Overestimation): S\uac00 \uae30\ub300\uac12 \u03bc\ub85c\ubd80\ud130 \u0394\ub9cc\ud07c \ud070 \uacbd\uc6b0\uc758 \ud655\ub960\uc740 \\(e^{-2m\\Delta^2}\\) \uc774\ud558
\ud558\ubc29(Underestimation): S\uac00 \uae30\ub300\uac12 \u03bc\ub85c\ubd80\ud130 \u0394\ub9cc\ud07c \uc791\uc740 \uacbd\uc6b0\uc758 \ud655\ub960\uc740 \\(e^{-2m\\Delta^2}\\) \uc774\ud558<\/p>\n\n\n\n

Theorem 3.2<\/mark> (Multiplicative Chernoff Bound). <\/p>\n\n\n

\n
\"\"<\/figure><\/div>\n\n\n

\uc0c1\ubc29(Overestimation): S\uac00 \uae30\ub300\uac12 \u03bc\ub85c\ubd80\ud130 \u0394\ub9cc\ud07c \ud070 \uacbd\uc6b0\uc758 \ud655\ub960\uc740 \\(e^{-2m\\Delta^2}\\) \uc774\ud558
\ud558\ubc29(Underestimation): S\uac00 \uae30\ub300\uac12 \u03bc\ub85c\ubd80\ud130 \u0394\ub9cc\ud07c \uc791\uc740 \uacbd\uc6b0\uc758 \ud655\ub960\uc740 \\(e^{-2m\\Delta^2}\\) \uc774\ud558<\/p>\n\n\n\n

Theorem 3.3<\/mark> (Azuma’s Inequality). <\/p>\n\n\n

\n
\"\"<\/figure><\/div>\n\n\n

\ud655\ub960 \ubcc0\uc218 \ud568\uc218\uc5d0 \ub300\ud55c \ub18d\ub3c4 \ubd80\ub4f1\uc2dd\uc744 \uc81c\uacf5\ud55c\ub2e4.
\uc77c\ub828\uc758 \ud655\ub960 \ubcc0\uc218\uac00 \uc8fc\uc5b4\uc84c\uc744 \ub54c \uac01 \\(X_i\\)\uac00 \uc784\uc758\uc758 \uac12 \uc9d1\ud569 \\(A_i\\)\ub85c\ubd80\ud130 \uac12\uc744 \ucde8\ud558\uace0, \uc774\ub7ec\ud55c \ud655\ub960 \ubcc0\uc218\ub4e4\uc758 \ud568\uc218 f\uac00 \uc8fc\uc5b4\uc9c8 \ub54c \uc801\uc6a9\ub41c\ub2e4.
\\(X_1, \\cdots, X_{i-1} = a_i\\)\uc640 \\(X_1, \\cdots, X_i = a_i’\\) \uc870\uac74 \ud558\uc5d0 f\uc758 \uae30\ub300\uac12 \ucc28\uc774\uac00 \\(c_i\\) \uc774\ud558\uc774\ub2e4.<\/p>\n\n\n\n

\\(f(X_1, \\cdots, X_m)\\)\uac00 \uadf8 \uae30\ub300\uac12 E[f]\ub85c\ubd80\ud130 t \uc774\uc0c1 \ucc28\uc774\ub0a0 \ud655\ub960\uc744 \uc81c\ud55c\ud558\ub294\ub370, \uc704\uc758 Pr \uc218\uc2dd \ud615\ud0dc\ub85c \ud45c\ud604\ub41c\ub2e4.
\\(\\sum_{i+1}^m c_i^2\\)\ub294 f\uc5d0 \ub300\ud55c \\(X_i\\)\uc758 \ucd5c\ub300 \uc601\ud5a5\ub825 \\(c_i\\)\uc758 \uc81c\uacf1\ud569\uc774\ub2e4.<\/p>\n\n\n\n

Theorem 3.4<\/mark> (Stirling’s Approximation). <\/p>\n\n\n

\n
\"\"<\/figure><\/div>\n\n\n

\ud329\ud1a0\ub9ac\uc5bc \ud568\uc218 n!\uc744 \uadfc\uc0ac\ud558\ub294 \ub370 \uc0ac\uc6a9\ub418\ub294 \uacf5\uc2dd \\(n! \\approx \\sqrt{2 \\pi n}(\\frac{n}{e})^n\\)<\/p>\n\n\n\n

\uc720\ub3c4 \uacfc\uc815: \ub77c\ud50c\ub77c\uc2a4 \ubc29\uc2dd<\/p>\n\n\n\n

<\/p>\n\n\n\n

Reference<\/h4>\n\n\n\n
    \n
  • Cynthia Dwork and Aaron Roth, The Algorithmic Foundations of Differential Privacy, 3. Basic Techniques and Composition Theorems<\/li>\n<\/ul>\n\n\n\n

    <\/p>","protected":false},"excerpt":{"rendered":"

    I provide basic probability tools that are essential for understanding and proving the effectiveness of differential privacy mechanisms.<\/p>","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[154],"tags":[175,155,174],"class_list":["post-3645","post","type-post","status-publish","format-standard","hentry","category-dp","tag-chernoff-bound","tag-differential-privacy","tag-feb-15-2024"],"_links":{"self":[{"href":"https:\/\/saraheee.com\/ko\/wp-json\/wp\/v2\/posts\/3645"}],"collection":[{"href":"https:\/\/saraheee.com\/ko\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/saraheee.com\/ko\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/saraheee.com\/ko\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/saraheee.com\/ko\/wp-json\/wp\/v2\/comments?post=3645"}],"version-history":[{"count":28,"href":"https:\/\/saraheee.com\/ko\/wp-json\/wp\/v2\/posts\/3645\/revisions"}],"predecessor-version":[{"id":4001,"href":"https:\/\/saraheee.com\/ko\/wp-json\/wp\/v2\/posts\/3645\/revisions\/4001"}],"wp:attachment":[{"href":"https:\/\/saraheee.com\/ko\/wp-json\/wp\/v2\/media?parent=3645"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/saraheee.com\/ko\/wp-json\/wp\/v2\/categories?post=3645"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/saraheee.com\/ko\/wp-json\/wp\/v2\/tags?post=3645"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}