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

Jul 16, 2026

Upload by Anda

Online maximization of non-monotone diminishing-return (DR)-submodular functions over down-closed convex sets is studied, where projection-free online methods incur suboptimal regret and weak feedback guarantees. A new structural result shows the class is 1/e-linearizable via exponential reparametrization, a scaling parameter, and a surrogate potential, reducing the problem to online linear optimization. This yields first non–Frank-Wolfe projection-free algorithms with approximation better than 1/4, plus O(T^1/2) static regret using one gradient query per round, with improved bounds under semi-bandit, bandit, and zeroth-order feedback.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages16

Reading Time40 min

Introduction

Online optimization of submodular and DR-submodular functions

Non-monotone objectives and down-closed convex domains

Linearizable function classes and the new structural characterization

Upper-Linearizability of Online Non-Monotone DR-Submodular Maximization over Down-Closed Convex Sets Yiyang Lu 1 Hareshkumar Jadav 2 Mohammad Pedramfar 3 Ranveer Singh 2 Vaneet Aggarwal 1 arXiv :2602 .20578v2 [ cs .LG] 10 Jul 2026 Abstract 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. This allows us to obtain first non-Frank-Wolfe type algorithms for this setting that obtain an approximation coefficient better than 1/4 . Moreover, the linearization framework allows us to move beyond offline 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. 1. Introduction Online optimization of submodular and DR-submodular functions has become a central primitive in machine learning, with applications in mean-field inference, revenue maximization, influence maximization, supply chain management, power network reconfiguration, and experimental design (Bian et al., 2019 ; Ito & Fujimaki, 2016 ; Gu et al., 2023 ; Aldrighetti et al., 2021 ; Mishra et al., 2017 ; Li et al., 2023) . In these problems, an algorithm repeatedly selects actions from a convex domain while an adversary reveals a reward function, and performance is measured through notions of 1Purdue University, West Lafayette, IN, USA 2IIT Indore, MP, India 3Mila-Quebec AI Institute/McGill University, Montreal, QC, Canada. Correspondence to: Yiyang Lu <[yiyanglu@purdue.edu](yiyanglu@purdue.edu) >, Vaneet Aggarwal <[vaneet@purdue.edu](vaneet@purdue.edu) >. Proceedings of the 43 rd International Conference on Machine Learning, Seoul, South Korea. PMLR 306, 2026 . Copyright 2026 by the author(s) . static, adaptive, or dynamic regret. A long line of work has developed projection-free algorithms, typically based on Frank–Wolfe or boosting-style updates (Fazel & Sadeghi, 2023 ; Chen et al., 2018 ; Zhang et al., 2022 ; Pedramfar et al., 2023 ; Zhang et al., 2024) . While most of the study in DR-submodular optimization is for monotone objectives (Hassani et al., 2017 ; Fazel & Sadeghi, 2023 ; Chen et al., 2018 ; Zhang et al., 2022), thenon-monotone objective plays an important role in many applications such as price optimization, social networks recommendation, and budget allocation (Ito & Fujimaki, 2016 ; Gu et al., 2023 ; Alon et al., 2012) . In this work, we study non-monotone DR-submodular maximization over downclosed convex sets, which remains particularly challenging. Down-closed domains include box constraints, knapsack polytopes, and intersections of matroids, and arise naturally in resource allocation and coverage problems. In this regime, even the best approximation ratio for online optimization remains open (Buchbinder & Feldman, 2024), while the best achievable approximation rate is 1/e (Thang & Srivastav, 2021 ; Zhang et al., 2023 ; Pedramfar et al., 2023) . Further, for this regime, existing projection-free methods either require multiple oracle queries per round or only achieve suboptimal regret rates such as O (T2/3) (Pedramfar et al., 2024a), and essentially no results were known for adaptive or dynamic regret. Recent work in (Pedramfar & Aggarwal, 2024) introduced the notion of linearizable function classes and showed how such a structure enables a generic reduction from online linear optimization to a wide family of non-convex problems, including several DR-submodular

FAQs

What is the main problem studied in this document?

The document studies online maximization of non-monotone diminishing-return (DR)-submodular functions over down-closed convex sets, a setting that is challenging for existing projection-free methods.

What is the key technical contribution?

It proves a new structural result that this function class is 1/e-linearizable using exponential reparametrization, a scaling parameter, and a surrogate potential.

How do the authors obtain efficient online algorithms and regret guarantees?

They design a Jacobian-corrected gradient estimator that uses a single gradient query per round, enabling a reduction to online linear optimization and leading to O(T^1/2) static regret with improved bounds across multiple feedback models.

Jul 16, 2026

Upload by Anda