Abstract

We give a polynomial-time algorithm for learning high-dimensional halfspaces with margins when the ambient distribution is an unknown affine transformation of the -fold product of an (unknown) symmetric one-dimensional logconcave distribution. Notably, our algorithm does not need labels and establishes the unique (and efficient) identifiability of the hidden halfspace.

Prior work addressed the special case when the underlying distribution is Gaussian via Non-Gaussian Component Analysis. We improve on this by providing polytime guarantees based on TV distance, in place of existing moment-bound guarantees that can be super-polynomial. Our work is also the first to go beyond Gaussians in this setting.

Time

2023-08-08  14:00 - 15:00   

Speaker

Xinyuan Cao, Georgia Institute of Technology

Room

Room 602