Open Problem: Can Local Regularization Learn All Multiclass Problems?

Julian Asilis, Siddartha Devic, Shaddin Dughmi, Vatsal Sharan, Shang-Hua Teng
Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:5301-5305, 2024.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v247-asilis24b, title = {Open Problem: Can Local Regularization Learn All Multiclass Problems?}, author = {Asilis, Julian and Devic, Siddartha and Dughmi, Shaddin and Sharan, Vatsal and Teng, Shang-Hua}, booktitle = {Proceedings of Thirty Seventh Conference on Learning Theory}, pages = {5301--5305}, year = {2024}, editor = {Agrawal, Shipra and Roth, Aaron}, volume = {247}, series = {Proceedings of Machine Learning Research}, month = {30 Jun--03 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v247/asilis24b/asilis24b.pdf}, url = {https://proceedings.mlr.press/v247/asilis24b.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T Open Problem: Can Local Regularization Learn All Multiclass Problems? %A Julian Asilis %A Siddartha Devic %A Shaddin Dughmi %A Vatsal Sharan %A Shang-Hua Teng %B Proceedings of Thirty Seventh Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2024 %E Shipra Agrawal %E Aaron Roth %F pmlr-v247-asilis24b %I PMLR %P 5301--5305 %U https://proceedings.mlr.press/v247/asilis24b.html %V 247 %X 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.
APA
Asilis, J., Devic, S., Dughmi, S., Sharan, V. & Teng, S.. (2024). Open Problem: Can Local Regularization Learn All Multiclass Problems?. Proceedings of Thirty Seventh Conference on Learning Theory, in Proceedings of Machine Learning Research 247:5301-5305 Available from https://proceedings.mlr.press/v247/asilis24b.html.

Related Material