Scaling Up Stochastic Dual Coordinate Ascent

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