Tight bounds on \(\ell_1\) approximation and learning of self-bounding functions
From MaRDI portal
Publication:2290687
DOI10.1016/j.tcs.2019.11.013zbMath1436.68152OpenAlexW2989742941MaRDI QIDQ2290687
Jan Vondrák, Vitaly Feldman, Pravesh K. Kothari
Publication date: 29 January 2020
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2019.11.013
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Selection of relevant features and examples in machine learning
- Decision theoretic generalizations of the PAC model for neural net and other learning applications
- Boolean functions with low average sensitivity depend on few coordinates
- Efficient distribution-free learning of probabilistic concepts
- Toward efficient agnostic learning
- Learning functions of \(k\) relevant variables
- Combinatorial auctions with decreasing marginal utilities
- Optimal Bounds on Approximation of Submodular and XOS Functions by Juntas
- Weakly learning DNF and characterizing statistical query learning using Fourier analysis
- Privately Releasing Conjunctions and the Statistical Query Barrier
- On maximizing welfare when utility functions are subadditive
- Concentration for self-bounding functions and an inequality of Talagrand
- Agnostically Learning Halfspaces
- A theory of the learnable
- A sharp concentration inequality with applications
- Submodular Functions: Learnability, Structure, and Optimization
- Approximate resilience, monotonicity, and the complexity of agnostic learning
- Bounded Independence Fools Halfspaces
- Learning Pseudo-Boolean k-DNF and Submodular Functions
This page was built for publication: Tight bounds on \(\ell_1\) approximation and learning of self-bounding functions
