I detta dokument studerar vi de grundläggande problemen med att maximera en kontinuerlig icke-monoton submodulär funktion över hyperkuben, både med och utan koordinatmässigt konkavitet. Denna familj av optimeringsproblem har flera tillämpningar inom maskininlärning, ekonomi och kommunikationssystem. Vårt huvudresultat är den första 1 2 - approximation algoritm för kontinuerlig submodulär funktion maximering; denna approximation faktor på 1 2 är den bästa möjliga för algoritmer som bara ifrågasätta den objektiva funktionen på polynomialt många punkter. För specialfallet DR-submodulär maximering, d.v.s. När de submodulära funktionerna också är koordinatmässigt konkava längs alla koordinater, ger vi en annan 1 2 - approximationsalgoritm som körs i kvasilinjär tid. Båda dessa resultat förbättras vid tidigare arbete [Bian et al., 2017a,b, Soma och Yoshida, 2017]. Vår första algoritm använder nya idéer som att minska den garanterade approximationen problem att analysera en nollsumma spel för varje koordinat, och innehåller geometrin i detta nollsum spel för att fixa värdet vid denna koordinat. Vår andra algoritm utnyttjar koordinat-wise koncavity för att identifiera en monoton jämvikt villkor tillräckligt för att få den nödvändiga approximation garanti, och jagar för jämviktspunkten med hjälp av binär sökning. Vi utför vidare experiment för att verifiera prestandan hos våra föreslagna algoritmer i relaterade applikationer för maskininlärning.
Tillsammans med utvecklingen av detta arbete 4 föreslog REF en optimal algoritm för DR-submodulär maximering.
Optimal Algorithms for Continuous Non-monotone Submodular and DR-Submodular Maximization
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}