Submodulära funktioner är en bred klass av setfunktioner, som naturligt uppstår inom olika områden såsom ekonomi, verksamhetsforskning och spelteori. Många algoritmer har föreslagits för att maximera dessa funktioner och uppnå både starka teoretiska garantier och god praktisk prestanda. Tyvärr, när funktionen avviker från submodularitet (även något), de kända algoritmerna för submodulär maximering kan utföra godtyckligt dåligt. Att ändra denna fråga, genom att få approximativa resultat för klasser av set funktioner som generaliserar submodulära funktioner, har stått i fokus för flera nya verk. En sådan klass, känd som klassen av svagt submodulära funktioner, har fått mycket uppmärksamhet från maskininlärningsgemenskapen på grund av dess starka kopplingar till begränsad stark konvexitet och sparsam rekonstruktion. Ett viktigt resultat bevisas av Das och Kempe (2011) visade att approximationen förhållandet av standard girig algoritm för problemet att maximera en svagt submodulär funktion som är föremål för en kardinality restriktion försämrar smidigt med avståndet av funktionen från submodularitet. Emellertid har inga resultat hittills erhållits för maximering av svagt submodulära funktioner som är föremål för begränsningar bortom kardinalitet. I synnerhet är det inte känt om den giriga algoritmen uppnår någon icke-trivial approximation förhållande för sådana begränsningar. I den här artikeln bevisar vi att en randomiserad version av den giriga algoritmen (tidigare använd av Buchbinder et al. (2014) för ett annat problem) uppnår en approximationsgrad på (1 + 1/γ) −2 för maximering av en svagt submodulär funktion som är föremål för en allmän matrisrestriktion, där γ är en parameter som mäter avståndet mellan funktionen och submoduliteten. Dessutom, vi också experimentellt jämföra prestandan av denna version av den giriga algoritmen på verkliga världen problem såsom gen splice plats upptäckt och video summering mot naturliga riktmärken, och visa att algoritmen vi studerar fungerar bra också i praktiken. Såvitt vi vet är detta den första algoritmen med en icke-trivial approximationsgaranti för att maximera en svagt submodulär funktion som är föremål för en annan begränsning än den enkla kardinalitetsbegränsningen. I synnerhet är det den första algoritmen med en sådan garanti för den viktiga och breda klassen av matris begränsningar.
Under förutsättning att en matroid begränsning i stället för en kardinality begränsning, REF analyserade prestandan av en randomiserad girig algoritm för svagt submodulär maximering.
Weakly Submodular Maximization Beyond Cardinality Constraints: Does Randomization Help Greedy?
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}