Learning pseudo-Boolean k-DNF and submodular functions
Sofya Raskhodnikova, Grigory Yaroslavtsev · 2013
We prove that any submodular function f: {0, 1} n → {0, 1,..., k} can be represented as a pseudo-Boolean 2k-DNF formula. Pseudo-Boolean DNFs are a natural generalization of DNF representation for functions with integer range. Each term in such a formula has an associated integral constant. We show that an analog of H˚astad’s switching lemma holds for pseudo-Boolean k-DNFs if all constants associated with the terms of the formula are bounded. This allows us to generalize Mansour’s PAC-learning algorithm for k-DNFs to pseudo-Boolean k-DNFs, and hence gives a PAC-learning algorithm with membership queries under the uniform distribution for submodular functions of the form f: {0, 1} n → {0, 1,..., k}. Our algorithm runs in time polynomial in n, k O(k log k/ɛ) and log(1/δ) and works even in the agnostic setting. The line of previous work on learning submodular functions [Balcan, Harvey (STOC ’11), Gupta, Hardt, Roth, Ullman; (STOC ’11), Cheraghchi, Klivans, Kothari, Lee