The Average Sensitivity of an Intersection of Half Spaces

2013/09/11 by Daniel M. Kane, Kane, Daniel M. · 3 citations
Computer Science · Mathematics · #Complexity and Algorithms in Graphs #Imbalanced Data Classification Techniques #Machine Learning and Algorithms #cs.CC #math.CO #math.MG

paper · pdf · doi:10.48550/arxiv.1309.2987

arxiv created 2015/01/27 · arxiv updated 2015/01/28

Abstract

We prove new bounds on the average sensitivity of the indicator function of an intersection of k halfspaces. In particular, we prove the optimal bound of O(√(nlog(k))). This generalizes a result of Nazarov, who proved the analogous result in the Gaussian case, and improves upon a result of Harsha, Klivans and Meka. Furthermore, our result has implications for the runtime required to learn intersections of halfspaces.

Cited by

• Tight Bounds for Learning Polyhedra with a Margin
• A Distributional-Lifting Theorem for PAC Learning
• The Power of Iterative Filtering for Supervised Learning with (Heavy) Contamination

Related

• Near-Optimal Statistical Query Lower Bounds for Agnostically Learning Intersections of Halfspaces with Gaussian Marginals
• Learning Functions of Halfspaces
• Tight Generalization Bounds for Large-Margin Halfspaces
• Reliable Learning of Halfspaces under Gaussian Marginals
• Improved Hardness Results for Learning Intersections of Halfspaces