The uniform hardcore lemma via approximate Bregman projections

By Boaz Barak, Moritz Hardt, Satyen Kale. 2009

68 citations recorded by the source corpus.

We give a simple, more efficient and uniform proof of the hard-core lemma, a fundamental result in complexity theory with applications in machine learning and cryptography. Our result follows from the connection between boosting algorithms and hard-core set constructions discovered by Klivans and Servedio [11]. Informally stated, our result is the following: suppose we fix a family of boolean functions. Assume there is an efficient algorithm which for every input length and every smooth distribution (i.e. one that doesn't assign too much weight to any single input) over the inputs produces a circuit such that the circuit computes the boolean function noticeably better than random. Then, there is an efficient algorithm which for every input length produces a circuit that computes the function correctly on almost all inputs. Our algorithm significantly simplifies previous proofs of the uniform and the non-uniform hard-core lemma, while matching or improving the previously best known parameters. The algorithm uses a generalized multiplicative update rule combined with a natural notion of approximate Bregman projection. Bregman projections are widely used in convex optimization and machine learning. We present an algorithm which efficiently approximates the Bregman projection onto the set of high density measures when the Kullback-Leibler divergence is used as a distance function. Our algorithm has a logarithmic runtime over any domain from which we can efficiently sample. High density measures correspond to smooth distributions which arise naturally, for instance, in the context of online learning. Hence, our technique may be of independent interest.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

Citations in the corpus

Boosting and Differential Privacy (2010, background): “There is a growing literature on such smooth boosting algorithms [32, 21, 17, 1], where no single example is assigned too much weight.”
The Multiplicative Weights Update Method: a Meta-Algorithm and Applications (2012, methodology): “This technique was extended in [8] to obtain uniform constructions of hard-core sets with the best known parameters.”
Revisiting Design Choices in Proximal Policy Optimization (2020, unknown): “The proof extends main ideas from the proof of Lemma 4.1 in [5] with a ﬁner-grain analysis, using Bregman’s theorem.”
Distribution-Specific Agnostic Boosting (2009, methodology): “In addition Kalai and Kanade give a simpler version of the agnostic halfspace learning algorithm of Kalai et al. [21] and include results from an empirical evaluation of their algorithm.”