I detta dokument tar vi upp följande fråga: Kan vi optimera objektiva funktioner från de träningsdata vi använder för att lära oss dem? Vi formaliserar denna fråga genom ett nytt ramverk som vi kallar optimering från prover (OPS). I OPS får vi provvärden för en funktion som hämtats från viss distribution och målet är att optimera funktionen under vissa begränsningar. Även om det finns intressanta klasser av funktioner som kan optimeras från prover, vårt främsta resultat är en omöjlighet. Vi visar att det finns klasser av funktioner som är statistiskt inlärbara och optimala, men för vilka ingen rimlig approximation för optimering från prover är möjlig. Framför allt visar vårt huvudresultat att det inte finns någon konstant faktor approximation för maximering av täckningsfunktioner under en kardinalitetsbegränsning med hjälp av polynomiskt många prover tagna från någon distribution. Vi visar också snäva approximationsgarantier för maximering under en kardinalitetsbegränsning av flera intressanta klasser av funktioner inklusive enhet-efterfrågan, additiv, och allmänna monotona submodulära funktioner, samt en konstant faktor approximation för monoton submodulära funktioner med avgränsad krökning. där förväntningen är över besluten av algoritmen, m  på pol ( och N  på), δ  på [0, 1) är en konstant.
Balkanki et al Ref-studie om täckningsfunktionerna kan optimeras från prover.
The limitations of optimization from samples
{'venue': 'STOC 2017', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}