Finally, for all \(q\in (1,2]\)  the Bregman projection in Eq. (REF ) (Line 6 in Algorithm REF ) involves solving a convex optimization problem, in general. For the OGD Algorithm however (\(q=2\) ) the projection becomes Euclidean, and can be performed in \(\operatorname{\mathcal {O}}\left(N^2\right)\)  steps, using the projection algorithm by Wang and Lu [1]}. Specifically when \(\frac{R}{h} = 1\) , only a single component of state is updated at each iteration, and Paschos et al. [2]} provide an algorithm that performs the projection in \(\operatorname{\mathcal {O}}\left(N\right)\)  time.The projection algorithm presented in [2]} requires an extra sorting operation before the projection, yielding a total complexity of \(\operatorname{\mathcal {O}}\left(N \log (N)\right)\)  per iteration. However, sorting can be replaced by a \(\operatorname{\mathcal {O}}\left(\log (N)\right)\)  binary search and insertion, which reduces the complexity to \(\operatorname{\mathcal {O}}\left(N\right)\)  per iteration.
