Accelerated Algorithm for Sparse Regularized Partial Optimal Transport

The gist The proposed framework enables efficient gradient-based updates for sparse regularized Partial Optimal Transport by reformulating Regularized Partial Optimal Transport using an exterior quadratic penalty on marginal constraints, which allows it to accommodate a broad class of smooth and strongly convex regularizers while preserving the structure of the original problem<ref:2609.40075#pg14>

Problem Motivation

Partial Optimal Transport (POT) extends classical optimal transport by relaxing the strict mass conservation constraint, enabling its use in applications involving outliers, missing content, or mismatched sample sizes<ref:2609.40075#pg3> While smooth and strongly convex regularizers have been used to induce sparsity and accelerate computation in machine learning, they have received less algorithmic attention compared to entropic approaches for computational POT<ref:2609.40075#pg4> The paper addresses the limitations of existing methods that typically yield dense transport plans due to entropic regularization, which are undesirable in applications favoring sparsity such as color transfer and domain adaptation<ref:2609.40075#pg5>

Proposed Optimization Framework

The authors propose a penalty-based optimization framework for Partial Optimal Transport with smooth and strongly convex regularizers, including quadratic and elastic-net-type regularization<ref:2609.40075#pg6> The key idea is to reformulate Regularized Partial Optimal Transport (RPOT) into a penalized optimization problem by introducing an exterior quadratic penalty on the marginal constraints<ref:2609.40075#pg7> This reformulation removes the need for strict feasibility during intermediate optimization while preserving the structure of the original problem<ref:2609.40075#pg8> The proposed framework includes QPOT as a special case while supporting a broader class of smooth and strongly convex regularizers<ref:2609.40075#pg9>

Accelerated Algorithm

Building on this formulation, the authors develop a dedicated accelerated first-order solver that combines gradient-based optimization of the penalized objective with simple projections onto the remaining constraints<ref:2609.40075#pg10> This algorithm is based on Proximal Nesterov’s method, combined with the rounding strategy from [24] to restore exact feasibility The algorithm achieves an ε-approximate solution to the original POT problem within O(n(7/8) ε(ln n)) iterations with O(n squared log(n)) per-iteration cost, while maintaining sparsity and scalability

Theoretical Guarantees

The paper proves that the solution to the penalized RPOT formulation is equivalent to that of the original problem with properly chosen penalty parameters The analysis shows that for sufficiently large but finite α, the solution of P-RPOT converges to that of RPOT Specifically, Theorem 3.2 derives a lower bound on α that guarantees a small objective gap between X η,α and X η The final complexity of k for which Algorithm 3 achieves ε-approximate solution is O(n(7/8) ε(ln n))

Empirical Validation

The framework is validated on various applications, including color transfer, domain adaptation, and partial point cloud registration against the Splitting Coni Solver (SCS) and APDAGD solver from [24] Experimental results demonstrate competitive transport cost, high sparsity, and strong feasibility PNAG-POT consistently converges to a lower-cost and sparser transport plan with higher efficiency across all tested regularizers

Conclusion

The paper develops a dedicated first-order solver for Regularized Partial Optimal Transport (RPOT) with smooth and strongly convex regularizers that promotes sparse transport plan, including quadratic and elastic-net regularization By reformulating RPOT using an exterior quadratic penalty framework on the marginal constraints, it allows the accelerated gradient method, PNAG-POT, to efficiently obtain an approximate solution that can then be rounded to a feasible plan whose cost is within ε of the original optimum The methodology shows promise for improving computational methods for other variants of Optimal Transport and scalable adoption in large-scale systems

How it works

The authors propose a new optimization framework that leverages smooth and strongly convex regularizers through a penalty-based reformulation, enabling efficient gradient-based updates while preserving the structure of the original problem<ref:2609.40075#pg4> This approach accommodates a broad class of regularizers that promote structured and sparse transport plans, including quadratic and elastic-net-type regularization<ref:2609.40075#pg9>

The framework involves several key steps to solve the penalized problem P-RPOTeta,α(r, c, s):

1. Reformulation: RPOT is reformulated into a penalized optimization problem by introducing an exterior quadratic penalty on the marginal constraints<ref:2609.40075#pg7> The penalty function P(X, α) is defined as P(X, α) = α sum i min(0, ri - (X1n) i) squared + min(0, ci - (X T1n) i) squared<ref:2609.40075#pg9>

2. Feasibility: The problem is solved over the set S = s = s: 1 T X1n = s, which reduces the marginal inequality constraints to a scaled simplex<ref:2609.40075#pg9>

3. Acceleration: A dedicated accelerated first-order solver based on Proximal Nesterov’s method is used to minimize the penalized objective Fη(X, α)<ref:2609.40075#pg10>

4. Feasibility Restoration: The ROUND-POT rounding procedure is applied to ensure feasibility, yielding the final output X¯

Theoretical Foundation

The mathematical analysis establishes the properties of the penalized objective function Fη(X, α) on S<ref:2609.40075#pg9> Lemma 4.1 proves that the function (28) is ηµ-strongly convex and β-smooth on S, where β = ηL + 4αn This strong convexity and smoothness are crucial to the convergence properties of the proposed gradient-based algorithm<ref:2609.40075#pg10> Theorem 3.1 establishes the equivalence between RPOTeta(r, c, s) and P-RPOTeta,α(r, c, s) up to a controlled error when α is sufficiently large

Algorithm Performance

The PNAGPOT algorithm achieves an objective gap of ε1 from the optimal objective, i.e., 0 ≤ Fη(Xk, α) − Fη(X η,α, α) ≤ ε1 The convergence rate is O(n(7/8) ε(ln n) This complexity is achieved when k ≥ K0, where K0 = s/(β ηµ ln(64 · 472 n squared s squared C squared∞ ε squared + ln 3/3)

Experimental Results

Empirical benchmarks on color transfer, point cloud registration, and domain adaptation consistently show that PNAG-POT obtains a lower transport cost and higher sparsity compared to established baselines like CVXPY For instance, in color transfer, PNAG-POT required 1,800 iterations compared to 50,000 for CVXPY while achieving a lower final cost of 0.9958 versus 5.1 for APDAGD The results are consistent across both quadratic and Elastic-Net regularizations

The gist The proposed framework enables efficient gradient-based updates for sparse regularized Partial Optimal Transport by reformulating Regularized Partial Optimal Transport using an exterior quadratic penalty on marginal constraints, which allows it to accommodate a broad class of smooth and strongly convex regularizers while preserving the structure of the original problem<ref:2609.

1. Improved AI system can perform sparse transport plans in real-world applications by leveraging a new optimization framework that leverages these regularizers through a penalty-based reformulation, enabling efficient gradient-based updates while preserving the structure of the original problem.

2. The improved system can solve Partial Optimal Transport (POT) problems with unbalanced distributions by relaxing the strict mass conservation constraint and using smooth and strongly convex regularizers like quadratic or elastic net to promote structured and sparse transport plans.

3. The system will achieve faster convergence for complex transport problems by utilizing a dedicated accelerated first-order solver that alternates between smooth updates and simple projection steps, achieving an ε-approximate solution to the original POT problem within O(n(7/8) ε ln n ε iterations with O(n squared log(n)) per-iteration cost.

4. The system can be used for color transfer, point cloud registration, and domain adaptation by producing competitive transport cost, high sparsity results compared to established baselines like CVXPY and APDAGD.

5. The system can maintain high adaptation accuracy while producing sparse solutions in domain adaptation tasks, as demonstrated by the result where PNAG-POT achieves an adaptation accuracy of 78.33%, matching or exceeding other methods.