New method gives high confidence bounds for stochastic convex optimization with minimal overhead.
problem Rare high probability guarantees in stochastic convex optimization.
method ProxBoost algorithm combining robust distance estimation and proximal point method.
result Wide class of stochastic optimization algorithms can achieve high confidence bounds with logarithmic and polylogarithmic overhead.