Stochastic Block-Coordinate Gradient Projection Algorithms for Submodular Maximization
Joint Authors
Wu, Qingtao
Zheng, Ruijuan
Zhang, Mingchuan
Zhu, Junlong
Li, Zhigang
Zhang, Qikun
Source
Issue
Vol. 2018, Issue 2018 (31 Dec. 2018), pp.1-11, 11 p.
Publisher
Hindawi Publishing Corporation
Publication Date
2018-12-05
Country of Publication
Egypt
No. of Pages
11
Main Subjects
Abstract EN
We consider a stochastic continuous submodular huge-scale optimization problem, which arises naturally in many applications such as machine learning.
Due to high-dimensional data, the computation of the whole gradient vector can become prohibitively expensive.
To reduce the complexity and memory requirements, we propose a stochastic block-coordinate gradient projection algorithm for maximizing continuous submodular functions, which chooses a random subset of gradient vector and updates the estimates along the positive gradient direction.
We prove that the estimates of all nodes generated by the algorithm converge to some stationary points with probability 1.
Moreover, we show that the proposed algorithm achieves the tight (pmin/2F⁎-ϵ) approximation guarantee after O(1/ϵ2) iterations for DR-submodular functions by choosing appropriate step sizes.
Furthermore, we also show that the algorithm achieves the tight (γ2/1+γ2pminF⁎-ϵ) approximation guarantee after O(1/ϵ2) iterations for weakly DR-submodular functions with parameter γ by choosing diminishing step sizes.
American Psychological Association (APA)
Li, Zhigang& Zhang, Mingchuan& Zhu, Junlong& Zheng, Ruijuan& Zhang, Qikun& Wu, Qingtao. 2018. Stochastic Block-Coordinate Gradient Projection Algorithms for Submodular Maximization. Complexity،Vol. 2018, no. 2018, pp.1-11.
https://search.emarefa.net/detail/BIM-1133310
Modern Language Association (MLA)
Li, Zhigang…[et al.]. Stochastic Block-Coordinate Gradient Projection Algorithms for Submodular Maximization. Complexity No. 2018 (2018), pp.1-11.
https://search.emarefa.net/detail/BIM-1133310
American Medical Association (AMA)
Li, Zhigang& Zhang, Mingchuan& Zhu, Junlong& Zheng, Ruijuan& Zhang, Qikun& Wu, Qingtao. Stochastic Block-Coordinate Gradient Projection Algorithms for Submodular Maximization. Complexity. 2018. Vol. 2018, no. 2018, pp.1-11.
https://search.emarefa.net/detail/BIM-1133310
Data Type
Journal Articles
Language
English
Notes
Includes bibliographical references
Record ID
BIM-1133310