This paper, recently published by researchers from Sun Yat-Sen University and the National University of Singapore, introduces a more efficient way to solve structured Optimal Transport (OT) problems at scale. By swapping out rigid "absolute error" requirements for a more flexible "relative error" criterion, the authors have created an algorithm that is not only faster but significantly easier to tune for real-world applications.
TL;DR
The authors propose ciPALM, a new optimization framework for group-quadratic regularized Optimal Transport that uses a relative error criterion for its subproblems. This approach eliminates the need for complex hyperparameter tuning of error tolerances and allows the solver to tackle massive problems that cause standard commercial solvers like Gurobi and Mosek to run out of memory.
What Problem Does This Paper Address?
Optimal Transport is a powerful mathematical tool used to compare probability distributions, with applications ranging from computer vision to domain adaptation in machine learning. However, the "classical" OT problem often lacks the specific structural properties (like group sparsity) needed for certain tasks. To fix this, researchers add regularizers.
The challenge is that adding these regularizers—specifically group-quadratic ones—makes the optimization problem much harder to solve. Existing state-of-the-art methods like SNIPAL rely on an "absolute error" criterion. This means the user must pre-specify a sequence of decreasing tolerance parameters ($\epsilon_k$) to ensure the algorithm converges. Tuning these sequences is a dark art that often leads to poor performance if done incorrectly. Furthermore, as problem sizes grow into the millions of variables, standard interior-point methods (used by commercial solvers) become prohibitively slow and memory-intensive.
Methods
The authors introduce the Corrected Inexact Proximal Augmented Lagrangian Method (ciPALM). Here are the key technical components:
- Relative Error Criterion: Unlike previous methods that require a sequence of tolerances, ciPALM uses a single relative tolerance parameter ($\rho$). This makes the algorithm much more "user-friendly" and robust to different problem scales.
- The "Correction" Step: To maintain theoretical convergence while using a relative error, the authors add a specific correction step after solving each subproblem. This ensures the algorithm stays on track toward the global optimum.
- Semi-smooth Newton (SSN) Subsolver: The inner loop of the algorithm uses an SSN method. The authors specifically exploit "second-order sparsity"—the fact that the underlying Hessian matrix in these problems is often very sparse—to solve linear systems much faster than general-purpose solvers.
- Unified Framework: The method is designed to handle various OT flavors, including classical, partial, and martingale optimal transport.
Datasets
The authors evaluated ciPALM using a mix of synthetic and real-world benchmark data:
- Synthetic OT Instances: Randomly generated distributions to test basic scalability.
- DOTmark "ClassicImages": A standard benchmark for discrete OT consisting of real-world images (e.g., shapes, textures) at various resolutions (32x32 to 96x96).
- Martingale OT Benchmarks: Synthetic distributions designed to test the specific constraints used in financial mathematics.
- Domain Adaptation Synthetic Data: A dataset specifically designed to show how group-quadratic regularization helps in mapping labeled data from a source to a target domain.
Key Insights and Ideas
- Ease of Tuning: The shift from a summable sequence of parameters to a single relative parameter is a major win for practitioners. It removes the "guess-and-check" work typically required to get proximal methods to converge quickly.
- Memory Efficiency: Commercial solvers like Gurobi and Mosek use interior-point methods that require constructing and factorizing large, dense matrices. ciPALM’s SSN approach keeps the matrices sparse and manageable, allowing it to solve problems with $10^8$ variables on a standard PC.
- Second-Order Sparsity is Key: The "aha moment" is realizing that while the transport plan $X$ might be large, the active constraints that define the Newton step are relatively few. By focusing only on these, the computational cost drops dramatically.
Key Results
- Scalability: ciPALM successfully solved problems with $m=n=17,000$ (nearly 300 million variables). In contrast, Gurobi and Mosek failed due to out-of-memory errors once $m=n$ exceeded 11,000.
- Speedup: On group-quadratic regularized problems, ciPALM was consistently 5 to 8 times faster than Mosek.
- Accuracy: Despite being an "inexact" method, ciPALM achieved feasibility and objective value accuracy comparable to (and sometimes better than) commercial solvers, typically reaching residuals in the $10^{-6}$ to $10^{-8}$ range.
Limitations and Future Work
- The Theoretical Gap: The authors note that while the "correction step" is mathematically necessary for their convergence proof, the algorithm often performs well in practice even without it. Bridging this gap between theory and empirical observation remains an open question.
- Implementation: The current implementation is in MATLAB. While fast, the authors suggest that a dedicated parallel implementation (e.g., in C++ or CUDA) could unlock even greater performance.
- Complex Regularizers: While group-quadratic regularizers are versatile, extending this relative-error framework to even more complex, non-convex, or multi-marginal OT problems is a suggested next step.
Summary updated