  This article is devoted to one particular case of using universal accelerated
proximal envelopes to obtain computationally efficient accelerated versions of
methods used to solve various optimization problem setups. We propose a
proximally accelerated coordinate descent method that achieves the efficient
algorithmic complexity of iteration and allows taking advantage of the data
sparseness. It was considered an example of applying the proposed approach to
optimizing a SoftMax-like function, for which the described method allowing
weaken the dependence of the computational complexity on the dimension $n$ in
$\mathcal{O}(\sqrt{n})$ times and, in practice, demonstrates a faster
convergence in comparison with standard methods. As an example of applying the
proposed approach, it was shown a variant of obtaining on its basis some
efficient methods for optimizing Markov Decision Processes (MDP) in a minimax
formulation with a Nesterov smoothed target functional.
