  In this paper, we develop a novel {\bf ho}moto{\bf p}y {\bf s}moothing (HOPS)
algorithm for solving a family of non-smooth problems that is composed of a
non-smooth term with an explicit max-structure and a smooth term or a simple
non-smooth term whose proximal mapping is easy to compute. The best known
iteration complexity for solving such non-smooth optimization problems is
$O(1/\epsilon)$ without any assumption on the strong convexity. In this work,
we will show that the proposed HOPS achieved a lower iteration complexity of
$\widetilde O(1/\epsilon^{1-\theta})$\footnote{$\widetilde O()$ suppresses a
logarithmic factor.} with $\theta\in(0,1]$ capturing the local sharpness of the
objective function around the optimal solutions. To the best of our knowledge,
this is the lowest iteration complexity achieved so far for the considered
non-smooth optimization problems without strong convexity assumption. The HOPS
algorithm employs Nesterov's smoothing technique and Nesterov's accelerated
gradient method and runs in stages, which gradually decreases the smoothing
parameter in a stage-wise manner until it yields a sufficiently good
approximation of the original function. We show that HOPS enjoys a linear
convergence for many well-known non-smooth problems (e.g., empirical risk
minimization with a piece-wise linear loss function and $\ell_1$ norm
regularizer, finding a point in a polyhedron, cone programming, etc).
Experimental results verify the effectiveness of HOPS in comparison with
Nesterov's smoothing algorithm and the primal-dual style of first-order
methods.
