If I have an algorithm that on $T$ iterations gets me within $O(\log(T)/T)$ accuracy, what is a (preferably concise, closed form) lower bound on $T$ that gets me within $\epsilon$ accuracy?
In other words, $$T \geq g(\epsilon) \implies \frac{\log(T)}{T} \leq \epsilon.$$ Find $g(\epsilon)$.
For $\epsilon\leq 1/e$, $$T \geq e^{-W_{-1}(-\epsilon)}=-\epsilon^{-1}W_{-1}(-\epsilon)$$ where $W_{-1}$ is the second branch of the Lambert $W$ function. The Lambert $W$ functions are branches of the inverse of $f(z)=ze^z$.
It cannot be expressed in terms of elementary functions, so this is the best you can do.
Answer courtesy Wolfram Alpha.