Algorithms for Multiclass Learning with Corrupted Samples

The success of modern Machine Learning Algorithms often relies on the availability of a large number of accurately labeled examples. However, the process of labeling examples is laborious and prone to unreliability in practice. As a result, extensive research has been conducted to develop Machine Learning Algorithms that can effectively handle corrupted samples. Nevertheless, previous works have primarily focused on addressing Binary Classification problems. In this thesis, we investigate Algorithms and Complexity for the challenges of Multiclass Classification with Coarse or Noisy labels. We examine the relationship between these problems and explore the computational complexity of these problems under different assumptions. Namely, we develop an algorithm for multiclass learning with agnostic label noise under the Gaussian distribution, which in terms is an algorithm for the Coarse label problem as well. Also motivated by current work on learning with coarse labels we develop an algorithm for learning Random Classification Noise without estimating the noise transition matrix.  Finally, we examine some special but commonly studied cases for the Coarse Label problem and develop polynomial time algorithms.