{"id":553,"date":"2024-04-29T16:56:27","date_gmt":"2024-04-29T16:56:27","guid":{"rendered":"https:\/\/www.let-all.com\/blog\/?p=553"},"modified":"2024-04-29T17:06:06","modified_gmt":"2024-04-29T17:06:06","slug":"the-curious-landscape-of-multiclass-learning","status":"publish","type":"post","link":"https:\/\/www.let-all.com\/blog\/2024\/04\/29\/the-curious-landscape-of-multiclass-learning\/","title":{"rendered":"The Curious Landscape of Multiclass Learning"},"content":{"rendered":"\n

Welcome to the second installment of the Learning Theory Alliance blog post series! In case you missed the first installment on calibration, check it out here<\/a>.<\/p>\n\n\n\n

This time, Nataly Brukhim<\/a> and Chirag Pabbaraju<\/a> tell us about some exciting breakthrough results on multiclass PAC learning.<\/p>\n\n\n\n

\n\n\n\n

The gold standard of learning theory is the classical PAC model defined by Valiant in 1984 [Val84<\/a>]. In particular, it allows us to reason about two fundamental questions: what<\/span><\/em><\/strong> can be learned, and how<\/span><\/em><\/strong> to learn it.<\/p>\n\n\n\n

Generally in this setting, we are given some domain \"\mathcal{X}\" (like images) and a label space \"\mathcal{Y}\" (“dog” or “cat”?). The problem of learning a given class \"\mathcal{H} then boils down to finding a hypothesis \"h after having observed training data drawn from some distribution \"\mathcal{D}\" over \"\mathcal{X}\", such that \"h\" has a small classification error with high probability, with respect to \"\mathcal{D}\".<\/p>\n\n\n\n

For binary<\/em> classification tasks, we get an especially clean and refined mathematical picture, in which these two questions are essentially resolved:<\/p>\n\n\n\n