Collaborative Research: CIF: Reinventing the Foundations of Multiclass Classification

Many important uses of machine learning require a computer to assign an object, signal, image, or measurement into one of many possible categories. Examples include identifying species from recordings or images, recognizing types of biological cells, detecting materials from sensor measurements, and classifying nanoparticles from their chemical and physical properties. Although the two-category case has been studied deeply, many real scientific and engineering problems involve much larger sets of possible categories. Existing methods for these many-category problems are often effective in practice, but the mathematical understanding of why they work, when they can be trusted, and how they can be made faster is less developed. This project will develop a stronger foundation for classification problems with many categories. The results are expected to support more reliable and efficient machine learning methods for scientific data analysis, engineering systems, and other applications in which accurate classification is essential. The project will also support student training and will produce research articles, tutorial materials, and open-source software. This project will develop new theory and algorithms for multiclass classification by extending the margin-based viewpoint that has played a central role in two-class classification. In the conventional approach to multiclass classification, a method assigns a numerical score to each possible class and uses a loss function to measure how well those scores support the correct class. This project will study loss functions through a complementary viewpoint that focuses on the relative comparisons among class scores. This framework will be used in three main directions. First, the project will develop statistical theory for multiclass surrogate loss functions, including loss functions for settings with a very large number of classes. Second, the project will analyze how explicit regularization and optimization-induced regularization affect generalization in multiclass learning, with attention to structures that arise only when there are more than two classes, such as shared structure among labels and imbalanced class frequencies. Third, the project will develop scalable second-order optimization methods for multiclass empirical risk minimization, including methods for linear classification and boosting. The expected contribution is a unified mathematical and computational framework that helps explain existing multiclass methods, guides the design of new ones, and improves the scalability and reliability of algorithms for many-category classification tasks. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.