2024-06-30-asilis24b.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
Open Problem: Can Local Regularization Learn All Multiclass Problems?	Open Problems	Multiclass classification is the simple generalization of binary classification to arbitrary label sets. Despite its simplicity, it has been remarkably resistant to study: a characterization of multiclass learnability was established only two years ago by Brukhim et al. 2022, and the understanding of optimal learners for multiclass problems remains fairly limited. We ask whether there exists a simple algorithmic template — akin to empirical risk minimization (ERM) for binary classification — which characterizes multiclass learning. Namely, we ask whether local regularization, introduced by Asilis et al. 2024, is sufficiently expressive to learn all multiclass problems possible. Towards (negatively) resolving the problem, we propose a hypothesis class which may not be learnable by any such local regularizer.	inproceedings	Proceedings of Machine Learning Research	PMLR	2640-3498	asilis24b	0	Open Problem: Can Local Regularization Learn All Multiclass Problems?	5301	5305	5301-5305	5301	false	Asilis, Julian and Devic, Siddartha and Dughmi, Shaddin and Sharan, Vatsal and Teng, Shang-Hua	given family Julian Asilis given family Siddartha Devic given family Shaddin Dughmi given family Vatsal Sharan given family Shang-Hua Teng	2024-06-30		Proceedings of Thirty Seventh Conference on Learning Theory	247	inproceedings	date-parts 2024 6 30	https://proceedings.mlr.press/v247/asilis24b/asilis24b.pdf