# Stochastic optimization for large scale optimal transport

A university project about Stochastic Optimal Transport.

## Description

The goal of this project was to reproduce and extend results from [1] which uses the Stochastic Average Gradient algorithm (SAG [2]) to solve regularized optimal transport problems faster. We compare SAG with other optimization algorithms, including SAGA [3]. After comparing the regularized optimal transport convergence results for these algorithms, I studied an optimal school placement and allocation problem in several French regions.

The figures below show some results of solving the semi-discrete optimal transport problem between the school positions and the population density. This enables finding an assignment mapping areas to school which is optimal with respect to a metric on the studied space. The metric here is absolute distance, but it should rather be the real travel distance to be realistic.

This project was my final evaluation for the course Mathematical Foundations Of Data Science taught by Gabriel Peyré in 2019.

### References

1. Genevay, A., Cuturi, M., Peyré, G. & Bach, F..Stochastic Optimization for Large-scale Optimal Transport. in Advances in Neural Information Processing Systems 29 (eds. Lee, D. D., Sugiyama, M., Luxburg, U. V., Guyon, I. & Garnett, R.) 3440–3448 (2016).
2. Schmidt, M., Roux, N. L. & Bach, F..Minimizing Finite Sums with the Stochastic Average Gradient. arXiv:1309.2388 [cs, math, stat] (2013).
3. Defazio, A., Bach, F. & Lacoste-Julien, S..SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives. arXiv:1407.0202 [cs, math, stat] (2014).