mlsanityData to 7 Oct 2026

Upper-Linearizability of Online Non-Monotone DR-Submodular Maximization over Down-Closed Convex Sets

arXiv 2602.20578 ↗First posted 24 Feb 2026cs.LG math.OC stat.MLcited by 1

Not on the map. Why?

Abstract (arXiv)

We study online maximization of non-monotone Diminishing-Return(DR)-submodular functions over down-closed convex sets, a regime where existing projection-free online methods suffer from suboptimal regret and limited feedback guarantees. Our main contribution is a new structural result showing that this class is 1/e-linearizable under carefully designed exponential reparametrization, scaling parameter, and surrogate potential, enabling a reduction to online linear optimization. As a result, we obtain O(T1/2) static regret with a single gradient query per round and unlock adaptive and dynamic regret guarantees, together with improved rates under semi-bandit, bandit, and zeroth-order feedback. Across all feedback models, our bounds strictly improve the state of the art.

Key facts. Cited by 1 paper in the map (data through 7 Oct 2026). Builds on 21 of its 36 references that are in the map. First posted on arXiv 24 Feb 2026.

Builds on

21 of 36 references.

References · 21

  1. 2018Adaptive Online Learning in Dynamic Environmentscited by 130
  2. 2019Bandit Convex Optimization in Non-stationary Environmentscited by 41
  3. 2018Online Continuous Submodular Maximizationcited by 35
  4. 2017Gradient Methods for Submodular Maximizationcited by 33
  5. 2022New Projection-free Algorithms for Online Convex Optimization with Adaptive Regret Guaranteescited by 26
  6. 2017Continuous DR-submodular Maximization: Structure and Algorithmscited by 24
  7. 2022Stochastic Continuous Submodular Maximization: Boosting via Non-oblivious Functioncited by 21
  8. 2022Resolving the Approximability of Offline and Online Non-monotone DR-Submodular Maximization over General Convex Setscited by 14
  9. 2023Constrained Submodular Maximization via New Bounds for DR-Submodular Functionscited by 13
  10. 2019Online Non-Monotone DR-submodular Maximizationcited by 10
  11. 2023A Unified Approach for Maximizing Continuous DR-submodular Functionscited by 10
  12. 2024From Linear to Linearizable Optimization: A Novel Framework with Applications to Stationary and Non-stationary DR-submodular Optimizationcited by 8
9 more
  1. 2021Fast First-Order Methods for Monotone Strongly DR-Submodular Maximizationcited by 7
  2. 2022On Maximizing Sums of Non-monotone Submodular and Linear Functionscited by 7
  3. 2025Decentralized Projection-free Online Upper-Linearizable Optimization with Applications to DR-Submodular Optimizationcited by 7
  4. 2022Profit Maximization in Social Networks and Non-monotone DR-submodular Maximizationcited by 6
  5. 2024Boosting Gradient Ascent for Continuous DR-submodular Maximizationcited by 6
  6. 2024Unified Projection-Free Algorithms for Adversarial DR-Submodular Optimizationcited by 5
  7. 2022Experimental Design Networks: A Paradigm for Serving Heterogeneous Learners under Networking Constraintscited by 4
  8. 2025Online Learning for Approximately-Convex Functions with Long-term Adversarial Constraintscited by 1
  9. 2026Stronger Approximation Guarantees for Non-Monotone γ-Weakly DR-Submodular Maximizationcited by 1

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2026: 1.

1 paper.

  1. 2026Dec-BFTRL: Squre-Root Regret for Decentralized Online Upper-Linearizable Optimization under Separation Access with Application to Continuous Submodular Maximizationcited by 0