PaperlayerView exact revision on arXiv

Source-linked AI summary

Accelerated Algorithm for Sparse Regularized Partial Optimal Transport

Khoa Nguyen, Dung T. Nguyen, Thong Huynh, Hoang-Hiep Nguyen-Mau, Anh Nguyen, Minh Ngoc Dinh, Juho Kannala

arXiv:2609.40075v1cs.LG

TL;DR

POT relaxes equal-mass transport, but scalable entropic approaches typically yield dense plans, while sparse regularized POT has received less algorithmic attention. This paper combines a penalty-based formulation for smooth, strongly convex regularizers with an accelerated first-order solver; its benchmarks report competitive cost, high sparsity, and strong feasibility relative to scalable POT solvers.

  • Problem

    POT accommodates unequal-mass distributions, but its structural constraints make scalable solution difficult, and entropic solvers typically produce dense plans.

    Source: §1 · p. 2

  • Method

    The paper uses an exterior-penalty formulation for smooth, strongly convex regularizers and develops an accelerated first-order solver with rounding to restore feasibility.

    Source: §1 · p. 3

  • Results

    Across color transfer, domain adaptation, and point-cloud registration, experiments report competitive transport cost, high sparsity, strong feasibility, and favorable performance over scalable POT solvers.

    Source: §1 · p. 4, §6 · p. 28

  • Takeaways & Limitations

    The framework offers a dedicated scalable first-order approach to sparse regularized POT without relying on general-purpose convex solvers.

    Source: §1 · p. 3

    The convergence guarantee for controlled constraint violation assumes Slater’s condition for RPOT.

    Source: §2.1 · p. 5, §3.2 · p. 12

Abstract

from arXiv · show

Partial Optimal Transport (POT) extends the classical optimal transport problem by relaxing the strict mass conservation constraint, enabling its use in a wide range of real-world applications. In many of these settings, sparse transport plans are preferred for their interpretability and computational benefits. While smooth and strongly convex regularizers - such as quadratic or elastic net - have been vastly used in various machine learning applications to induce sparsity and accelerate computation, they have received less algorithmic attention compared to entropic approaches for computational POT. In this paper, we propose 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. Our method accommodates a broad class of regularizers that promote structured and sparse transport plans. Building on this formulation, we design an accelerated first-order algorithm that alternates between smooth updates and simple projection steps. Through empirical benchmarks on color transfer, domain adaptation, and point cloud registration, our approach consistently outperforms established baselines - achieving lower transport cost, higher sparsity, and faster convergence - making it a practical and scalable solution for modern transport problems.

1 Introduction

The introduction motivates sparse regularized POT as a response to computationally difficult partial-transport constraints and the dense plans produced by entropic solvers. It presents a penalty-based framework and accelerated first-order solver, then reports favorable empirical performance.

Motivation

  • POT permits transporting a prescribed amount of mass between distributions with unequal totals, accommodating outliers, missing content, or mismatched sample sizes.Applications include color transfer, domain adaptation, and dictionary learning.Source: §1 · p. 2
  • Existing scalable entropic approaches typically produce dense plans, while dummy-variable reformulations increase problem size and can raise memory and computational costs.These trade-offs motivate methods that retain sparsity without relying on entropic regularization.Source: §1 · p. 2

Proposed framework

  • The proposed penalty-based framework covers quadratic and elastic-net-type smooth, strongly convex regularizers, including QPOT as a special case.It targets the gap between QPOT's general-purpose optimization and the need for dedicated scalable methods.Source: §1 · p. 3
  • An exterior quadratic penalty on marginal constraints enables gradient-based optimization without requiring strict feasibility during intermediate updates, while preserving the original problem's structure.The penalized solution approximates the original RPOT solution with suitably chosen parameters.Source: §1 · p. 3

Algorithm and guarantees

  • Proximal Nesterov acceleration is combined with rounding to restore exact feasibility and obtain an ε-approximate solution to the original POT problem.The paper also provides bounds on objective gap and constraint violations for the penalized formulation.Source: §1 · p. 3

Empirical evaluation

  • Across color transfer, domain adaptation, and partial point-cloud registration, experiments report competitive transport cost, high sparsity, strong feasibility, and favorable performance over scalable POT solvers.The stated per-iteration cost is O(n^2 log(n)), while maintaining sparsity and scalability.Source: §1 · pp. 3–4

2 Preliminaries

The preliminaries define OT and POT and establish the assumptions and regularizer properties used in the paper's RPOT formulation.

2.1 Optimal Transport and Partial Optimal Transport

  • OT transports equal-mass distributions, whereas POT allows a specified transported mass between distributions that may have different total masses.The transported mass lies between zero and the smaller of the two total masses.Source: §2.1 · p. 4
  • The analysis assumes Slater’s condition: a strictly feasible POT plan exists with positive slack in both marginal inequalities.The assumption is stated with slack value ζ.Source: §2.1 · p. 5

2.2 Regularizers in Partial Optimal Transport

  • RPOT adds a regularizer to the transport objective; regularizers can promote sparsity, and the formulation assumes a nonnegative, smooth, strongly convex regularizer.Quadratic regularization is identified as a sparsity-promoting example.Source: §2.2 · p. 5
  • The preliminaries establish a finite upper bound on the regularizer over the feasible set, supporting the later bounds for the penalized problem.The feasible set is compact, and the paper gives regularizer-specific smoothness, strong-convexity, and boundedness parameters.Source: §2.2 · pp. 5–7

3 Penalty Method for RPOT

This section replaces difficult marginal feasibility constraints with an exterior quadratic penalty while retaining the remaining simple constraints. It establishes asymptotic and finite-parameter guarantees connecting the penalized solution to the original RPOT solution.

3 Penalty Method for RPOT

  • Explicitly enforcing RPOT feasibility can be demanding, so the section uses exterior penalties to soften constraint violations during optimization.The approach is intended to retain an approximation guarantee for the original constrained problem under suitable penalty parameters.Source: §3 · p. 7

3.1 Penalty Function

  • The quadratic penalty targets the marginal inequalities, while nonnegativity and the transported-mass equality remain the simpler constraints.The marginal feasible set T comprises plans satisfying both source and target marginal upper bounds.Source: §3.1 · p. 8
  • As the penalty parameter grows, minimizing the penalized problem converges to minimizing RPOT; for sufficiently large finite parameters, the penalized solution can approximate the true solution.The penalty increases for plans outside the marginal-feasible set.Source: §3.1 · pp. 8–10

3.2 Convergence to the true solution of RPOT

  • Under Slater’s condition, a sufficiently large penalty parameter bounds both the objective gap and constraint violation of the penalized solution.The constraint-violation tolerance is controlled by the parameter choice, and the theorem supplies a lower bound on that choice.Source: §3.2 · pp. 10–11

4 Complexity Analysis of Approximating RPOT

This section establishes the smoothness and strong convexity of the penalized RPOT objective, then uses the resulting solver and rounding guarantees to bound approximation error and iteration complexity.

4 Complexity Analysis of Approximating RPOT

  • The section organizes solution notation and error terms to describe how solving P-RPOT approximates the original POT and RPOT objectives.It proceeds from the P-RPOT properties to the gradient method and then its iteration-complexity analysis.Source: §4 · p. 12

4.1 Smoothness and Convexity of P-RPOT

  • The penalized objective is ηµ-strongly convex and β-smooth, with β = ηL + 4αn, supporting the gradient-based convergence analysis.The section uses the equivalence between RPOT and P-RPOT up to controlled error when α is sufficiently large.Source: §4.1 · pp. 13, 14, 16

4.2 Gradient Method for P-RPOT

  • PNAG-POT applies gradient updates with projection onto the feasible set, then ROUND-POT rounding to ensure feasibility.The cited projection has O(n^2 log(n)) complexity, and rounding has O(n^2) complexity.Source: §4.2 · p. 16

4.3 Iteration Complexity of Approximating RPOT

  • For k ≥ K0, the output of Algorithm 3 is an ε−approximate solution to the original POT problem, and the analysis derives a final iteration complexity for achieving that accuracy.Source: §4.3 · pp. 18, 22

5 Experiments

The experiments compare PNAG-POT with CVXPY and APDAGD on color transfer, point-cloud registration, and domain adaptation under quadratic regularization. Across the tasks, PNAG-POT produces sparse plans while reporting lower costs, fewer iterations, or faster runtimes, depending on the comparison.

5 Experiments

  • The benchmarks use color transfer, point-cloud registration, and domain adaptation, comparing PNAG-POT with CVXPY-based QPOT or ENPOT and with APDAGD.Transport mass is fixed at 90% of the smaller total mass, and sparsity thresholds entries below 10^-8.Source: §5 · p. 23

5.1.1 Color Transfer

  • Color transfer transports smoothed, normalized 1,024-bin RGB histograms using squared Euclidean distances between bin centers.The task transfers a source image’s color distribution to emulate a reference image while preserving spatial structure.Source: §5.1.1 · p. 23

5.1.2 Point Cloud Registration

  • Point-cloud registration transports between uniform discrete distributions of 500 points using squared Euclidean distances.The task seeks to align point clouds of unequal size.Source: §5.1.2 · pp. 23–24

5.1.3 Domain Adaptation

  • Domain adaptation uses 300-sample uniform distributions from the moons dataset and evaluates an SVM trained on transported data against the target domain.The cost matrix uses normalized pairwise Euclidean distances.Source: §5.1.3 · p. 24

5.2 Quadratic Regularization

  • APDAGD is compared only on final transport cost and sparsity because its entropically regularized formulation makes its iteration count and runtime incomparable with CVXPY and PNAG-POT.The quadratic-regularization comparison is summarized in Table 3.Source: §5.2 · p. 24, Table 3 · p. 24

5.2.3 Domain Adaptation

  • PNAG-POT matches CVXPY’s 0.036 final cost, raises sparsity from 0.4532 to 0.9180, and cuts iterations from 8,500 to 1,420.Runtime falls from 210.09 to 8.12 seconds; adaptation accuracy is 78.33%, versus 76.41% for CVXPY and 78.12% for APDAGD.Source: Table 3 · p. 24, §5.2.3 · pp. 26–27, Figure 6 · p. 27

5.2.1 Color Transfer

  • PNAG-POT reaches a 0.027 final cost and 0.9958 sparsity in color transfer, requiring 1,800 iterations versus 50,000 for CVXPY.Compared with APDAGD, it also achieves a substantially lower final cost and a slightly sparser plan.Source: Table 3 · p. 24, §5.2.1 · pp. 24–25, Figure 2 · p. 25

5.2.2 Point Cloud Registration

  • For point-cloud registration, PNAG-POT attains a 0.0084 final cost and 0.9229 sparsity, requiring 2,940 iterations versus 11,650 for CVXPY.Runtime falls from 820.14 to 198.12 seconds; compared with APDAGD, the plan is lower-cost and sparser.Source: Table 3 · p. 24, §5.2.2 · p. 25, Figure 4 · p. 26

5.3 Elastic-Net Regularization

The Elastic-Net experiments test whether the optimization framework extends beyond quadratic regularization. Across three tasks, PNAG-POT produces comparable or lower costs, sparser plans, and requires fewer iterations than CVXPY.

5.3 Elastic-Net Regularization

  • Across color transfer, point-cloud registration, and domain adaptation, PNAG-POT obtains comparable or lower final costs while producing sparser plans and requiring fewer iterations.The reported behavior is consistent with the quadratic-regularization experiments.Source: §5.3 · p. 27, Table 4 · p. 27
  • For domain adaptation, PNAG-POT reaches 78.33% accuracy, compared with 76.42% for CVXPY and 78.12% for APDAGD.It also matches CVXPY’s final cost while producing a substantially sparser plan and requiring considerably fewer iterations.Source: §5.3 · p. 28, Figure 7 · p. 28
  • The Elastic-Net color-transfer and point-cloud results, along with transport-plan visualizations for all three tasks, are reported in Appendix E.Source: §5.3 · p. 28

6 Conclusions

The paper presents P-RPOT and PNAG-POT for sparse, regularized partial transport. It reports benchmarking across three machine-learning applications and suggests possible extensions beyond POT.

6 Conclusions

  • P-RPOT uses an exterior quadratic penalty on marginal constraints, and PNAG-POT is a dedicated first-order solver for smooth, strongly convex regularizers including quadratic and Elastic-Net regularization.The method seeks an approximate solution that can be rounded to a feasible plan with cost within ε of the original optimum.Source: §6 · p. 28
  • The authors suggest that the framework could extend to Unbalanced Optimal Transport or other constrained optimization problems.They describe possible downstream applications in machine learning, not demonstrated outcomes.Source: §6 · pp. 28–29

A Guarantees for the quadratic exterior penalty [45]

The appendix states conditions and a guarantee for the quadratic exterior penalty. Its argument draws on results that rely on a saddle point and a strictly feasible point.

A Guarantees for the quadratic exterior penalty [45]

  • The penalty threshold argument assumes a saddle point and uses a strictly feasible point to establish the required bound.The passage identifies Slater’s condition as a condition under which the saddle point exists.Source: A Guarantees for the quadratic… · p. 30
  • Under the stated saddle-point and penalty-threshold conditions, every minimizer of the penalized objective satisfies each constraint to within τ.The appendix expresses this as gi(X⋆) ≥ −τ for every constraint i.Source: A Guarantees for the quadratic… · p. 30
  • The cited proof technique depends on the saddle-point inequality and a strictly feasible point, not on the specific penalty form.The appendix notes that the analysis can be applied with the feasible set S in place of the ambient space.Source: A Guarantees for the quadratic… · p. 30

B Algorithm: Projection of a matrix on to S

The algorithm projects a matrix onto S via the probability simplex, then reshapes the projected vector back into an n-by-n matrix.

C Guarantees for ROUND-POT [24, Theorem 6]

The stated ROUND-POT guarantee gives an exact feasible nonnegative vector near an approximately feasible nonnegative input, with a linear-time-in-n-squared bound [24, Theorem 6].

D Proof of Lemma 4.4

The proof derives a bound for constraint violations and then combines inequalities (54) and (55), using a result established in (52).

E Additional Results for Elastic-Net Regularization

These additional Elastic-Net results cover color transfer, point cloud registration, and domain adaptation, with transport-plan visualizations across the tasks.

E Additional Results for Elastic-Net Regularization

E.2 Point Cloud Registration

E Additional Results for Elastic-Net Regularization

Loading 2609.40075v1…