Accelerated Stochastic Block Coordinate Gradient Descent for Sparsity Constrained Nonconvex Optimization

Jinghui Chen, Quanquan Gu
Proceedings of the 32nd Conference on Uncertainty in Artificial Intelligence, PMLR R14:524-533, 2016.

Abstract

We propose an accelerated stochastic block coordinate descent algorithm for nonconvex optimization under sparsity constraint in the high dimensional regime. At the core of our algorithm is leveraging both stochastic partial gradient and full partial gradient restricted to each coordinate block to accelerate the convergence. We prove that the algorithm converges to the unknown true parameter at a linear rate, up to the statistical error of the underlying model. Experiments on both synthetic and real datasets backup our theory.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR14-chen16a, title = {Accelerated Stochastic Block Coordinate Gradient Descent for Sparsity Constrained Nonconvex Optimization}, author = {Chen, Jinghui and Gu, Quanquan}, booktitle = {Proceedings of the 32nd Conference on Uncertainty in Artificial Intelligence}, pages = {524--533}, year = {2016}, editor = {Ihler, Alexander and Janzing, Dominik}, volume = {R14}, series = {Proceedings of Machine Learning Research}, month = {25--29 Jun}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r14/main/assets/chen16a/chen16a.pdf}, url = {https://proceedings.mlr.press/r14/chen16a.html}, abstract = {We propose an accelerated stochastic block coordinate descent algorithm for nonconvex optimization under sparsity constraint in the high dimensional regime. At the core of our algorithm is leveraging both stochastic partial gradient and full partial gradient restricted to each coordinate block to accelerate the convergence. We prove that the algorithm converges to the unknown true parameter at a linear rate, up to the statistical error of the underlying model. Experiments on both synthetic and real datasets backup our theory.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Accelerated Stochastic Block Coordinate Gradient Descent for Sparsity Constrained Nonconvex Optimization %A Jinghui Chen %A Quanquan Gu %B Proceedings of the 32nd Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2016 %E Alexander Ihler %E Dominik Janzing %F pmlr-vR14-chen16a %I PMLR %P 524--533 %U https://proceedings.mlr.press/r14/chen16a.html %V R14 %X We propose an accelerated stochastic block coordinate descent algorithm for nonconvex optimization under sparsity constraint in the high dimensional regime. At the core of our algorithm is leveraging both stochastic partial gradient and full partial gradient restricted to each coordinate block to accelerate the convergence. We prove that the algorithm converges to the unknown true parameter at a linear rate, up to the statistical error of the underlying model. Experiments on both synthetic and real datasets backup our theory. %Z Reissued by PMLR on 04 October 2026.
APA
Chen, J. & Gu, Q.. (2016). Accelerated Stochastic Block Coordinate Gradient Descent for Sparsity Constrained Nonconvex Optimization. Proceedings of the 32nd Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R14:524-533 Available from https://proceedings.mlr.press/r14/chen16a.html. Reissued by PMLR on 04 October 2026.

Related Material