Dynamic Stepsize Techniques in DR-Submodular Maximization

Yanfei Li, Min Li, Qian Liu and Yang Zhou ()
Additional contact information
Yanfei Li: School of Mathematics and Statistics, Shandong Normal University, Jinan 250014, China
Min Li: School of Mathematics and Statistics, Shandong Normal University, Jinan 250014, China
Qian Liu: School of Mathematics and Statistics, Shandong Normal University, Jinan 250014, China
Yang Zhou: School of Mathematics and Statistics, Shandong Normal University, Jinan 250014, China

Mathematics, 2025, vol. 13, issue 9, 1-31

Abstract: The Diminishing-Return (DR)-submodular function maximization problem has garnered significant attention across various domains in recent years. Classic methods often employ continuous greedy or Frank–Wolfe approaches to tackle this problem; however, high iteration and subproblem solver complexity are typically required to control the approximation ratio effectively. In this paper, we introduce a strategy that employs a binary search to find the dynamic stepsize, integrating it into traditional algorithm frameworks to address problems with different constraint types. We demonstrate that algorithms using this dynamic stepsize strategy can achieve comparable approximation ratios to those using a fixed stepsize strategy. In the monotone case, the iteration complexity is O ∥ ∇ F ( 0 ) ∥ 1 ϵ − 1 , while in the non-monotone scenario, it is O n + ∥ ∇ F ( 0 ) ∥ 1 ϵ − 1 , where F denotes the objective function. We then apply this strategy to solving stochastic DR-submodular function maximization problems, obtaining corresponding iteration complexity results in a high-probability form. Furthermore, theoretical examples as well as numerical experiments validate that this stepsize selection strategy outperforms the fixed stepsize strategy.

Keywords: DR-submodular; approximation algorithm; dynamic stepsizes; computational complexity; stochastic optimization (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2025
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/13/9/1447/pdf (application/pdf)
https://www.mdpi.com/2227-7390/13/9/1447/ (text/html)

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:gam:jmathe:v:13:y:2025:i:9:p:1447-:d:1644745

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().