From Cone Geometry to Monge Structure: Local Defects and Global Regret in High-Dimensional Optimal Transport

Abstract

Exact optimal transport in high dimensions becomes tractable only when additional structure selects the optimal coupling. Classical Monge transportation solves the discrete problem once a cost array is known to be Monge, but it does not explain when geometry in the original feature space creates that structure. We characterize this regime for cone-induced orders and squared Mahalanobis costs: Macuteness of the cone is equivalent to the Monge property of every cross-cost matrix generated by two cone chains, after which classical northwest-corner optimality gives exact transport. When the inequalities fail, we derive an exact variational representation of northwestcorner regret over a marginal-dependent cumulative-deficit polytope. Its Fréchet box relaxation yields a projection-free, marginal-weighted localdefect bound; we characterize when the relaxation is exact and prove that it is worst-case sharp when only local defect budgets are known. We further show that the worst-case defect patterns can be realized by genuine squared-Euclidean cross-costs. Finally, Mahalanobis distances of observed increments to the cone control the local defects, while a strict geometric margin gives an explicit radius of exact stability. The resulting theory links high-dimensional ground-space geometry to exact Monge transport and quantifies the global loss induced by local departures from ordered structure.

17 pages, 2 figures, including appendices