Submodulära och fraktionerat subadditiva (eller motsvarande XOS) funktioner spelar en grundläggande roll i kombinatorisk optimering, algoritmisk spelteori och maskininlärning. Motiverade av inlärningsförmågan hos dessa klasser av funktioner från slumpmässiga exempel, överväger vi frågan om hur väl sådana funktioner kan approximeras av låggradiga polynom i 2 norm över den enhetliga fördelningen. Denna fråga är likvärdig med att förstå koncentrationen av Fourier vikt på låggradiga koefficienter, ett centralt begrepp i Fourier analys. Om man anger den minsta grad som är tillräcklig för att approximera f i 2 norm inom deg 2 (f ), visar vi att • För någon submodulär funktion f : {0, 1} n → [0, 1], deg 2 (f ) = O(log(1/ ) / 4/5 ) och det finns en submodulär funktion som kräver grad  till (1/ 4/5 ). • För alla XOS-funktioner f : {0, 1} n → [0, 1], deg 2 (f ) = O(1/ ) och det finns en XOS-funktion som kräver grad (1/ ). Detta förbättrar tidigare metoder som alla visade en övre gräns för O(1/ 2 ) för submodulära [CKKL12], [FKV13], [FV13] och XOS [FV13] funktioner. Den bästa tidigare nedre gränsen var (1/ 2/3 ) för monotona submodulära funktioner [FKV13]. Våra tekniker avslöjar nya strukturella egenskaper hos submodulära och XOS-funktioner och de övre gränserna leder till nästan optimala PAC-lärande algoritmer för dessa klasser av funktioner.
Feldman m.fl. visa en algoritm med körtid 2Õ (1/ 4/5 ) · n 2 för att approximera en submodulär funktion med L 2 fel REF.
Tight Bounds on Low-Degree Spectral Concentration of Submodular and XOS Functions
{'venue': '2015 IEEE 56th Annual Symposium on Foundations of Computer Science', 'journal': '2015 IEEE 56th Annual Symposium on Foundations of Computer Science', 'mag_field_of_study': ['Mathematics', 'Computer Science']}