Machine learning with Optimal Transport and Algorithmic Fairness

Contents

• Introduction and overview
• 0. Review: convexity and LP duality
• 1. The transport problem
• 2. Duality and the Wasserstein distance
• 3. Entropic regularization: Sinkhorn
• 4. OT and machine learning
• 5. Gromov-Wasserstein and beyond
• 6. Fairness through transport
• 7. Research at CMAP (Flamary, Gaucher)
• Exercises
• Projects and assessment
• References

Introduction and overview

Audience: an engineer who has already compared two histograms (KL, MMD) and seen domain adaptation “work on a toy, die in prod”.

Empirical first: EMD too slow on 5k points; Sinkhorn diverging when \varepsilon is too small; FID dropping while the eye sees no gain — then we name Monge, Wasserstein, duality.

Theory (Monge, Kantorovich, duality) + practice (Sinkhorn / POT), then losses, domain adaptation, Gromov-Wasserstein and fairness. Flamary & Gaucher (CMAP); Flamary co-created POT.

What you will be able to do

• Formulate Monge’s transport problem and its Kantorovich relaxation, and relate them to linear programming.
• Exploit duality to interpret the Wasserstein distance and its potentials.
• Implement the Sinkhorn algorithm and understand the role of entropic regularization.
• Use transport as a machine learning tool: Wasserstein losses, domain adaptation, barycenters.
• Understand Gromov-Wasserstein to compare objects with no direct correspondence, typically graphs.
• Apply transport to fairness questions, acting on distributions rather than on predictions.

Official objectives and syllabus (2026-2027 catalog)

The official course description (X3A session “Machine learning with Optimal Transport and Algorithmic Fairness”) sets a clear objective: “to discover some of the major current issues of machine learning”, around two stated themes — optimal transport for statistical learning and algorithmic fairness in statistical learning.

The teaching is organized into “fundamental lectures providing the necessary foundations to discover the various topics”, complemented by a group project of reading, understanding and numerical implementation of scientific papers, followed by an oral presentation of the results — which carries 100% of the grade.

Official volume: “36 heures en présentiel” (36 h in person), while the breakdown line of the same sheet gives “(CTD) Module Cours-TD: 40.3” — an internal inconsistency of the sheet that we report without resolving it; these notes are calibrated on the 36 h headline figure.

Languages: French and English; limited enrollment (maximum 24 on the course unit, 30 on the 2026–2027 occurrence). Detailed week-by-week syllabus: not displayed on the sheet. Official prerequisites: the sheet states, for students of the engineering degree only, that it is “strongly recommended to have taken the MAP553 course”; it displays no prerequisite for the LLGA track.

Both official themes are fully covered, the description not publishing any more detailed syllabus. Our extensions, beyond the official description: the refresher chapter 0 (convexity and LP duality), chapter 5 (Gromov-Wasserstein and its FGW/COOT variants) and chapter 7 (the research work of the team, foremost among which those of Rémi Flamary around POT).

Where this course fits in the program

Module of period 2 of M1 (36 h, 4.5 ECTS): one of the six electives of the Period 2 “Choose 1” group of the LLGA 1 – S2 list, and no route of the home page preselects it. Official prerequisites: none displayed for the LLGA track; for engineering-degree students the sheet strongly recommends having taken MAP553. It is the course that gives the master’s program its common language for talking about distances between distributions.

• Prerequisites — Machine Learning for the learning framework and Refresher in Statistics for handling distributions; the Signal Processing module (P1, same instructor) is useful without being a blocker, as this course extends its “signal for ML” chapter.
• Downstream modules — the Gromov-Wasserstein chapter directly prepares Graph Generative Models and Applications (M2), which aligns relational structures by transport; the FID that evaluates the generative models of the Multimodal Generative AI module (same period, same “Choose 1” group) is a Wasserstein distance between distributions; finally, the fairness approach crosses paths with the master’s concerns in responsible AI.

Course outline

• Review: convexity and LP duality — the two reading keys for the rest of the module.
• The transport problem — from Monge to Kantorovich: moving mass at minimum cost, and why we relax.
• Duality and the Wasserstein distance — the dual viewpoint, and the geometry the distance induces on distributions.
• Entropic regularization: Sinkhorn — making transport computable, iteration by iteration.
• OT and machine learning — Wasserstein losses, domain adaptation, barycenters: the toolbox in action.
• Gromov-Wasserstein and beyond — transporting between spaces with no correspondence, up to the FGW and COOT variants.
• Fairness through transport — correcting distributional disparities between populations.
• Research at CMAP (Flamary, Gaucher) — a tour of the research work of Rémi Flamary (self-study, and entry points for the project).
• Exercises and References — systematic training and sources to go further.

Session plan

36 h in class = 12 sessions of 3 h. The volume is the headline figure of the SynapseS 2026–2027 sheet (“36 heures en présentiel”); the same sheet’s breakdown line gives 40.3 h of lecture-exercise module, an inconsistency we report but do not follow, because the LLGA curriculum page of the programme wiki (msct.dix.polytechnique.fr/llga, last modified on 9 September 2026 by the programme director) states that “all subsequent M1 courses are 36h and will credit 4.5 ECTS”.

The sheet publishes no session-by-session programme, so the split below is our proposal for covering these notes in that time. Level 1 = foundations (reviews, definitions, first worked examples), 2 = core theory and algorithms, 3 = advanced extensions and recent research; the level never goes down from one session to the next.

Self-study, outside the 36 h (about 3 h in total): ch. 7 Research at CMAP — POT, OT for domain adaptation, FGW, COOT, sliced theory, biosignals (≈ 3 h; it also gives entry points for the group project).

How to study this module

• First absorb convexity and duality (the review section): almost every theorem of the course is a duality theorem in disguise.
• Solve tiny discrete cases by hand (two or three points): the optimal transport plan takes shape there, and the intuition generalizes.
• Experiment with the POT library, created by the instructor: varying the entropic regularization and observing the transport plan is the best way to understand Sinkhorn.
• Relate each application to the generic problem “compare two distributions”: a loss, domain adaptation or fairness are just different instances of this same question.
• Multimodal Generative AI sits in the same “Choose 1” group, so you cannot take both. This course proves what the Wasserstein-GAN and the FID rest on (prop. 4.2, th. 2.7); for the generative models they train and evaluate, read its chapter 2. If you chose Multimodal GenAI instead, ch. 2 of these notes proves the duality and the Bures formula, and prop. 4.2 sketches the step to the WGAN critic.
• Redo the exercises of each section before moving on to the next; the hand calculations prepare the software implementation.

0. Review: convexity and LP duality

Every transport problem of this course is a convex optimization problem, and most of its proofs are duality arguments. This review states the four tools used throughout: linear-programming duality, the pushforward of a measure, uniqueness under strict convexity, and the positivity of the Kullback-Leibler divergence.

1. The transport problem

Concrete scene: two 1D histograms of 20 bins each, a source and a target. A greedy coupling that sends each bin to the nearest bin with remaining capacity costs 12.4; the linear-programming solver of POT finds 7.1.

And when one source bin must feed two target bins, no deterministic map can do the job, whereas a transport plan that splits the mass exists. This chapter states the two formulations of the problem, Monge’s and Kantorovich’s, before any algorithm.

2. Duality and the Wasserstein distance

Computing a transport plan is a minimization; its dual, a maximization over pairs of potentials, gives certificates of optimality, the structure of optimal plans (Brenier’s theorem) and closed formulas in dimension 1 and for Gaussians. This chapter derives the duality, then defines the Wasserstein distances and proves that they are distances.

3. Entropic regularization: Sinkhorn

Exact transport is a linear program whose cost grows like n^3 \log n and whose solution is not differentiable in the data. Adding a small entropy term makes the problem strictly convex, solvable by a few matrix-vector products (the Sinkhorn algorithm) and smooth — the version of OT that machine learning actually uses.

import numpy as np
import ot                              # POT: Python Optimal Transport

n = 200
xs, xt = np.random.RandomState(0).normal(0, 1, (n, 2)), np.random.RandomState(1).normal([2, 0], [0.5, 2], (n, 2))
a, b = np.ones(n) / n, np.ones(n) / n
C = ot.dist(xs, xt)                    # squared costs ||x-y||^2

G = ot.emd(a, b, C)                    # exact OT (LP, transport simplex)
G0 = ot.emd2(a, b, C)                  # value only (exact W2^2)
Gs = ot.sinkhorn(a, b, C / C.max(), reg=0.05)
print("exact  :", (G * C).sum())
print("sinkhorn:", (Gs * C).sum())     # slight entropy overhead
print("sliced  :", ot.sliced_wasserstein_distance(xs, xt, n_projections=500))

# 1D: quantiles (prop. 2.6) -- exact W2 computed by sorting
print("W2 1d :", ot.wasserstein_1d(xs[:,0], xt[:,0], p=2)**0.5)

Sinkhorn in the log domain, from scratch. The iterations of theorem 3.2 can run on the potentials f = \varepsilon\log u and g = \varepsilon\log v instead of the scalings. Since u_i = e^{f_i/\varepsilon}, the update u \leftarrow a/(Kv) becomes a log-sum-exp: f_i \leftarrow \varepsilon\log a_i - \varepsilon\log\sum_j e^{(g_j - C_{ij})/\varepsilon}, \qquad g_j \leftarrow \varepsilon\log b_j - \varepsilon\log\sum_i e^{(f_i - C_{ij})/\varepsilon}.

The kernel K = e^{-C/\varepsilon} is never formed, so nothing underflows at small \varepsilon: this is what ot.sinkhorn(..., method="sinkhorn_log") runs (ot.bregman.sinkhorn_log). The lines below reuse the clouds of the previous block and check the plan against POT.

from scipy.special import logsumexp

def sinkhorn_log(a, b, C, eps, n_iter=1000):
    """Log-domain Sinkhorn (th. 3.2) on the potentials f = eps*log(u), g = eps*log(v)."""
    f, g = np.zeros(len(a)), np.zeros(len(b))
    for _ in range(n_iter):
        f = eps * np.log(a) - eps * logsumexp((g[None, :] - C) / eps, axis=1)  # u <- a / (K v)
        g = eps * np.log(b) - eps * logsumexp((f[:, None] - C) / eps, axis=0)  # v <- b / (K^T u)
    return np.exp((f[:, None] + g[None, :] - C) / eps), f, g

Cn = C / C.max()                                        # same clouds and costs as above
P, f, g = sinkhorn_log(a, b, Cn, eps=0.01)
P_pot = ot.sinkhorn(a, b, Cn, reg=0.01, method="sinkhorn_log")
print("max |P - P_pot|:", np.abs(P - P_pot).max())     # about 1e-11
print("marginal error :", np.abs(P.sum(1) - a).max(), np.abs(P.sum(0) - b).max())
print("<C,P> vs exact :", (P * Cn).sum(), ot.emd2(a, b, Cn))  # entropic plan costs more

The two plans agree to about 10^{-11} and the marginals hold to machine precision. The transport cost of the entropic plan stays above the exact optimum, because that plan is admissible but blurred: the entropic bias of the note above.

These f and g are log-scalings, not the multipliers of the proof of th. 3.2. From u_i = a_i e^{\lambda_i/\varepsilon}, \lambda = f - \varepsilon\log a , and the potential of th. 3.4 is \lambda^\star, because def. 3.1 measures the entropy against ab^\top. So f gives the gradient in a, up to a constant, only when a is uniform; a finite-difference check with random weights shows the difference.

4. OT and machine learning

With the tools of ch. 1–3 in hand, this chapter uses transport to solve learning problems: adapting a classifier to a shifted domain, training generative models with a Wasserstein loss, averaging distributions, comparing documents — and asks how many samples are needed to estimate a Wasserstein distance.

import numpy as np, ot
# two partially shared "documents", fictitious embeddings
X = np.array([[0., 0.], [1., 0.], [10., 0.]])     # king, queen, cat (source)
Y = np.array([[0.1, 0.], [1.2, 0.], [10.4, 0.]])  # queen, king, dog  (target)
a = np.array([.5, .3, .2]); b = np.array([.4, .4, .2])
C = ot.dist(X, Y, metric="euclidean")              # Euclidean costs (WMD is a W_1)
print("WMD :", ot.emd2(a, b, C))                   # exact plan: ot.emd(a, b, C)

5. Gromov-Wasserstein and beyond

Sometimes the two distributions live in different spaces — two graphs with unrelated node sets, two word-embedding spaces of different languages — so that no cost c(x, y) between their points exists. Gromov-Wasserstein compares instead the internal distances of each space; this chapter defines it, proves its invariance, and gives its algorithms and its variants for attributed graphs and data matrices.

import numpy as np, ot                          # POT: ot.gromov
from scipy.sparse.csgraph import shortest_path

# two non-isomorphic 4-node graphs: a star K_{1,3} and a path P_4
A1 = np.array([[0., 1., 1., 1.], [1., 0., 0., 0.], [1., 0., 0., 0.], [1., 0., 0., 0.]])
A2 = np.array([[0., 1., 0., 0.], [1., 0., 1., 0.], [0., 1., 0., 1.], [0., 0., 1., 0.]])
D1 = shortest_path(A1, unweighted=True)         # distance matrices: zero diagonal
D2 = shortest_path(A2, unweighted=True)
a = np.ones(4) / 4 ; b = np.ones(4) / 4

# exact GW (conditional gradient, no regularization): node alignment plan
G = ot.gromov.gromov_wasserstein(D1, D2, a, b, loss_fun='square_loss')
print("GW2^2 :", ot.gromov.gromov_wasserstein2(D1, D2, a, b))     # 0.375 > 0

# FGW: add node attributes (same dimension here) and sweep alpha (def. 5.3)
F1 = np.array([[0., 0.], [1., 0.], [1., 0.], [0., 1.]])
F2 = np.array([[1., 0.], [0., 0.], [0., 1.], [1., 0.]])
Cf = ot.dist(F1, F2)
for alpha in (0.0, 0.5, 1.0):                   # 0: features only, 1: structure only
    Gf, log = ot.gromov.fused_gromov_wasserstein(Cf, D1, D2, a, b,
                                                 loss_fun='square_loss', alpha=alpha,
                                                 log=True)
    print(f"FGW(alpha={alpha}) :", log['fgw_dist'])

6. Fairness through transport

A model trained on historical data reproduces the disparities between groups that these data contain. Fairness criteria compare the distributions of decisions across groups, so transport — which moves one distribution onto another at minimal cost — gives a natural way to repair the data or the decisions while changing them as little as possible.

import numpy as np, ot
from sklearn.linear_model import LogisticRegression
# Adult: X = numerical variables, S = gender, Y = income > 50k
# (load with pandas.read_csv("adult.data"), encode the categoricals)

def repair_1d(x, s, lam):
    """Partial quantile repair of one feature (th. 6.2): x -> (1-lam) x + lam Q*(F_s(x))."""
    xR, groups = x.astype(float).copy(), np.unique(s)
    p = {g: np.mean(s == g) for g in groups}                       # group weights p_s
    u = np.linspace(0, 1, 101)                                     # quantile levels
    bary = sum(p[g] * np.quantile(x[s == g], u) for g in groups)   # Q*(u) = sum_s p_s Q_s(u)
    for g in groups:
        xg = x[s == g]
        ug = (np.argsort(np.argsort(xg)) + 0.5) / len(xg)          # within-group ranks F_s(x)
        xR[s == g] = (1 - lam) * xg + lam * np.interp(ug, u, bary)
    return xR

def repair(X, s, lam):                                             # feature by feature
    return np.column_stack([repair_1d(X[:, j], s, lam) for j in range(X.shape[1])])

assert np.allclose(repair(X_num, S, 0.0), X_num)                   # lambda = 0 changes nothing
for lam in np.linspace(0, 1, 11):                  # lambda -> trade-off curve
    Xr = repair(X_num, S, lam)
    clf = LogisticRegression().fit(Xr, Y)
    acc = clf.score(Xr, Y)
    dp = abs(clf.predict_proba(Xr[S==0])[:,1].mean()
           - clf.predict_proba(Xr[S==1])[:,1].mean())
    print(f"lambda={lam:.1f}  accuracy={acc:.3f}  dp_gap={dp:.3f}")
# Plot accuracy vs dp_gap: knee of the curve, discussion in the lab

7. Research at CMAP (Flamary, Gaucher)

Exercises

1. ★ Duality in dimension 2 (solution). Source and target in \mathbb{R}, cost \|x - y\|: a = (1/2, 1/2) \text{ at } x_1 = 0,\ x_2 = 1, \qquad b = (1/2, 1/2) \text{ at } y_1 = 0,\ y_2 = 2. Write the primal, guess the optimal plan, deduce the dual potentials from the complementarity of th. 2.1 and check the equality of the values.

   Solution (sketch). The cost matrix is C = \begin{pmatrix}0 & 2\\ 1 & 1\end{pmatrix}, and the extreme admissible plans are \Gamma_1 = \big(\begin{smallmatrix}1/2 & 0\\ 0 & 1/2\end{smallmatrix}\big) \ (\text{cost } 1/2), \qquad \Gamma_2 = \big(\begin{smallmatrix}0 & 1/2\\ 1/2 & 0\end{smallmatrix}\big) \ (\text{cost } 3/2). Optimum: \Gamma_1, with W_1 = 1/2.

   Complementarity: the support of \Gamma^\star is \{(1,1), (2,2)\}, which gives the equalities f_1 + g_1 = C_{11} = 0 and f_2 + g_2 = C_{22} = 1, together with the inequalities f_1 + g_2 \leq 2 and f_2 + g_1 \leq 1.

   Take f = (0, 1), g = (0, 0): the value \langle a, f\rangle + \langle b, g\rangle = 1/2 equals the primal value — strong duality verified by hand.

2. ★ Sinkhorn 2×2 by hand (solution). With a = b = (1/2, 1/2), C = \begin{pmatrix}0 & 1\\ 1 & 0\end{pmatrix} and \varepsilon = 1, compute K and initialize v = \mathbf{1}. Then perform two complete iterations of u \leftarrow a/(Kv), \qquad v \leftarrow b/(K^\top u), and check that the row marginals converge to a.

   Solution (values). The kernel is K = \big(\begin{smallmatrix}1 & e^{-1}\\ e^{-1} & 1\end{smallmatrix}\big). Iteration 1: Kv = (1 + e^{-1}, 1 + e^{-1})^\top, so u = \frac{1}{2(1+e^{-1})}(1,1)^\top; then K^\top u = \frac12(1,1)^\top, so v = (1,1)^\top again. The second iteration reproduces the same u and v: the fixed point is reached after a single complete iteration (symmetric case).

   The plan \Gamma = \mathrm{diag}(u)\,K = \frac{1}{2(1+e^{-1})}\big(\begin{smallmatrix}1 & e^{-1}\\ e^{-1} & 1\end{smallmatrix}\big) \approx \big(\begin{smallmatrix}0.366 & 0.134\\ 0.134 & 0.366\end{smallmatrix}\big) indeed has rows and columns summing to 1/2; the entropic plan “blurs” the diagonal toward the anti-diagonal (entropic bias, ch. 3).

3. ★ Bures in simulation (lab). Draw n = 5000 points from two anisotropic 2D Gaussians (\Sigma_1 = \mathrm{diag}(4, 1) rotated, \Sigma_2 = \mathrm{diag}(1, 4)), compare the empirical W_2^2 (Sinkhorn on the samples) with the closed formula of th. 2.7 and with ot.gaussian.empirical_bures_wasserstein_distance (it returns the distance, not its square). Observe the effect of \varepsilon.

   Hint. The gap comes from the entropic bias (use ot.bregman.empirical_sinkhorn_divergence) and from the sampling noise (n^{-1/d}, th. 4.5: severe in dimension 2 if n is small).

4. ★ Weighted Gaussian barycenter (hint). Rederive corollary 2.8 with arbitrary weights, then in the case of two laws \mathcal{N}(0, 1) and \mathcal{N}(0, 9): show that the standard deviation of the equal-weight barycenter equals 2 (and not \sqrt{5}), and comment (“the mean of the variances” is not the barycenter).

   Hint. Minimize pointwise in u the quantile function (zero derivative), then identify the resulting Gaussian quantile: \sigma = \sum_k w_k \sigma_k.

5. ★ WMD on two sentences (solution). With real word2vec embeddings (Text Mining and NLP module, ch. 4), compute the WMD between “the president addresses the congress” and “Obama speaks to the parliament”, then between two unrelated sentences; display the plan (ot.emd) and comment on the word matchings.

   Solution (key). Documents = uniform distributions over the words (minus the stopwords); cost = Euclidean distance between embeddings (not its square: WMD uses W_1); the plan connects “president”↔︎“Obama”, “congress”↔︎“parliament” (neighbors in the space): the distance stays small where the centroid distance would be misled by function words.

6. ★ GW invariant, W not (solution). Let \mu be uniform on three non-collinear points of the plane and \nu = \tau_\#\mu its translate by a vector of norm r, with the internal Euclidean distances. Show \mathrm{GW}_2(\mu, \nu) = 0 and W_2(\mu, \nu) = r. What happens under a rotation?

   Solution. The translation \tau preserves all the internal distances (an isometry in the sense of th. 5.2): diagonal plan at zero cost. For W_2, the plan (\mathrm{Id}, \tau)_\#\mu costs \big(\int \|x - (x + \tau)\|^2 d\mu\big)^{1/2} = r, and no coupling can do better, since by Jensen \mathbb{E}\|X - Y\|^2 \geq \|\mathbb{E}X - \mathbb{E}Y\|^2 = r^2 for every coupling (X, Y) (the means differ by the translation).

   Rotation: still GW = 0 (isometry); W_2 > 0 as soon as the points actually move — this is the motivation of ch. 5 (objects defined up to an isometry).

7. ★★ Kantorovich-Rubinstein (solution). In the framework of prop. 4.2, show that if f is 1-Lipschitz then f^c = -f for the cost c(x, y) = |x - y| (in dimension 1), and conclude that W_1(\mu, \nu) = \sup_{\mathrm{Lip}(f) \leq 1} \int f\,d(\mu - \nu).

   Solution (key). By definition, f^c(y) = \inf_x [|x - y| - f(x)]. The choice x = y gives f^c(y) \leq -f(y). For every x, f(x) \leq f(y) + |x - y| (1-Lipschitz), hence |x - y| - f(x) \geq -f(y) . The infimum is therefore attained at x = y, and f^c = -f. The dual of th. 2.1 becomes \int f\,d\mu + \int (-f)\,d\nu over the admissible pairs (f, -f), which are exactly (up to an additive constant) the 1-Lipschitz functions — hence the formula.

8. ★★ Vertices of the transport polytope (solution) — promised in ch. 1. Show that an optimal plan can be chosen with at most n + m - 1 non-zero coefficients (th. 1.3), build an example where the optimal plan is not deterministic, and connect it to example 1.2.

   Solution (sketch). Vertex: nm variables, constraints of rank \leq n + m - 1 (sum of the rows = sum of the columns); a vertex requires nm independent active constraints, of which at least nm - (n+m-1) are \Gamma_{ij} = 0.

   Non-deterministic example: a = (1) at x_1, b = (1/2, 1/2) — every plan has the form (1/2, 1/2), one row toward two columns: no vertex is a partial permutation. Link: this is example 1.2 (one mass, two half-masses).

   In general, a vertex has at most n + m - 1 non-zeros spread over n rows, each row having at least one: at most m - 1 rows carry more than one non-zero, so when n \gg m almost every source point goes to a single target.

   And when n = m with uniform weights 1/n, Birkhoff’s theorem says that the vertices are permutation matrices divided by n — the optimal plan is then a map.

9. ★★ Partial repair and repair speed (hint). In the 1D framework of th. 6.2, show that the level-\lambda partial repair sends the conditionals toward laws at distance W_2\big(\mathcal{L}(\tilde X^{(\lambda)}\mid S{=}0), \mathcal{L}(\tilde X^{(\lambda)}\mid S{=}1)\big) = (1-\lambda)\, W_2(\mu_0, \mu_1).

   Hint. Write the interpolated quantile functions Q^{(\lambda)}_s = (1-\lambda)Q_s + \lambda Q^\star and use prop. 2.6: the difference factorizes, Q^{(\lambda)}_0(u) - Q^{(\lambda)}_1(u) = (1-\lambda)(Q_0(u) - Q_1(u)).

10. ★★ Limits of FGW (hint). With the convention of def. 5.3 (that of POT), check that \mathrm{FGW}_{\alpha=0} recovers the OT of the features and \mathrm{FGW}_{\alpha=1} pure GW, then build two graphs where the FGW ranking changes from one to the other (consistent features but opposite structures).

    Hint. Take two 3-node graphs: the same star; features swapped between center and leaves; plot FGW as a function of \alpha (continuity, def. 5.3) on a synthetic set in POT.

11. ★★ Binary equalized odds (hint). Two groups of equal sizes, Y binary and balanced within each, perfect scores for group 0 (\hat Y = Y) and random scores (coin flips) for group 1. Determine the randomized post-processing of prop. 6.3 that achieves EO, and its accuracy.

    Hint. In ROC coordinates (FPR, TPR), randomization makes the feasible set of each group convex: for group 0 (perfect scores) it is the triangle with vertices (0,0), (0,1), (1,1); for group 1 (coin flips) it is only the diagonal \mathrm{TPR} = \mathrm{FPR}.

    EO forces a common point, hence a point of the diagonal, where (balanced classes) the accuracy in both groups is \tfrac12\mathrm{TPR} + \tfrac12(1 - \mathrm{FPR}) = \tfrac12 . Group 0 must be “noised” down to chance level. Discuss this cost (the debate of ch. 6).

12. ★★★ Synthesis lab — OTDA + FGW in POT. (a) Generate two 2D “source/target” clouds (shifted moons): full OTDA of ch. 4 with ot.da.SinkhornLpl1Transport (class-regularized transport, then transform), accuracy before/after.

    2. Two attributed 15-node graphs (stochastic block models): FGW alignment (ot.gromov.fused_gromov_wasserstein), recovered permutation matrix (f-score); sweep \alpha and \varepsilon, multiple initializations (GW non-convex, def. 5.1).

    Deliverables: curves, transport plan visualized (ot.plot.plot1D_mat), a short analysis.

Projects and assessment

The official assessment is a group project: “reading, understanding and numerical implementation of scientific papers, followed by an oral presentation of the results”, which carries 100% of the grade. The modality on the 2026–2027 sheet is “oral presentation by the group of the final project”, displayed for the engineering degree, the exchange programmes and the AI & Advanced Visual Computing MScT; the LLGA section of the sheet displays none. The subjects below are proposals of these notes, not official rules.

The group subjects follow the official format, a paper reimplemented, extended and presented orally by the group, and can stand for the graded project. The solo subjects train for it, or serve as individual variants if the instructors allow them. The written exam is a self-assessment proposal only, since the official grade has no exam.

The projects exercise mainly O1 (the mathematics and algorithms under OT losses), O8 (fairness repair and its limits) and O4 (Gromov-Wasserstein on graphs). The knowledge-graph subject adds O5, the evaluation suite adds O2 and O6, and every subject exercises O7 (hands-on work with POT, on real data except in the first solo subject).

Solo projects

1. [Solo · ≈ 20 h] Sinkhorn from scratch, and as a loss. When is entropic OT a faithful, differentiable stand-in for exact OT, and at which statistical rate?
   • Work: log-domain Sinkhorn with ε-scaling and the debiased divergence S_\varepsilon, in NumPy then PyTorch (ch. 3); the gradient in a given by the potential \lambda^\star of th. 3.4 (not the log-scaling f of the ch. 3 code) compared with autodiff through the iterations; timings against ot.sinkhorn and ot.emd.
   • Experiments: a small MLP pushed from a Gaussian onto two moons with an S_\varepsilon loss; distances between two independent n-samples of the same law, for exact W_2, S_\varepsilon and sliced W_2, in dimensions 2, 10 and 50.
   • Data: synthetic only (Gaussians, sklearn.datasets.make_moons); a laptop is enough.
   • Success criterion: plans within 10^{-6} of POT; potential and autodiff gradients equal up to an additive constant; log-log slopes with intervals over 20 repetitions, compared with the rates of th. 4.5.
   • Deliverables: code, a 4–6 page report, a 10-minute talk; ch. 0–4.
2. [Solo · ≈ 25 h] Paper study: OT domain adaptation (Courty, Flamary, Tuia and Rakotomamonjy, 2016) and JDOT (Courty, Flamary, Habrard and Rakotomamonjy, 2017). Does transporting the source onto the target beat a source-only classifier, and what does the class regularizer buy?
   • Work: OTDA with exact, entropic and class-regularized plans (ot.da.EMDTransport, SinkhornTransport, SinkhornLpl1Transport), out-of-sample mapping (ch. 4, step 5) and JDOT; first on shifted two moons, then on frozen ResNet-50 features. Baselines: source-only and a target-supervised oracle. An ablation with different class proportions in the target (label shift) breaks the covariate-shift assumption of def. 4.1.
   • Data: Office-31 (Saenko, Kulis, Fritz and Darrell, 2010), pairs A→W, D→W and W→A; MNIST→USPS as a fallback.
   • Success criterion: target accuracy per pair over 5 seeds, with intervals; the gain of the class regularizer measured at fixed \varepsilon; the label-shift failure observed and explained.
   • Deliverables: code, report, talk; ch. 1–4 and ch. 7. Extension: cross-subject EEG with Convolutional Monge Mapping Normalization (Gnassounou, Flamary and Gramfort, 2023).

Group projects

1. [Group of 3 · ≈ 30 h each] Paper study: fair learning by Wasserstein-barycenter repair (Gordaliza, Del Barrio, Gamboa and Loubes, 2019). How much accuracy does demographic parity cost on real data, and which transport repair buys it most cheaply?
   • Data: Adult (UCI; Becker and Kohavi, 1996) with sex as the sensitive attribute; the COMPAS data released by ProPublica (Angwin, Larson, Mattu and Kirchner, 2016) as a second set.
   • Work: the per-feature partial repair of the ch. 6 lab; multivariate repair toward an entropic barycenter (def. 4.3) with the barycentric projection; equalized-odds post-processing by quantile coupling (prop. 6.3); accuracy against the DP and EO gaps as \lambda varies, on held-out data; calibration per group.
   • Split: 1D repair and the check of exercise 9; multivariate repair; EO post-processing and calibration; shared evaluation code.
   • Success criterion: \lambda = 0 reproduces the baseline exactly; for one feature, the W_2 distance between the repaired group laws follows (1-\lambda)\,W_2(\mu_0, \mu_1) within sampling error; Pareto curves with intervals over 5 splits; the calibration–EO incompatibility (Kleinberg, Mullainathan and Raghavan, 2017) observed and explained.
   • Deliverables: code, an 8–10 page joint report, a 20-minute group talk (the official format); ch. 2–4 and ch. 6. It is the fairness option of the Y1.3 news-recommendation project, where the groups are news categories and the repaired quantity is exposure.
2. [Group of 3 · ≈ 30 h each] Paper study: entity alignment between knowledge graphs with Fused Gromov-Wasserstein (Vayer, Chapel, Flamary, Tavenard and Courty, 2019). How far does unsupervised FGW go on a real benchmark, and when does the structure term help over the attributes alone?
   • Data: DBP15K (Sun, Hu and Li, 2017), the ZH–EN pair, cut into samples of 500–1,000 aligned entity pairs with their induced subgraphs; node attributes from a multilingual sentence encoder such as LaBSE (Feng et al., 2022) applied to entity names; shortest-path distances on the relation graph.
   • Work: GW, FGW and entropic FGW, with \alpha swept in the POT convention (def. 5.3) and \varepsilon scaled down; COOT on the attribute matrices (def. 5.4); several initializations (non-convexity). Baselines: attribute-only OT (\alpha = 0) and nearest-neighbour matching.
   • Split: graph and attribute construction; solvers and sweeps; evaluation, plus an entity-disambiguation step for GraphRAG (Graph ML, ch. 10).
   • Success criterion: Hits@1 and Hits@10 against the gold alignment, with intervals over samples; an \alpha-curve whose best value is explained; runtime against the number of entities.
   • Deliverables: code, joint report, group talk; ch. 3, ch. 5 and ch. 7. It is the alignment option of the Y1.1 GraphRAG project and the alignment baseline of Y2.1.
3. [Group of 3 · ≈ 30 h each] An OT evaluation suite for generative models: FID, Sinkhorn divergence, sliced Wasserstein and FGW. Do these metrics rank generators the same way, and how do their bias and variance depend on the sample size and the dimension (th. 4.5)?
   • Data: CIFAR-10 test images under a ladder of corruptions (noise, blur, black rectangles, as in Heusel et al., 2017), plus samples of the public DDPM checkpoint google/ddpm-cifar10-32 on a free GPU tier; for graphs, the generators of Graph ML, ch. 9 on community graphs or QM9.
   • Work: FID from the Bures formula (th. 2.7) on Inception features, checked against clean-fid (Parmar, Zhang and Zhu, 2022); S_\varepsilon and sliced W_2 on the same features; an FGW distance between sets of graphs (def. 5.3); bias and variance against n and against the feature dimension (PCA).
   • Split: image metrics; graph metrics; the statistical study.
   • Success criterion: the Bures FID equal to clean-fid on identical features; rank correlations between the metrics over the ladder; bias curves compared with th. 4.5 and with the 1/n bias of FID (Chong and Forsyth, 2020); one disagreement between metrics explained.
   • Deliverables: code, joint report, group talk; ch. 2–5. It reuses the evaluation chapter of Multimodal Generative AI and prepares the evaluation of graph generators in Graph Generative Models.

Written exam (proposal)

Two hours, one handwritten A4 sheet allowed, no calculator needed; four questions. The official grade has no written exam, so this proposal is for self-assessment.

1. Question (4 points). State Monge’s problem and Kantorovich’s relaxation. Explain with \mu = \delta_0 and \nu = \tfrac12\delta_{-1} + \tfrac12\delta_{1} why the relaxation is needed, and state when an optimal plan is induced by a map.
   • Expected: Monge minimizes \int c(x, T(x))\,d\mu under T_\#\mu = \nu; Kantorovich minimizes \int c\,d\gamma over the couplings \Pi(\mu, \nu), a linear program in the discrete case (ch. 1).
   • Any map gives T_\#\delta_0 = \delta_{T(0)}, a single atom, so no map reaches \nu; the plan \tfrac12\delta_{(0,-1)} + \tfrac12\delta_{(0,1)} splits the mass (example 1.2).
   • Brenier (cor. 2.3): if \mu \ll \mathrm{Leb} and the cost is quadratic, the optimal plan is unique and induced by T = \nabla\varphi with \varphi convex.
2. Question (6 points). Three closed-form computations; give exact values.
   • 1. \mu uniform on \{0, 1, 3\} and \nu uniform on \{1, 2, 5\}: compute W_1(\mu, \nu) and W_2^2(\mu, \nu).
   • 2. W_2^2 between \mathcal{N}(0, \Sigma_1) and \mathcal{N}(e_1, \Sigma_2), with \Sigma_1 = \mathrm{diag}(4, 1) and \Sigma_2 = \mathrm{diag}(1, 4).
   • 3. The Wasserstein barycenter of \mathcal{N}(0, 1) and \mathcal{N}(0, 9) with weights 1/4 and 3/4.
   • Expected: (a) in 1D the optimal plan matches the sorted points (prop. 2.6): 0 \to 1, 1 \to 2, 3 \to 5, so W_1 = 4/3 and W_2^2 = (1 + 1 + 4)/3 = 2.
   • 2. The covariances commute, so the trace term of th. 2.7 is the sum of the squared differences of the standard deviations, (2-1)^2 + (1-2)^2 = 2; adding \|e_1\|^2 = 1 gives W_2^2 = 3.
   • 3. Corollary 2.8 gives \mathcal{N}(0, \sigma^2) with \sigma = \tfrac14 \cdot 1 + \tfrac34 \cdot 3 = 2.5: variance 6.25, not the mean of the variances, 7.
3. Question (5 points). Two short proofs.
   • 1. Show that W_1(\mu, \nu) \leq W_2(\mu, \nu).
   • 2. Let \Gamma \in U(a, b) couple the points x_i and z_j, with barycentric projection \hat T (ch. 4, OTDA step 3) and costs C_{ij} = \|x_i - z_j\|^2. Prove that \sum_i a_i\, \|x_i - \hat T(x_i)\|^2 \;\leq\; \langle C, \Gamma\rangle , and give an example where \hat T does not push a onto b.
   • Expected: (a) take an optimal plan \gamma for W_2; it is admissible for W_1, and Cauchy–Schwarz gives W_1 \leq \int d\,d\gamma \leq \Big(\int d^2\,d\gamma\Big)^{1/2} = W_2 .
   • 2. \hat T(x_i) is the mean of z_j under the conditional weights \Gamma_{ij}/a_i, and \|x_i - \cdot\|^2 is convex.
   • Jensen bounds \|x_i - \hat T(x_i)\|^2 by the conditional mean of \|x_i - z_j\|^2; multiply by a_i and sum over i.
   • Example: \mu = \delta_0 and \nu = \tfrac12\delta_{-1} + \tfrac12\delta_1 (example 1.2). The only plan splits the mass, \hat T(0) = 0, and \hat T pushes \mu onto \delta_0 \neq \nu: the barycentric map of OTDA only approximates a Monge map.
4. Question (5 points). A score R is uniform on [0, 1] in group s = 0 and uniform on [0, 1/2] in group s = 1; the groups have equal sizes, and the decision is R > 1/2.
   • 1. Give the demographic-parity gap. (b) Give the barycentric quantile function of th. 6.2 and the gap after full repair. (c) Same for the partial repair with \lambda = 1/2, and give the W_2 distance between the two repaired score laws.
   • Expected: (a) positive rates 1/2 and 0, so the gap is 1/2.
   • 2. Q_0(u) = u and Q_1(u) = u/2, so Q^\star(u) = \tfrac34 u: both groups become uniform on [0, 3/4], the positive rate is 1/3 in each, and the gap is 0 (proof of th. 6.2).
   • 3. The repaired quantile functions are \tfrac78 u and \tfrac58 u: positive rates 3/7 and 1/5, gap 8/35 \approx 0.23.
   • They differ by u/4, so W_2 = \sqrt{1/48} \approx 0.144: half of the initial \sqrt{1/12} \approx 0.289, as exercise 9 predicts.

Grading rubric (proposal)

References

• G. Peyré, M. Cuturi, Computational Optimal Transport, Foundations and Trends in Machine Learning 11(5-6), 2019 — the reference of the course: ch. 2 (theoretical foundations: Kantorovich, duality, c-transform), ch. 4 (entropic regularization and Sinkhorn), ch. 8 (statistical divergences, minimax formulations: WGAN), ch. 9 (variational problems: barycenters), ch. 10 (extensions: Gromov-Wasserstein, sliced, unbalanced).
• C. Villani, Optimal Transport: Old and New, Grundlehren 338, Springer, 2009 — for the general proofs (Brenier, Kantorovich-Rubinstein).
• F. Santambrogio, Optimal Transport for Applied Mathematicians, Birkhäuser, 2015 — calculus of variations, Monge-Ampère formula.
• M. Cuturi, Sinkhorn Distances: Lightspeed Computation of Optimal Transport, NIPS 2013 — the entropic regularization (ch. 3).
• J. Franklin, J. Lorenz, “On the scaling of algorithm for transportation problems”, SIAM J. Sci. Stat. Comput., 1989 — geometric convergence of Sinkhorn (th. 3.3).
• J. Feydy et al., Interpolating between Optimal Transport and MMD using Sinkhorn Divergences, AISTATS 2019 — the debiased divergences (ch. 3).
• A. Genevay, L. Chizat, M. Bach, G. Peyré, R. Rigollet, Sample Complexity of Sinkhorn Divergences, AISTATS 2019 — the n^{-1/2} rate (th. 4.5).
• N. Fournier, A. Guillin, “On the rate of convergence in Wasserstein distance of the empirical measure”, Probab. Theory Relat. Fields 162, 2015 — the n^{-1/d} curse (th. 4.5).
• M. Arjovsky, S. Chintala, L. Bottou, Wasserstein GAN, ICML 2017 (proposition 4.2); I. Gulrajani et al., Improved Training of Wasserstein GANs, NeurIPS 2017 (gradient penalty); T. Miyato et al., Spectral Normalization, ICLR 2018.
• M. Agueh, G. Carlier, “Barycenters in the Wasserstein space”, SIAM J. Math. Anal. 43, 2011; M. Cuturi, A. Doucet, Fast Computation of Wasserstein Barycenters, ICML 2014; J.-D. Benamou, G. Carlier, M. Cuturi, L. Nenna, G. Peyré, Iterative Bregman Projections for Regularized Transportation Problems, 2015 — barycenters (def. 4.3).
• N. Courty, R. Flamary, D. Tuia, A. Rakotomamonjy, Optimal Transport for Domain Adaptation, IEEE TPAMI 39(9), 2017 (online 2016) (ch. 4, OTDA algorithm); N. Courty, R. Flamary, A. Habrard, A. Rakotomamonjy, Joint Distribution Optimal Transportation for Domain Adaptation, NeurIPS 2017 (JDOT).
• M. Kusner, Y. Sun, N. Kolkin, K. Weinberger, From Word Embeddings to Document Distances, ICML 2015 — WMD (example 4.4).
• F. Mémoli, “Gromov-Wasserstein distances and the metric approach to object matching”, Found. Comput. Math. 11, 2011 — GW (def. 5.1); G. Peyré, M. Cuturi, J. Solomon, Gromov-Wasserstein Averaging of Kernel and Distance Matrices, ICML 2016 (PGW); J. Solomon, G. Peyré, V. G. Kim, S. Sra, “Entropic Metric Alignment for Correspondence Problems”, ACM Transactions on Graphics 35(4) (SIGGRAPH), 2016 (entropic GW).
• T. Vayer, L. Chapel, R. Flamary, R. Tavenard, N. Courty, Optimal Transport for Structured Data with Application on Graphs, ICML 2019 (FGW, def. 5.3); T. Vayer et al., Sliced Gromov-Wasserstein, NeurIPS 2019 (SGW).
• I. Redko, T. Vayer, R. Flamary, N. Courty, CO-Optimal Transport, NeurIPS 2020 (COOT, def. 5.4).
• D. Alvarez-Melis, T. Jaakkola, Gromov-Wasserstein Alignment of Word Embedding Spaces, EMNLP 2018 — unsupervised alignment of embeddings (example 5.5).
• M. Feldman et al., Certifying and Removing Disparate Impact, KDD 2015 (repair); M. Hardt, E. Price, N. Srebro, Equality of Opportunity in Supervised Learning, NeurIPS 2016 (equalized odds).
• P. Gordaliza, E. Del Barrio, F. Gamboa, J.-M. Loubes, Obtaining Fairness using Optimal Transport Theory, ICML 2019 (repair by barycenter, th. 6.2).
• L. de Lara, A. González-Sanz, N. Asher, L. Risser, J.-M. Loubes, Transport-based Counterfactual Models, JMLR 25(136), 2024 (bicausal OT and counterfactuals, prop. 6.3).
• J. Kleinberg, S. Mullainathan, M. Raghavan, Inherent Trade-offs in the Fair Determination of Risk Scores, ITCS 2017; A. Chouldechova, “Fair prediction with disparate impact”, Big Data 5(2), 2017 — the incompatibility of the metrics (ch. 6).
• R. Flamary et al., POT: Python Optimal Transport, JMLR 22(78), 2021 — pythonot.github.io: the tool used in all the labs (ch. 7).
• E. Tanguy, R. Flamary, J. Delon, Reconstructing discrete measures from projections, C. R. Mathématique 362, 2024; T. Gnassounou, R. Flamary, A. Gramfort, Convolutional Monge Mapping Normalization for learning on sleep data, NeurIPS 2023 — the recent research of ch. 7.