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

In this paper we show how to accelerate randomized coordinate descent methodsand achieve faster convergence rates without paying per-iteration costs inasymptotic running time. In particular, we show how to generalize andefficiently implement a method proposed by Nesterov, giving faster asymptoticrunning times for various algorithms that use standard coordinate descent as ablack box. In addition to providing a proof of convergence for this new generalmethod, we show that it is numerically stable, efficiently implementable, andin certain regimes, asymptotically optimal.  To highlight the computational power of this algorithm, we show how it canused to create faster linear system solvers in several regimes:  - We show how this method achieves a faster asymptotic runtime than conjugategradient for solving a broad class of symmetric positive definite systems ofequations.  - We improve the best known asymptotic convergence guarantees for Kaczmarzmethods, a popular technique for image reconstruction and solvingoverdetermined systems of equations, by accelerating a randomized algorithm ofStrohmer and Vershynin.  - We achieve the best known running time for solving Symmetric DiagonallyDominant (SDD) system of equations in the unit-cost RAM model, obtaining an O(mlog^{3/2} n (log log n)^{1/2} log (log n / eps)) asymptotic running time byaccelerating a recent solver by Kelner et al.  Beyond the independent interest of these solvers, we believe they highlightthe versatility of the approach of this paper and we hope that they will openthe door for further algorithmic improvements in the future.

Efficient Accelerated Coordinate Descent Methods and Faster Algorithms for Solving Linear Systems