A real-valued set function is (additively) approximately submodular if it satisfies the submodularity conditions with an additive error. Approximate submodularity arises in many settings, especially in machine learning, where the function evaluation might not be exact. In this paper we study how close such approximately submodular functions are to truly submodular functions. We show that an approximately submodular function defined on a ground set of n elements is pointwise-close to a submodular function. This result also provides an algorithmic tool that can be used to adapt existing submodular optimization algorithms to approximately submodular functions. To complement, we show an lower bound on the distance to submodularity. These results stand in contrast to the case of approximate modularity, where the distance to modularity is a constant, and approximate convexity, where the distance to convexity is logarithmic.

On additive approximate submodularity / Chierichetti, Flavio; Dasgupta, Anirban; Kumar, Ravi. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - 922:(2022), pp. 346-360. [10.1016/j.tcs.2022.04.035]

On additive approximate submodularity

Flavio Chierichetti;
2022

Abstract

A real-valued set function is (additively) approximately submodular if it satisfies the submodularity conditions with an additive error. Approximate submodularity arises in many settings, especially in machine learning, where the function evaluation might not be exact. In this paper we study how close such approximately submodular functions are to truly submodular functions. We show that an approximately submodular function defined on a ground set of n elements is pointwise-close to a submodular function. This result also provides an algorithmic tool that can be used to adapt existing submodular optimization algorithms to approximately submodular functions. To complement, we show an lower bound on the distance to submodularity. These results stand in contrast to the case of approximate modularity, where the distance to modularity is a constant, and approximate convexity, where the distance to convexity is logarithmic.
2022
submodularity;hyers-ulam;approximate
01 Pubblicazione su rivista::01a Articolo in rivista
On additive approximate submodularity / Chierichetti, Flavio; Dasgupta, Anirban; Kumar, Ravi. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - 922:(2022), pp. 346-360. [10.1016/j.tcs.2022.04.035]
File allegati a questo prodotto
File Dimensione Formato  
Chierichetti_additive_2022.pdf

solo gestori archivio

Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 419.98 kB
Formato Adobe PDF
419.98 kB Adobe PDF   Contatta l'autore
Chierichetti_additive.pdf

accesso aperto

Tipologia: Documento in Pre-print (manoscritto inviato all'editore, precedente alla peer review)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 271.95 kB
Formato Adobe PDF
271.95 kB Adobe PDF

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/1652630
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
social impact