Abstract Semi-supervised support vector machines is an extension of standard support vector machines with unlabeled instances, and the goal is to fifind a label assignment of the unlabeled instances, so that the decision boundary has the maximal minimum margin on both the original labeled instances and unlabeled instances. Recent studies, however, disclosed that maximizing the minimum margin does not necessarily lead to better performance, and instead, it is crucial to optimize the margin distribution. In this paper, we propose a novel approach ssODM (SemiSupervised Optimal margin Distribution Machine), which tries to assign the labels to unlabeled instances and to achieve optimal margin distribution simultaneously. Specififically, we characterize the margin distribution by the fifirst- and second-order statistics, i.e., the margin mean and variance, and extend a stochastic mirror prox method to solve the resultant saddle point problem. Extensive experiments on twenty UCI data sets show that ssODM is signifificantly better than compared methods, which verififies the superiority of optimal margin distribution learning.