Solving Non-smooth Constrained Programs with Lower Complexity than $mathcal{O}(1/varepsilon)$: A Primal-Dual Homotopy Smoothing Approach

We propose a new primal-dual homotopy smoothing algorithm for a linearly constrained convex program, where neither the primal nor the dual function has to be smooth or strongly convex. The best known iteration complexity solving such a non-smooth problem is $mathcal{O}(varepsilon^{-1})$. In this paper, we show that by leveraging a local error bound condition on the dual function, the proposed algorithm can achieve a better primal convergence time of $mathcal{O}left(varepsilon^{-2/(2+beta)}log_2(varepsilon^{-1})right)$, where $betain(0,1]$ is a local error bound parameter. As an example application of the general algorithm, we show that the distributed geometric median problem, which can be formulated as a constrained convex program, has its dual function non-smooth but satisfying the aforementioned local error bound condition with $beta=1/2$, therefore enjoying a convergence time of $mathcal{O}left(varepsilon^{-4/5}log_2(varepsilon^{-1})right)$. This result improves upon the $mathcal{O}(varepsilon^{-1})$ convergence time bound achieved by existing distributed optimization algorithms. Simulation experiments also demonstrate the performance of our proposed algorithm.