Randomized block-coordinate adaptive algorithms for nonconvex optimization problems

Zhou, Yangfan; Huang, Kaizhu; Li, Jiang; Cheng, Cheng; Wang, Xuguang; Hussian, Amir; Liu, Xin

Abstract

Nonconvex optimization problems have always been one focus in deep learning, in which many fast adaptive algorithms based on momentum are applied. However, the full gradient computation of high-dimensional feature vector in the above tasks become prohibitive. To reduce the computation cost for optimizers on nonconvex optimization problems typically seen in deep learning, this work proposes a randomized block-coordinate adaptive optimization algorithm, named RAda, which randomly picks a block from the full coordinates of the parameter vector and then sparsely computes its gradient. We prove that RAda converges to a -accurate solution with the stochastic first-order complexity of , where is the upper bound of the gradient’s square, under nonconvex cases. Experiments on public datasets including CIFAR-10, CIFAR-100, and Penn TreeBank, verify that RAda outperforms the other compared algorithms in terms of the computational cost.

• Journal Article Type: Article
• Acceptance Date: Feb 5, 2023
• Online Publication Date: Feb 11, 2023
• Publication Date: 2023-05
• Deposit Date: Feb 13, 2023
• Publicly Available Date: Feb 12, 2024
• Journal: Engineering Applications of Artificial Intelligence
• Print ISSN: 0952-1976
• Publisher: Elsevier
• Peer Reviewed: Peer Reviewed
• Volume: 121
• Article Number: 105968
• DOI: https://doi.org/10.1016/j.engappai.2023.105968