English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
 
 
DownloadE-Mail
  A Unified Approach to Analyzing Asynchronous Coordinate Descent and Tatonnement

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

Item is

Files

show Files
hide Files
:
1612.09171.pdf (Preprint), 510KB
Name:
1612.09171.pdf
Description:
File downloaded from arXiv at 2017-01-31 08:48
OA-Status:
Visibility:
Public
MIME-Type / Checksum:
application/pdf / [MD5]
Technical Metadata:
Copyright Date:
-
Copyright Info:
-

Locators

show

Creators

show
hide
 Creators:
Cheung, Yun Kuen1, Author           
Cole, Richard2, Author
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              
2External Organizations, ou_persistent22              

Content

show
hide
Free keywords: Mathematics, Optimization and Control, math.OC,Computer Science, Data Structures and Algorithms, cs.DS,Computer Science, Computer Science and Game Theory, cs.GT,Mathematics, Dynamical Systems, math.DS
 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.

Details

show
hide
Language(s): eng - English
 Dates: 2016-12-292016
 Publication Status: Published online
 Pages: 41 pages
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: arXiv: 1612.09171
URI: http://arxiv.org/abs/1612.09171
BibTex Citekey: Cheungarxiv16
 Degree: -

Event

show

Legal Case

show

Project information

show

Source

show