  We provide improved convergence rates for various \emph{non-smooth}
optimization problems via higher-order accelerated methods. In the case of
$\ell_\infty$ regression, we achieves an $O(\epsilon^{-4/5})$ iteration
complexity, breaking the $O(\epsilon^{-1})$ barrier so far present for previous
methods. We arrive at a similar rate for the problem of $\ell_1$-SVM, going
beyond what is attainable by first-order methods with prox-oracle access for
non-smooth non-strongly convex problems. We further show how to achieve even
faster rates by introducing higher-order regularization.
  Our results rely on recent advances in near-optimal accelerated methods for
higher-order smooth convex optimization. In particular, we extend Nesterov's
smoothing technique to show that the standard softmax approximation is not only
smooth in the usual sense, but also \emph{higher-order} smooth. With this
observation in hand, we provide the first example of higher-order acceleration
techniques yielding faster rates for \emph{non-smooth} optimization, to the
best of our knowledge.
