Timezone: »

 
Poster
Theoretical Insights Into Multiclass Classification: A High-dimensional Asymptotic View
Christos Thrampoulidis · Samet Oymak · Mahdi Soltanolkotabi

Thu Dec 10 09:00 PM -- 11:00 PM (PST) @ Poster Session 6 #1737
in Poster Session 7 »

Contemporary machine learning applications often involve classification tasks with many classes. Despite their extensive use, a precise understanding of the statistical properties and behavior of classification algorithms is still missing, especially in modern regimes where the number of classes is rather large. In this paper, we take a step in this direction by providing the first asymptotically precise analysis of linear multiclass classification. Our theoretical analysis allows us to precisely characterize how the test error varies over different training algorithms, data distributions, problem dimensions as well as number of classes, inter/intra class correlations and class priors. Specifically, our analysis reveals that the classification accuracy is highly distribution-dependent with different algorithms achieving optimal performance for different data distributions and/or training/features sizes. Unlike linear regression/binary classification, the test error in multiclass classification relies on intricate functions of the trained model (e.g., correlation between some of the trained weights) whose asymptotic behavior is difficult to characterize. This challenge is already present in simple classifiers, such as those minimizing a square loss. Our novel theoretical techniques allow us to overcome some of these challenges. The insights gained may pave the way for a precise understanding of other classification algorithms beyond those studied in this paper.

Author Information

Christos Thrampoulidis (University of British Columbia)
Samet Oymak (University of California Berkeley)
Mahdi Soltanolkotabi (University of Southern california)

More from the Same Authors