# Item

ITEM ACTIONSEXPORT

Released

Paper

#### A Unified Approach to Analyzing Asynchronous Coordinate Descent and Tatonnement

##### External Resource

No external resources are shared

##### Fulltext (restricted access)

There are currently no full texts shared for your IP range.

##### Fulltext (public)

1612.09171.pdf

(Preprint), 510KB

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Cheung, Y. K., & Cole, R. (2016). A Unified Approach to Analyzing Asynchronous Coordinate Descent and Tatonnement. Retrieved from http://arxiv.org/abs/1612.09171.

Cite as: https://hdl.handle.net/11858/00-001M-0000-002C-5014-A

##### Abstract

This paper concerns asynchrony in iterative processes, focusing on gradient

descent and tatonnement, a fundamental price dynamic.

Gradient descent is an important class of iterative algorithms for minimizing

convex functions. Classically, gradient descent has been a sequential and

synchronous process, although distributed and asynchronous variants have been

studied since the 1980s. Coordinate descent is a commonly studied version of

gradient descent. In this paper, we focus on asynchronous coordinate descent on

convex 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 a

smooth convex function, and each $\Psi_k:\mathbb{R}\rightarrow\mathbb{R}$ is a

univariate and possibly non-smooth convex function. Such functions occur in

many data analysis and machine learning problems.

We give new analyses of cyclic coordinate descent, a parallel asynchronous

stochastic coordinate descent, and a rather general worst-case parallel

asynchronous coordinate descent. For all of these, we either obtain sharply

improved bounds, or provide the first analyses. Our analyses all use a common

amortized framework. The application of this framework to the asynchronous

stochastic version requires some new ideas, for it is not obvious how to ensure

a uniform distribution where it is needed in the face of asynchronous actions

that may undo uniformity. We believe that our approach may well be applicable

to 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 or

Leontief utilities, for which tatonnement is equivalent to coordinate descent.

descent and tatonnement, a fundamental price dynamic.

Gradient descent is an important class of iterative algorithms for minimizing

convex functions. Classically, gradient descent has been a sequential and

synchronous process, although distributed and asynchronous variants have been

studied since the 1980s. Coordinate descent is a commonly studied version of

gradient descent. In this paper, we focus on asynchronous coordinate descent on

convex 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 a

smooth convex function, and each $\Psi_k:\mathbb{R}\rightarrow\mathbb{R}$ is a

univariate and possibly non-smooth convex function. Such functions occur in

many data analysis and machine learning problems.

We give new analyses of cyclic coordinate descent, a parallel asynchronous

stochastic coordinate descent, and a rather general worst-case parallel

asynchronous coordinate descent. For all of these, we either obtain sharply

improved bounds, or provide the first analyses. Our analyses all use a common

amortized framework. The application of this framework to the asynchronous

stochastic version requires some new ideas, for it is not obvious how to ensure

a uniform distribution where it is needed in the face of asynchronous actions

that may undo uniformity. We believe that our approach may well be applicable

to 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 or

Leontief utilities, for which tatonnement is equivalent to coordinate descent.