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."
Their proof of their main result "uses duality of linear programming (or, equivalently, the finite dimensional Hahn-Banach Theorem) in the form of the min-max theorem for two-player zero-sum games."
1 "most boosting algorithms consist of iteratively learning weak classifiers with respect to a distribution and adding them to a final strong classifier."