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

Abstract

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}({\epsilon }^{-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({\epsilon }^{-2/(2+\beta )}{\log }_2({\epsilon }^{-1})\right)$, where $\beta \in (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({\epsilon }^{-4/5}{\log }_2({\epsilon }^{-1})\right)$. This result improves upon the $\mathcal{O}({\epsilon }^{-1})$ convergence time bound achieved by existing distributed optimization algorithms. Simulation experiments also demonstrate the performance of our proposed algorithm.

arXiv commentin NIPS 2018, Montreal, Canada

Cited by in corpus (2)

• Inexact Proximal-Point Penalty Methods for Constrained Non-Convex Optimization
• Fast Multi-Agent Temporal-Difference Learning via Homotopy Stochastic Primal-Dual Optimization