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

arXiv:2606.04695v2 Announce Type: replace 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\'echet 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.

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.

Machine Learning (cs.LG)

arXiv:2606.04695 [cs.LG]

(or arXiv:2606.04695v2 [cs.LG] for this version)

https://doi.org/10.48550/arXiv.2606.04695 Focus to learn more arXiv-issued DOI via DataCite

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.

aiqbench analysis

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

Related coverage