The Sample Complexity of Smooth Boosting and the Tightness of the Hardcore Theorem
<|reference_start|>The Sample Complexity of Smooth Boosting and the Tightness of the Hardcore Theorem: 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 $\gamma$-advantage over smooth distributions with $m$ samples, for which strong learning over the uniform distribution requires $\tilde{\Omega}(1/\gamma^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/\gamma)$.   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.<|reference_end|>
@article{blanc2024the,
    title={The Sample Complexity of Smooth Boosting and the Tightness of the
  Hardcore Theorem},
    author={Guy Blanc and Alexandre Hayderi and Caleb Koch and Li-Yang Tan},
    journal={arXiv preprint arXiv:2409.11597},
    year={2024},
    archivePrefix={arXiv},
    eprint={2409.11597},
    primaryClass={cs.CC cs.DS cs.LG stat.ML}
}