  Standard results in stochastic convex optimization bound the number of
samples that an algorithm needs to generate a point with small function value
in expectation. More nuanced high probability guarantees are rare, and
typically either rely on "light-tail" noise assumptions or exhibit worse sample
complexity. In this work, we show that a wide class of stochastic optimization
algorithms for strongly convex problems can be augmented with high confidence
bounds at an overhead cost that is only logarithmic in the confidence level and
polylogarithmic in the condition number. The procedure we propose, called
proxBoost, is elementary and builds on two well-known ingredients: robust
distance estimation and the proximal point method. We discuss consequences for
both streaming (online) algorithms and offline algorithms based on empirical
risk minimization.
