2024-06-30-gajjar24a.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
Agnostic Active Learning of Single Index Models with Linear Sample Complexity	Original Papers	We study active learning methods for single index models of the form $F({\bm x}) = f(⟨{\bm w}, {\bm x}⟩)$, where $f:\mathbb{R} \to \mathbb{R}$ and ${\bx,\bm w} \in \mathbb{R}^d$. In addition to their theoretical interest as simple examples of non-linear neural networks, single index models have received significant recent attention due to applications in scientific machine learning like surrogate modeling for partial differential equations (PDEs). Such applications require sample-efficient active learning methods that are robust to adversarial noise. I.e., that work even in the challenging agnostic learning setting. We provide two main results on agnostic active learning of single index models. First, when $f$ is known and Lipschitz, we show that $\tilde{O}(d)$ samples collected via {statistical leverage score sampling} are sufficient to learn a near-optimal single index model. Leverage score sampling is simple to implement, efficient, and already widely used for actively learning linear models. Our result requires no assumptions on the data distribution, is optimal up to log factors, and improves quadratically on a recent ${O}(d^{2})$ bound of Gajjar et. al 2023. Second, we show that $\tilde{O}(d)$ samples suffice even in the more difficult setting when $f$ is \emph{unknown}. Our results leverage tools from high dimensional probability, including Dudley’s inequality and dual Sudakov minoration, as well as a novel, distribution-aware discretization of the class of Lipschitz functions.	inproceedings	Proceedings of Machine Learning Research	PMLR	2640-3498	gajjar24a	0	Agnostic Active Learning of Single Index Models with Linear Sample Complexity	1715	1754	1715-1754	1715	false	Gajjar, Aarshvi and Tai, Wai Ming and Xingyu, Xu and Hegde, Chinmay and Musco, Christopher and Li, Yi	given family Aarshvi Gajjar given family Wai Ming Tai given family Xu Xingyu given family Chinmay Hegde given family Christopher Musco given family Yi Li	2024-06-30		Proceedings of Thirty Seventh Conference on Learning Theory	247	inproceedings	date-parts 2024 6 30	https://proceedings.mlr.press/v247/gajjar24a/gajjar24a.pdf