Stochastic Incremental Algorithms for Optimal Transport with SON Regularizer

Ashkan Panahi, Erik Thiel, Morteza Haghir Cheraghani, Devdatt P. Dubhashi

TL;DR

This paper introduces a new framework for Optimal Transport (OT) that explicitly accounts for underlying class structures in data. They propose a novel regularization technique (sum-of-norms) that helps recover these classes and an efficient algorithm to compute the transport plan, demonstrating improved accuracy and robustness on real-world datasets.

What Problem Does This Paper Address?

Optimal Transport (OT) is a powerful tool for comparing probability distributions by finding the most efficient way to "transport" mass from one distribution to another. While OT has seen success in various applications, it often struggles when the data has an underlying, potentially hidden, class structure. Standard OT methods might ignore or mishandle these classes, leading to suboptimal results. This paper addresses the challenge of performing OT in a way that respects and recovers these class structures, especially when they are not explicitly known beforehand. They aim to find transport maps that not only minimize cost but also ensure that samples from a specific class in the source distribution are mapped to the corresponding class in the target distribution.

Methods

The core of the paper lies in a novel sum-of-norms (SON) regularization applied to the Optimal Transport problem. This regularization term encourages the resulting transport plan to have a block-like structure, where each block corresponds to a class. By carefully choosing the regularization parameter, the method can recover the underlying class structure and their associations between source and target domains.

They also propose an accelerated proximal-projection algorithm to efficiently compute this regularized OT. This algorithm is designed to handle the non-smoothness introduced by the SON regularization and the constraints of the OT problem. It leverages techniques like closed-form proximal operators and stochastic updates to achieve computational efficiency, especially for large-scale problems.

Furthermore, they provide theoretical recovery bounds that guarantee the method can recover the class structure under certain geometric conditions (e.g., how well-separated the classes are). They also offer a novel argument for the uniqueness of the optimal solution, even when the objective function isn't strongly convex.

Datasets

The paper evaluates their proposed method on several real-world datasets:

  • MNIST and USPS: Used for domain adaptation experiments, comparing the performance of their method against others when transferring image data between these digit datasets.
  • Caltech Office: Another standard dataset for domain adaptation, consisting of four different domains (Amazon, Webcam, Caltech, DSLR) with object recognition images.
  • Path-based data: A synthetic dataset with diverse class shapes used to test robustness.

Key Insights and Ideas

  • SON Regularization for Class Discovery: The sum-of-norms regularization is not just for improving OT; it actively helps discover and preserve the underlying class structure in the data, acting as a form of unsupervised clustering within the OT framework.
  • Geometric Threshold for Class Recovery: The paper establishes theoretical conditions (geometric thresholds) under which the class structure can be reliably recovered. This provides a principled way to understand when the method is likely to succeed.
  • Robustness to Data Geometry: The proposed regularizer is shown to be more robust to variations in data geometry compared to previous methods, meaning it performs well even when class distributions are complex or imbalanced.
  • Efficient Algorithm for Complex Problems: Developing an accelerated stochastic algorithm that can handle the non-smoothness and constraints of the SON-regularized OT is crucial for practical applications, especially with large datasets.
  • Uniqueness Beyond Strong Convexity: The theoretical contribution on proving solution uniqueness without relying on strong convexity is a valuable general result for optimization problems.

Key Results

  • Improved Accuracy: On domain adaptation tasks (MNIST/USPS and Caltech Office), their OT-SON method consistently achieved higher classification accuracies compared to other state-of-the-art OT regularization techniques (OT-1112, OT-lp11, OT-Sinkhorn). For instance, on Caltech Office, OT-SON achieved accuracies up to 0.852, outperforming others.
  • Robustness: The method demonstrated significantly better robustness to variations in regularization parameters and class imbalances, often avoiding numerical errors that plagued other methods.
  • Class Structure Preservation: Experiments visually confirmed that OT-SON effectively transports source data to corresponding target classes, avoiding mis-mapping or scattering data points.
  • Computational Efficiency: The proposed stochastic incremental algorithm offers a scalable solution for computing the regularized OT, making it practical for larger datasets.

Limitations and Future Work

  • Geometric Assumptions: The theoretical recovery bounds rely on certain geometric assumptions about the separation and shape of the classes. The practical performance might vary if these assumptions are strongly violated.
  • Parameter Tuning: While the method is shown to be more robust, finding the optimal regularization parameters ($\lambda_1, \lambda_2$) still requires some tuning, though the authors suggest it's less sensitive than other methods.
  • Future Work: The authors suggest exploring further applications of their framework, such as unsupervised domain adaptation (which they briefly touch upon), and investigating its use in other optimization problems where class structure is relevant. They also highlight the potential for further algorithmic improvements.

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{panahi2019stochastic,
  author = {Ashkan Panahi and Erik Thiel and Morteza Haghir Cheraghani and Devdatt P. Dubhashi},
  title = {{Stochastic Incremental Algorithms for Optimal Transport with SON Regularizer}},
  year = {2019},
  eprint = {1903.03850},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1903.03850},
}
Figure