A Corrected Inexact Proximal Augmented Lagrangian Method with a Relative Error Criterion for a Class of Group-Quadratic Regularized Optimal Transport Problems

Lei Yang, Ling Liang, Hong T. M. Chu, Kim-Chuan Toh

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

Abstract

The optimal transport (OT) problem and its related problems have attracted significant attention and have been extensively studied in various applications. In this paper, we focus on a class of group-quadratic regularized OT problems which aim to find solutions with specialized structures that are advantageous in practical scenarios. To solve this class of problems, we propose a corrected inexact proximal augmented Lagrangian method (ciPALM), with the subproblems being solved by the semi-smooth Newton method. We establish that the proposed method exhibits appealing convergence properties under mild conditions. Moreover, our ciPALM distinguishes itself from the recently developed semismooth Newton-based inexact proximal augmented Lagrangian (Snipal) method for linear programming. Specifically, Snipal uses an absolute error criterion for the approximate minimization of the subproblem for which a summable sequence of tolerance parameters needs to be pre-specified for practical implementations. In contrast, our ciPALM adopts a relative error criterion with a single tolerance parameter, which would be more friendly to tune from computational and implementation perspectives. These favorable properties position our ciPALM as a promising candidate for tackling large-scale problems. Various numerical studies validate the effectiveness of employing a relative error criterion for the inexact proximal augmented Lagrangian method, and also demonstrate that our ciPALM is competitive for solving large-scale group-quadratic regularized OT problems.
BibTeX
@article{yang2024corrected,
  author = {Lei Yang and Ling Liang and Hong T. M. Chu and Kim-Chuan Toh},
  title = {{A Corrected Inexact Proximal Augmented Lagrangian Method with a Relative Error Criterion for a Class of Group-Quadratic Regularized Optimal Transport Problems}},
  journal = {J. Sci. Comput.},
  year = {2024},
  url = {https://openreview.net/forum?id=sK6dHy6lWu},
}

Loading related content...

Figure