Technical Summary: Sinkhorn Linearization and the Spectral Proxy

1. Problem Statement

This paper addresses the Inverse Optimal Transport (IOT) problem under a feature-parameterized cost setting, $C_\theta(i, j) = -\theta^\top \phi(i, j)$. Unlike classical IOT formulations that often assume explicit or low-dimensional costs, this work focuses on recovering the sparse cost parameter $\theta$ from observed conditional transition operators (state-transition data) induced by an entropic optimal transport (OT) plan.

The core challenge lies in the non-linear, high-dimensional relationship between the cost parameters and the observed transport plans, complicated by:

• Gauge Degeneracy: The OT plan is invariant under the addition of row and column constants to the cost (the gauge subspace $G$), leading to non-identifiability of $\theta$ in the original parameter space.
• Statistical Inference: Recovering $\theta$ from finite samples of transition operators requires establishing identifiability, sparsity recovery rates, stability, and convergence guarantees.
• Misspecification: Real-world data may not strictly follow the OT model, necessitating an analysis of where the estimator converges when the true data-generating mechanism departs from the OT assumption.

2. Methodology and Core Technical Contributions

The paper's central technical innovation is the Sinkhorn Linearization and its associated Spectral Proxy.

Sinkhorn Linearization

By applying implicit differentiation to the Karush-Kuhn-Tucker (KKT) conditions of the entropic OT problem, the authors derive the exact linear response of the transport plan $\pi$ to perturbations in the cost $C$. The relationship is given by:
$$\delta x = -B H_T^{-1} B^\top \delta c$$
where $x = \text{vec}(\pi)$, $c = \text{vec}(C)$, $B$ is an orthonormal basis for the tangent space of the transport polytope, and $H_T$ is the restricted Hessian of the entropic objective on the tangent space.

The Spectral Sandwich and Proxy

A critical lemma establishes a spectral sandwich for the inverse of the restricted Hessian:
$$\frac{\pi_{\min}}{\varepsilon} I \preceq H_T^{-1} \preceq \frac{\pi_{\max}}{\varepsilon} I$$
where $\pi_{\min}$ and $\pi_{\max}$ are the minimum and maximum entries of the entropic plan, and $\varepsilon$ is the regularization parameter.

To provide geometric transparency and computational efficiency, the authors introduce the Spectral Proxy (SSP):
$$\delta x_{SSP} = -\frac{1}{\varepsilon} P_T D_\pi P_T \delta c$$
This formula (project to tangent space $\to$ elementwise multiply by $\pi$ $\to$ project back) is not elementwise equal to the exact derivative but is spectrally exact, preserving the same upper and lower singular value bounds as the exact linearization. This allows all subsequent statistical bounds to be derived using the simpler proxy.

The Core Spectral Bound

Combining the spectral sandwich with the feature-parameterized cost structure yields the core spectral bound that drives the entire theory:
$$\sigma_{\min}(J_\theta) \geq \frac{\pi_{\min}}{a_{\max} \varepsilon} \sqrt{\lambda_{\min}(\Sigma)}$$
where $J_\theta$ is the Jacobian of the transition operator with respect to $\theta$, $a_{\max}$ is the maximum marginal mass, and $\Sigma$ is the gauge-cleaned Gram matrix of the feature vectors.

3. Key Theoretical Results

The paper establishes four theorems and one observation, all radiating from the core spectral bound.

T1: Identifiability

• Result: The parameter $\theta$ is globally identifiable on the quotient space $F / N_\Phi$ (where $N_\Phi$ is the gauge kernel), provided the feature dimension satisfies $F \leq (K-1)^2$ and the rank condition $\text{rank}(\Sigma) = F$ holds.
• Mechanism: Identifiability is proved via a three-step composition argument: (1) linear parameterization is injective modulo gauge; (2) the Sinkhorn map is injective modulo gauge (due to strict convexity of the dual); (3) the normalization to conditional operators is linear and injective.
• Note: Identifiability of the scale coupling $(\theta, \varepsilon) \to (c\theta, c\varepsilon)$ is resolved by fixing $\varepsilon$ or imposing a normalization constraint.

T2: Sparsistency

• Result: The $\ell_1$-penalized estimator recovers the true support of $\theta$ with exponentially decaying failure probability.
• Conditions: Requires the irrepresentability condition on the actual OT information matrix, all-coordinate score concentration, and a global selection condition.
• Rate: The failure probability decays as $\exp(-C_2 n t_n^2)$, where $C_2 = 2/\Delta_{\max}^2$ and $\Delta_{\max}$ is the range of the per-sample score derived from the spectral proxy.

T3: Well-Posedness and Stability

• Result: The inverse map from the observed operator to the cost parameter is strongly monotone and Lipschitz continuous.
• Local vs. Global:
  • Local: Strong monotonicity holds on any compact convex subset without requiring global compactness.
  • Global: Requires the parameter domain to be compact to ensure a uniform lower bound on $\pi_{\min}$.
• Lipschitz Bound: The inverse map has a Lipschitz constant $L \leq \frac{\varepsilon \|\Phi^\top S_a\|_{op}}{\pi_{\min} \lambda_{\min}(\Sigma)}$.
• Bias: If the estimator uses a regularization level $\varepsilon' \neq \varepsilon$, the bias is $O(|\varepsilon' - \varepsilon|)$.

T4: Convergence

• Result: The population cross-entropy objective is locally strongly convex around the true parameter $\theta^*$.
• Convergence: Gradient descent with a sufficiently small step size converges monotonically to a local minimum.
• Curvature: The Hessian at the truth is positive definite with a lower bound $\mu \geq \frac{\pi_{\min}^2 \lambda_{\min}(\Sigma)}{\varepsilon^2}$. The empirical Hessian concentrates at the population Hessian at rate $O(n^{-1/2})$.

O5: Misspecification Analysis

• Result: Under model misspecification (data not generated by OT), the estimator converges to the projection of the true operator onto the OT model set.
• Conjecture: The Hölder continuity of this projection map is conjectured but not proven; numerical experiments suggest an empirical effective exponent $\alpha_{eff} \in (0, 1)$.

4. Experimental Verification

The authors provide extensive numerical verification (Experiments E1–E10) supporting the theoretical claims:

• Identifiability (T1): Confirms that rank is independent of the number of marginals but degrades as $\varepsilon \to 0$ due to $\pi_{\min} \to 0$. Pure gauge features are shown to be unidentifiable.
• Sparsistency (T2): Demonstrates phase transitions in support recovery probability and validates the exponential decay rate. It notes that while the irrepresentability condition is sufficient, it is not strictly necessary in practice for unstructured features.
• Well-Posedness (T3): Validates the Lipschitz constant predictions and observes a "V-shape" in the bias function when $\varepsilon'$ varies, confirming the local minimality at the true $\varepsilon$.
• Convergence (T4): Shows that multiscale initialization significantly improves convergence success rates compared to random initialization, aligning with the existence of local basins of attraction.
• Misspecification (O5): Shows that under non-OT generation, the estimator projects to a pseudo-true point, and the projection map exhibits a setting-dependent Hölder exponent.
• Scaling Laws: Experiments reveal that $\pi_{\min}$ decays exponentially as $\varepsilon \to 0$, contradicting any uniform polynomial lower bound and highlighting the ill-conditioning of IOT in the low-regularization regime.

5. Significance and Claims

The paper claims to unify the statistical and algorithmic theory of feature-parameterized IOT through a single spectral framework. Its significance lies in:

1. Reducing Complexity: Deriving complex statistical properties (identifiability, sparsity rates, stability, convergence) from a single core spectral bound derived from the Sinkhorn linearization.
2. Explicit Constants: Providing computable constants for key theoretical quantities, such as the feature-dimension bound $F \leq (K-1)^2$, the exponential rate constant for sparse recovery, and the Lipschitz constant for the inverse map.
3. Geometric Transparency: The spectral proxy offers a geometrically intuitive and computationally efficient alternative to the exact linearization for operator-norm analyses.
4. Rigorous Foundations: Moving beyond Bayesian frameworks or heuristic approaches to establish frequentist guarantees (support recovery, consistency) for IOT, explicitly addressing the gauge degeneracy and misspecification issues often overlooked in prior work.

The authors remain modest regarding open problems, acknowledging that global strong monotonicity on unbounded spaces, the proof of Hölder continuity for the projection map, and minimax lower bounds remain unresolved.