高效且穩定收斂的平行非同步隨機對偶座標梯度下降演算法

Parallel Asynchronous Stochastic Dual Coordinate Descent Algorithms for High Efficiency and Stable Convergence

陳勇辰(Yung-Chen Chen)

指導教授 ： 劉邦鋒

國立臺灣大學/電機資訊學院/資訊網路與多媒體研究所/碩士(2020年)

https://doi.org/10.6342/NTU202003062

摘要

平行非同步隨機對偶座標梯度下降演算法(PASSCoDe)是一種用於在單台多核心且共用記憶體的機器上訓練線性模型的演算法。 當執行緒的數目小於8時，PASSCoDe在稀疏資料集(非零項所佔的比例很低的資料集)上有著十分良好的加速。 但是因為記憶體的衝突及延遲參數存取的因素，PASSCoDe時常無法收斂到和循序隨機對偶座標梯度下降演算法相同的準確度或是無法收斂。 在此篇論文中，我們提出了兩個演算法 - 適應性混合算法及惰性同步算法以克服平行算法無法收斂的議題。實驗結果指出，我們所提出的兩個演算法在所有資料集中皆可以收斂至和循序隨機對偶座標梯度下降演算法相同的準確度除了一個極小的資料集例外。相比之下PASSCoDe收斂至一個較差的準確度或是不收斂。我們所提出的演算法在收斂的穩定度、執行時間和可擴展性上超越了PASSCoDe的一個改進過後的版本PASSCoDe-Fix.

關鍵字

機器學習 ； 平行對偶座標梯度下降算法 ； 非同步算法 ； 線性模型 ； 支撐向量機

並列摘要

Parallel asynchronous stochastic dual coordinate descent algorithm (PASSCoDe) is an efficient method to train linear models in multi-core shared-memory systems.
PASSCoDe enjoys a good speedup when the number of threads is less than 8 on sparse datasets, i.e., the percentage of nonzero elements in the training data is relatively small. However, due to the memory conflict and delayed parameter access problem in parallel execution, it often diverges or does not converge to the best accuracy as a serial dual coordinate descent algorithm does. In this paper, we proposed two algorithms - Adaptive Hybrid algorithm and Lazy-Sync algorithm, to overcome the convergence issues in parallel execution. Experiment results indicate that both algorithms converge to the same high accuracy as a sequential program does on all datasets we tested, except on one extremely small dataset.
On the other hand, PASSCoDe sometimes converges to a less accurate value or does not converge at all on some datasets.
Our methods also outperform PASSCoDe-Fix, an improved version of PASSCoDe, in stable convergence, execution speed, and scalability.

並列關鍵字

machine learning ； parallel dual coordinate descent ； asynchronous algorithm ； linear model ； support vector machine

參考文獻

[1] Libsvm – a library for support vector machines. https://www.csie.ntu.edu.tw/~cjlin/libsvm/.

[2] V. Abeykoon, G. Fox, and M. Kim. Performance optimization on model synchronization in parallel stochastic gradient descent based svm. arXiv preprint arXiv:1905.01219, 2019.

[3] L. Besacier, E. Barnard, A. Karpov, and T. Schultz. Automatic speech recognition for under-resourced languages: A survey. Speech Communication, 56:85–100, 2014.

[4] C. J. Burges. A tutorial on support vector machines for pattern recognition. Data mining and knowledge discovery, 2(2):121–167, 1998.

[5] Y. Chen, X. S. Zhou, and T. S. Huang. One-class svm for learning in image retrieval. In Proceedings 2001 International Conference on Image Processing (Cat. No. 01CH37205), volume 1, pages 34–37. IEEE, 2001.