Learning Pseudo-Boolean k-DNF and Submodular Functions

DOI10.1137/1.9781611973105.98zbMATH Open1422.68206arXiv1208.2294OpenAlexW1519426874MaRDI QIDQ5741807FDOQ5741807

Authors: Sofya Raskhodnikova, Grigory Yaroslavtsev 

Publication date: 15 May 2019

Published in: Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Abstract: 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 Hastad'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 / epsilon)}, 1/epsilon and log(1/delta) 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 (SODA '12)] implies only n^{O(k)} query complexity for learning submodular functions in this setting, for fixed epsilon and delta. Our learning algorithm implies a property tester for submodularity of functions f:{0,1}^n -> {0, ..., k} with query complexity polynomial in n for k=O((log n/ loglog n)^{1/2}) and constant proximity parameter epsilon.

Full work available at URL: https://arxiv.org/abs/1208.2294

Recommendations

• Submodular functions: learnability, structure, and optimization
• Learning submodular functions
• Learning with submodular functions: a convex optimization perspective
• Efficient Learning of Pseudo-Boolean Functions from Limited Training Data
• A subexponential exact learning algorithm for DNF using equivalence queries
• Disjunctive analogues of submodular and supermodular pseudo-Boolean functions
• Learning of bounded-weight Boolean functions
• scientific article; zbMATH DE number 2045447
• Learning nearly monotone \(k\)-term DNF

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40)

Cited In (9)

• Submodular functions: learnability, structure, and optimization
• Approximate F_2-Sketching of Valuation Functions
• Efficient Learning of Pseudo-Boolean Functions from Limited Training Data
• Learning submodular functions
• Testing convexity of figures under the uniform distribution
• Tight bounds on \(\ell_1\) approximation and learning of self-bounding functions
• Optimal bounds on approximation of submodular and XOS functions by juntas
• Submodular functions are noise stable
• Disjunctive analogues of submodular and supermodular pseudo-Boolean functions

This page was built for publication: Learning Pseudo-Boolean k-DNF and Submodular Functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5741807)