Tight bounds on _1 approximation and learning of self-bounding functions

MaRDI QIDQ4645666zbMATH OpenFDO

Authors Vitaly Feldman, Pravesh Kothari, Jan Vondrák

Publication date 10 January 2019

Full work available at URL https://arxiv.org/abs/1404.4702, http://proceedings.mlr.press/v76/feldman17a.html

Mathematics Subject Classification ID

Computational learning theory (68Q32)

Recommendations

• Tight bounds on \(\ell_1\) approximation and learning of self-bounding functions
• Optimal bounds on approximation of submodular and XOS functions by juntas
• Bounding the sensitivity of polynomial threshold functions
• Submodular functions are noise stable
• Improved approximation of linear threshold functions

Cited in

(4)

• The Limitations of Optimization from Samples
• Tight bounds on \(\ell_1\) approximation and learning of self-bounding functions
• Testing distributional assumptions of learning algorithms
• Optimal bounds on approximation of submodular and XOS functions by juntas

This page was built for publication: Tight bounds on \(\ell_1\) approximation and learning of self-bounding functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4645666)