2024-06-30-chandrasekaran24a.md

title	section	abstract	layout	series	publisher	issn	id	month	tex_title	firstpage	lastpage	page	order	cycles	bibtex_author	author	date	address	container-title	volume	genre	issued	pdf	extras
Smoothed Analysis for Learning Concepts with Low Intrinsic Dimension	Original Papers	In the well-studied agnostic model of learning, the goal of a learner– given examples from an arbitrary joint distribution on $\mathbb{R}^d \times \{\pm 1\}$– is to output a hypothesis that is competitive (to within $\epsilon$) of the best fitting concept from some class. In order to escape strong hardness results for learning even simple concept classes in this model, we introduce a smoothed analysis framework where we require a learner to compete only with the best classifier that is robust to small random Gaussian perturbation. This subtle change allows us to give a wide array of learning results for any concept that (1) depends on a low-dimensional subspace (aka multi-index model) and (2) has a bounded Gaussian surface area. This class includes functions of halfspaces and (low-dimensional) convex sets, cases that are only known to be learnable in non-smoothed settings with respect to highly structured distributions such as Gaussians. Perhaps surprisingly, our analysis also yields new results for traditional non-smoothed frameworks such as learning with margin. In particular, we obtain the first algorithm for agnostically learning intersections of $k$-halfspaces in time $k^{\poly(\frac{\log k}{\epsilon \gamma}) }$ where $\gamma$ is the margin parameter. Before our work, the best-known runtime was exponential in $k$ (Arriaga and Vempala, 1999).	inproceedings	Proceedings of Machine Learning Research	PMLR	2640-3498	chandrasekaran24a	0	Smoothed Analysis for Learning Concepts with Low Intrinsic Dimension	876	922	876-922	876	false	Chandrasekaran, Gautam and Klivans, Adam and Kontonis, Vasilis and Meka, Raghu and Stavropoulos, Konstantinos	given family Gautam Chandrasekaran given family Adam Klivans given family Vasilis Kontonis given family Raghu Meka given family Konstantinos Stavropoulos	2024-06-30		Proceedings of Thirty Seventh Conference on Learning Theory	247	inproceedings	date-parts 2024 6 30	https://proceedings.mlr.press/v247/chandrasekaran24a/chandrasekaran24a.pdf