Dimensionality reduction plays an important role in various machine learning tasks. In this paper, we propose a novel method dubbed Sparse Multi-label bILinear Embedding (SMILE) on Stiefel manifolds for supervised dimensionality reduction on multi-label data. Unlike the traditional multi-label dimensionality reduction algorithms that work on the vectorized data, the proposed SMILE directly takes the second-order tensor data as the input, and thus characterizes the spatial structure of the tensor data in an efficient way. Differentiating from the existing tensor-based dimensionality reduction methods that perform the eigen-decomposition in each iteration, SMILE utilizes a gradient ascent strategy to optimize the objective function in each iteration, and thus is more efficient. Moreover, we introduce column-orthonormal constraints to transformation matrices to eliminate the redundancy between the projection directions of the learned subspace and add an $$L:1$$ -norm regularization term to the objective function to enhance the interpretability of the learned subspace. Experiments on a standard image dataset validate the effectiveness of the proposed method.