Let us assume that an optimization algorithm requires $\mathcal{O}(n^{\log1/\epsilon})$ flops to find a solution $\bar{X}$ such that $$\| \bar{X} - X^{\star}\| \leq \epsilon$$ where $\epsilon < 1$ and $X^{\star}$ is the true optimum point.
What kind of algorithm is this? Can it be considered polynomial?
It is a polynomial-time approximation scheme (see Polynomial-time Approximation Scheme). This can be seen since when you fix $\epsilon$, the running time is polynomial in $n$. It is however no FPTAS, since this would require that its running time is in $O((n/\epsilon)^C)$ for some fixed constant $C$ (see this post).
