A Omitted Proofs

In this section we include all of the proofs omitted from the main body. For the convenience of the reader, we will restate each claim before proceeding with its proof. A.1 Preliminary Proofs We commence with the proof of Proposition 1. Proposition 1. F or any η 0 and at all times t N, the OFTRL optimization problem on Line 3 of Algorithm 1 admits a unique optimal solution (λ Uniqueness follow immediately from strict convexity. In the rest of the proof we focus on the existence part. We start by showing that there exists a point x X whose coordinates are all strictly positive.