  Ordinal regression (OR) is classification of ordinal data in which the
underlying categorical target variable has a natural ordinal relation for the
underlying explanatory variable. For $K$-class OR tasks, threshold methods
learn a one-dimensional transformation (1DT) of the explanatory variable so
that 1DT values for observations of the explanatory variable preserve the order
of label values $1,\ldots,K$ for corresponding observations of the target
variable well, and then assign a label prediction to the learned 1DT through
threshold labeling, namely, according to the rank of an interval to which the
1DT belongs among intervals on the real line separated by $(K-1)$ threshold
parameters. In this study, we propose a parallelizable algorithm to find the
optimal threshold labeling, which was developed in previous research, and
derive sufficient conditions for that algorithm to successfully output the
optimal threshold labeling. In a numerical experiment we performed, the
computation time taken for the whole learning process of a threshold method
with the optimal threshold labeling could be reduced to approximately 60\,\% by
using the proposed algorithm with parallel processing compared to using an
existing algorithm based on dynamic programming.
