The average sensitivity of an intersection of half spaces
Daniel M. Kane · 2014
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.