Stochastic Block-Coordinate Gradient Projection Algorithms for Submodular Maximization

Zhigang Li, Mingchuan Zhang, Junlong Zhu, Ruijuan Zheng, Qikun Zhang and Qingtao Wu

Complexity, 2018, vol. 2018, 1-11

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 approximation guarantee after iterations for DR-submodular functions by choosing appropriate step sizes. Furthermore, we also show that the algorithm achieves the tight approximation guarantee after iterations for weakly DR-submodular functions with parameter by choosing diminishing step sizes.

Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://downloads.hindawi.com/journals/8503/2018/2609471.pdf (application/pdf)
http://downloads.hindawi.com/journals/8503/2018/2609471.xml (text/xml)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hin:complx:2609471

DOI: 10.1155/2018/2609471

Access Statistics for this article

More articles in Complexity from Hindawi
Bibliographic data for series maintained by Mohamed Abdelhakeem ().