where the exponent \(c_{q}\in(0,\infty)\) depends on \(\beta\) and the algorithm \(q\). For example, when \(q\) encodes the counting measure \(q_{T}(i):=n_{T}(i)/T\) (reminiscent of SGD), it was shown that \(c_{q}=(1-1/\beta)/2\in(0,1/2)\). Another algorithm \(q_{T}(i):=1[n_{T}(i)\geq 1]/\sum_{\ell}1[n_{T}(\ell)\geq 1]\) (reminiscent of ADAM ) was proposed which attains a optimal error rate (over all algorithms based on random embeddings) with \(c_{q}=\beta-1\).