A Proofs

We first introduce two useful known lemmas, and prove the propositions in their order of appearance. We refer the reader to the original references for proofs. We will also need a uniform law of large numbers for functions. The following lemma is a consequence of Example 19.7 and Lemma 19.36 of V an der V aart (2000), and is copied in Lemma B.6 in We use Theorem 1 from Diaconis and Freedman (1999). We then turn to prove Proposition 2. A.3.1 Noise-free online Sinkhorn Proposition 5. Proof of Proposition 2. For discrete realizations ˆ α and ˆ β, we define the perturbation terms ε From Eq. (8), for all t > 0, we have 0 null e Following the derivations of Moulines and Bach (2011, Theorem 2), we have the following bias-variance decomposed upper-bound, provided that 0 null a < 1 and a + b > 1 .