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

Dual first-order methods are essential techniques for large-scale constrainedconvex optimization. However, when recovering the primal solutions, we need$T(\epsilon^{-2})$ iterations to achieve an $\epsilon$-optimal primal solutionwhen we apply an algorithm to the non-strongly convex dual problem with$T(\epsilon^{-1})$ iterations to achieve an $\epsilon$-optimal dual solution,where $T(x)$ can be $x$ or $\sqrt{x}$. In this paper, we prove that theiteration complexity of the primal solutions and dual solutions have the same$O\left(\frac{1}{\sqrt{\epsilon}}\right)$ order of magnitude for theaccelerated randomized dual coordinate ascent. When the dual function furthersatisfies the quadratic functional growth condition, by restarting thealgorithm at any period, we establish the linear iteration complexity for boththe primal solutions and dual solutions even if the condition number isunknown. When applied to the regularized empirical risk minimization problem,we prove the iteration complexity of $O\left(n\logn+\sqrt{\frac{n}{\epsilon}}\right)$ in both primal space and dual space, where$n$ is the number of samples. Our result takes out the $\left(\log\frac{1}{\epsilon}\right)$ factor compared with the methods based onsmoothing/regularization or Catalyst reduction. As far as we know, this is thefirst time that the optimal $O\left(\sqrt{\frac{n}{\epsilon}}\right)$ iterationcomplexity in the primal space is established for the dual coordinate ascentbased stochastic algorithms. We also establish the accelerated linearcomplexity for some problems with nonsmooth loss, i.e., the least absolutedeviation and SVM.

On the Complexity Analysis of the Primal Solutions for the Accelerated Randomized Dual Coordinate Ascent