2015 ScalingUpStochasticDualCoordina

• (Tran et al., 2015) ⇒ Kenneth Tran, Saghar Hosseini, Lin Xiao, Thomas Finley, and Mikhail Bilenko. (2015). “Scaling Up Stochastic Dual Coordinate Ascent.” In: Proceedings of the 21st ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2015). ISBN:978-1-4503-3664-2 doi:10.1145/2783258.2783412

Subject Headings:

Cited By

• http://scholar.google.com/scholar?q=%222015%22+Scaling+Up+Stochastic+Dual+Coordinate+Ascent
• http://dl.acm.org/citation.cfm?id=2783258.2783412&preflayout=flat#citedby

Quotes

Author Keywords

• General

Abstract

Stochastic Dual Coordinate Ascent (SDCA) has recently emerged as a state-of-the-art method for solving large-scale supervised learning problems formulated as minimization of convex loss functions. It performs iterative, random-coordinate updates to maximize the dual objective. Due to the sequential nature of the iterations, it is typically implemented as a single-threaded algorithm limited to in-memory datasets. In this paper, we introduce an asynchronous parallel version of the algorithm, analyze its convergence properties, and propose a solution for primal-dual synchronization required to achieve convergence in practice. In addition, we describe a method for scaling the algorithm to out-of-memory datasets via multi-threaded deserialization of block-compressed data. This approach yields sufficient pseudo-randomness to provide the same convergence rate as random-order in-memory access. Empirical evaluation demonstrates the efficiency of the proposed methods and their ability to fully utilize computational resources and scale to out-of-memory datasets.

References

;

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2015 ScalingUpStochasticDualCoordina	Mikhail Bilenko Kenneth Tran Saghar Hosseini Lin Xiao Thomas Finley			Scaling Up Stochastic Dual Coordinate Ascent				10.1145/2783258.2783412		2015