Testing Halfspaces over Rotation-Invariant Distributions
We present an algorithm for testing halfspaces over arbitrary, unknown rotation-invariant distributions. Using $\tilde O(\sqrt{n}\epsilon^{-7})$ random examples of an unknown function $f$, the algorithm determines with high probability whether $f$ is of the form $f(x) = sign(\sum_i w_ix_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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Downsampling for Testing and Learning in Product Distributions
We study distribution-free property testing and learning problems where the unknown probability distribution is a product distribution over $\mathbb{R}^d$. For many important classes of functions, such as intersections o…
Data-driven Cloud Clustering via a Rotationally Invariant Autoencoder
Advanced satellite-born remote sensing instruments produce high-resolution multi-spectral data for much of the globe at a daily cadence. These datasets open up the possibility of improved understanding of cloud dynamics …
ClusteringTesting Distributions Against Bounded Distinguishers
Motivated by the challenge of testing distributions over high-dimensional or continuous domains, we study distribution testing with respect to bounded classes of distinguishers. A representative task is to use samples fr…
Pointwise Rotation-Invariant Network with Adaptive Sampling and 3D Spherical Voxel Convolution
Point cloud analysis without pose priors is very challenging in real applications, as the orientations of point clouds are often unknown. In this paper, we propose a brand new point-set learning framework PRIN, namely, P…
3D Feature MatchingData AugmentationAgnostic Learning of Halfspaces with Gradient Descent via Soft Margins
We analyze the properties of gradient descent on convex surrogates for the zero-one loss for the agnostic learning of linear halfspaces. If $\mathsf{OPT}$ is the best classification error achieved by a halfspace, by appe…
General Classification