We present a technique for learning the parameters of a continuous-state Markov random field (MRF) model of optical flow, by minimizing the training loss for a set of ground-truth images using simultaneous perturbation stochastic approximation (SPSA). The use of SPSA to directly minimize the training loss offers several advantages over most previous work on learning MRF models for low-level vision, which instead seek to maximize the likelihood of the data given the model parameters. In particular, our approach explicitly optimizes the error criterion used to evaluate the quality of the flow field, naturally handles missing data values in the ground truth, and does not require the kinds of approximations that current methods use to address the intractable nature of maximum-likelihood estimation for such problems. We show that our method achieves state-of-the-art results and requires only a very small number of training images. We also find that our method generalizes well to unseen data, including data with quite different characteristics than the training set.