I det här dokumentet studerar vi problemet med att maximera kontinuerliga submodulära funktioner som naturligt uppstår i många inlärningsapplikationer, t.ex. sådana som omfattar allmännyttiga funktioner i aktiv inlärning och avkänning, matris approximationer och nätverksinferens. Trots den uppenbara bristen på konvexitet i sådana funktioner, bevisar vi att stokastiska projicerade gradientmetoder kan ge starka approximativa garantier för att maximera kontinuerliga submodulära funktioner med konvexa begränsningar. Mer specifikt visar vi att för monotona kontinuerliga DR-submodulära funktioner, alla fasta punkter av projicerad lutning stigning ger en faktor 1 2 approximation till den globala maxima. Vi studerar också stokastisk lutning och spegel metoder och visar att efter O(12 ) iterationer dessa metoder når lösningar som uppnår i förväntan objektiva värden som överstiger ( OPT 2 − ). En omedelbar tillämpning av våra resultat är att maximera submodulära funktioner som definieras stokastiskt, dvs.. submodulfunktionen definieras som en förväntan över en familj av submodulära funktioner med en okänd fördelning. Vi kommer att visa hur stokastiska gradientmetoder är naturligt väl lämpade för denna inställning, vilket leder till en faktor 1 2 approximation när funktionen är monoton. I synnerhet tillåter det oss att ungefär maximera diskreta, monotona submodulära optimeringsproblem via projicerad lutning nedstigning på en kontinuerlig avkoppling, direkt ansluta diskreta och kontinuerliga domäner. Slutligen visar experiment på verkliga data att våra prognostiserade gradientmetoder konsekvent uppnår den bästa nyttan jämfört med andra kontinuerliga baslinjer samtidigt som de förblir konkurrenskraftiga när det gäller beräkningssatsning.
Projicerade gradientmetoder undersöktes i REF och visades uppnå ett 1/2- approximationsförhållande för monotona kontinuerliga DR-submodulära funktioner.
Gradient Methods for Submodular Maximization
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}