-
bounds on the sample complexity for private learning and private data release
جزئیات بیشتر مقاله- تاریخ ارائه: 1392/07/24
- تاریخ انتشار در تی پی بین: 1392/07/24
- تعداد بازدید: 852
- تعداد پرسش و پاسخ ها: 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.
مقالات جدیدترین رویدادها
-
استفاده از تحلیل اهمیت-عملکرد در ارائه الگوی مدیریت خلاقیت سازمانی و ارائه راهکار جهت بهبود
-
بررسی تاثیر ارزش وجوه نقد مازاد بر ساختار سرمایه شرکت های پذیرفته شده در بورس اوراق بهادار تهران
-
بررسی تأثیر سطح افشای ریسک بر قرارداد بدهی شرکت های پذیرفته شده در بورس اوراق بهادار تهران
-
بررسی تأثیر رتبه بندی اعتباری مبتنی بر مدل امتیاز بازار نوظهور بر نقد شوندگی سهام با تأکید بر خصوصی سازی شرکت ها
-
تأثیر آمیخته بازاریابی پوشاک ایرانی بر تصویر ذهنی مشتری پوشاک ایرانی (هاکوپیان)
-
گزارش یک مورد نادر پاتوفیزیولوژی کلاسپ تامب مادرزادی
-
بررسی رابطه بین رقیب گرایی با عملکرد بازاریابی و با توجه به نقش میانجی استراتژی بازاریابی کارآفرینانه (مطالعه موردی صنایع تولیدی صباح)
-
بررسی خواص مغناطیسی و ناهمسانگردی مغناطیسی چند لایه ای های نازک مغناطیسی نامتجانس (fe(2.5nm)/sb(xnm)/mn(2.5nm
-
ارزشهای معماری بومی و نقش آن در توسعه پایدار شهری (نمونه موردی بافت قدیم دزفول)
-
a review of heat transfer between concentric rotating cylinders with or without axial flow
مقالات جدیدترین ژورنال ها
-
مدیریت و بررسی افسردگی دانش آموزان دختر مقطع متوسطه دوم در دروان کرونا در شهرستان دزفول
-
مدیریت و بررسی خرد سیاسی در اندیشه ی فردوسی در ادب ایران
-
واکاوی و مدیریت توصیفی قلمدان(جاکلیدی)ضریح در موزه آستان قدس رضوی
-
بررسی تاثیر خلاقیت، دانش و انگیزه کارکنان بر پیشنهادات نوآورانه کارکنان ( مورد مطالعه: هتل های 3 و 4 ستاره استان کرمان)
-
بررسی تاثیر کیفیت سیستم های اطلاعاتی بر تصمیم گیری موفق در شرکتهای تولیدی استان اصفهان (مورد مطالعه: مدیران شرکتهای تولیدی استان اصفهان)
-
تحلیل ارتباط بین نقد شوندگی سهام و ریسک ورشکستگی شرکت با تأکید بر نقش مالکان نهادی
-
نقش سرمایه گذاران نهادی در رابطه بین مدیریت سود و بازده دارایی ها
-
تاثیر سرمایه روانشناختی بر رضایت شغلی حسابرسان داخلی شرکت های پذیرفته شده در بورس اوراق بهادار تهران
-
بررسی ویژگیهای مدل بالندگی سازمانی مدیریت پروژه (opm3) در مقایسه با سایر مدلهای بلوغ مدیریت پروژه
-
بررسی واقعات h.pylori در نزد اطفال پرورشگاه ولایت بلخ
سوال خود را در مورد این مقاله مطرح نمایید :