-
bounds on the sample complexity for private learning and private data release
جزئیات بیشتر مقاله- تاریخ ارائه: 1392/07/24
- تاریخ انتشار در تی پی بین: 1392/07/24
- تعداد بازدید: 813
- تعداد پرسش و پاسخ ها: 0
- شماره تماس دبیرخانه رویداد: -
learning is a task that generalizes many of the analyses that are applied to collections of data, in particular, to collections of sensitive individual information. hence, it is natural to ask what can be learned while preserving individual privacy. kasiviswanathan et al. (in siam j. comput., 40(3):793–826, 2011) initiated such a discussion. they formalized the notion of private learning, as a combination of pac learning and differential privacy, and investigated what concept classes can be learned privately. somewhat surprisingly, they showed that for finite, discrete domains (ignoring time complexity), every pac learning task could be performed privately with polynomially many labeled examples; in many natural cases this could even be done in polynomial time.while these results seem to equate non-private and private learning, there is still a significant gap: the sample complexity of (non-private) pac learning is crisply characterized in terms of the vc-dimension of the concept class, whereas this relationship is lost in the constructions of private learners, which exhibit, generally, a higher sample complexity.looking into this gap, we examine several private learning tasks and give tight bounds on their sample complexity. in particular, we show strong separations between sample complexities of proper and improper private learners (such separation does not exist for non-private learners), and between sample complexities of efficient and inefficient proper private learners. our results show that vc-dimension is not the right measure for characterizing the sample complexity of proper private learning.we also examine the task of private data release (as initiated by blum et al. in stoc, pp. 609–618,2008), and give new lower bounds on the sample complexity. our results show that the logarithmic dependence on size of the instance space is essential for private data release.
مقالات جدیدترین رویدادها
-
استفاده از تحلیل اهمیت-عملکرد در ارائه الگوی مدیریت خلاقیت سازمانی و ارائه راهکار جهت بهبود
-
بررسی تاثیر ارزش وجوه نقد مازاد بر ساختار سرمایه شرکت های پذیرفته شده در بورس اوراق بهادار تهران
-
بررسی تأثیر سطح افشای ریسک بر قرارداد بدهی شرکت های پذیرفته شده در بورس اوراق بهادار تهران
-
بررسی تأثیر رتبه بندی اعتباری مبتنی بر مدل امتیاز بازار نوظهور بر نقد شوندگی سهام با تأکید بر خصوصی سازی شرکت ها
-
تأثیر آمیخته بازاریابی پوشاک ایرانی بر تصویر ذهنی مشتری پوشاک ایرانی (هاکوپیان)
-
بررسی رابطه بین سبک روابط کاری و سبک رهبری با جو سازمانی و نوآوری سازمانی در یک سازمان صنعتی
-
دیدگاه پزشکان عمومی در مورد وضعیت و انگیزه های شرکت کنندگان در برنامه های بازآموزی و چگونگی اجرای آن
-
استخراج آب از منابع زیرزمینی بر اساس مدیریت هزینه (مطالعه موردی: دشت سیلوانا-زیوه)
-
بررسی تئوری شهرسازی در جهت معماری (نمونه موردی کرمان)
-
استفاده از انرژی خورشیدی در ساختمان
مقالات جدیدترین ژورنال ها
-
مدیریت و بررسی افسردگی دانش آموزان دختر مقطع متوسطه دوم در دروان کرونا در شهرستان دزفول
-
مدیریت و بررسی خرد سیاسی در اندیشه ی فردوسی در ادب ایران
-
واکاوی و مدیریت توصیفی قلمدان(جاکلیدی)ضریح در موزه آستان قدس رضوی
-
بررسی تاثیر خلاقیت، دانش و انگیزه کارکنان بر پیشنهادات نوآورانه کارکنان ( مورد مطالعه: هتل های 3 و 4 ستاره استان کرمان)
-
بررسی تاثیر کیفیت سیستم های اطلاعاتی بر تصمیم گیری موفق در شرکتهای تولیدی استان اصفهان (مورد مطالعه: مدیران شرکتهای تولیدی استان اصفهان)
-
نشانه های بصری معراج پیامبر در نگارگری عثمانی، مطالعه ی موردی نسخه اسکندرنامه ی احمدی
-
دستیابی به شاخص های مطلوب سکونت شهری در بافت های فرسوده تاریخی ایران؛ نمونه موردی: بافت فرسوده تاریخی شهر اردبیل
-
همبستگی بین نگرش های مذهبی و سلامت عمومی در دختران مقطع دبیرستان
-
ساخت و تحلیل دستگاه اندازه گیری و مقایسه ضربه کلت
-
modelling of bonded post-tensioned concrete cantilever beams under flexural loading
سوال خود را در مورد این مقاله مطرح نمایید :