Computational Efficiency. The subroutine \(\mathbf {\mathsf {JohnEllpsoidCenter}}(\mathcal {W}_{t+1})\)  can be run in time polynomial in \(T\)  and \(d\)  by solving a Semi-definite Program (SDP) [1]}, [2]}. Note that we change our predictor \(f_t\)  only at the times \(t\)  that we make a mistake; thus, the number of calls to the SDP is also logarithmic in \(T\) .
