Stochastic block-coordinate gradient projection algorithms for submodular maximization
type: Item
instance of: scholarly article
title: Stochastic block-coordinate gradient projection algorithms for submodular maximization
zbMATH Open document ID: 1407.90276
DOI: 10.1155/2018/2609471
author: Zhigang Li
author: Mingchuan Zhang
author: Junlong Zhu
author: Ruijuan Zheng
author: Qikun Zhang
author: Qingtao Wu
published in: Complexity
publication date: 2019-02-19T00:00:00Z
review text: Summary: 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_{\min}/2)F^\ast -\epsilon)\) approximation guarantee after \(O(1/\epsilon^2)\) iterations for DR-submodular functions by choosing appropriate step sizes. Furthermore, we also show that the algorithm achieves the tight \(((\gamma^2/(1+\gamma^2)) p_{\min} F^\ast -\epsilon)\) approximation guarantee after \(O(1/\epsilon^2)\) iterations for weakly DR-submodular functions with parameter \(\gamma\) by choosing diminishing step sizes.
Mathematics Subject Classification ID: 90C27
Mathematics Subject Classification ID: 90C59
zbMATH DE Number: 7025145
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.1155/2018/2609471
OpenAlex ID: W2903318095
cites work: Q3112637
cites work: Submodular Utility Maximization for Deadline Constrained Data Collection in Sensor Networks
cites work: A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions
cites work: A faster strongly polynomial time algorithm for submodular function minimization
cites work: A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
cites work: Exceptional Paper—Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate Algorithms
cites work: An analysis of approximations for maximizing submodular set functions—I
cites work: Q4196269
cites work: Maximizing Non-monotone Submodular Functions
cites work: Submodular Function Maximization via the Multilinear Relaxation and Contention Resolution Schemes
cites work: Maximizing a Monotone Submodular Function Subject to a Matroid Constraint
cites work: Submodular functions: from discrete to continuous domains
cites work: Q3151174
cites work: Q3096154
cites work: Accelerated block-coordinate relaxation for regularized optimization
cites work: A coordinate gradient descent method for nonsmooth separable minimization
cites work: Block-coordinate gradient descent method for linearly constrained nonsmooth separable optimization
cites work: A coordinate gradient descent method for \(\ell_{1}\)-regularized convex minimization
cites work: Coordinate descent algorithms for lasso penalized regression
cites work: Coordinate descent optimization for \(l^{1}\) minimization with application to compressed sensing; a greedy algorithm
cites work: On the convergence of the coordinate descent method for convex differentiable minimization
cites work: Convergence of a block coordinate descent method for nondifferentiable minimization
cites work: Q2934047
cites work: Efficiency of coordinate descent methods on huge-scale optimization problems
cites work: Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function
cites work: On the complexity analysis of randomized block-coordinate descent methods
cites work: An Asynchronous Parallel Stochastic Coordinate Descent Algorithm
cites work: Asynchronous Stochastic Coordinate Descent: Parallelism and Convergence Properties
cites work: Submodular functions and optimization.
cites work: On Multiplicative Weight Updates for Concave and Submodular Function Maximization
cites work: Submodular function maximization via the multilinear relaxation and contention resolution schemes
Wikidata QID: Q128813625
description: scientific article; zbMATH DE number 7025145