[DB Seminar] Spring 2016: Pengtao Xie
Matrix-parametrized models, including multiclass logistic regression and sparse coding, are used in machine learning (ML) applications ranging from computer vision to computational biology. When these models are applied to large scale ML problems starting at millions of samples and tens of thousands of classes, their parameter matrix can grow at an unexpected rate, resulting in high parameter synchronization costs that greatly slow down distributed learning. To address this issue, we propose a Sufficient Factor (SF) abstraction for efficient distributed learning of a large family of matrix-parameterized models, which share the following property: the parameter update computed on each data sample is a rank-1 matrix, i.e. the outer product of two “sufficient factors” (SFs). Leveraging this property, both models and their updates are represented with sufficient factors, which can greatly reduce communication, computation and storage cost from quadratic to linear — without affecting computational correctness. We present a theoretical convergence analysis of SF abstraction, and empirically corroborate its efficiency on four different matrix-parametrized ML models.