องค์ประกอบขั้นสูงใน DP แย่กว่าองค์ประกอบพื้นฐาน

ฉันมีปัญหาเกี่ยวกับการทำความเข้าใจทฤษฎีบทองค์ประกอบขั้นสูงใน DP

ให้ฉันมีสองกลไก DP โดยประมาณ ($k = 2)$ ที่แต่ละคนพึงพอใจ $(\epsilon = 0.5, \delta = 0.1)$-DP. ตามองค์ประกอบพื้นฐาน ฉันรู้ว่าการใช้สองข้อความค้นหาตามลำดับจะรับประกันได้ $(2 \cdot 0.5, 2 \cdot 0.1) = (1, 0.2)$-DP.

อย่างไรก็ตาม องค์ประกอบขั้นสูงกล่าวว่า แทนที่จะมีองค์ประกอบ $\delta' = k\cdot \เดลต้า$ถ้าเราเต็มใจรับ $\delta ' = k\cdot \delta + \tilde{\delta}$ สำหรับบางคน $\tilde{\delta}>0$แล้วของเรา $\epsilon'$ ปรับปรุงจาก $2\epsilon$ ถึง $\epsilon' = k\cdot \epsilon(\exp(\epsilon) - 1) + \epsilon\sqrt{2 \cdot k \cdot \log (1/\tilde{\delta})}$.

ตอนนี้ถือว่าฉันมีความสุขกับ $\delta' = 0.3$ แทน $\delta' = 0.2$. นี่หมายความว่า $\tilde{\delta}= 0.1$. ดังนั้น, $$\epsilon' = 2\cdot 0.5(\exp(0.5) - 1) + 0.5\sqrt{2 \cdot 2 \cdot \log (1/0.1)} = 2.16 \gg 1.$$

ฉันไม่เข้าใจว่าสิ่งนี้ปรับปรุงองค์ประกอบพื้นฐานอย่างไร เพราะเห็นได้ชัดว่านี่ไม่ใช่กรณี! ฉันทำอะไรผิดหรือเปล่า?

แก้ไข:

ตัวเลขที่ฉันแก้ไขไม่มีผล โดยทั่วไปเรารู้ว่าเราสามารถแต่งเพลงได้ $k$ กลไก (สมมติว่าแต่ละอันคือ $(\epsilon, \delta)$-DP) และได้รับ $(k\epsilon, k\เดลต้า)$-DP เพียงแค่องค์ประกอบพื้นฐาน แต่ด้วยการเพิ่มขึ้น $k\เดลต้า$ เล็กน้อย เราได้รับ $\epsilon'$ ซึ่งเท่ากับ:

$$k \epsilon \underbrace{(e^\epsilon - 1)}_{\geq 0} + \underbrace{\epsilon \sqrt{2 k \log(1 / \tilde{\delta})}}_{ \geq 0} $$ ซึ่งไม่น้อยหน้ากันเสมอไป $k\epsilon$.

โดยเฉพาะอย่างยิ่ง ให้ค่าเผื่อพิเศษของฉันเป็น $\tilde{\delta} = 0.1$. ฉันต้องการดูว่าเมื่อใดที่องค์ประกอบขั้นสูงจะดีขึ้นเมื่อเทียบกับองค์ประกอบพื้นฐาน โดยสรุปแล้ว ฉันต้องการดูเมื่อมีการระงับสิ่งต่อไปนี้:

\begin{จัด} & k\epsilon > k \epsilon (e^\epsilon - 1) + \epsilon \sqrt{2 k \log(1 / \tilde{\delta})} \ \iff & k > k (e^\epsilon - 1) + \sqrt{2 k \log(1 / \tilde{\delta})} \ \iff & \sqrt{k}(2 - e^\epsilon) > \sqrt{2 \log(1 / \tilde{\delta})} \ \iff & k > \frac{2 \log(1 / \tilde{\delta})}{(2 - e^\epsilon)^2} \ \iff & k > \frac{2 \log(10)}{(2 - e^\epsilon)^2} \end{จัด} ตอนนี้ถือว่าฉันต้องการใช้ $2$ กลไก จากนั้น ฉันต้องมี:

\begin{จัด} & \log(10) <(2 - e^\epsilon)^2 \ \iff & \epsilon < \log(2 - \sqrt{\log(10)}) = -0.7286 \end{จัด} ซึ่งไม่มีทางเป็นไปได้ ดังนั้นเมื่อ $k = 2$และถ้าฉันเต็มใจที่จะเพิ่มเท่านั้น $0.1$ ถึง $\delta'$แล้วฉันก็ไม่สามารถปรับปรุงการจัดองค์ประกอบพื้นฐานด้วยการจัดองค์ประกอบขั้นสูงได้เลยหรือ

แก้ไข 2: โดยทั่วไป เราสามารถพูดได้ว่าการจัดองค์ประกอบภาพขั้นสูงจะปรับปรุงเมื่อจัดองค์ประกอบภาพพื้นฐานเท่านั้น หากเป็นไปตามสิ่งต่อไปนี้:

$$ \epsilon < \log\left[2 - \sqrt{\frac{2 \log ( 1/\tilde{\delta})}{k}} \right] $$

ซึ่งต้องใช้ $k > 4$ เมื่อ เช่น $\tilde{\delta} = 0.1$ และจำนวนนี้จะเพิ่มขึ้นเมื่อ $\tilde{\delta}$ ลดลง

โดยรวมแล้ว ฉันรู้สึกว่าองค์ประกอบขั้นสูงนั้นไร้ประโยชน์จริงๆ $k$ ขนาดไม่ใหญ่นัก นี่เป็นเรื่องจริงหรือไม่?

ประการแรก มีผลการจัดองค์ประกอบอื่นๆ เช่น ฉันเชื่อ อันนี้ ปรับปรุงองค์ประกอบขั้นสูง ฉันจะตอบคำถามทั่วไปมากกว่านี้ (ซึ่งฉันคิดว่าคุณเข้าใจแล้ว)

กำหนดกลไก $M_1,\จุด, M_n$เราจะได้ค่าพารามิเตอร์ที่ดีที่สุดสำหรับการจัดองค์ประกอบได้อย่างไร

ตามหลักการแล้ว เราอาจพูดว่า "ใช้องค์ประกอบพื้นฐานสำหรับสิ่งเล็ก ๆ $k$" และ "ใช้องค์ประกอบขั้นสูงสำหรับขนาดใหญ่ $k$". น่าเสียดายที่ใคร ๆ ก็สามารถแสดงให้เห็นอย่างเป็นทางการว่าสิ่งนี้ไม่ตรงไปตรงมา ความซับซ้อนของการคำนวณองค์ประกอบที่เหมาะสมที่สุดของความเป็นส่วนตัวที่แตกต่างกัน การศึกษาสำหรับกลไก "อินพุต" $M_1,\จุด, M_n$ ของพารามิเตอร์ $(\epsilon_1,\delta_1),\dots, (\epsilon_n, \delta_n)$ปัญหาของการค้นหาพารามิเตอร์ "ขั้นต่ำ" $(\epsilon^*, \delta^*)$ ของกลไกการประกอบ

ตัวอย่างเช่นทราบผลลัพธ์ก่อนหน้านี้

ถ้า $M_1,\จุด, M_n$ ล้วน $(\epsilon,\delta)$- ส่วนตัวสำหรับคู่คงที่ของ $(\epsilon, \delta)$และเป้าหมาย $\เดลต้า^*$ จะได้รับ จากนั้นค่าที่เหมาะสมที่สุดของ $\epsilon^*$ เป็นขั้นต่ำ $\epsilon^*\geq 0$ ดังนั้น $$\frac{1}{(1+e^\epsilon)^n}\sum_{\ell = \lceil (\epsilon^*+n\epsilon)/2\epsilon\rceil}^n\binom{n }{\ell}(e^{\ell \epsilon}-e^{\epsilon^*}e^{(n-\ell)\epsilon}) \leq 1 - \frac{1-\delta^*} {(1-\delta)^n}.$$

กระดาษที่ฉันเชื่อมโยงขยายผลนี้ไปยังกรณีของ $M_1,\จุด, M_n$ เป็นส่วนตัวของพารามิเตอร์ $(\epsilon_1,\delta_1),\dots,(\epsilon_n,\delta_n)$ ไม่เหมือนกันทั้งหมด พวกเขาพบนิพจน์ที่คล้ายกัน (แต่ซับซ้อนกว่า) ที่แสดงค่าที่เหมาะสมที่สุดของ $\epsilon^*$ (เมื่อได้รับ "เป้าหมาย" $\เดลต้า^*$) และพบว่าการคำนวณโซลูชันที่เหมาะสมที่สุดคือ $\#P$- สมบูรณ์ เช่น ไม่น่าจะสามารถทำได้อย่างมีประสิทธิภาพ นี่เป็นเรื่องจริงแม้ในกรณีขององค์ประกอบสำหรับกลไกบริสุทธิ์ ความหมาย $\delta_i = 0$ สำหรับทุกอย่าง $i$.

บางทีสิ่งที่น่าสนใจที่สุดสำหรับคุณก็คือมีอัลกอริธึมการประมาณค่าสำหรับปัญหานี้ด้วย (ในบทความนี้ด้วย) ฉันไม่รู้ว่ามีใครนำไปใช้หรือไม่ แต่ถ้ามีก็ดูเหมือนจะเป็นตัวเลือกที่ดีสำหรับการเลือกพารามิเตอร์อย่างเป็นรูปธรรม

เป็นมูลค่าการกล่าวขวัญเช่นกันว่ามีแนวคิดเกี่ยวกับความเป็นส่วนตัวที่เกี่ยวข้องอย่างใกล้ชิด (กล่าวคือ ความเป็นส่วนตัวที่แตกต่างเข้มข้น) ซึ่งเรื่องราวการแต่งเพลงนั้นตรงไปตรงมามากกว่า ในขณะที่เรื่องราวยังคงประสบความสำเร็จ (ในแง่หนึ่ง) $O(\sqrt{k})$ ขูดหินปูนด้วย $k$องค์ประกอบ -fold มากกว่า $O(k)$ การปรับขนาด "องค์ประกอบพื้นฐาน" ช่วยให้คุณ