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

This paper concerns asynchrony in iterative processes, focusing on gradientdescent and tatonnement, a fundamental price dynamic.  Gradient descent is an important class of iterative algorithms for minimizingconvex functions. Classically, gradient descent has been a sequential andsynchronous process, although distributed and asynchronous variants have beenstudied since the 1980s. Coordinate descent is a commonly studied version ofgradient descent. In this paper, we focus on asynchronous coordinate descent onconvex functions $F:\mathbb{R}^n\rightarrow\mathbb{R}$ of the form $F(x) = f(x)+ \sum_{k=1}^n \Psi_k(x_k)$, where $f:\mathbb{R}^n\rightarrow\mathbb{R}$ is asmooth convex function, and each $\Psi_k:\mathbb{R}\rightarrow\mathbb{R}$ is aunivariate and possibly non-smooth convex function. Such functions occur inmany data analysis and machine learning problems.  We give new analyses of cyclic coordinate descent, a parallel asynchronousstochastic coordinate descent, and a rather general worst-case parallelasynchronous coordinate descent. For all of these, we either obtain sharplyimproved bounds, or provide the first analyses. Our analyses all use a commonamortized framework. The application of this framework to the asynchronousstochastic version requires some new ideas, for it is not obvious how to ensurea uniform distribution where it is needed in the face of asynchronous actionsthat may undo uniformity. We believe that our approach may well be applicableto the analysis of other iterative asynchronous stochastic processes.  We extend the framework to show that an asynchronous version of tatonnement,a fundamental price dynamic widely studied in general equilibrium theory,converges toward a market equilibrium for Fisher markets with CES utilities orLeontief utilities, for which tatonnement is equivalent to coordinate descent.

A Unified Approach to Analyzing Asynchronous Coordinate Descent and Tatonnement