Stochastic block-coordinate gradient projection algorithms for submodular maximization
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.
- Stochastic conditional gradient methods: from convex minimization to submodular maximization
- scientific article; zbMATH DE number 7255156
- An accelerated continuous greedy algorithm for maximizing strong submodular functions
- Stochastic conditional gradient++: (Non)convex minimization and continuous submodular maximization
- Stochastic-lazier-greedy algorithm for monotone non-submodular maximization
- A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
- A coordinate gradient descent method for \(\ell_{1}\)-regularized convex minimization
- A coordinate gradient descent method for nonsmooth separable minimization
- A faster strongly polynomial time algorithm for submodular function minimization
- Accelerated block-coordinate relaxation for regularized optimization
- Adaptive submodularity: theory and applications in active learning and stochastic optimization
- An analysis of approximations for maximizing submodular set functions—I
- An Asynchronous Parallel Stochastic Coordinate Descent Algorithm
- Asynchronous stochastic coordinate descent: parallelism and convergence properties
- Block-coordinate gradient descent method for linearly constrained nonsmooth separable optimization
- Convergence of a block coordinate descent method for nondifferentiable minimization
- Coordinate descent algorithms for lasso penalized regression
- Coordinate descent method for large-scale L2-loss linear support vector machines
- Coordinate descent optimization for \(l^{1}\) minimization with application to compressed sensing; a greedy algorithm
- Efficiency of coordinate descent methods on huge-scale optimization problems
- Exceptional Paper—Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate Algorithms
- scientific article; zbMATH DE number 6378119 (Why is no real title available?)
- scientific article; zbMATH DE number 1818892 (Why is no real title available?)
- scientific article; zbMATH DE number 3635849 (Why is no real title available?)
- Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function
- Maximizing a monotone submodular function subject to a matroid constraint
- Maximizing Non-monotone Submodular Functions
- On multiplicative weight updates for concave and submodular function maximization
- On the complexity analysis of randomized block-coordinate descent methods
- On the convergence of the coordinate descent method for convex differentiable minimization
- Submodular function maximization via the multilinear relaxation and contention resolution schemes
- Submodular function maximization via the multilinear relaxation and contention resolution schemes
- Submodular functions and optimization.
- Submodular functions: from discrete to continuous domains
- Submodular Utility Maximization for Deadline Constrained Data Collection in Sensor Networks
This page was built for publication: Stochastic block-coordinate gradient projection algorithms for submodular maximization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1723100)
