nucleation

LIT-1815: Structured Optimal Transport

1 min read

Properties5
StatusActive — read in full 2026-10-29 (NOTE-1324), from arXiv v1; worth reading as a convex way to make a transport cost depend on sets of assignments rather than single ones, and for its limits: the structure is supplied, only submodular interactions are tractable, and its own threshold cost is not submodular.
Version2
Tagsmathematics, anthology-candidate
Cited as “paper” byNOTE-1324 — Alvarez-Melis et al. — Structured optimal transport
Cited as “source” byTHEORY-1138 — Optimal transport whose cost is the Lovász extension of a submodular set function on source–target assignments stays a convex problem, a zero-sum game in which an adversary picks the cost matrix from the function's base polytope, and reduces to ordinary optimal transport exactly when the set function is modular; the convexity needs submodularity, so the paper's own threshold cost, which is not concave at its threshold, falls outside it, and the induced discrepancy is symmetric only when the set function is

Graph View

Alvarez-Melis, D., Jaakkola, T. S., & Jegelka, S. (2018). Structured optimal transport. AISTATS 2018, PMLR 84, 1771–1780.

Why this is here

A6, as exploratory: it would matter if pragmatic force rests on a configuration of cues (speaker role, form of address, a later commitment) and not on each cue alone, which is the ternary-structure worry of QUESTION-283. The test would be behavioural prediction, not expressiveness.

The reading (NOTE-1324) narrows the fit: SOT encodes structure among assignments between two objects, from groups fixed in advance and only of the grouping (submodular) kind; it cannot learn a ternary relation among cue values. A configuration of cues could enter only as a pre-set grouping whose joint mapping is cheaper.

Backlinks