A key problem in image annotation is to learn the underlying semantics. However, finding such semantic embeddings is a challenge task and often requires large amount of tagging information. In this paper, we propose to utilize multi-modality cues by incorporating visual and textual information as embedded objects. The paper further presents a multi-task learning framework that simultaneously learns the approximation of two semantic embeddings with efficient multi-stage convex relaxation technique. The experiments show that the proposed method presents very promising performance in both memory usage and training time for large-scale dataset, as well as image classification accuracy.