  Concentration inequalities for the sample mean, like those due to Bernstein
and Hoeffding, are valid for any sample size but overly conservative, yielding
confidence intervals that are unnecessarily wide. The central limit theorem
(CLT) provides asymptotic confidence intervals with optimal width, but these
are invalid for all sample sizes. To resolve this tension, we develop new
computable concentration inequalities with asymptotically optimal size,
finite-sample validity, and sub-Gaussian decay. These bounds enable the
construction of efficient confidence intervals with correct coverage for any
sample size and efficient empirical Berry-Esseen bounds that require no prior
knowledge of the population variance. We derive our inequalities by tightly
bounding non-uniform Kolmogorov and Wasserstein distances to a Gaussian using
zero-bias couplings and Stein's method of exchangeable pairs.
