{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:38:00Z","timestamp":1787341080739,"version":"build-2736575974"},"reference-count":30,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","funder":[{"DOI":"10.13039\/100011199","name":"FP7 Ideas: European Research Council","doi-asserted-by":"publisher","award":["337122"],"award-info":[{"award-number":["337122"]}],"id":[{"id":"10.13039\/100011199","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100010661","name":"Horizon 2020 Framework Programme","doi-asserted-by":"publisher","award":["708935"],"award-info":[{"award-number":["708935"]}],"id":[{"id":"10.13039\/100010661","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["1388\/16"],"award-info":[{"award-number":["1388\/16"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["336\/18"],"award-info":[{"award-number":["336\/18"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2020,1]]},"abstract":"<jats:p>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 [ Trans. Amer. Math. Soc., 278 (1983), pp. 803--816] (and further improved by Bondarenko, Prymak, and Radchenko [ J. Math. Anal. Appl., 402 (2013), pp. 234--241]). 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, and thus improve upon a previous algorithm of Chierichetti, Das, Dasgupta, and Kumar [ Proceedings of the 56th Symposium on Foundations of Computer Science, 2015, pp. 1143--1162] that is randomized and makes more than a quadratic number of queries. Our learning algorithm is based on the Hadamard transform.<\/jats:p>","DOI":"10.1137\/18m1173873","type":"journal-article","created":{"date-parts":[[2020,1,21]],"date-time":"2020-01-21T11:04:47Z","timestamp":1579604687000},"page":"67-97","source":"Crossref","is-referenced-by-count":1,"title":["Approximate Modularity Revisited"],"prefix":"10.1137","volume":"49","author":[{"given":"Uriel","family":"Feige","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Michal","family":"Feldman","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Inbal","family":"Talgam-Cohen","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2020,1,21]]},"reference":[{"key":"atypb1","doi-asserted-by":"crossref","unstructured":"M.F. Balcan and N. J. A. Harvey,\n                      Learning submodular functions\n                      , in Proceedings of the 43rd Annual ACM Symposium on Theory of Computing, 2011, pp. 793-802.","DOI":"10.1145\/1993636.1993741"},{"key":"atypb2","doi-asserted-by":"crossref","unstructured":"E. Balkanski, A. Rubinstein, and Y. Singer,\n                      The limitations of optimization from samples\n                      , in Proceedings of the 48th Annual ACM Symposium on Theory of Computing, 2017, pp. 1016-1027.","DOI":"10.1145\/3055399.3055406"},{"key":"atypb3","unstructured":"A. Belloni, T. Liang, H. Narayanan, and A. Rakhlin,\n                      Escaping the local minima via simulated annealing: Optimization of approximately convex functions\n                      , in Proceedings of the 28th Conference on Learning Theory, 2015, pp. 240-265."},{"key":"atypb4","first-page":"95","author":"Bertsimas D.","year":"2014","journal-title":"INFORMS PubsOnline"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(93)90044-W"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1016\/j.jmaa.2013.01.019"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1007\/s003659910008"},{"key":"atypb8","doi-asserted-by":"crossref","unstructured":"F. Chierichetti, A. Das, A. Dasgupta, and R. Kumar,\n                      Approximate modularity\n                      , in Proceedings of the 56th IEEE Symposium on Foundations of Computer Science, 2015, pp. 1143-1162.","DOI":"10.1109\/FOCS.2015.74"},{"key":"atypb9","first-page":"469","author":"Dwork C.","year":"2008","journal-title":"Springer"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1137\/070680977"},{"key":"atypb11","unstructured":"U. Feige, M. Feldman, and I. Talgam-Cohen,\n                      Approximate Modularity Revisited\n                      , supplemented version, available as version \u201cv1\u201d athttps:\/\/arxiv.org\/abs\/1612.02034v1, 2016."},{"key":"atypb12","first-page":"247","author":"Feige U.","year":"2013","journal-title":"ACM"},{"key":"atypb13","doi-asserted-by":"crossref","unstructured":"M. X. Goemans, N. J. A. Harvey, S. Iwata, and V. S. Mirrokni,\n                      Approximating submodular functions everywhere\n                      , in Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms, 2009, pp. 535-544,https:\/\/doi.org\/10.1137\/1.9781611973068.59.","DOI":"10.1137\/1.9781611973068.59"},{"key":"atypb14","first-page":"1069","author":"Hassidim A.","year":"2017","journal-title":"PMLR"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.27.4.222"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502096"},{"key":"atypb17","doi-asserted-by":"crossref","unstructured":"S. M. Jung,\n                      Hyers-Ulam-Rassias Stability of Functional Equations in Nonlinear Analysis\n                      , Springer, 2011.","DOI":"10.1007\/978-1-4419-9637-4"},{"key":"atypb18","first-page":"243","volume":"37","author":"Kalton N. J.","year":"1978","journal-title":"Compositio Math."},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1983-0701524-4"},{"key":"atypb20","first-page":"567","author":"Krause A.","year":"2010","journal-title":"Omnipress"},{"key":"atypb21","first-page":"235","volume":"9","author":"Krause A.","year":"2008","journal-title":"J. Mach. Learn. Res."},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2005.02.006"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2017.10.016"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1002\/sapm1933121311"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.4064\/cm-54-1-163-164"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1137\/0206022"},{"key":"atypb27","unstructured":"T. Roughgarden, I. Talgam-Cohen, and J. Vondr\u00e1k,\n                      When are welfare guarantees robust?\n                      , in Proceedings of the 20th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, 2017, art. 22."},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.2000.1989"},{"key":"atypb29","unstructured":"Y. Singer and J. Vondr\u00e1k,\n                      Information-theoretic lower bounds for convex optimization with erroneous oracles\n                      , in Proceedings of the 28th Annual Conference on Neural Information Processing Systems, 2015, pp. 3204-3212."},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1080\/14786446708639914"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/18M1173873","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:04:46Z","timestamp":1787339086000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/18M1173873"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,1]]},"references-count":30,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2020,1]]}},"alternative-id":["10.1137\/18M1173873"],"URL":"https:\/\/doi.org\/10.1137\/18m1173873","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,1]]}}}