Solving Non-smooth Constrained Programs with Lower Complexity than O(1/ε): A Primal-Dual Homotopy Smoothing Approach

09/05/2018
by   Xiaohan Wei, et al.
0

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 O(ε^-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 O(ε^-2/(2+β)_2(ε^-1)), where β∈(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 β=1/2, therefore enjoying a convergence time of O(ε^-4/5_2(ε^-1)). This result improves upon the O(ε^-1) convergence time bound achieved by existing distributed optimization algorithms. Simulation experiments also demonstrate the performance of our proposed algorithm.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset