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