  In this paper, we propose online algorithms for multiclass classification
using partial labels. We propose two variants of Perceptron called Avg
Perceptron and Max Perceptron to deal with the partial labeled data. We also
propose Avg Pegasos and Max Pegasos, which are extensions of Pegasos algorithm.
We also provide mistake bounds for Avg Perceptron and regret bound for Avg
Pegasos. We show the effectiveness of the proposed approaches by experimenting
on various datasets and comparing them with the standard Perceptron and
Pegasos.
