Stochastic Block-Coordinate Gradient Projection Algorithms for Submodular Maximization. (5th December 2018)

• Record Type: Journal Article
• Authors: Li, Zhigang; Zhang, Mingchuan; Zhu, Junlong; Zheng, Ruijuan; Zhang, Qikun; Wu, Qingtao
• Other Names: Pratama Mahardhika Academic Editor.
• Is Part Of: Complexity. Volume 2018(2018)
• Publication Date: 2018-12-05
• Subjects: Chaotic behavior in systems -- Periodicals; Complexity (Philosophy) -- Periodicals; 003
• DOI: 10.1155/2018/2609471
• Languages: English
• ISSNs: 1076-2787

Abstract

Abstract : 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 ( p m i n / 2 F ⁎ - ϵ ) 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 + γ 2 p m i n F ⁎ - ϵ ) approximation guarantee after O ( 1 / ϵ 2 ) iterations for weakly DR-submodular functions with parameter γ by choosing diminishing step sizes.