Testing Halfspaces over Rotation-Invariant Distributions

DOI10.1137/1.9781611975482.44MaRDI QIDQ5236226zbMATH OpenOpenAlexFDO

Authors Nathaniel Harms

Publication date 15 October 2019

Published in Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Distribution theory (60E99) Randomized algorithms (68W20)

Abstract: We present an algorithm for testing halfspaces over arbitrary, unknown rotation-invariant distributions. Using $ildeO(sqrtnepsilo{n}^{-7})$ random examples of an unknown function $f$, the algorithm determines with high probability whether $f$ is of the form $f(x)=sign(su{m}_i{w}_i{x}_i-t)$ or is $epsilon$-far from all such functions. This sample size is significantly smaller than the well-known requirement of $Omega(n)$ samples for learning halfspaces, and known lower bounds imply that our sample size is optimal (in its dependence on $n$) up to logarithmic factors. The algorithm is distribution-free in the sense that it requires no knowledge of the distribution aside from the promise of rotation invariance. To prove the correctness of this algorithm we present a theorem relating the distance between a function and a halfspace to the distance between their centers of mass, that applies to arbitrary distributions.

Recommendations

• On optimal tests for rotational symmetry against new classes of hyperspherical distributions
• Testing Halfspaces
• Testing halfspaces
• Testing uniformity on high-dimensional spheres against monotone rotationally symmetric alternatives
• Rotation invariant tests for discrete uniformity against peak shaped alternatives
• A decomposition for invariant tests of uniformity on the sphere
• Testing ±1-weight halfspace
• A rotation test to verify latent structure

Cited in

(5)

• Testing Halfspaces
• Testing halfspaces
• Testing (Subclasses of) Halfspaces
• Spectral analysis of matrix scaling and operator scaling
• Distribution-free testing for halfspaces (almost) requires PAC learning

This page was built for publication: Testing Halfspaces over Rotation-Invariant Distributions

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