Vi undersöker tre relaterade och viktiga problem kopplade till maskininlärning: approximering av en submodulär funktion överallt, lärande en submodulär funktion (i en PAC-liknande inställning [53] ), och begränsad minimering av submodulära funktioner. Vi visar att komplexiteten hos alla tre problemen beror på den submodulära funktionens "kurva" och ger lägre och övre gränser som förfinar och förbättrar tidigare resultat [3, 16, 18, 52]. Våra bevistekniker är ganska generiska. Vi använder antingen en svart-box omvandling av funktionen (för approximation och lärande), eller en omvandling av algoritmer för att använda en lämplig surrogatfunktion (för minimering). Märkligt nog har krökning varit känd för att påverka approximationer för submodulär maximering [7, 55], men dess effekt på minimering, approximation och lärande har hittills varit öppen. Vi fullbordar denna bild och stöder även våra teoretiska påståenden genom empiriska resultat.
Våra approximationsbegränsningar beror på n (markuppsättningen) och krökning av de submodulära funktionerna f i REF.
Curvature and Optimal Algorithms for Learning and Minimizing Submodular Functions
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}