{"id":3527,"date":"2024-01-28T21:29:53","date_gmt":"2024-01-28T12:29:53","guid":{"rendered":"https:\/\/saraheee.com\/?p=3527"},"modified":"2024-03-05T20:28:24","modified_gmt":"2024-03-05T11:28:24","slug":"algorithmic-foundations-2-post-processing-proposition","status":"publish","type":"post","link":"https:\/\/saraheee.com\/ko\/2024\/01\/algorithmic-foundations-2-post-processing-proposition\/","title":{"rendered":"[Algorithmic Foundations] #2. Post-Processing proposition"},"content":{"rendered":"

Definition 2.4<\/mark> (Differential Privacy)
Pr[M(x)\u2208S]\u2264exp(\u03b5)Pr[M(y)\u2208S]+\u03b4<\/p>\n\n\n\n

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

– in detail: https:\/\/saraheee.com\/2024\/01\/foundation-differential-privacy-definition\/<\/a><\/p>\n\n\n\n

Proposition 2.1<\/mark> (Post-Processing). Let \\(M: \\mathbb{N}^{|X|} \\to R\\) be a randomized algorithm that is (\u03b5,\u03b4)-differentially private. Let f: R \u2192 R’ be an arbitrary randomized mapping. Then f \u25e6 M : \\(\\mathbb{N^{|X|}}\\) \u2192 R’ is (\u03b5, \u03b4)-differentially private.<\/p>\n\n\n\n

Proof. We prove the proposition for a deterministic function f : R \u2192 R\u2032. The result then follows because any randomized mapping can be decomposed into a convex combination of deterministic functions, and a convex combination of differentially private mechanisms is differentially private.<\/p>\n\n\n\n

Fix any pair of neighboring databases x, y with \\(||x-y||_1 \\leq 1\\), and fix any event S \u2286 R’. Let T = {r \u2208 R : f(r) \u2208 S}. We then have: <\/p>\n\n\n\n

Pr[f(M(x)) \u2208 S] = Pr[M(x) \u2208 T]
\u2264 exp(\u03b5) Pr[M(y) \u2208 T] + \u03b4
= exp(\u03b5)Pr[f(M(y)) \u2208 S] + \u03b4<\/p>\n\n\n\n

which was what we wanted.<\/p>\n\n\n\n

M: \ub370\uc774\ud130\uc14b\uc744 \uc785\ub825\uc73c\ub85c \ubc1b\uc544 R \ubc94\uc704\uc758 \ucd9c\ub825\uc744 \uc0dd\uc131\ud558\ub294 \ubb34\uc791\uc704 \uc54c\uace0\ub9ac\uc998
f: M\uc758 \ucd9c\ub825\uc744 \ub2e4\ub978 \ubc94\uc704 R’\ub85c \ub9e4\ud551\ud558\ub294 \uc784\uc758\uc758 \ubb34\uc791\uc704 \ud568\uc218
f \u25e6 M: M\uc758 \ucd9c\ub825\uc5d0 \ud568\uc218 f\ub97c \uc801\uc6a9\ud55c \uac12
(\u03b5,\u03b4)-differentially private: M\uacfc f \u25e6 M \ubaa8\ub450 \uac19\uc740 \uc218\uc900\uc758 \ucc28\ub4f1 \ud504\ub77c\uc774\ubc84\uc2dc\ub97c \uc900\uc218\ud568<\/p>\n\n\n\n

\uc9d1\ud569 T: f\uc5d0 \uc758\ud574 S\ub85c \ub9e4\ud551\ub418\ub294 R\uc758 \ubaa8\ub4e0 \uc694\uc18c\ub97c \ud3ec\ud568\ud568
f(M(x))\uac00 S\uc5d0 \uc18d\ud560 \ud655\ub960\uc774 M(x)\uac00 T\uc5d0 \uc18d\ud560 \ud655\ub960\uacfc \uac19\uc74c
\ud558\ub098\uc758 \ub370\uc774\ud130\uc14b\uc5d0 \ub300\ud55c \uba54\ucee4\ub2c8\uc998 \ucd9c\ub825\uc758 \ud655\ub960\uc774 \uc774\uc6c3 \ub370\uc774\ud130\uc138\ud2b8\uc5d0 \ub300\ud55c \ud655\ub960\ubcf4\ub2e4 \ud06c\uac8c \ud06c\uc9c0 \uc54a\ub2e4\ub294 \uac83<\/p>\n\n\n\n

R’\uc5d0\uc11c \uac00\ub2a5\ud55c \ubaa8\ub4e0 \ucd9c\ub825\uc758 \ud558\uc704 \uc9d1\ud569, \uc54c\uace0\ub9ac\uc998 \ucd9c\ub825\uc744 \ubd84\uc11d\ud560 \ub54c\uc758 \ubaa8\ub4e0 (\uc7a0\uc7ac\uc801) \uacb0\uacfc \uc9d1\ud569<\/p>\n\n\n\n

\uac1c\uc778\uc815\ubcf4 \ubcf4\ud638 \uc54c\uace0\ub9ac\uc998\uc758 \ucd9c\ub825\uc740 \uc0ac\ud6c4 \ucc98\ub9ac \ud6c4\uc5d0\ub3c4 \ucc28\ub4f1 \uac1c\uc778 \uc815\ubcf4 \ubcf4\ud638\uac00 \uc720\uc9c0\ub428
\ucc28\ub4f1 \ube44\uacf5\uac1c \uba54\ucee4\ub2c8\uc998\uc758 \ucd9c\ub825\uc5d0 \uc5b4\ub5a4 \ucd94\uac00 \ub370\uc774\ud130 \ucc98\ub9ac \ub610\ub294 \ubd84\uc11d\uc774 \uc801\uc6a9\ub418\ub354\ub77c\ub3c4 \uac1c\uc778 \uc815\ubcf4 \ubcf4\ud638 \ubcf4\uc7a5\uc774 \uc190\uc0c1\ub418\uc9c0 \uc54a\uc74c\uc744 \uc758\ubbf8
\ucd9c\ub825 \ub370\uc774\ud130\uc758 \uacc4\uc0b0\uc774\ub098 \uc870\uc791\uc5d0 \ub300\ud574 \uac1c\uc778 \uc815\ubcf4 \ubcf4\ud638\uc758 \uacac\uace0\uc131\uc744 \ubcf4\uc7a5\ud568<\/p>\n\n\n\n

Theorem 2.2<\/mark>. Any (\u03b5, 0)-differentially private mechanism M is (k\u03b5, 0)-differential private for groups of size k. That is, for all \\(||x-y||_1\\) \u2264 k and all S \u2286 Range(M)<\/p>\n\n\n\n

Pr[M(x) \u2208 S] \u2264 exp(k\u03b5) Pr[M(y) \u2208 S]<\/p>\n\n\n\n

where the probability space is over the coin flips of the mechanism M.<\/p>\n\n\n\n

(\u03b5, 0)-differentially private\ub97c \ub9cc\uc871\ud55c\ub2e4\uba74, \ud06c\uae30 k\uc758 \uadf8\ub8f9\uc5d0 \ub300\ud574 (k\u03b5, 0)-differentially private\ub97c \ub9cc\uc871
\ub450 \ub370\uc774\ud130\uc14b x\uc640 y\uac00 \ucd5c\ub300 k\uac1c\uc758 \uc694\uc18c\uc5d0\uc11c\ub9cc \ucc28\uc774\uac00 \ub09c\ub2e4\uba74, \uc989 \\(||x-y||_1\\) \u2264 k \uc774\ub77c\uba74
\uadf8\ub9ac\uace0 M\uc758 \ucd9c\ub825 \ubc94\uc704\uc758 \uc784\uc758\uc758 \ubd80\ubd84\uc9d1\ud569 S\uc5d0 \ub300\ud574, M\uc774 x\uc5d0\uc11c S\uc5d0 \uc18d\ud558\ub294 \uacb0\uacfc\ub97c \ub0b4\ub294 \ud655\ub960\uc740 y\uc5d0\uc11c \ub3d9\uc77c\ud55c \uacb0\uacfc\ub97c \ub0b4\ub294 \ud655\ub960\uc758 \ucd5c\ub300 exp(k\u03b5)\ubc30\uc774\ub2e4. <\/p>\n\n\n\n

(k\u03b5, 0)-differentially private: k \ud06c\uae30\uc758 \uadf8\ub8f9\uc5d0 \ub300\ud574 \ud655\uc7a5\ub41c \ucc28\ub4f1 \ud504\ub77c\uc774\ubc84\uc2dc
x\uc640 y\uac00 k\uac1c\uc758 \uc694\uc18c\uc5d0\uc11c \ucc28\uc774\uac00 \ub0a0 \ub54c, \uba54\ucee4\ub2c8\uc998 M\uc774 exp(k\u03b5)\ubc30 \uc774\ub0b4\uc758 \ud655\ub960\ub85c \uacb0\uacfc\ub97c \uc0dd\uc131\ud558\ub3c4\ub85d \ubcf4\uc7a5\ud568<\/p>\n\n\n\n

\\(||x-y||_1\\) \u2264 k: \ub370\uc774\ud130\uc14b x\uc640 y\uac00 \ucd5c\ub300 k\uac1c\uc758 \uc694\uc18c\uc5d0\uc11c\ub9cc \ucc28\uc774\uac00 \ub0a8<\/p>\n\n\n\n