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

Randomly pick α (0, 1) with probability density function f (α) = 2 α . Randomly pick α (0, 1) with probability density function f (α) = 2 α . We dedicate the rest of the section to prove Theorem 4. Notice that Algorithm 4 is identical to Theorem 4 follows by the exact same steps that Theorem 3 follows using Lemma 2. The proof of Lemma 4 is concluded at the end of the section. Lemma 5. [36] F or the matrix B constructed at Step 2 of Algorithm 4, the following holds: 1. This is formally stated below.