Order-Optimal Sample Complexity of Rectified Flows
This work provides a theoretical explanation for the observed efficiency of rectified flow models, which is significant for researchers and practitioners working with generative models, especially those concerned with sample efficiency.
This paper investigates rectified flow models, which use linear transport trajectories for generative modeling. The authors prove that these models achieve an order-optimal sample complexity of \tilde{O}(\varepsilon^{-2}), improving upon the previously known O(\varepsilon^{-4}) bounds for flow matching models.
Recently, flow-based generative models have shown superior efficiency compared to diffusion models. In this paper, we study rectified flow models, which constrain transport trajectories to be linear from the base distribution to the data distribution. This structural restriction greatly accelerates sampling, often enabling high-quality generation with a single Euler step. Under standard assumptions on the neural network classes used to parameterize the velocity field and data distribution, we prove that rectified flows achieve sample complexity $\tilde{O}(\varepsilon^{-2})$. This improves on the best known $O(\varepsilon^{-4})$ bounds for flow matching model and matches the optimal rate for mean estimation. Our analysis exploits the particular structure of rectified flows: because the model is trained with a squared loss along linear paths, the associated hypothesis class admits a sharply controlled localized Rademacher complexity. This yields the improved, order-optimal sample complexity and provides a theoretical explanation for the strong empirical performance of rectified flow models.