PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Yiyang Lu, Haresh Jadav, Mohammad Pedramfar, Ranveer Singh, Vaneet Aggarwal

arXiv:2602.20578v2cs.LGmath.OCstat.ML

TL;DR

Online non-monotone DR-submodular maximization over down-closed convex sets has faced regret and query-efficiency limitations. The paper proves 1/e-linearizability using an exponential reparametrization and surrogate potential, reducing the problem to online linear optimization. It reports O(T^1/2) static regret with one gradient query per round and improved guarantees across feedback models.

  • Problem

    For non-monotone DR-submodular maximization over down-closed convex sets, existing projection-free methods have suboptimal regret or require multiple oracle queries, with adaptive and dynamic guarantees largely absent.

    Source: §1 · p. 1

  • Method

    The paper establishes 1/e-linearizability with an exponential reparametrization and surrogate potential, enabling reduction to online linear optimization.

    Source: §1 · p. 1, §3.5 · p. 4, §4 · p. 4

  • Results

    O(T^1/2) static regret with one gradient query per round accompanies adaptive and dynamic guarantees and improved rates across limited-feedback models.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The framework provides a projection-free route to online linear optimization for this non-monotone down-closed setting while retaining the 1/e approximation factor.

    Source: §1 · p. 1, §6 · p. 9

    The online 1/e approximation remains below the reported 0.401 offline guarantee; adversarial revelation of the non-monotone penalty prevents globally aware corrective steps.

    Source: §6 · p. 9

Abstract

from arXiv · show

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(T^{1/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

The paper addresses non-monotone DR-submodular maximization over down-closed convex sets, where existing projection-free methods have query or regret limitations. It establishes 1/e-linearizability and uses it to obtain improved regret guarantees across feedback settings.

1. Introduction

  • Online submodular optimization serves applications including mean-field inference, revenue maximization, influence maximization, supply chain management, and experimental design.The paper highlights non-monotone objectives in price optimization, social-network recommendation, and budget allocation.Source: §1 · p. 1
  • Existing projection-free methods for this regime require multiple oracle queries per round or achieve suboptimal regret such as O(T^2/3), with adaptive and dynamic guarantees essentially absent.The setting includes down-closed convex domains such as box constraints, knapsack polytopes, and intersections of matroids.Source: §1 · p. 1
  • The function class is 1/e-linearizable under an exponential reparametrization and surrogate potential, enabling reduction to online linear optimization.The potential weights early trajectory stages to support exact cancellation in the integration-by-parts analysis.Source: §1 · pp. 1–2
  • The Jacobian-corrected BQND estimator accounts for the exponential mapping’s curvature to construct unbiased linear surrogates under a single-query budget.The framework decouples non-convex oracle queries from constraint handling and can use an efficient regret-minimizing linear-optimization algorithm as its base learner.Source: §1 · p. 2
  • O(T^1/2) static regret with one gradient query per round accompanies adaptive and dynamic guarantees and improved rates across limited-feedback models.The paper reports strict improvements over prior bounds across feedback models.Source: §1 · p. 2

2. Related Works

Prior work established projection-free and linearizable approaches for online DR-submodular maximization, but the non-monotone down-closed setting retained regret and query-efficiency trade-offs. The paper positions its guarantees against these gaps and extends coverage to non-stationary and limited-feedback regimes.

Online Non-monotone DR-Submodular Maximization

  • Earlier linearizable results covered several DR-submodular settings, but the general-convex-set case yielded a 1/4 approximation for non-monotone objectives.The cited 1/4 coefficient is described as optimal for that class of problems.Source: §2 · p. 2

The Down-Closed Convex Sets & The Frank-Wolfe Bottleneck

  • For down-closed sets, the best known online approximation is 1/e, while the best reported offline rate is 0.401 and the absolute upper bound is 0.478.The online 1/e result had been tied to Frank–Wolfe or continuous-greedy methods, with a regret-versus-query trade-off.Source: §2 · p. 2
  • O(T^1/2) regret with O(1) queries and adaptive and dynamic guarantees distinguishes this framework from earlier bounds for down-closed sets.Thang & Srivastav (2021) report O(T^3/4) regret with T^3/4 queries per round; Zhang et al. (2023) report O(T^1/2) with T^3/2 queries or O(T^4/5) with O(1) queries.Source: Table 1 · p. 3, §2 · p. 3

Non-Stationary and Limited Feedback

  • Adaptive and dynamic regret were less explored for non-monotone DR-submodular objectives; earlier unified feedback frameworks did not provide those guarantees for the down-closed setting.The paper reports dynamic regret guarantees and improved results for semi-bandit and bandit feedback.Source: §2 · p. 3

3. Preliminaries

The preliminaries specify the domains, objectives, online interaction, feedback models, regret measures, and linearizability framework used in the paper.

3.1. Notations

  • The setup uses coordinate-wise vector operations and exponentials, a probabilistic-sum operation, and a bounded-diameter down-closed convex set with an efficient OLO base algorithm.The objective class is non-negative, differentiable, non-monotone DR-submodular, and assumed Lipschitz and smooth.Source: §3.1 · p. 3

3.2. Problem Setting: Adversarial Online Optimization

  • Each adversarial round selects played and query points in K, then reveals an objective and oracle feedback; the gradient oracle is unbiased and bounded.The query oracle is the player's only way to learn the adversary's functions.Source: §3.2 · p. 4

3.3. Limited Feedback Setting

  • Non-trivial queries provide full-information feedback, while querying the played action gives semi-bandit feedback for gradients or bandit feedback for values.The analysis also considers zeroth-order full-information feedback.Source: §3.3 · p. 4

3.4. Regret

  • The paper minimizes α-regret against an α-approximate static optimum and also defines adaptive interval regret and dynamic regret against time-varying comparators.The dynamic comparator sequence is bounded using path length PT.Source: §3.4 · p. 4

3.5. Linearizability

  • α-linearizability upper-bounds scaled reward using a linear surrogate term, so low-regret OLO transfers to α-regret for the original rewards, up to β and the mapping h.The mapping h is the reparameterization, β the scaling parameter, and g the surrogate potential.Source: §3.5 · p. 4

4. Non-monotone DR-submodular Functions over Down-Closed Convex Sets are 1/e-Linearizable

The section establishes 1/e-linearizability for non-monotone DR-submodular objectives on down-closed convex sets containing the origin. An exponential reparameterization and surrogate potential support the reduction, while BQND supplies an unbiased, bounded gradient estimate.

4. Non-monotone DR-submodular Functions over Down-Closed Convex Sets are 1/e-Linearizable

  • Non-monotone DR-submodular functions on down-closed convex sets are 1/e-linearizable.The stated setting takes K ⊆ [0, 1]^d, with 0 ∈ K.Source: §4 · pp. 4–5
  • The exponential map h_z(x) = 1-e^(-zx) yields a structural lower bound relative to a comparator y, leveraging down-closedness.The inequality is presented as the structural step for handling the non-monotone online setting.Source: §4 · p. 5
  • The construction uses h(x) = 1-e^(-x) and β = 1-e^(-1); surrogate F weights early trajectory stages to cancel the non-monotone penalty.The cancellation occurs in the integration-by-parts analysis.Source: §4 · p. 5
  • The regret-transfer theorem bounds the main algorithm's regret by the online linear learner's surrogate regret up to scaling β.This permits the framework to inherit the chosen base solver's convergence rates.Source: §4 · p. 6
  • BQND samples z, queries the first-order oracle once at 1-e^(-zx), and returns a bounded unbiased estimate of the surrogate gradient.Its output is g = v ⊙ e^(-zx), and the stated bound is B1.Source: §4 · pp. 6–7

5. Regret Results Applied from Linearizable Optimization

The linearizable formulation reduces the non-monotone problem to online linear optimization, with BQND supplying the query algorithm. Instantiating the framework with suitable base learners yields static, adaptive, dynamic, and limited-feedback regret guarantees.

5. Regret Results Applied from Linearizable Optimization

  • Algorithm 2 instantiates OMBQ with h(x) = 1−e^(−x) and BQND, transferring linear-optimization guarantees through the 1/e-linearizable structure.The framework uses a base learner for online linear optimization and a query algorithm fixed to BQND.Source: §5 · p. 7

5.1. Static Regret

  • With SO-OGA, Algorithm 2 achieves 1/e-approximation static regret for any fixed comparator and requires only O(1) gradient queries per round.The supplied passages do not preserve the static-regret bound itself.Source: §5.1 · p. 7

5.2. Adaptive and Dynamic Regrets

  • SO-OGA also gives a 1/e-approximation adaptive-regret guarantee, reported as the first such guarantee for this domain.The bound is stated as O(T^1/2).Source: §5.2 · p. 8
  • With Improved Ader, Algorithm 2 achieves 1/e-approximation dynamic regret, with the bound depending on the path length of the optimal sequence.The supplied passages do not preserve the complete dynamic-regret bound.Source: §5.2 · p. 8

5.3. Semi-Bandit, Zeroth-order Full-Information, and Bandit Feedback

  • The same modular framework transfers guarantees across feedback models and provides dynamic-regret bounds for limited feedback.The stated limited-feedback dynamic bounds depend on P_T, the path length of the optimal sequence.Source: §5.3 · p. 9

6. Conclusion and Future Work

The conclusion attributes the improved guarantees to 1/e-linearizability, an exponential reparameterization, a surrogate potential, and BQND. It also identifies an online-versus-offline approximation gap and several open questions.

6. Conclusion and Future Work

  • The paper proves strict 1/e-linearizability and uses an exponential reparameterization, surrogate potential, and BQND to reduce the problem to online linear optimization with one query per round.The surrogate potential yields an exact cancellation during integration by parts; the conclusion reports O(T^1/2) static regret and the first adaptive and dynamic guarantees for this domain.Source: §6 · p. 9
  • The online approximation ratio of 1/e remains below the best achievable offline approximation of 0.401.The authors identify breaking the online barrier and establishing limited-feedback regret lower bounds as open challenges; extension to γ-weakly DR-submodular functions also remains open.Source: §6 · p. 9

A. Useful Lemmas

  • The analysis uses inequalities established by Buchbinder and Feldman for non-negative continuous DR-submodular functions over [0,1]^d.The supplied lemma passages state conditions for two inequalities used in the analysis.Source: A. Useful Lemmas · p. 12

B. Proof of Lemma 1

The proof specializes an inequality to the online adversarial setting by taking the trajectory to be constant, then simplifies its lower bound using non-negativity.

B. Proof of Lemma 1

  • For the online adversarial setting, the proof takes x(τ) = x throughout [0,t], making the trajectory integral equal to tx.It rewrites the probabilistic-sum term as 1−(1−x)^i.Source: B. Proof of Lemma 1 · p. 12
  • Because the surrogate potential F is non-negative, each integral term and the resulting infinite sum are non-negative.This sign property supports dropping the sum from the right-hand side.Source: B. Proof of Lemma 1 · p. 12
  • The proof sets y = 1−a and the time parameter to z, then defines h_z(x) = 1−e^(−zx) to express the transformed update.It relates h_z(x) to the probabilistic sum with y.Source: B. Proof of Lemma 1 · p. 12

C. Infeasible Projection and Online Gradient Ascent via a Separation Oracle (SO-OGA)

The appendix describes SO-OGA as a projection-free base learner implemented with a separation oracle. Its updates use gradient ascent followed by an infeasible projection routine.

C. Infeasible Projection and Online Gradient Ascent via a Separation Oracle (SO-OGA)

  • SO-OGA uses a separation oracle to avoid Euclidean projections, while the paper notes that separation and linear-optimization oracles have complementary efficiency across domains.For the nuclear norm ball, the linear-optimization oracle is efficient and separation is expensive; for the spectral norm ball, the reverse holds.Source: C. Infeasible Projection and Online… · pp. 12–13
  • SO-OGA is initialized at a center of a shrunken constraint set, plays its current point, and takes a gradient-ascent step before calling SO-IPK.The shrunken set is defined using a center c and radius r of a ball contained in K.Source: C. Infeasible Projection and Online… · p. 13
  • SO-IPK handles an infeasible update using affine-hull and ball operations, then calls the separation oracle to obtain a separating hyperplane or return a feasible point.The routine iterates until it returns a point in K.Source: C. Infeasible Projection and Online… · p. 13
  • The cited SO-OGA result gives adaptive regret guarantees for linear functions under stated norm, diameter, and step-size conditions.The supplied theorem passage specifies δ = vT^−1/2 and a step size proportional to T^−1/2.Source: C. Infeasible Projection and Online… · p. 13

D. Meta-Algorithms and Regret Bounds Towards Diverse Feedback Types

OMBQ wraps a linear learner with a mapping and query algorithm to maximize a non-monotone DR-submodular function. FOTZO describes a zeroth-order query procedure and states conditions for its regret lemma.

D.1. The Generic Meta-Algorithm (OMBQ)

  • The regret-transfer setup combines a linearizable function class with surrogate potential g, mapping h, and a query algorithm to form OMBQ(A, G, h).The passage states that an unbiased oracle output bounded by B1 precedes a guarantee, and identifies β as a scaling constant.Source: §D.1 · pp. 13–14
  • OMBQ maps the learner’s action to the played action, queries an oracle at the learner’s action, and returns the negated estimate for the learner’s update.The framework uses a mapping h and query algorithm G to transform a linear learner into a non-monotone DR-submodular maximizer.Source: §D.1 · pp. 13–14

D.2. First Order To Zeroth Order (FOTZO)

  • FOTZO samples directions in L0, queries at y_t,i + δv_t,i, and passes k/δ times the oracle output and direction to A.Its stated lemma assumes an M1-Lipschitz function class, δ < r, and a first-order online optimizer.Source: §D.2 · p. 14

D.3. Semi-bandit To Bandit (STB)

Lemma 6 describes STB as a way to use a semi-bandit algorithm under the stated assumptions, with the same regret bounds.

D.3. Semi-bandit To Bandit (STB)

  • Under Lemma 5’s assumptions, STB(A) retains the same regret bounds when A is a semi-bandit online optimizer.The lemma also states that setting δ = T^-1 gives a same-order regret comparison.Source: §D.3 · p. 14
  • The stated same-order comparison applies when δ = T^-1.This condition appears as an additional case in Lemma 6.Source: §D.3 · p. 14

D.4. Stochastic Full-information To Trivial query (SFTT)

SFTT organizes query actions and ordinary plays into blocks, using a random schedule for the query actions. Its stated lemma concerns full-information algorithms with multiple queries per timestep.

D.4. Stochastic Full-information To Trivial query (SFTT)

  • SFTT divides play into blocks and schedules query actions at randomly permuted time slots, using the base action in the other slots.The algorithm returns observations from the selected plays to the corresponding query oracle.Source: §D.4 · p. 15
  • The SFTT lemma assumes a full-information algorithm with K queries per timestep whose query choices do not depend on current-round observations.It also specifies a Lipschitz function class closed under convex combination, with B1 ≥ M1.Source: §D.4 · p. 15
  • The lemma’s stated setting includes 0 < α ≤ 1 and intervals with 1 ≤ a ≤ b ≤ T.It defines rescaled endpoints a′ and b′ using block size L.Source: §D.4 · p. 15

E. Algorithms for Dynamic Regret

The dynamic-regret section restates Improved Ader and its expert algorithm. The method aggregates step-size experts and uses gradient-based linear losses; its update can use a projection-free subroutine.

E. Algorithms for Dynamic Regret

  • Improved Ader activates experts for a set of step sizes and aggregates their actions into the played action.After observing the gradient, it defines a linear loss around that action and sends the gradient to each expert.Source: E. Algorithms for Dynamic Regret · p. 16
  • The expert algorithm receives the main algorithm’s action and gradient before updating its own action.The displayed expert-algorithm passage gives the send-and-receive sequence.Source: E. Algorithms for Dynamic Regret · p. 16
  • The stated update can use a Frank-Wolfe step or the Infeasible Projection subroutine to maintain the framework’s projection-free property.The section presents Improved Ader and its performance theorem as supporting dynamic-regret guarantees.Source: E. Algorithms for Dynamic Regret · pp. 15–16

Related papers

Loading 2602.20578v2…