  Supervised dictionary learning (SDL) is a classical machine learning method
that simultaneously seeks feature extraction and classification tasks, which
are not necessarily a priori aligned objectives. The goal of SDL is to learn a
class-discriminative dictionary, which is a set of latent feature vectors that
can well-explain both the features as well as labels of observed data. In this
paper, we provide a systematic study of SDL, including the theory, algorithm,
and applications of SDL. First, we provide a novel framework that `lifts' SDL
as a convex problem in a combined factor space and propose a low-rank projected
gradient descent algorithm that converges exponentially to the global minimizer
of the objective. We also formulate generative models of SDL and provide global
estimation guarantees of the true parameters depending on the hyperparameter
regime. Second, viewed as a nonconvex constrained optimization problem, we
provided an efficient block coordinate descent algorithm for SDL that is
guaranteed to find an $\varepsilon$-stationary point of the objective in
$O(\varepsilon^{-1}(\log \varepsilon^{-1})^{2})$ iterations. For the
corresponding generative model, we establish a novel non-asymptotic local
consistency result for constrained and regularized maximum likelihood
estimation problems, which may be of independent interest. Third, we apply SDL
for imbalanced document classification by supervised topic modeling and also
for pneumonia detection from chest X-ray images. We also provide simulation
studies to demonstrate that SDL becomes more effective when there is a
discrepancy between the best reconstructive and the best discriminative
dictionaries.
