Methods for reconstructing images of a subject from data acquired with a medical imaging system, such as a magnetic resonance imaging (“MRI”) system, are described. In general, the image reconstructions implement a primal-dual optimization strategy that, in each iteration, stochastically updates a dual variable.