Recovery Bounds on Class-Based Optimal Transport: A Sum-of-Norms Regularization Framework

Ashkan Panahi, Arman Rahbar, Morteza Haghir Chehreghani, Devdatt Dubhashi, Krim, Hamid

Abstract

We develop a novel theoretical framework for understating OT schemes respecting a class structure. For this purpose, we propose a convex OT program with a sum-of-norms regularization term, which provably recovers the underlying class structure under geometric assumptions. Furthermore, we derive an accelerated proximal algorithm with a closed-form projection and proximal operator scheme, thereby affording a more 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 not only results in a better preservation of the class structure in the data but also yields additional robustness to the data geometry, compared to previous regularizers.

Introduction

Optimal Transport (OT) has emerged as a fundamental tool for data alignment and domain adaptation, enabling the transformation of one distribution into another by minimizing a transport cost. However, a significant limitation of standard OT is its tendency to ignore latent class structures. In scenarios like digit recognition (e.g., MNIST to USPS), a naive OT map might split a single source cluster across multiple target clusters to minimize global cost, thereby destroying the semantic integrity of the data. While previous attempts to incorporate class structure used various regularizers, they often lacked rigorous theoretical guarantees. This work addresses this gap by introducing a Sum-of-Norms (SON) regularization framework that provably preserves class structures.

Methodology

The proposed framework introduces two primary innovations:

SON-Regularized OT

The authors modify the Kantorovich relaxation of OT by incorporating a Sum-of-Norms (SON) penalty. In clustering contexts, SON regularization is known to encourage "grouping" by forcing variables to be identical. Applied to OT, this penalty encourages the transport plan to adopt a block-diagonal structure, effectively treating entire clusters as single units for transport rather than individual points.

Accelerated Stochastic Incremental Algorithm

To address the $O(n^2)$ complexity of standard OT, the authors developed a scalable stochastic proximal-projection scheme. This algorithm utilizes closed-form operators for the SON proximal step, significantly speeding up iterations. By adapting a "Point-SAGA" style approach for constraint handling, the method scales efficiently to larger datasets.

Theoretical Guarantees

A core contribution of this paper is the establishment of a "geometric threshold" for class recovery.

Geometric parameters D, d, and E defining the threshold for class-structure recovery in SON-OT.

The theory posits that if data clusters are sufficiently well-separated—defined by a specific ratio of cluster separation to cluster width—the SON-OT is mathematically guaranteed to recover the correct class mapping. Furthermore, the authors prove the uniqueness of the solution without requiring strong convexity, using a novel "resistant optimal points" argument. This ensures that the algorithm consistently finds the semantically correct transport plan.

Experimental Evaluation

The framework was evaluated on benchmark datasets including MNIST, USPS, and the Caltech Office dataset.

Comparative performance of OT-SON against standard regularizers across different real-world domain adaptation tasks.

As shown in the results, OT-SON consistently outperforms existing methods. For instance, in the MNIST-to-USPS task, OT-SON achieved an accuracy of 0.550, significantly higher than the 0.421 achieved by standard OT-1112 regularization. Beyond accuracy, the method demonstrated remarkable robustness to the regularization parameter ($\lambda$) and handled class imbalances more gracefully than competing methods like Sinkhorn or $L_pL_1$ OT.

Conclusion

This work provides the first rigorous proof that OT can automatically recover and preserve class structures through SON regularization. While the current theory assumes disjoint supports for clusters, the empirical results suggest broad applicability. Future work will explore extending this framework to unbalanced OT settings, which are common in open-set domain adaptation where source and target classes may not perfectly overlap.

Summary updated

Abstract

We develop a novel theoretical framework for understating OT schemes respecting a class structure. For this purpose, we propose a convex OT program with a sum-of-norms regularization term, which provably recovers the underlying class structure under geometric assumptions. Furthermore, we derive an accelerated proximal algorithm with a closed-form projection and proximal operator scheme, thereby affording a more 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 not only results in a better preservation of the class structure in the data but also yields additional robustness to the data geometry, compared to previous regularizers.
BibTeX
@misc{panahi2019recovery,
  author = {Ashkan Panahi and Arman Rahbar and Morteza Haghir Chehreghani and Devdatt Dubhashi and Krim, Hamid},
  title = {{Recovery Bounds on Class-Based Optimal Transport: A Sum-of-Norms Regularization Framework}},
  year = {2019},
  eprint = {1903.03850},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1903.03850},
}
Figure