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

zbMATH Open1403.68092arXiv1404.4702MaRDI QIDQ4645666FDOQ4645666

Authors: Vitaly Feldman, Pravesh Kothari, Jan Vondrák 

Publication date: 10 January 2019

Full work available at URL: https://arxiv.org/abs/1404.4702

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

Mathematics Subject Classification ID

Computational learning theory (68Q32)

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)