The average sensitivity of an intersection of half spaces

DOI10.1145/2591796.2591798zbMATH Open1315.68165arXiv1309.2987OpenAlexW2117475098MaRDI QIDQ5259578FDOQ5259578

Daniel M. Kane

Publication date: 26 June 2015

Published in: Proceedings of the forty-sixth annual ACM symposium on Theory of computing (Search for Journal in Brave)

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(sqrtnlog(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.

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

zbMATH Keywords

learning theorynoise sensitivitylinear threshold function

Mathematics Subject Classification ID

Computational learning theory (68Q32) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Theory of Cryptography
• The geometry of differential privacy: the small database and approximate cases
• On the geometry of differential privacy
• Interactive privacy via the median mechanism
• The price of privately releasing contingency tables and the spectra of random matrices with correlated rows
• Lower Bounds in Differential Privacy
• Iterative Constructions and Private Data Release
• Differential Privacy and the Fat-Shattering Dimension of Linear Queries
• Our Data, Ourselves: Privacy Via Distributed Noise Generation
• On the complexity of differentially private data release
• Collusion-secure fingerprinting for digital data
• Advances in Cryptology – CRYPTO 2004
• New Efficient Attacks on Statistical Disclosure Control Mechanisms
• Bounds on the Sample Complexity for Private Learning and Private Data Release
• Answering n _{2+o(1)} counting queries with differential privacy is hard
• Characterizing the sample complexity of private learners
• Faster Algorithms for Privately Releasing Marginals
• Faster private release of marginals on small databases
• Private Learning and Sanitization: Pure vs. Approximate Differential Privacy
• Privately releasing conjunctions and the statistical query barrier
• Efficient algorithms for privately releasing marginals via convex relaxations

Cited In (2)

• Approximating the Noise Sensitivity of a Monotone Boolean Function
• Fooling Polytopes

Uses Software

• SuLQ

This page was built for publication: The average sensitivity of an intersection of half spaces

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