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

arXiv: https://arxiv.org/abs/1809.01275 · HTML: https://mlsanity.com/paper/1809.01275/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Sep 2018.

## Built on by (most cited first, 2 of 2)

- [Damped Proximal Augmented Lagrangian Method for weakly-Convex Problems with Convex Constraints](https://mlsanity.com/paper/2311.09065/) (2023)
- [Nonsmooth Projection-Free Optimization with Functional Constraints](https://mlsanity.com/paper/2311.11180/) (2023)

## Abstract (arXiv)

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(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 Oleft(varepsilon-2/(2+β)log2(varepsilon-1)right), 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 Oleft(varepsilon-4/5log2(varepsilon-1)right). This result improves upon the O(varepsilon-1) convergence time bound achieved by existing distributed optimization algorithms. Simulation experiments also demonstrate the performance of our proposed algorithm.