| Paper ID | MLSP-45.3 |
| Paper Title |
PHASE TRANSITIONS FOR ONE-VS-ONE AND ONE-VS-ALL LINEAR SEPARABILITY IN MULTICLASS GAUSSIAN MIXTURES |
| Authors |
Ganesh Ramachandra Kini, University of California, Santa Barbara, United States; Christos Thrampoulidis, University of British Columbia, Canada |
| Session | MLSP-45: Performance Bounds |
| Location | Gather.Town |
| Session Time: | Friday, 11 June, 13:00 - 13:45 |
| Presentation Time: | Friday, 11 June, 13:00 - 13:45 |
| Presentation |
Poster
|
| Topic |
Machine Learning for Signal Processing: [MLR-PERF] Bounds on performance |
| IEEE Xplore Open Preview |
Click here to view in IEEE Xplore |
| Virtual Presentation |
Click here to watch in the Virtual Conference |
| Abstract |
We study a fundamental statistical question in multiclass classification: When are data linearly separable? Unlike binary classification, linear separability in multiclass settings can be defined in different ways. Here, we focus on the so called one-vs-one (OvO) and one-vs-all (OvA) linear separability. We consider data generated from a Gaussian mixture model (GMM) in a linear asymptotic high-dimensional regime. In this setting, we prove that both the OvO and OvA separability undergo a sharp phase-transition as a function of the overparameterization ratio. We present precise formulae characterizing the phase transitions as a function of the data geometry and the number of classes. Existing results on binary classification follow as special cases of our new formulae. Numerical simulations verify the validity of the asymptotic predictions in finite dimensions. |
