In many real-world applications, such as recommender systems and image retrieval, images include various high-level semantics, called tags or annotations. Virtually all the state-of-the-art image annotation methods that handle the issue of imbalanced labeling are search-based techniques (i.e., nearest neighbors), which are inherently timeconsuming. In this paper, a novel coupled dictionary learning approach has been proposed to learn a limited number of visual prototypes and their corresponding semantics, simultaneously. Most coupled dictionary learning methods utilize squared loss function for both visual and semantic modalities that is inappropriate for image annotation with imbalanced labels. We have employed a marginalized loss function in the proposed method while utilizing a simple and effective method to update prototypes. Meanwhile, we have introduced l_1 regularization on semantic prototypes to preserve the sparse and imbalanced nature of labels in learned semantic prototypes. Finally, comprehensive experimental results on various datasets demonstrate the efficiency of the proposed method for image annotation tasks in terms of accuracy and scalability.