Distributed Inexact Newton-type Pursuit for Non-convex Sparse Learning

Bo Liu, Xiao-Tong Yuan, Lezi Wang, Qingshan Liu, Junzhou Huang, Dimitris N. Metaxas
Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, PMLR 89:343-352, 2019.

Abstract

In this paper, we present a sample distributed greedy pursuit method for non-convex sparse learning under cardinality constraint. Given the training samples uniformly randomly partitioned across multiple machines, the proposed method alternates between local inexact sparse minimization of a Newton-type approximation and centralized global results aggregation. Theoretical analysis shows that for a general class of convex functions with Lipschitze continues Hessian, the method converges linearly with contraction factor scaling inversely to the local data size; whilst the communication complexity required to reach desirable statistical accuracy scales logarithmically with respect to the number of machines for some popular statistical learning models. For nonconvex objective functions, up to a local estimation error, our method can be shown to converge to a local stationary sparse solution with sub-linear communication complexity. Numerical results demonstrate the efficiency and accuracy of our method when applied to large-scale sparse learning tasks including deep neural nets pruning

Cite this Paper

BibTeX
@InProceedings{pmlr-v89-liu19a, title = {Distributed Inexact Newton-type Pursuit for Non-convex Sparse Learning}, author = {Liu, Bo and Yuan, Xiao-Tong and Wang, Lezi and Liu, Qingshan and Huang, Junzhou and Metaxas, Dimitris N.}, booktitle = {Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics}, pages = {343--352}, year = {2019}, editor = {Chaudhuri, Kamalika and Sugiyama, Masashi}, volume = {89}, series = {Proceedings of Machine Learning Research}, month = {16--18 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v89/liu19a/liu19a.pdf}, url = {https://proceedings.mlr.press/v89/liu19a.html}, abstract = {In this paper, we present a sample distributed greedy pursuit method for non-convex sparse learning under cardinality constraint. Given the training samples uniformly randomly partitioned across multiple machines, the proposed method alternates between local inexact sparse minimization of a Newton-type approximation and centralized global results aggregation. Theoretical analysis shows that for a general class of convex functions with Lipschitze continues Hessian, the method converges linearly with contraction factor scaling inversely to the local data size; whilst the communication complexity required to reach desirable statistical accuracy scales logarithmically with respect to the number of machines for some popular statistical learning models. For nonconvex objective functions, up to a local estimation error, our method can be shown to converge to a local stationary sparse solution with sub-linear communication complexity. Numerical results demonstrate the efficiency and accuracy of our method when applied to large-scale sparse learning tasks including deep neural nets pruning} }
Endnote
%0 Conference Paper %T Distributed Inexact Newton-type Pursuit for Non-convex Sparse Learning %A Bo Liu %A Xiao-Tong Yuan %A Lezi Wang %A Qingshan Liu %A Junzhou Huang %A Dimitris N. Metaxas %B Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2019 %E Kamalika Chaudhuri %E Masashi Sugiyama %F pmlr-v89-liu19a %I PMLR %P 343--352 %U https://proceedings.mlr.press/v89/liu19a.html %V 89 %X In this paper, we present a sample distributed greedy pursuit method for non-convex sparse learning under cardinality constraint. Given the training samples uniformly randomly partitioned across multiple machines, the proposed method alternates between local inexact sparse minimization of a Newton-type approximation and centralized global results aggregation. Theoretical analysis shows that for a general class of convex functions with Lipschitze continues Hessian, the method converges linearly with contraction factor scaling inversely to the local data size; whilst the communication complexity required to reach desirable statistical accuracy scales logarithmically with respect to the number of machines for some popular statistical learning models. For nonconvex objective functions, up to a local estimation error, our method can be shown to converge to a local stationary sparse solution with sub-linear communication complexity. Numerical results demonstrate the efficiency and accuracy of our method when applied to large-scale sparse learning tasks including deep neural nets pruning
APA
Liu, B., Yuan, X., Wang, L., Liu, Q., Huang, J. & Metaxas, D.N.. (2019). Distributed Inexact Newton-type Pursuit for Non-convex Sparse Learning. Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 89:343-352 Available from https://proceedings.mlr.press/v89/liu19a.html.

Related Material