PaperlayerView exact revision on arXiv

Source-linked AI summary

A Unified Dual Method for Matching Problems

Guillaume Houry, Ferdinand Genans, Jean Feydy, François-Xavier Vialard

arXiv:2609.39339v1cs.CGstat.ML

TL;DR

Matching is difficult to solve at scale, and existing solvers are often tailored to particular formulations. The paper develops a duality-based framework for a broad class of matching problems, with convergence guarantees for regularized quadratic matching and applications to GW variants and fracture matching.

  • Problem

    Matching objectives can be non-convex and require optimization over large plans, while existing methods lack a general approach for arbitrary matching problems.

    Source: §1 · p. 1, §2 · p. 3

  • Method

    The framework uses DC decompositions and duality to recast matching as implicit registration and, for quadratic matching, as a sequence of optimal-transport computations.

    Source: §1 · p. 2, §2 · pp. 3–4

  • Results

    The framework establishes convergence guarantees for a broad class of regularized quadratic problems and encompasses Gromov–Wasserstein variants and fracture matching.

    Source: §6 · p. 10

  • Takeaways & Limitations

    The framework can be adapted to new models such as fracture matching without designing a solver from scratch.

    Source: §6 · p. 10

    The general matching result assumes a DC objective; exact DC decompositions are guaranteed in the finite case.

    Source: §2 · p. 3

Abstract

from arXiv · show

Matching problems are ubiquitous in data science as they enable the alignment of structured objects and distributions. While existing solvers are often tailored to specific matching formulations, we unify a broad class of such problems within a common mathematical and optimization framework based on duality theory. Theoretically, we demonstrate that matching objectives decomposable as a difference of convex (DC) functions can be recast as implicit registration problems. This connection links matching to another well-studied class of objectives and yields a dual formulation amenable to natural optimization strategies. We then apply these findings to quadratic matching (QM) problems, which admit DC decompositions and for which we provide extensive convergence guarantees. Our framework applies to Gromov-Wasserstein (GW), as well as its unbalanced formulation and several variants, which are increasingly popular QM problems. Numerically, we implement our algorithms at scale for various data modalities such as graphs, point clouds, meshes, and word embeddings. Finally, our modular approach allows us to explore new formulations such as fracture matching, broadening the scope of problems that can be addressed within this framework..

1 INTRODUCTION

Matching offers flexible pointwise correspondences across data modalities, but it is harder to solve efficiently than registration. The paper proposes a duality-based framework to address the scalability and generality limits of existing quadratic-matching solvers.

1 INTRODUCTION

  • Matching provides flexible pointwise correspondences across modalities, while registration produces more regular outputs but is less flexible and not suitable for every modality.Efficient solvers for arbitrary matching problems remain a bottleneck for downstream applications.Source: §1 · p. 1
  • Quadratic matching includes quadratic assignment, Gromov–Wasserstein, graph matching, and quadratic-form optimal transport, with custom instances also used for shape matching.The cited examples are quadratic assignment, Gromov–Wasserstein (M´emoli, 2011), graph matching, quadratic-form optimal transport, and custom shape matching.Source: §1 · p. 1
  • Quadratic matching is non-convex and NP-hard to minimize globally, while explicit matching matrices constrain the scalability of local first-order methods.Duality-based reductions to linear matching or optimal transport can avoid explicit matrices, but prior approaches lack generality for arbitrary QM problems.Source: §1 · p. 2
  • The proposed framework links matching to registration, reduces arbitrary matching problems to sequences of optimal-transport computations, and specializes the approach to quadratic matching with convergence guarantees.The authors also describe an optimized, backend-agnostic modular implementation that can be extended to other regularized quadratic problems.Source: §1 · p. 2

2 MEASURE MATCHING AS AN IMPLICIT REGISTRATION PROBLEM

The section formulates matching over measures and shows how difference-of-convex objectives yield an implicit-registration formulation. A dual approach can avoid explicit plan optimization by reducing the problem to regularized optimal-transport computations.

2 MEASURE MATCHING AS AN IMPLICIT REGISTRATION PROBLEM

  • Matching plans are measures on the product space, with one-to-one matching represented by a bijection graph or, in finite settings, a permutation matrix.Plans also allow relaxed correspondences in which points can send mass to, or receive mass from, multiple points.Source: §2 · p. 3
  • Under the stated regularity conditions, a difference-of-convex matching objective is equivalent to a formulation with convex functions R and S, and compact Euclidean inputs admit a Hilbert-embedding representation.The DC structure isolates the concave part of the objective; the text states that any matching problem is approximable by a DC one and finite problems admit exact decompositions.Source: §2 · p. 3
  • The resulting structure matches registration formulations, whose non-convexity is isolated in an outer optimization and whose transformations depend on global input geometry.The passage describes registration transformations as intrinsically robust to empirical noise, point resampling, or permutations, motivating transfer of registration tools to matching.Source: §2 · p. 4
  • Alternating optimization over transformations and plans is possible, but still requires explicit plan optimization, motivating a dual formulation that avoids manipulating plans directly.The dual strategy adapts duality results for DC functions to handle arbitrary regularizations on the plan.Source: §2 · p. 4
  • When efficient regularized optimal-transport solvers are available, the dual result supplies a strategy for solving the original matching problem through those computations.The reformulation shifts difficulty into the embedding functions and makes the problem structure agnostic to the matching objective.Source: §2 · p. 4

3 AN EXPLICIT DUAL FOR REGULARIZED QUADRATIC MATCHING

For quadratic matching, explicit kernel decompositions make the dual framework computationally usable. Additional block-separability conditions recover a registration-like form, while low-rank structure can yield lower-dimensional optimization.

3 AN EXPLICIT DUAL FOR REGULARIZED QUADRATIC MATCHING

  • Quadratic matching uses a symmetric kernel, and explicit DC decompositions in finite and certain continuous settings define the factorizable-kernel case.The decomposition is expressed through integral operators A and B.Source: §3 · p. 5
  • For factorizable kernels, the paper adapts its earlier dual formulas to regularized quadratic matching.This result is stated under the factorizability hypothesis.Source: §3 · p. 5
  • A registration-like form additionally requires B to be block-separable, meaning its squared norm decomposes as a sum over separable components.The resulting formulation uses embeddings and a compact subspace.Source: §3 · p. 5
  • With both operators block-separable, explicit embeddings make the effective cost a scalar product, and low-rank operators can make optimization low-dimensional.For GW kernels, the paper describes direct block-embedding computations that avoid diagonalizing the entire kernel, supporting tractability on large inputs.Source: §3 · p. 5

4 NUMERICAL OPTIMIZATION OF THE RQM DUAL

The RQM solver alternates among Γ, Ξ, and a primal or dual ROT block, with convergence guarantees under stated smoothness and inner-loop conditions. Entropic unbalanced GW provides a practical Sinkhorn-based case, while block-separable structure supports modular OT backends.

Block updates

  • The algorithm alternates ROT solves over ϕ or π, gradient ascent updates for Ξ, and a closed-form Γ update.The Γ update sets Γ = B[π].Source: §4 · p. 6

Convergence guarantees

  • The solver terminates in O(δ^-2) outer iterations when inner loops converge; with hΓ L-smooth, total ROT work is eO(Lδ^-2).The stated step size is τ = 1/L and ROT accuracy is δROT = Θ(δ^2/L^2).Source: §4 · p. 6

Output plans

  • When δROT ≤ δ^2/4 and inner loops converge, the algorithm outputs a δ-critical plan, not a guaranteed global minimizer.The paper characterizes the output as almost critical because RQM is non-convex.Source: §4 · p. 6

Entropic unbalanced GW

  • For entropic regularization, Sinkhorn supports dual, memory-saving ROT solves; its linear convergence yields eO((ρ + ε)/(δ2ε2)) single iterations.The entropic case makes hΓ L-smooth with L = 1 + O(ε^-1); Nesterov acceleration can save a factor ε^-1/2 in end-to-end complexity.Source: §4 · pp. 6–7

Warm starts and early stopping

  • Warm starts and even one Sinkhorn update per ϕ-block remain stable empirically in the entropic case, avoiding a full ROT solve before each Ξ update.These stopping practices are described as practical accelerations beyond the conservative theoretical criteria.Source: §4 · p. 7

Efficient implementation

  • Block-separable embeddings make the implementation modular and compatible with available ROT backends, with GPU, memory, multiscaling, and dimensionality-reduction options.The cost is an inner product supported by most OT libraries.Source: §4 · p. 7, Figure 1 · p. 7

5 APPLICATIONS

The same numerical routine is applied across graph, word-embedding, shape, point-cloud, and fracture-matching tasks, with changes only to feature embeddings and the selected term R. The experiments report fast or large-scale matching across these settings.

Applications

  • One numerical routine handles applications across data types, with changes only to feature embeddings and the selected term R.The applications include graphs, word embeddings, meshes, point clouds, and fractured objects.Source: §5 · pp. 8–9

Graph matching

  • Figure 2 compares speed and accuracy; our method reaches excellent accuracy at D = 10 and robustly matches graphs with tens of thousands of nodes in seconds.The low-rank solver trades matching quality for speed, while EGW remains competitive in this setting despite lacking theoretical convergence guarantees.Source: Figure 2 · p. 8, §5 · p. 8

Word embedding alignment

  • Almost 20× faster than the baseline, our solver achieves comparable total precision when aligning MUSE word vocabularies.The experiment aligns the 20k most frequent words across languages; Nyström methods further trade precision for running time.Source: §5 · p. 8

Semi-balanced shape matching

  • Minutes-long convergence accurately preserves texture when semi-balanced GW matches a source mesh to partial targets.Semi-balancedness matches the whole partial shapes to the source while ignoring full-mesh vertices corresponding to target holes.Source: Figure 3 · p. 9, §5 · p. 9

Fused matching of 3D point clouds

  • About 30 min suffices to produce qualitatively satisfying fused unbalanced GW matches between room scans containing 100k–200k points.RGB colors provide additional linear features for matching scans of the same room.Source: Figure 4 · p. 9, §5 · p. 9

Fracture reconstruction

  • 100k–200k-vertex fracture reconstructions take several hours, and the selected output is the best result over dozens of initializations.The cluster-aware GW variant is invariant to isometries of individual fragments; multiscaling reduces computational burden.Source: Figure 5 · p. 9, §5 · p. 9

6 CONCLUSION

The framework unifies matching methods, including GW variants, and supports new formulations such as fracture matching. In baseline comparisons, it converges where EGW oscillates and produces accurate unbalanced GW solutions on the tested input size.

6 CONCLUSION

  • The framework brings matching formulations under a common, duality-based foundation rather than requiring a dedicated solver for each one.It encompasses GW and fused and unbalanced entropic variants.Source: §6 · pp. 9–10
  • For a broad class of regularized quadratic problems, the paper establishes convergence rates and uses fracture matching to illustrate exploring new formulations without designing a solver from scratch.The authors suggest generic solvers can facilitate rapid prototyping and testing.Source: §6 · p. 10

A.1 OTHER BASELINE COMPARISONS

  • On shortest-path graph costs and 2D point clouds with p > 2, our solver reaches the correct minimum while EGW oscillates between transport plans; Figures 6 and 7 show the iterations.The authors describe these as typical GW inputs, not pathological examples; their solver also breaks symmetry in the graph example and reaches a global minimum.Source: §A.1 · pp. 13–14, Figure 6 · p. 14, Figure 7 · p. 14
  • For partial shape matching, the low-rank unbalanced solver produces quantization artifacts and balanced EGW shows large distortion, while the authors report accurate unbalanced GW solutions at this input size in reasonable time.Figure 8 shows the low-rank unbalanced solver above and balanced EGW below.Source: §A.1 · p. 14, Figure 8 · p. 15

A.2 EXPERIMENTAL SETUP

The appendix records experimental configurations for the paper’s matching applications and supplies additional mathematical ingredients. These include examples of regularizers and their duals, alongside results on DC decompositions and GW formulations.

A.2 EXPERIMENTAL SETUP

  • Experiments use PyTorch on an RTX6000 GPU, with KeOps or FlashSinkhorn for dimension-reduction OT operations; application-specific costs, weights, and initialization strategies vary across shape, point-cloud, graph, and word-alignment tasks.For example, graph matching uses shortest-path distances and adds 20% noisy edges to target graphs; word-alignment precision counts valid dictionary translations after CSLS matching.Source: §A.2 · pp. 16–17

B ADDITIONAL RESULTS

  • The additional-results appendix supplies examples of matching regularizers and their duals, and establishes conditions for DC decompositions and factorizations of quadratic objectives.Its following sections treat block-separable dual theorems and explicit GW decompositions.Source: B ADDITIONAL RESULTS · p. 17

B.1 CLASSICAL CHOICES OF R

  • The classical regularizer examples include optimal transport couplings, closest-point matching, and marginal penalization with entropic or KL-divergence regularization.In unbalanced matching, the generalized KL terms avoid biasing objectives toward zero-mass plans.Source: §B.1 · p. 18, B ADDITIONAL RESULTS · p. 18

B.2 GENERAL DC DECOMPOSITION OF MATCHING PROBLEMS

This appendix establishes DC decomposition results and develops the block-wise factorizations used to formulate GW problems for the solver. It also explains how the framework extends to arbitrary finite costs and weighted kernels.

B.2 GENERAL DC DECOMPOSITION OF MATCHING PROBLEMS

  • On compact domains, continuous matching objectives can be approximated to any precision by a difference of convex functions, and finite C2 objectives admit exact DC decompositions.The approximation result assumes weak-* continuity and growth to infinity, with a bounded convex set containing the objective’s minima.Source: §B.2 · p. 19
  • With entropic regularization and compactly supported measures, a continuous quadratic kernel admits a DC factorization through linear operators on the L2 space of plan densities.The paper notes that its duality results can be adapted to this L2 setting.Source: §B.2 · p. 20

B.3 DETAIL OF THE BLOCK-SEPARABLE CASE

  • For block-separable operators, the appendix constructs concatenated embeddings and block-wise transforms that restrict optimization to a small fraction of all linear operators.This formalism supports efficient numerical implementations.Source: §B.3 · pp. 20–22

B.4 EXPLICIT DECOMPOSITIONS OF GROMOV-WASSERSTEIN KERNELS

  • GW kernels based on scalar products or squared norms admit explicit block-separable factorizations, and finite GW instances can fit this structure after diagonalizing their costs.For finite inputs, diagonalizing the costs is described as tractable compared with diagonalizing the full kernel.Source: §B.4 · pp. 22–23, §1 · p. 24

1. The cost c is CNT,

  • For CNT costs, Hilbert-space embeddings represent costs as squared distances; finite inputs can use cost-matrix diagonalization to obtain embeddings, with approximation techniques available to reduce their dimension.Tree, hyperbolic geodesic, spherical, and non-squared Euclidean distances are listed as CNT examples.Source: §B.4 · p. 23, §1 · p. 24
  • For finite spaces, arbitrary costs can be expressed as differences of scalar products, enabling the GW factorization; weighted kernels also model affinity-based matching penalties, including fracture matching.In the fracture example, the weights encode fragment membership on the fractured input.Source: §1 · p. 24

C DETAILED IMPLEMENTATION

  • The implementation section focuses on discrete inputs and Euclidean operator spaces, where finite-dimensional plans and operator images support the solver’s practical computations.It assumes measures with N and M points and Euclidean Hilbert spaces for the operators.Source: C DETAILED IMPLEMENTATION · pp. 24–25

C.1 FAST IMPLEMENTATION OF BLOCK UPDATES

The appendix develops block-aware implementations and acceleration strategies for the solver, then describes initialization choices and their empirical boundary. These choices address computational scale and sensitivity to starting potentials.

C.1 FAST IMPLEMENTATION OF BLOCK UPDATES

  • Cross-correlations can be computed through transport integrals, with the inner integral performed on the lower-dimensional embedding.With linear-memory OT backends, the stated time complexity is O(NM min(D, E) + (N + M)DE), and memory is O(ND + ME).Source: §C.1 · p. 25
  • Splitting potentials across both embeddings reduces effective-vector dimensions and thus the per-iteration cost of Sinkhorn.Each Sinkhorn iteration scales linearly with the effective-vector dimension.Source: §C.1 · pp. 26–27
  • Block-separable updates avoid the quadratic dependency on embedding dimension found in naive implementations.The separable solver uses standard matrix-vector operations and a black-box Sink solver; block-separable computations follow a similar structure.Source: §C.1 · pp. 26–27

C.2 ADVANCED IMPLEMENTATION TECHNIQUES

  • Factoring embeddings as tuples instead of explicitly storing tensor products reduces memory from N dim(f) dim(g) to N(dim(f)+dim(g)).For the stated Euclidean Gromov-Wasserstein cases, these techniques make implementation scale linearly in input dimension.Source: §C.2 · p. 27
  • Coarse-to-fine multiscaling initializes the fine problem from coarse potentials and substantially reduces iterations to convergence.Coarse inputs may be formed by subsampling, k-means, or a predefined subset; coarse plans also support sparsity masks for fine-scale solving.Source: §C.2 · p. 28

C.3 INITIALIZATION OF POTENTIALS

  • Initialization can use a trivial plan, known landmarks, or random potential samples, but the trivial choice is poorly suited to unbalanced or challenging symmetric cases.The trivial initialization generally gives satisfying results in balanced settings and does not bias the optimization trajectory.Source: §C.3 · pp. 28–29

D.1 PROOFS OF SECTION 2

These proofs establish the paper’s general reformulations through convex duality and embedding arguments. They connect DC matching objectives to registration-style forms and give dual representations under stated convexity and compactness conditions.

D.1 PROOFS OF SECTION 2

  • When the objective has the stated DC structure, Theorem 1 proves an equivalent reformulation, with convexity of the transformed regularizer following from a linear change of variables.The proof constructs Hilbert-space embeddings and a Hilbert-Schmidt transform for the decomposition.Source: §D.1 · pp. 29–30
  • The proof identifies the dual representation using convex conjugacy and density of separable polynomial functions on compact Euclidean domains.The argument uses Stone–Weierstrass density and continuity of the convex conjugate for uniform convergence.Source: §D.1 · p. 29
  • For proper lower semi-continuous convex R, Theorem 2 derives a dual formulation of matching; compact Euclidean domains additionally yield continuous Hilbert embeddings and an effective cost.The proof applies Rockafellar–Fenchel duality under its continuity and finite-value hypotheses.Source: §D.1 · pp. 30–31

D.2 PROOFS OF SECTION 3

These proofs establish the quadratic-matching identities by applying the general duality results to quadratic operators. They also state the resulting embedding and effective-cost forms for block-separable operators.

D.2 PROOFS OF SECTION 3

  • The quadratic conjugate’s supremum is attained only when c = A⊤A[π]; otherwise the supremum is +∞.This follows from setting the derivative of the quadratic objective to zero.Source: §D.2 · p. 31
  • Theorem 3 obtains the quadratic identity by applying the general reformulation to a quadratic case and its convex conjugate.The proof changes variables through the operator image and identifies the adjoint action with an inner product against the kernel.Source: §D.2 · pp. 31–32
  • For block-separable operators, Theorems 4 and 7 provide embedding-based equivalent forms, including a scalar-product effective cost when both operators are block-separable.The proof derives the separable identity from the operator representation and extends it using Theorem 3.Source: §D.2 · p. 32

D.3 PROOFS OF THE APPENDIX

The appendix supplies existence and approximation results, specifies the solver’s notation and assumptions, and proves the fixed-potential certificate used for stopping. Together, these results formalize approximation conditions and the algorithm’s certificate-based analysis.

D.3 PROOFS OF THE APPENDIX

  • On a bounded convex set containing the minima, a continuous objective can be approximated to any precision by a difference of continuous convex functions.The proof uses density of DC functions in continuous functions on a weak-* compact set.Source: §D.3 · p. 33
  • With an entropic regularizer, continuous kernel, and compactly supported marginals, Proposition 2 represents the objective using two linear operators.The resulting form is a difference of squared operator norms plus the regularizer.Source: §D.3 · p. 34

E.1 NOTATION AND SETTING

  • The appendix’s standing assumptions require R to be proper, convex, and lower semicontinuous, with a finite value somewhere, and the RQM objective bounded below.Under these assumptions, the outer objective Λ is finite everywhere.Source: §E.1 · p. 36
  • A δROT-accurate plan yields a computable certificate that bounds the fixed-Γ inner subproblem’s optimality gap.The certificate is tested by the inner stopping rule; for hard marginal constraints, the recovered plan must first be rounded onto the constraint set.Source: §E.1 · p. 36, §E.2 · p. 36
  • The inner loop updates Ξ using the discrepancy A[bπ] − Ξ, and terminates when the outer change in Γ is at most δ.For the entropic regularizers described, this Ξ update is an inexact gradient step.Source: §E.1 · p. 36

E.3 OUTER CONVERGENCE: PROOF OF THEOREM 5(I)

The Γ-update majorizes the original energy and is a majorization–minimization (equivalently, DC) step. Under the stated conditions, the outer algorithm reaches an approximately critical plan after a finite number of outer iterations, provided its inner loops terminate.

E.3 OUTER CONVERGENCE: PROOF OF THEOREM 5(I)

  • The Γ-update majorizes the original energy with equality at Γ = B[π], making it a majorization–minimization (equivalently, DC) step.Its fixed points are DC-critical plans.Source: §E.3 · p. 37
  • A plan is (δ, η)-critical exactly when it is an η-minimizer of the convex function π ↦ Q_B[π̂](π) + δ ∥B[π − π̂]∥.For (δ, η) = (0, 0), this is DC criticality.Source: §E.3 · p. 37
  • Theorem 12 guarantees that the stopping test is met before Tδ, assuming every inner loop terminates.The theorem permits any ROT solver, step size, and accuracy satisfying that termination condition.Source: §E.3 · p. 38
  • When the stopping test is met before Tδ, the returned plan is (δ, δ²/4)-critical.The bound on the Γ-step makes it (δ′, δ²/4)-critical for some δ′ ≤ δ, which implies the stated tolerance.Source: §E.3 · p. 38
  • Theorem 12’s guarantee is conditional on inner-loop termination; a smoothness condition in Corollary 1 guarantees termination with an explicit bound on Kt.Termination is also observed at run time.Source: §E.3 · p. 38

E.4 INNER-LOOP COMPLEXITY: PROOF OF THEOREM 5(II)

The inner-loop analysis establishes geometric convergence and certificate-based stopping under smoothness assumptions. It also shows that acceleration preserves the usual condition-number dependence up to logarithmic factors when the ROT oracle converges geometrically.

E.4 INNER-LOOP COMPLEXITY: PROOF OF THEOREM 5(II)

  • The local smoothness form used in practice requires bounded iterates and a twice-differentiable reduced objective on a specified ball.The stated local condition includes δROT ≤ 1/2.Source: §E.4 · p. 39
  • A δROT-accurate ROT plan bounds the inner-loop gradient error by √(2LδROT).For δROT = 0, the gradient error is zero.Source: §E.4 · p. 40
  • With step τ = 1/L, the inner loop converges geometrically and reaches certificate level η after at most NΞ(η) + 1 ROT solves.The result assumes (S1)–(S2) and (HL) at Γ.Source: §E.4 · pp. 40, 42
  • Under the shared smoothness assumptions, Corollary 1 bounds the total ROT solves by the outer-iteration count times the per-loop bound NΞ(δ²/4) + 1.Each inner loop terminates by the certificate threshold, so Theorem 12 applies.Source: §E.4 · p. 43

E.5 ACCELERATED VERSIONS.

  • When the ROT oracle converges geometrically, accelerated inexact-gradient optimization preserves the usual accelerated dependence on the condition number up to logarithmic factors.The increased oracle accuracy changes each call’s cost only logarithmically.Source: §E.5 · p. 44

F ENTROPIC UNBALANCED GROMOV–WASSERSTEIN: PROOF OF THEOREM 13

For entropically regularized unbalanced Gromov–Wasserstein, the analysis establishes regularity of the reduced objective and uses generalized Sinkhorn as the UOT solver. Under the stated bounds, the algorithm obtains a critical plan in finite time, while geometric Sinkhorn convergence also permits an accelerated variant.

F ENTROPIC UNBALANCED GROMOV–WASSERSTEIN: PROOF OF THEOREM 13

  • The reduced UGW objective is finite, twice continuously differentiable, and 1-strongly concave under the proposition’s stated conditions.The proposition also bounds its Hessian on {∥Ξ∥ ≤ R}.Source: F ENTROPIC UNBALANCED… · p. 45
  • For fixed positive marginal penalties and uniformly bounded R and ∥Γ∥, the mass bound avoids exponential deterioration in 1/ε and gives Lh = O(ε⁻¹) as ε ↓ 0.The mass bound contains an exponential term rather than exp(C/ε).Source: F ENTROPIC UNBALANCED… · p. 46
  • With equal marginal penalties ρ, each generalized Sinkhorn half-step contracts the distance to the optimal potentials by ρ/(ρ + ε).The result holds for any current potentials.Source: F ENTROPIC UNBALANCED… · p. 46
  • Under the theorem’s assumptions, algorithm 1 terminates within Tδ outer iterations with a (δ, δ²/4)-critical plan.Each inner loop terminates within NΞ iterations when UOT subproblems are solved by Sinkhorn within the assumed iteration bound.Source: F ENTROPIC UNBALANCED… · p. 48
  • Geometric Sinkhorn convergence permits accelerated Ξ-updates, and the smaller UOT accuracy changes call cost only logarithmically.The stated accelerated scheme can save a factor ε⁻¹/² in end-to-end complexity under its conditions.Source: F ENTROPIC UNBALANCED… · pp. 49–50
Loading 2609.39339v1…