Stochastic Gradient Descent for Semi-Discrete Optimal Transport

Semi-discrete optimal transport maps a continuous probability distribution onto finitely many target points with prescribed masses. We study stochastic gradient descent (SGD) for its Kantorovich dual energy, using source samples to estimate the masses of the associated Laguerre cells. For quadratic cost, a compact convex source domain, and a positive bounded H\"older continuous density, we derive an explicit lower bound on the smallest positive eigenvalue of the dual Hessian from a transport variance inequality. The bound is linear in the smallest cell mass. The main difficulty is that cells can become empty during SGD, making this eigenvalue bound vanish. We prove an explicit restricted strong-convexity bound on an entire bounded region of potentials, including empty-cell configurations. Clipping and centering keep every iterate in this region. Together with an explicit smoothness bound, decreasing steps and weighted averaging give an $O(1/T)$ expected dual-energy error, with separate initialization and sampling terms. We also introduce MC-guided SGD, which uses sampled spectra to choose practical steps and can restart the guaranteed algorithm when needed. Experiments up to dimension 128 and 5000 targets show lower errors than the global schedule in many settings, with competitive accuracy against projected SGD and a measurable spectral-estimation overhead.