Supplementary Material Efficient Online Learning of Optimal Rankings: Dimensionality Reduction via Gradient Descent A Omitted Proofs of Section 3 Proof of Lemma 1