mlsanityData to 14 Oct 2026

A Unified Approach for Maximizing Continuous DR-submodular Functions

arXiv 2305.16671 ↗First posted 26 May 2023cs.LG cs.AI cs.CCcited by 10

Not on the map. Why?

Abstract (arXiv)

This paper presents a unified approach for maximizing continuous DR-submodular functions that encompasses a range of settings and oracle access types. Our approach includes a Frank-Wolfe type offline algorithm for both monotone and non-monotone functions, with different restrictions on the general convex set. We consider settings where the oracle provides access to either the gradient of the function or only the function value, and where the oracle access is either deterministic or stochastic. We determine the number of required oracle accesses in all cases. Our approach gives new/improved results for nine out of the sixteen considered cases, avoids computationally expensive projections in two cases, with the proposed framework matching performance of state-of-the-art approaches in the remaining five cases. Notably, our approach for the stochastic function value-based oracle enables the first regret bounds with bandit feedback for stochastic DR-submodular functions.

Key facts. Cited by 10 papers in the map (data through 14 Oct 2026). Builds on 26 of its 39 references that are in the map. First posted on arXiv 26 May 2023.

Builds on

26 of 39 references.

References · 26

  1. 2019Introduction to Online Convex Optimizationcited by 803
  2. 2015An Optimal Algorithm for Bandit and Zero-Order Convex Optimization with Two-Point Feedbackcited by 111
  3. 2018Stochastic Conditional Gradient Methods: From Convex Minimization to Submodular Maximizationcited by 47
  4. 2021Online Learning via Offline Greedy Algorithms: Applications in Market Design and Optimizationcited by 40
  5. 2018Online Continuous Submodular Maximizationcited by 35
  6. 2017Gradient Methods for Submodular Maximizationcited by 33
  7. 2019Online Continuous Submodular Maximization: From Full-Information to Bandit Feedbackcited by 33
  8. 2016Guaranteed Non-convex Optimization: Submodular Maximization over Continuous Domainscited by 31
  9. 2018Projection-Free Online Optimization with Stochastic Gradient: From Convexity to Submodularitycited by 31
  10. 2015Submodular Functions: from Discrete to Continous Domainscited by 25
  11. 2017Continuous DR-submodular Maximization: Structure and Algorithmscited by 24
  12. 2017Conditional Gradient Method for Stochastic Submodular Maximization: Closing the Gapcited by 21
14 more
  1. 2022Stochastic Continuous Submodular Maximization: Boosting via Non-oblivious Functioncited by 21
  2. 2022Resolving the Approximability of Offline and Online Non-monotone DR-Submodular Maximization over General Convex Setscited by 14
  3. 2023Bandit Multi-linear DR-Submodular Maximization and Its Applications on Adversarial Submodular Banditscited by 13
  4. 2018Optimal Algorithms for Continuous Non-monotone Submodular and DR-Submodular Maximizationcited by 12
  5. 2019Online Non-Monotone DR-submodular Maximizationcited by 10
  6. 2019Black Box Submodular Maximization: Discrete and Continuous Settingscited by 9
  7. 2021Fast First-Order Methods for Monotone Strongly DR-Submodular Maximizationcited by 7
  8. 2022An improved approximation algorithm for maximizing a DR-submodular function over a convex setcited by 6
  9. 2022Lyapunov function approach for approximation algorithm design and analysis: with applications in submodular maximizationcited by 6
  10. 2022Profit Maximization in Social Networks and Non-monotone DR-submodular Maximizationcited by 6
  11. 2022Experimental Design Networks: A Paradigm for Serving Heterogeneous Learners under Networking Constraintscited by 4
  12. 2022Online Learning for Non-monotone Submodular Maximization: From Full Information to Bandit Feedbackcited by 3
  13. 2019Non-monotone DR-submodular Maximization: Approximation and Regret Guaranteescited by 2
  14. 2023Jointly Optimal Routing and Caching with Bounded Link Capacitiescited by 1

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 5; 2025: 1; 2026: 4.

10 papers.

  1. 2024From Linear to Linearizable Optimization: A Novel Framework with Applications to Stationary and Non-stationary DR-submodular Optimizationcited by 9
  2. 2025Decentralized Projection-free Online Upper-Linearizable Optimization with Applications to DR-Submodular Optimizationcited by 7
  3. 2024Boosting Gradient Ascent for Continuous DR-submodular Maximizationcited by 6
  4. 2024Unified Projection-Free Algorithms for Adversarial DR-Submodular Optimizationcited by 5
  5. 2024A Unified Framework for Analyzing Meta-algorithms in Online Convex Optimizationcited by 4
  6. 2026Upper-Linearizability of Online Non-Monotone DR-Submodular Maximization over Down-Closed Convex Setscited by 3
  7. 2024Bridging the Gap Between General and Down-Closed Convex Sets in Submodular Maximizationcited by 1
  8. 2026Stronger Approximation Guarantees for Non-Monotone γ-Weakly DR-Submodular Maximizationcited by 1
  9. 2026γ-weakly θ-up-concavity: A Unified Framework for Non-Convex Optimization Beyond DR-Submodular and OSS Functionscited by 1
  10. 2026Advancing Optimal Subset Oracle via Learning Relaxation of Neural Set Functionscited by 0