  This paper addresses the following question: given a sample of i.i.d. random
variables with finite variance, can one construct an estimator of the unknown
mean that performs nearly as well as if the data were normally distributed? One
of the most popular examples achieving this goal is the median of means
estimator. However, it is inefficient in a sense that the constants in the
resulting bounds are suboptimal. We show that a permutation-invariant
modification of the median of means estimator admits deviation guarantees that
are sharp up to $1+o(1)$ factor if the underlying distribution possesses more
than $\frac{3+\sqrt{5}}{2}\approx 2.62$ moments and is absolutely continuous
with respect to the Lebesgue measure. This result yields potential improvements
for a variety of algorithms that rely on the median of means estimator as a
building block. At the core of our argument is are the new deviation
inequalities for the U-statistics of order that is allowed to grow with the
sample size, a result that could be of independent interest.
