  We develop an algorithm for parameter-free stochastic convex optimization
(SCO) whose rate of convergence is only a double-logarithmic factor larger than
the optimal rate for the corresponding known-parameter setting. In contrast,
the best previously known rates for parameter-free SCO are based on online
parameter-free regret bounds, which contain unavoidable excess logarithmic
terms compared to their known-parameter counterparts. Our algorithm is
conceptually simple, has high-probability guarantees, and is also partially
adaptive to unknown gradient norms, smoothness, and strong convexity. At the
heart of our results is a novel parameter-free certificate for SGD step size
choice, and a time-uniform concentration result that assumes no a-priori bounds
on SGD iterates.
