Approximate modularity revisited

DOI10.1145/3055399.3055476zbMATH Open1370.68150arXiv1612.02034OpenAlexW2560393541MaRDI QIDQ4978043FDOQ4978043

Authors: Michal Feldman, Inbal Talgam-Cohen, Uriel Feige 

Publication date: 17 August 2017

Published in: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Abstract: Set functions with convenient properties (such as submodularity) appear in application areas of current interest, such as algorithmic game theory, and allow for improved optimization algorithms. It is natural to ask (e.g., in the context of data driven optimization) how robust such properties are, and whether small deviations from them can be tolerated. We consider two such questions in the important special case of linear set functions. One question that we address is whether any set function that approximately satisfies the modularity equation (linear functions satisfy the modularity equation exactly) is close to a linear function. The answer to this is positive (in a precise formal sense) as shown by Kalton and Roberts [1983] (and further improved by Bondarenko, Prymak, and Radchenko [2013]). We revisit their proof idea that is based on expander graphs, and provide significantly stronger upper bounds by combining it with new techniques. Furthermore, we provide improved lower bounds for this problem. Another question that we address is that of how to learn a linear function $h$ that is close to an approximately linear function $f$, while querying the value of $f$ on only a small number of sets. We present a deterministic algorithm that makes only linearly many (in the number of items) nonadaptive queries, by this improving over a previous algorithm of Chierichetti, Das, Dasgupta and Kumar [2015] that is randomized and makes more than a quadratic number of queries. Our learning algorithm is based on a Hadamard transform.

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

Recommendations

• Approximate modularity revisited
• Learning submodular functions
• Optimal bounds on approximation of submodular and XOS functions by juntas
• scientific article; zbMATH DE number 7051222
• Submodular functions: learnability, structure, and optimization

zbMATH Keywords

learninglinear functionsset functions

Mathematics Subject Classification ID

Computational learning theory (68Q32) Combinatorial optimization (90C27) Real- or complex-valued set functions (28A10)

Cited In (6)

• Modularity of confluence: A simplified proof
• Approximate Modularity Revisited
• Generalized modularity matrices
• On additive approximate submodularity
• Modularity in planted partition model
• When Are Welfare Guarantees Robust

This page was built for publication: Approximate modularity revisited

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