Online Algorithms for Multiclass Classification using Partial Labels

In this paper, we propose online algorithms for multiclass classification using partial labels. We propose two variant s of Perceptron called Avg Perceptron and Max Perceptron to deal with the par tial labeled data. We also propose Avg Pegasos and Max Pegasos, whic h are extensions of Pegasos algorithm. We also provide mistake bounds for Avg Perceptron and regret bound for Avg Pegasos. We show the effec tiveness of the proposed approaches by experimenting on various data sets and comparing them with the standard Perceptron and Pegasos.