English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We propose a new primal-dual homotopy smoothing algorithm for a linearlyconstrained convex program, where neither the primal nor the dual function hasto be smooth or strongly convex. The best known iteration complexity solvingsuch a non-smooth problem is $\mathcal{O}(\varepsilon^{-1})$. In this paper, weshow that by leveraging a local error bound condition on the dual function, theproposed algorithm can achieve a better primal convergence time of$\mathcal{O}\left(\varepsilon^{-2/(2+\beta)}\log_2(\varepsilon^{-1})\right)$,where $\beta\in(0,1]$ is a local error bound parameter. As an exampleapplication of the general algorithm, we show that the distributed geometricmedian problem, which can be formulated as a constrained convex program, hasits dual function non-smooth but satisfying the aforementioned local errorbound condition with $\beta=1/2$, therefore enjoying a convergence time of$\mathcal{O}\left(\varepsilon^{-4/5}\log_2(\varepsilon^{-1})\right)$. Thisresult improves upon the $\mathcal{O}(\varepsilon^{-1})$ convergence time boundachieved by existing distributed optimization algorithms. Simulationexperiments also demonstrate the performance of our proposed algorithm.

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