ترجمه فارسی مقاله پیچیدگی نمونه تقویت هموار و محکم بودن قضیه هاردکور

چکیده

Smooth boosters generate distributions that do not place too much weight on any given example. Originally introduced for their noise-tolerant properties, such boosters have also found applications in differential privacy, reproducibility, and quantum learning theory. We study and settle the sample complexity of smooth boosting: we exhibit a class that can be weak learned to $γ$-advantage over smooth distributions with $m$ samples, for which strong learning over the uniform distribution requires $\tildeΩ(1/γ^2)\cdot m$ samples. This matches the overhead of existing smooth boosters and provides the first separation from the setting of distribution-independent boosting, for which the corresponding overhead is $O(1/γ)$. Our work also sheds new light on Impagliazzo’s hardcore theorem from complexity theory, all known proofs of which can be cast in the framework of smooth boosting. For a function $f$ that is mildly hard against size-$s$ circuits, the hardcore theorem provides a set of inputs on which $f$ is extremely hard against size-$s’$ circuits. A downside of this important result is the loss in circuit size, i.e. that $s’ \ll s$. Answering a question of Trevisan, we show that this size loss is necessary and in fact, the parameters achieved by known proofs are the best possible.

چکیده به فارسی (ترجمه ماشینی)

تقویت کننده های صاف توزیع هایی را ایجاد می کنند که بر روی هر نمونه مشخص وزن زیادی قرار نمی دهند.در ابتدا برای خصوصیات تحمل نویز آنها معرفی شده است ، چنین تقویت کننده هایی نیز در زمینه حفظ حریم خصوصی ، تکرارپذیری و نظریه یادگیری کوانتومی کاربردی پیدا کرده اند.ما پیچیدگی نمونه از تقویت صاف را مطالعه و حل می کنیم: ما یک کلاس را نشان می دهیم که می تواند ضعیف باشد و با استفاده از نمونه های صاف $ $ $ $ با نمونه های $ m $ ، با استفاده از نمونه های $ m $ ، که برای آن یادگیری قوی نسبت به توزیع یکنواخت نیاز به \ tildeΩ دارد (1/γ^2) \ cdot m $ نمونه.این با سربار تقویت کننده های صاف موجود مطابقت دارد و اولین جدایی از تنظیم تقویت مستقل توزیع را فراهم می کند ، که سربار مربوط به آن $ O (1/γ) $ است.کار ما همچنین نور جدیدی را بر قضیه هاردکور Impagliazzo از تئوری پیچیدگی می گذارد ، که همه اثبات شناخته شده آن را می توان در چارچوب تقویت صاف قرار داد.برای یک عملکرد $ f $ که کاملاً در برابر مدارهای اندازه $ S $ سخت است ، قضیه هاردکور مجموعه ای از ورودی ها را ارائه می دهد که در آن $ f $ در برابر مدارهای اندازه-$ s $ بسیار سخت است.نکته منفی این نتیجه مهم ، از بین رفتن اندازه مدار است ، یعنی $ s ‘\ ll s $.با پاسخ به یک سؤال از Trevisan ، ما نشان می دهیم که این از دست دادن اندازه ضروری است و در واقع ، پارامترهای حاصل از اثبات شناخته شده بهترین ممکن است.