Numerical embedding has become one standard technique for processing and analyzing unstructured data. It stores the main characteristics of data by mapping it onto a numerical vector. Given an embedding, a downstream learning method, referred to as a two-stage method, is applicable to unstructured data. In this article, we introduce a novel framework of embedding learning to deliver a higher learning accuracy, while identifying an optimal learning-adaptive embedding. Particularly, we propose a concept of minimal sufficient learning-adaptive embeddings, based on which we seek an optimal one to maximize the accuracy subject to an embedding loss constraint. Moreover, we derive a graph embedding classifier for an input to be a hyperlink tensor representing multiway relations of unstructured data. Numerically, we use blockwise coordinate descent and projected gradient descent to implement linear and neural network classifiers, respectively. Theoretically, we establish a learning theory to quantify the generalization error of both linear and neural network embedding learners. Finally, we demonstrate the utility of the classifiers on two benchmarks in tagging and sentiment analysis.