Abstract
We propose a new regularizer for optimal transport (OT) which is tailored to better preserve the class structure of the subjected process. Accordingly, we provide the first theoretical guarantees for an OT scheme that respects class structure. We derive an accelerated proximal algorithm with a closed form projection and proximal operator scheme thereby affording a highly scalable algorithm for computing optimal transport plans. We provide a novel argument for the uniqueness of the optimum even in the absence of strong convexity. Our experiments show that the new regularizer does not only result in a better preservation of the class structure but also in additional robustness relative to previous regularizers.
Introduction
Optimal Transport (OT) has emerged as a powerful framework for Domain Adaptation, enabling the alignment of a source distribution (e.g., high-quality studio images) with a target distribution (e.g., low-resolution mobile photos). However, standard OT is often "class-blind," potentially mapping samples from one source class to multiple unrelated target classes. While various regularizers have been proposed to mitigate this, they often lack theoretical guarantees and computational scalability.
This paper introduces a novel framework using Sum-of-Norms (SON) regularization to ensure that transported data respects its underlying class structure. We provide the first theoretical recovery bounds for class-based OT and introduce a scalable, stochastic proximal algorithm to make this approach practical for large-scale applications.
Methodology
SON Regularization
The proposed approach incorporates a Sum-of-Norms (SON) penalty into the convex optimization program for OT. This penalty encourages "sparsity in differences" within the transport plan matrix. By forcing specific rows and columns to become identical, SON regularization naturally induces a block-diagonal structure. This ensures that clusters in the source domain map cleanly to corresponding clusters in the target domain, effectively preserving the semantic integrity of the data during transport.
Stochastic Incremental Algorithm
Traditional SON-regularized problems suffer from quadratic complexity ($n^2$) relative to the number of data points. To overcome this, we developed an accelerated stochastic proximal-projection scheme. By utilizing memory vectors—similar to the Point-SAGA algorithm—the method provides fast, incremental updates. This allows the algorithm to achieve a convergence rate of $O(1/T)$ without requiring a decaying step size, significantly improving scalability compared to existing gradient-based methods.
Theoretical Guarantees
The Geometric Threshold
A key contribution of this work is the definition of a "geometric threshold" for successful class recovery. We prove that if the components of the data are sufficiently separated, the algorithm will perfectly recover the class associations. Specifically, the distance between unassociated clusters ($D$) must be significantly larger than the distance between associated clusters ($d$) and the cluster radius ($\omega$).
Uniqueness and Robustness
We provide a novel proof that the optimal solution is unique even in the absence of strong convexity, introducing the concept of a "resistant optimal point." Furthermore, the OT-SON framework demonstrates remarkable stability across a wide range of the regularization parameter $\lambda$, avoiding the numerical errors and sensitivity common in Laplacian or $L_p$ regularizers.
Experimental Results
We evaluated the framework on synthetic data and real-world benchmarks, including MNIST, USPS, and the Caltech Office dataset.
As shown in the results, OT-SON achieved an accuracy of 0.550 on the MNIST-to-USPS task (real1), significantly outperforming the standard Sinkhorn method (0.414) and other class-based regularizers like OT-lpl1 (0.457). The method also proved robust in scenarios with class imbalance, correctly identifying and handling source classes that were absent in the target domain.
Conclusion
By combining SON regularization with a high-performance stochastic algorithm, this work provides both the theoretical foundation and the practical tools necessary for class-preserving Optimal Transport. While the current theory assumes well-separated clusters, future research will focus on integrating these methods with deep learning embeddings to handle more complex, overlapping latent spaces in unsupervised settings.
Summary updated