How about Boosting1 and the Hardcore Lemma, as described in this paper?
Trevisan, Luca, Madhur Tulsiani, and Salil Vadhan. "Regularity, boosting, and efficiently simulating every high-entropy distribution." 24th Annual IEEE Conference on Computational Complexity, IEEE, 2009. (PDF download.)
The Hardcore Lemma can be proved via LP duality:
"if a problem is hard-on-average in a weak sense on uniformly distributed inputs, then there is a 'hardcore' subset of inputs of noticeable density such that the problem is hard-on-average in a much stronger sense on inputs randomly drawn from such set."
1 "most boosting algorithms consist of iteratively learning weak classifiers with respect to a distribution and adding them to a final strong classifier."