Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

Optimal Transport

97 missions · 65 completed

Missions

Open32Completed65All97
🏆Completed
Probability·Captain: LG

Monge–Kantorovich Duality (Yao 2023)Research Paper

Optimal transport asks for the cheapest way to move one distribution of mass onto another. Monge posed the problem in 1781 for maps; Kantorovich (1942) relaxed it to transference plans (couplings), turning it into an infinite-dimensional linear program with a dual: maximize the total revenue ∫ψ dμ+∫φ dν\int\psi\,d\mu+\int\varphi\,d\nu∫ψdμ+∫φdν of pickup and delivery prices…

10 thms3 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: mikedeng1

Scenario Reduction Algorithms in Stochastic Programming I: Fast Forward Selection Realizes the Forward Selection PrincipleResearch Paper

Multistage and two-stage stochastic programs are solved numerically on a discrete probability distribution: a finite set of scenarios ω1,…,ωN\omega_1,\dots,\omega_Nω1​,…,ωN​ with probabilities p1,…,pNp_1,\dots,p_Np1​,…,pN​. The size of the resulting optimization problem grows with NNN, and scenario sets produced by sampling or by historical data are often far too large to be solved…

12 thms3 active usersReviewed
🏆Completed
Linear OptimizationOperations Research·Captain: mikedeng1

Scenario Reduction in Stochastic Programming: The Optimal Redistribution Rule and the Explicit Kantorovich Distance of a Reduced MeasureResearch Paper

Stochastic programs are solved in practice on a finite set of scenarios: a discrete probability distribution P=∑i=1NpiδωiP=\sum_{i=1}^N p_i\delta_{\omega_i}P=∑i=1N​pi​δωi​​ that approximates the true distribution of the uncertain data. The size of the resulting deterministic problem grows with NNN, and for multistage models it grows very fast, so NNN is often reduced before solving. The…

7 thms3 active usersReviewed
CombinatoricsGraph TheoryTheoretical Computer Science·Captain: Shuze Chen

Graph Similarity Meets Optimal TransportResearch Paper

A common way to measure how different two graphs are is to align their vertex sets and count how much the adjacency structure disagrees under the alignment. With different matrix norms this gives graph edit distance, a standard tool in pattern recognition and graph matching (Gao et al. 2010); local edit distance, the largest number of edits needed at a…

21 thms2 active usersReviewed
🏆Completed
Operations ResearchProbabilityStatistics·Captain: mikedeng1

Joint Mixability and Notions of Negative Dependence: The Minimizers of the Worst-Case Quadratic Cost over Subsets of Components Are Exactly the NCD Joint Mixes with Correlation Matrix P*_nResearch Paper

A joint mix is a random vector X=(X1,…,Xn)\mathbf X=(X_1,\dots,X_n)X=(X1​,…,Xn​) whose component sum ∑i=1nXi\sum_{i=1}^n X_i∑i=1n​Xi​ is almost surely constant. For fixed marginal distributions it minimizes the variance, the stop-loss premium and the Expected Shortfall of the aggregate, which comonotonicity maximizes, and for this reason it is regarded as the canonical form of extremal negative…

10 thms2 active usersReviewed
🏆Completed
Operations ResearchOptimizationProbability·Captain: mikedeng1

Distributionally Robust Mean-Variance Portfolio Selection with Wasserstein Distances: The Robust Problem Is Equivalent to Empirical Variance Minimization with a Norm PenaltyResearch Paper

Portfolio selection uses observed asset returns to choose weights that balance expected return against variability. Estimates of both quantities can change sharply when the historical sample changes. A distributionally robust model addresses this uncertainty by allowing the return law to vary around the empirical law, then judging a portfolio by its worst…

7 thms2 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: mikedeng1

Robustifying Conditional Portfolio Decisions via Optimal Transport 5: For a Fiber of Radius γ > 0 and Fiber Mass at Least ε > 0, the Worst-Case Conditional Loss Equals a Finite-Dimensional DualResearch Paper

A portfolio manager who observes side information, the covariate XXX (a market state, a set of signals), wants to choose a portfolio for the asset returns YYY given the current value x0x_0x0​ of that covariate. Estimating the conditional law of YYY given X=x0X=x_0X=x0​ from NNN joint samples is fragile: typically no sample has x^i=x0\hat x_i=x_0x^i​=x0​ exactly, and a nearest-neighbour or…

12 thms2 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: mikedeng1

Robustifying Conditional Portfolio Decisions via Optimal Transport 4: For a Fiber of Radius γ > 0 and a Budget ρ < ρ_max, Every Measure in the Ball Puts at Least an Explicit Mass ε > 0 on the FiberResearch Paper

A portfolio manager who observes side information, such as a vector of market covariates x0x_0x0​ today, wants a decision that performs well conditionally on that information: the relevant risk is the expected loss of the portfolio given that the covariate equals, or is close to, x0x_0x0​. Estimating this conditional loss from NNN historical pairs (x^i,y^i)(\hat x_i,\hat y_i)(x^i​,y^​i​) of…

11 thms2 active usersReviewed
🏆Completed
Operations ResearchProbability·Captain: mikedeng1

Global Sensitivity Analysis via Optimal Transport 2: OT-Based Sensitivity Measures Are Monotone in Information and Continuous Along Increasing σ-AlgebrasResearch Paper

Global sensitivity analysis asks how much the uncertainty in an output YYY of a model or a data set is explained by an input XXX. A large family of indices has the form "expected discrepancy between the marginal law of YYY and its conditional law given XXX": the variance-based index of Sobol' and Wagner, the L1L^1L1 density-based index, Kuiper and Cramér–von Mises…

13 thms2 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: mikedeng1

Robustifying Conditional Portfolio Decisions via Optimal Transport 2: With a Singleton Fiber and Fiber Mass at Least ε > 0, the Worst-Case Conditional Expected Loss Equals a Two-Multiplier DualResearch Paper

A portfolio manager who observes today's value x0x_0x0​ of a covariate (a market signal, a macroeconomic indicator) wants to choose a portfolio that performs well conditionally on that observation: the relevant risk is E[ℓ(Y,α,β)∣X=x0]\mathbb E[\ell(Y,\alpha,\beta)\mid X=x_0]E[ℓ(Y,α,β)∣X=x0​] of the asset return YYY, not its unconditional mean. With finitely many historical pairs …

9 thms2 active usersReviewed
ProbabilityStatistics·Captain: mikedeng1

Global Sensitivity Analysis via Optimal Transport 3: The Partition Estimator of an OT-Based Sensitivity Measure Converges Under Weak Convergence of the Joint LawsResearch Paper

Global sensitivity analysis asks how much of the uncertainty in a model output YYY is due to an input XXX. Borgonovo, Figalli, Plischke and Savaré (Management Science, 2025) propose a family of indicators built on optimal transport: the expected optimal transport cost between the marginal law of YYY and the law of YYY conditioned on the information carried by XXX.…

12 thms2 active usersReviewed
🏆Completed
Operations ResearchOptimizationProbability·Captain: mikedeng1

Sinkhorn Distributionally Robust Optimization 1: Strong Duality — the Worst-Case Expectation over a Sinkhorn Ball Equals inf over λ ≥ 0 of λρ̄ + λε·E log E_Q[e^{f/(λε)}]Research Paper

Distributionally robust optimization (DRO) hedges a decision against uncertainty in the data distribution. It minimizes the worst-case expected loss over an ambiguity set of distributions around a nominal one, typically the empirical distribution of the data. Ambiguity sets built from the Wasserstein (optimal-transport) distance are standard in operations…

12 thms2 active usersReviewed
🏆Completed
Operations ResearchOptimizationProbability·Captain: mikedeng1

Distributionally Robust Stochastic Optimization with Wasserstein Distance: If the Growth Rate κ of Ψ Is Finite, sup{E_μ[Ψ] : W_p(μ, ν) ≤ θ} Equals Its One-Dimensional Dual and Is FiniteResearch Paper

Distributionally robust stochastic optimization (DRSO) chooses a decision xxx to minimize the worst expected loss sup⁡μ∈MEμ[Ψ(x,ξ)]\sup_{\mu\in\mathfrak M}\mathbb E_\mu[\Psi(x,\xi)]supμ∈M​Eμ​[Ψ(x,ξ)] over an ambiguity set M\mathfrak MM of probability distributions, instead of the expectation under one estimated distribution. When M\mathfrak MM is a ball around a nominal distribution ν\nuν (often the…

16 thms2 active usersReviewed
ProbabilityStatistics·Captain: mikedeng1

Finite-Sample Guarantees for Wasserstein Distributionally Robust Optimization: Breaking the Curse of Dimensionality 1: Under T_p(τ), True Loss ≤ Empirical Loss + R(√(τt/n); −f) w.p. ≥ 1 − e^(−t)Research Paper

Wasserstein distributionally robust optimization (Wasserstein DRO) replaces the expected loss under an empirical distribution by the worst-case expected loss over all distributions within a Wasserstein distance ρ\rhoρ of it. It is used in operations research, statistics and machine learning to guard decisions and predictors against the gap between the sample…

10 thms2 active usersReviewed
🏆Completed
Operations ResearchOptimizationProbability·Captain: mikedeng1

A Short and General Duality Proof for Wasserstein Distributionally Robust Optimization III: Under a Tight Nominal Measure, f(x) − λd(x̂, x)^p Satisfies the Interchangeability PrincipleResearch Paper

Wasserstein distributionally robust optimization (DRO) replaces the expected loss under a nominal distribution P^\widehat{\mathbb P}P (typically an empirical distribution) by the worst expected loss over all distributions within a given optimal-transport distance of P^\widehat{\mathbb P}P. Its tractability rests on a strong duality theorem that turns a supremum…

7 thms2 active usersReviewed
Operations ResearchProbabilityStochastic Systems·Captain: mikedeng1

A Stochastic Control Approach to No-Arbitrage Bounds Given Marginals, with an Application to Lookback Options: The Robust Superhedging Bound of g(X*_T) Given the Law of X_T Equals μ^HL(g)Research Paper

A lookback option pays a function of the running maximum of the underlying asset over the life of the contract. When the prices of European call options of all strikes at the maturity are quoted, the risk-neutral law μ\muμ of the terminal price is known, but the law of the whole path is not. The robust (model-free) superhedging cost of the lookback payoff is…

13 thms2 active usersReviewed
Machine LearningProbabilityStatistics·Captain: mikedeng1

Wasserstein Distributionally Robust Optimization and Variation Regularization III: With Probability 1 − e^(−t), E_Pn[(ρ − d(z, D_f))₊] ≤ Cρ² + 2ρ·E[Rademacher] + ρ√(t/2n) for Every fResearch Paper

Wasserstein distributionally robust optimization (DRO) replaces the empirical risk EPn[f]\mathbb E_{P_n}[f]EPn​​[f] of a loss fff by its worst case over all distributions within Wasserstein distance ρ\rhoρ of the empirical law PnP_nPn​. Gao, Chen and Kleywegt (arXiv:1712.06050; Operations Research, 2024, doi:10.1287/opre.2022.2383) show that, for small radii, this worst-case risk…

8 thms2 active usersReviewed
🏆Completed
Functional AnalysisProbabilityStatistics·Captain: mikedeng1

Computational Optimal Transport XI: For p = 1, 2 the p-Wasserstein Distance on ℝ^d with d ≥ 2 Is Not HilbertianTextbook

Kernel methods, multidimensional scaling and low-distortion embeddings all work best on data whose distance comes from a Hilbert space. A distance ddd on a set Z\mathcal ZZ is Hilbertian when Z\mathcal ZZ can be mapped into a Hilbert space so that ddd becomes the norm distance; for such a ddd, the kernel e−dp/te^{-d^p/t}e−dp/t is positive definite for 0≤p≤20\le p\le 20≤p≤2 and t>0t>0t>0 (Berg,…

10 thms2 active usersReviewed
🏆Completed
CombinatoricsGraph TheoryLinear Optimization·Captain: mikedeng1

Computational Optimal Transport IV: The Support Graph of an Extreme Point of the Transportation Polytope U(a, b) Has No Cycle, Hence at Most n + m − 1 Nonzero EntriesTextbook

Discrete optimal transport between two histograms is a linear program. Its feasible set, the transportation polytope, has been studied since Hitchcock (1941) and Kantorovich, and the structure of its vertices underlies the classical algorithms for the problem: the north-west corner rule produces a vertex, and the network simplex moves from vertex to vertex.…

7 thms2 active usersReviewed
ProbabilityStatistics·Captain: mikedeng1

On the Rate of Convergence in Wasserstein Distance of the Empirical Measure II: Concentration Inequalities for T_p(μ_N, μ) under Exponential or Polynomial Moments (Theorem 2)Research Paper

Approximating an unknown probability measure μ\muμ by the empirical measure μN=1N∑k=1NδXk\mu_N=\frac1N\sum_{k=1}^N\delta_{X_k}μN​=N1​∑k=1N​δXk​​ of an i.i.d. sample is the basic operation of statistics, Monte Carlo integration, quantization and particle approximations of nonlinear PDEs. The natural way to compare μN\mu_NμN​ with μ\muμ on Rd\mathbb R^dRd is an optimal-transport cost, because it…

13 thms2 active usersReviewed
ProbabilityStatistics·Captain: mikedeng1

On the Rate of Convergence in Wasserstein Distance of the Empirical Measure I: Non-Asymptotic Moment Bounds on E T_p(μ_N, μ) under a q-th Moment Condition (Theorem 1)Research Paper

How fast does the empirical measure of an i.i.d. sample approach the law it is drawn from? When distance is measured by optimal transport, the answer enters the analysis of statistical estimators built from empirical distributions, quantization of probability measures, Monte Carlo and particle approximations of nonlinear PDEs (McKean–Vlasov systems), and…

11 thms2 active usersReviewed
🏆Completed
CombinatoricsLinear OptimizationOptimization·Captain: mikedeng1

Computational Optimal Transport I: For Uniform Marginals 1/n Some Permutation Matrix Solves the Kantorovich Problem, so the Relaxation of Optimal Assignment Is TightTextbook

An assignment problem pairs each of nnn sources with exactly one of nnn destinations while minimizing a specified cost. A permutation records those pairings. The number of permutations grows as n!n!n!, so a direct search quickly becomes impractical. In discrete optimal transport, the same data can be placed in a linear optimization problem over nonnegative…

7 thms2 active usersReviewed
Operations ResearchOptimizationProbability·Captain: mikedeng1

On a Problem of Optimal Transport Under Marginal Martingale Constraints 2: The Shadow of γ1 + γ2 in ν Is the Shadow of γ1 Plus the Shadow of γ2 in What RemainsResearch Paper

The martingale optimal transport problem asks for a coupling of two probability measures μ,ν\mu,\nuμ,ν on R\mathbb RR that is the law of a one-step martingale and minimizes an expected cost. It arises in robust finance, where the marginals are the risk-neutral laws of an asset at two dates implied by option prices, and model-independent price bounds for exotic…

18 thms2 active usersReviewed
Operations ResearchOptimizationProbability·Captain: mikedeng1

On a Problem of Optimal Transport Under Marginal Martingale Constraints 5: For c = ϕ(x)ψ(y), ψ Strictly Convex, ϕ Strictly Decreasing, the Left-Curtain Coupling Is the Unique OptimizerResearch Paper

Martingale optimal transport asks for the cheapest way to couple two given laws μ\muμ and ν\nuν on R\mathbb RR by a one-step martingale: a pair (X,Y)(X,Y)(X,Y) with X∼μX\sim\muX∼μ, Y∼νY\sim\nuY∼ν and E[Y∣X]=XE[Y\mid X]=XE[Y∣X]=X. The problem arises in mathematical finance, where μ\muμ and ν\nuν are the risk-neutral laws of an asset at two maturities, implied by quoted vanilla option prices, and the…

11 thms2 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchOptimization·Captain: mikedeng1

Computational Optimal Transport VI: On Termination the Auction Algorithm Returns an Assignment Whose Cost Is Within nε of the OptimumTextbook

The optimal assignment problem asks for a one-to-one matching of nnn points to nnn objects of least total cost. It is the discrete optimal transport problem between two uniform measures with the same number of atoms, and by the Birkhoff–von Neumann theorem it coincides with the Kantorovich linear program on that instance (Peyré and Cuturi, Computational Optimal…

5 thms2 active usersReviewed
PreviousPage 3 of 4Next

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me