Safe Screening for Unbalanced Optimal Transport
Xun Su Zhongxi Fang Hiroyuki Kasai
This paper introduces a framework that utilizes the Safe Screening technique
to accelerate the optimization process of the Unbalanced Optimal Transport
(UOT) problem by proactively identifying and eliminating zero elements in the
sparse solutions. We demonstrate the feasibility of applying Safe Screening to
the UOT problem with $\ell_2$-penalty and KL-penalty by conducting an analysis
of the solution's bounds and considering the local strong convexity of the dual
problem. Considering the specific structural characteristics of the UOT in
comparison to general Lasso problems on the index matrix, we specifically
propose a novel approximate projection, an elliptical safe region construction,
and a two-hyperplane relaxation method. These enhancements significantly
improve the screening efficiency for the UOT's without altering the algorithm's
complexity.