Runtime: for a single \(t\in [T]\)  we invoke Alg. REF , and its runtime is \(O(nm^{1.5}\log (m/\varepsilon ))\)  (Lemma REF ), additionally \(\tau _{CP}\)  for the update. Multiplying this by \(T\)  we get a runtime of \(O( n m^{2.5}{\theta ^{-1}}\log ^2(m/\varepsilon )+\tau _{CP}m\theta ^{-1}\log (m/\varepsilon ) )\) .
Also, every call to the separation oracle for \(\mathcal {D}\)  takes \(O(m)\) 
which is negligible
compared to computing the gradient and value oracles.

Note that inside our algorithm we could use not only Vaidya's and Ellipsoid methods, but any other cutting plane scheme. For example, the faster cutting plane methods proposed by [1]}, [2]} can be used as well.
