-
bounds on the sample complexity for private learning and private data release
جزئیات بیشتر مقاله- تاریخ ارائه: 1392/07/24
- تاریخ انتشار در تی پی بین: 1392/07/24
- تعداد بازدید: 840
- تعداد پرسش و پاسخ ها: 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.
مقالات جدیدترین رویدادها
-
استفاده از تحلیل اهمیت-عملکرد در ارائه الگوی مدیریت خلاقیت سازمانی و ارائه راهکار جهت بهبود
-
بررسی تاثیر ارزش وجوه نقد مازاد بر ساختار سرمایه شرکت های پذیرفته شده در بورس اوراق بهادار تهران
-
بررسی تأثیر سطح افشای ریسک بر قرارداد بدهی شرکت های پذیرفته شده در بورس اوراق بهادار تهران
-
بررسی تأثیر رتبه بندی اعتباری مبتنی بر مدل امتیاز بازار نوظهور بر نقد شوندگی سهام با تأکید بر خصوصی سازی شرکت ها
-
تأثیر آمیخته بازاریابی پوشاک ایرانی بر تصویر ذهنی مشتری پوشاک ایرانی (هاکوپیان)
-
معرفی متابوکسیت کروندوم دارحیدرآباد (ارومیه) به عنوان نخستین یافته از ترکیبی مشابه امری در ایران
-
استفاده از برنامه نویسی ژنتیکی در تخمین نشست پی های سطحی در خاکهای دانه ای
-
ارزیابی گزینه های پیشنهادی برای حمل و نقل همگانی شهر قم
-
تاثیر معماری زیست آگاه با اکولوژیک پایدار بر ساختمان های بلند مرتبه
-
a comparison between a symmetric and a non-symmetric galerkin finite element—boundary integral equation coupling for the two-dimensional exterior stokes problem
مقالات جدیدترین ژورنال ها
-
مدیریت و بررسی افسردگی دانش آموزان دختر مقطع متوسطه دوم در دروان کرونا در شهرستان دزفول
-
مدیریت و بررسی خرد سیاسی در اندیشه ی فردوسی در ادب ایران
-
واکاوی و مدیریت توصیفی قلمدان(جاکلیدی)ضریح در موزه آستان قدس رضوی
-
بررسی تاثیر خلاقیت، دانش و انگیزه کارکنان بر پیشنهادات نوآورانه کارکنان ( مورد مطالعه: هتل های 3 و 4 ستاره استان کرمان)
-
بررسی تاثیر کیفیت سیستم های اطلاعاتی بر تصمیم گیری موفق در شرکتهای تولیدی استان اصفهان (مورد مطالعه: مدیران شرکتهای تولیدی استان اصفهان)
-
تاملی در مفهوم زیست پذیری؛ شناخت، سنجش و رویکردها
-
پیش بینی تقاضا برای نفت کوره با استفاده از شبکه های هوش مصنوعی
-
نقش گیاهان در فرهنگ مازندران و بازتاب نمادین آن در صنایع دستی مازندران با رویکرد سپهر نشانه ای ( مطالعه موردی دست بافته ها )
-
ابطال حکم موات بودن اراضی و چالش های متعاقب آن برای محاکم قضایی
-
نقش آموزش هنر بر درمان آسیب های اجتماعی و تقویت باورهای دینی دانش آموزان
سوال خود را در مورد این مقاله مطرح نمایید :