Homotopy Smoothing for Non-Smooth Problems with Lower Complexity than O(1/ɛ)

In this paper, we develop a novel homotopy smoothing (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/ɛ) without any assumption on the strong convexity.