Smoothed Analysis for Learning Concepts with Low Intrinsic Dimension
A smoothed-analysis framework that requires a learner to compete only with the best classifier that is robust to small random Gaussian perturbation is introduced, and the first algorithm for agnostic learning intersections of halfspaces in time is obtained, where $γ$ is the margin parameter.
Gautam Chandrasekaran, Adam R. Klivans, Vasilis Kontonis et al.
· Annual Conference Computatio... · 15 citations
· ⚡1