Abstract
In 2016, Carmosino, Impagliazzo, Kabanets, and Kolokolova (CCC, 2016) showed that the existence of natural properties in the sense of Razborov and Rudich (JCSS, 1997) implies PAC learning algorithms in the sense of Valiant (Comm. ACM, 1984), for boolean functions in P/poly, under the uniform distribution and with membership queries. It is still an open problem to get from natural properties improved learning algorithms that do not rely on membership queries but rather use randomly drawn labeled examples.
Natural properties may be understood as an average-case version of MCSP, the problem of deciding the minimum size of a circuit computing a given truth-table. Problems related to MCSP include those concerning time-bounded Kolmogorov complexity. MKTP, for example, asks for the KT-complexity of a given string. KT-complexity is a relaxation of circuit size, as it does away with the requirement that a short description of a string be interpreted as a boolean circuit.
In this work, under assumptions of MKTP and related problems of time-bounded Kolmogorov complexity being easy on average, we get learning algorithms for boolean functions in P/poly that
- work over any distribution D samplable by a polynomial-size circuit (given either explicitly or as a ``black box’’),
- do not require membership queries but only randomly drawn labeled examples from D, and
- are agnostic in that they do not require the target function to belong to the hypothesis class in question.
Our results build upon the recent work of Hirahara and Nanashima (FOCS, 2021) who showed similar learning consequences but under a stronger assumption that NP is easy on average.
This is joint work with Valentine Kabanets.