Doubly Sparse Asynchronous Learning for Stochastic Composite Optimization

Doubly Sparse Asynchronous Learning for Stochastic Composite Optimization

Runxue Bao, Xidong Wu, Wenhan Xian, Heng Huang

Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence
Main Track. Pages 1916-1922. https://doi.org/10.24963/ijcai.2022/266

Parallel optimization has become popular for large-scale learning in the past decades. However, existing methods suffer from huge computational costs, memory usage, and communication burden in high-dimensional scenarios. To address the challenges, we propose a new accelerated doubly sparse asynchronous learning (DSAL) method for stochastic composite optimization, under which two algorithms are proposed on shared-memory and distributed-memory architecture respectively, which only conducts gradient descent on the nonzero coordinates (data sparsity) and active set (model sparsity). The proposed algorithm can converge much faster and achieve significant speedup by simultaneously enjoying the sparsity of the model and data. Moreover, by sending the gradients on the active set only, communication costs are dramatically reduced. Theoretically, we prove that the proposed method achieves the linear convergence rate with lower overall complexity and can achieve the model identification in a finite number of iterations almost surely. Finally, extensive experimental results on benchmark datasets confirm the superiority of our proposed method.
Keywords:
Data Mining: Big Data and Scalability
Data Mining: Parallel, Distributed and Cloud-based High Performance Mining
Machine Learning: Optimisation
Machine Learning: Feature Extraction, Selection and Dimensionality Reduction