PaperlayerView exact revision on arXiv

Source-linked AI summary

Online Non-Monotone DR-Submodular Maximization Matching the Offline $0.401$ Factor

Vaneet Aggarwal, Yiyang Lu

arXiv:2609.02145v1cs.LGcs.AIcs.CCstat.ML

TL;DR

The paper addresses whether the best constructive offline approximation factor can survive adversarial online variation. It replaces the offline objective-dependent box step with weighted online learning and an amortized composition, achieving factor 0.401 with sublinear approximate regret. The guarantees include oracle-budget trade-offs and a one-point bandit extension, under bounded conditionally unbiased feedback and stated scope limitations.

  • Problem

    The paper asks whether the constructive offline factor 0.401 can be achieved online when actions precede the current objective, whereas comparable adversarial guarantees remained at 1/e.

  • Method

    The method uses a weighted online unconstrained-maximization learner, an exact asymmetric balance theorem, and an amortized composition that preserves the offline asymmetric coefficients.

  • Results

    The algorithm achieves factor 0.401 with sublinear approximate regret; direct implementation has O(T^3/4) regret and O(dT^1/4) oracle calls per round, while batching and bandit extensions provide stated trade-offs.

  • Takeaways & Limitations

    The result shows that the best known constructive offline benchmark can also be attained online in the post-decision value-oracle model.

  • Takeaways & Limitations

    The factor 0.401 is an asymptotic coefficient rather than a finite-horizon guarantee, and the stated noisy-feedback bounds require balanced parameters; if OPTT is sublinear, no constant factor is guaranteed.

Abstract

from arXiv · show

We study online maximization of nonnegative, non-monotone DR-submodular functions over compact convex down-closed subsets of the $d$-dimensional unit cube. The best known constructive offline approximation factor is $0.401$ under the corresponding meta-solvability assumptions, whereas comparable adversarial online guarantees had remained at $1/e$. We show that this factor is also achievable online. In the post-decision full-information value-oracle model, our algorithm attains factor $0.401$ with sublinear approximate regret when oracle feedback is conditionally unbiased and bounded. The online algorithm does not run the offline construction on a changing objective. Instead, it replaces the offline objective-dependent box step by a weighted online learner that controls the required residual terms cumulatively. An exact asymmetric balance theorem preserves the offline coefficients despite adversarial variation. The direct implementation has $O(T^{3/4})$ regret and uses $O(dT^{1/4})$ oracle calls per round. More generally, for every $δ\in[0,1/4]$, batching gives $O(T^δ)$ calls per round and $O(T^{4/5-δ/5})$ regret, including a one-call $O(T^{4/5})$ endpoint. Under a positive-anchor condition, randomized blocking retains factor $0.401$ with $O(T^{5/6})$ one-point bandit regret.

1 Introduction

The paper asks whether the best constructive offline factor, 0.401, survives adversarial online variation, and answers yes with sublinear approximate regret. Its approach replaces the offline objective-dependent box step with weighted online learning and amortizes residual terms while preserving the asymmetric coefficients.

  • Online/offline gap: 0.401 is achieved online with sublinear approximate regret, matching the best known constructive offline factor.The comparison concerns approximation coefficients rather than identical algorithms or oracle assumptions.
  • Why online is harder than offline: Online selection is harder because actions must be committed before the current objective is revealed, preventing a black-box use of the offline box step.Past or averaged objectives do not control current rewards against adversarial variation, and post-feedback queries cannot retroactively change the action.
  • The online construction: The algorithm replaces the unavailable per-round box optimum with an independent weighted online unconstrained-maximization state and controls residual debts cumulatively.The certificate amortizes delayed-trajectory debts over the sequence instead of eliminating them pointwise.
  • The online composition: An exact weighted balance theorem handles unequal Double-Greedy coefficients after discretizing coordinates into levels and lifting the box objective to a submodular set function.The largest feasible balance constant for positive weights cX and cY is 2√cXcY.
  • The online composition: The online composition preserves the offline factor-revealing value by matching the certified delay and asymmetry, although online and offline repay the relevant debt through different mechanisms.The offline construction uses an approximate local maximum, while the online method uses a lattice inequality whose linear residue is absorbed by the outer learner.
  • The online composition: O(T^3/4) regret and O(dT^1/4) oracle calls per round are obtained by the direct implementation.Batching extends the trade-off to O(T^δ) calls per round and O(T^4/5−δ/5) regret for δ ∈ [0,1/4].

2 Related work

Prior work established foundational approximation and online methods for DR-submodular maximization, while this paper targets the asymmetric box layer needed to extend the constructive offline benchmark online.

  • Offline DR-submodular maximization: Continuous greedy methods established a 1/e guarantee for nonnegative non-monotone objectives over down-closed convex bodies, later improving to approximately 0.372 and 0.385.Buchbinder and Feldman subsequently introduced a sharper DR-submodular inequality underlying the 0.401 constructive benchmark.
  • Online submodular maximization: Online continuous submodular maximization was introduced for monotone objectives, while later work studied time-varying DR-submodular resource allocation.For set functions, Blackwell approachability yielded an optimal no-regret reduction for online unconstrained submodular maximization.
  • Online submodular maximization: Existing online work covered approximate regret over convex sets, general convex-body geometry, and linearization frameworks for first-order, adaptive, and nonstationary guarantees.This paper instead focuses on the asymmetric box layer rather than reducing only a structural inequality to online linear optimization.
  • Value-query and bandit feedback: Value-query methods use smoothing or finite differences, while prior online non-monotone results included 1/e guarantees and value-feedback or bandit regret rates through several feedback reductions.The cited prior methods include one-shot first-order, one-point bandit, post-decision value-oracle, and bandit guarantees with differing regret exponents.

3 Problem formulation

The problem concerns online reward maximization with changing DR-submodular functions over a compact convex down-closed feasible set, under noisy value-oracle feedback and explicit approximation-regret trade-offs.

  • Feasible domain: The feasible region K is a nonempty compact convex down-closed subset of [0,1]^d, with coordinatewise down-closure ensuring that 0 belongs to K.The set diameter is denoted D, and the learner has a polynomial-time projection oracle for K.
  • Reward assumptions: A differentiable reward is DR-submodular when its gradient is antitone, and the paper assumes nonnegative L-smooth rewards bounded by M.An oblivious adversary fixes the sequence f_1,...,f_T satisfying these structural and range conditions.
  • Online protocol: At each round, the learner commits to a feasible action before seeing the current function, receives its true reward, and is evaluated against the best fixed feasible point in hindsight.The formulation separates nonconcavity-induced approximation loss from learning losses caused by estimating directions and structural choices from past observations.
  • Feedback models: The noisy value oracle returns scalar feedback at queried points, with conditionally unbiased, bounded errors and conditional independence across calls.The noise level σ bounds error magnitude and implies a single-call conditional variance at most σ^2.
  • Feedback models: Post-decision full-information permits polynomially many queries after playing, whereas one-point bandit feedback provides exactly one noisy value from the played feasible point.The models differ in where calls may be placed, not in how their observations are corrupted.
  • Noise caveat: Conditional unbiasedness is essential for the inner layer: systematic bias propagates through Double-Greedy marginals and finite differences, producing terms that repetition cannot remove.At balanced parameters, the resulting bias contribution can be of order βT^(5/4), so slower bias decay dominates the direct T^(3/4) rate.
  • Guarantee conventions: The approximation factor is asymptotic: with OPT_T=Θ(T), the direct and bandit deficits scale as O(T^(-1/4)) and O(T^(-1/6)), respectively.If OPT_T is sublinear, no constant factor is guaranteed; the horizon is assumed known for parameter tuning, though doubling removes that assumption at constant-factor cost.

4 Post-decision full-information value-oracle result

The online construction preserves the 0.401 offline approximation coefficient by replacing the anticipatory box step with weighted online learners and cumulative certificates. It provides noisy post-decision value-oracle guarantees with explicit regret–query trade-offs and an exact asymmetric balance theorem.

  • 0.401 is preserved online under noisy post-decision value-oracle feedback with sublinear approximate regret.The guarantee holds for an obliviously fixed adversarial sequence and actions selected before current-function feedback.
  • O(T^3/4) regret uses O(dT^1/4) oracle calls per round under balanced parameters.With bounded conditionally unbiased noise, noise changes constants through Mσ but not the approximation factor, regret exponent, or call-budget exponent.
  • O(T^δ) calls per round trade against O(T^4/5−δ/5) regret for every δ ∈ [0, 1/4].The endpoints are one call and O(T^4/5) regret at δ = 0, versus O(dT^1/4) calls and O(T^3/4) regret at δ = 1/4.
  • The structural certificate retains the two nonlinear endpoint values while routing the lattice residue into outer online linear optimization.This gives the same asymmetry-optimized value as the offline coefficient program at the certified delay.
  • 2√cXcY is the exact approachable balance constant, and the normalization (cX, cY) = (1/r, r) yields amax = 2.This asymmetric balance recovers the offline box coefficients cumulatively online, without improvement through reweighting.
  • The algorithm replaces the unavailable per-round offline box optimum with an independent weighted online USM learner whose debts are paid cumulatively.The outer online learner absorbs the remaining linear term, while randomized mixing of inner and outer candidates produces the reward guarantee.

4.3 Algorithm and factor-revealing composition

The algorithm combines an outer projected online learner with weighted inner USM learners, using noisy post-decision oracle estimates and an asymmetric factor-revealing analysis. At certified parameters, the resulting online coefficient matches the offline benchmark 0.401.

  • Algorithm: The composition uses weighted balance learners for the inner transformed objective and projected stochastic online optimization for the outer state.The transformed objective is G_t(a) = f_t(x_t ⊙ a), while the outer field estimate is updated with a second-moment-calibrated step size.
  • Noisy feedback: Conditional unbiasedness supports splitting the outer analysis into optimization, martingale, and bias terms, with only estimator bias charged linearly in T.The field estimate remains unclipped under noisy feedback because clipping could introduce bias; fluctuations are handled through the second moment.
  • Factor-revealing composition: 0.401 is the certified headline factor, with λ0 ≈ 0.8038 and α(s0, r0) ≈ 0.40102 at the selected parameters.The formal theorem uses the rounded factor 0.401, while the certified parameter choice satisfies α(s0, r0) > 0.401.
  • Factor-revealing composition: The online and offline factor-revealing programs have equal optimized coefficients at the certified delay, without claiming identical algorithms or global equality for every delay.The comparison preserves the offline coefficient through the common asymmetry switch; the online regret theorem relies on the certified inequality.

4.4 Consequences, complexity, and robustness

The method replaces pointwise offline box optimization with cumulative online learning over transformed objectives, preserving the offline coefficient while incurring sublinear learning and estimation losses. Its guarantees remain robust to bounded conditionally unbiased noise and expose explicit complexity trade-offs.

  • Consequences: The inner learner controls transformed residual terms cumulatively instead of eliminating them pointwise with an offline local-optimality condition.This amortized certificate pays residuals through cumulative online learning and recovers the offline coefficient at the certified delay.
  • Complexity: O(dT^1/4) calls per round and O(T^3/4) regret result from the direct same-round implementation.Batching spreads the query list across blocks to reduce the per-round budget.
  • Consequences: The online replacement is not an offline-to-online black-box reduction because the outer state and transformed objective sequence change over time.Theorem 4.8 shows that the asymmetric coefficients survive this changing-objective setting with only additive learning loss.
  • Offline connection: A constant-sequence argument connects a polynomial-time online factor with suitably normalized polynomial-rate regret to the corresponding offline factor.The argument applies when the online algorithm is run on a repeated objective and a uniformly random played point is considered.
  • Offline frontier: The factor 0.401 is a constructive benchmark rather than an optimality claim, while a related value-oracle hardness threshold is 0.478.The hardness statement concerns multilinear-extension maximization over down-closed polytopes, including partition matroid and cardinality constraints.
  • Robustness: For every fixed noise level, bounded conditionally unbiased oracle noise changes additive terms but leaves the approximation factor and regret exponents unchanged.The structural certificate, balance geometry, and factor-revealing program depend on true functions and are unaffected by feedback noise.

5 Secondary extension to one-point bandit feedback

The bandit extension uses randomized blocking to simulate the many oracle queries required by the full-information method while ensuring every query is itself a feasible action. Under a known positive anchor, it retains factor 0.401 with a one-point bandit regret guarantee whose geometry-dependent cost is explicit.

  • Bandit construction: One-point bandit feedback prevents direct use of the post-decision algorithm because its updates require many current-function values.Randomized block simulation injects labeled feasible query points into blocks and uses exploitation actions on remaining rounds.
  • Feasibility: A known anchor x̄ with coordinates at least ρ enables contraction and feasible finite-difference probes for the bandit algorithm.For x ∈ Kγ and h ≤ γρ/2, all inner and outer query points lie in K.
  • Geometric caveat: The anchor margin ρ is a genuine geometric parameter: thin bodies can make the bandit bound deteriorate as ρ → 0.The post-decision model has no analogous cost because its probes need only remain in the ambient cube.
  • Bandit construction: The block method freezes the state over blocks, uses past-block feedback, and assigns query labels through a uniform injection into physical rounds.The resulting block-average sequence is analyzed at the meta-round level under an obliviously fixed adversary.
  • Guarantee: O(T^5/6) one-point bandit regret retains approximation factor 0.401 for fixed problem parameters and fixed noise level.The additive term includes a geometry-dependent BD/ρ contribution, and the exponent is unchanged as the noise level varies while remaining fixed with T.

6 Conclusion

The paper shows that the best known constructive offline factor, 0.401, is achievable in adversarial online optimization with sublinear regret. Its implementation preserves the asymmetric offline coefficients while supporting query-limited and noisy-oracle settings.

  • 0.401 approximation factor is achieved online in an adversarial setting with sublinear regret.
  • An exact weighted balance theorem and amortized online composition preserve the asymmetric offline coefficients.
  • O(T^3/4) regret requires O(dT^1/4) oracle calls per round in the direct post-decision value-oracle implementation.
  • Randomized blocking achieves O(T^5/6) one-point bandit regret under the positive-anchor condition.
  • Conditionally unbiased bounded oracle noise changes additive terms but not the approximation factor.

A Block simulation of the query list

The block simulation fixes each update’s nonadaptive oracle-query list before current-block feedback, then randomly injects labeled queries into physical rounds while keeping the exploitation action feasible and nonanticipating.

  • Block averages preserve nonnegativity, smoothness, DR-submodularity, boundedness, and gradient-norm bounds through convex combinations.
  • All oracle locations needed for an update are fixed before feedback from the current objective is received.The complete list can therefore be scheduled across a block in advance.
  • Uniform random injection assigns labeled query points to distinct rounds, while unassigned rounds play the exploitation point.The schedule is sampled before the block begins, preserving nonanticipation.
  • Conditionally unbiased oracle noise leaves finite-difference bias unchanged, while injection and oracle fluctuations contribute to the second moment.When σ ≤ M, the combined scale differs by at most a constant factor of four.
  • Noisy sampled inner marginals remain conditionally unbiased for true marginals, although observed estimates need not satisfy admissibility constraints.

B Proof of the limited-query frontier

The limited-query proof batches a nonadaptive query list into groups and injects them across block rounds, yielding a tunable trade-off between per-round oracle calls and regret without changing the asymptotic noise dependence.

  • εδ = T^−(1+δ)/5, h = εδ/2, and Q = ⌈εδ^−1⌉ set the field accuracy and query-list parameters.
  • O(dT^ξ) labels per update are partitioned into groups and injected across blocks, using at most k oracle calls per round.
  • O(T^(4−δ)/5) regret follows for the limited-query frontier, with the stochastic-field and incomplete-block terms below this exponent.
  • The noise level appears only in constants through Mσ, so fixed σ does not affect the regret exponents.

C Offline implications of constant sequences

Constant-sequence analysis converts an online approximation guarantee with sublinear regret into an offline approximation guarantee by averaging or randomly selecting played points. The conversion requires a positive lower bound on the offline optimum for polynomial-time quantitative guarantees.

  • R(T) = o(T) makes the expected approximation converge to α on every fixed instance.
  • A regret bound R(T) ≤ CT^κ with κ < 1 and known v > 0 yields an (α − ε)-approximation in expectation.
  • Polynomial per-round computation and query budgets, together with computable bounds on C and v^−1, are required for the offline implication.
  • Randomly selecting a played point is implementable under noisy value feedback and bandit feedback, unlike returning the best played point.
  • A known lower bound v on the optimum is essential because without it an additive o(T) term need not become relatively negligible in polynomially many rounds.

D Proof of the endpoint comparison inequalities

This appendix proves inequalities (22)–(23), which are specialized offline inequalities used in Lemma 4.6. The proofs allow an arbitrary comparator and establish the comparator-uniformity needed quantitatively.

  • D Proof of the endpoint comparison inequalities: Inequalities (22)–(23) are specialized from Lemmas 5.7 and 5.9 of [10].The specialization uses z = x and the constant direction x(τ) ≡ x, with an arbitrary comparator o replacing an optimizer.
  • D Proof of the endpoint comparison inequalities: The appendix gives complete proofs because these nonstandard offline inequalities are imported by the outer certificate.
  • D Proof of the endpoint comparison inequalities: Comparator-uniformity is used quantitatively in the endpoint comparison argument.

D.1 DR-submodular toolbox

This section develops basic consequences of differentiable DR-submodularity, including closure under coordinatewise operations and gradient-based inequalities. These properties support later comparison arguments.

  • D.1 DR-submodular toolbox: The basic properties include concavity along nonnegative coordinate directions and upper and lower gradient bounds for feasible increments.The listed properties are (P1)–(P4), including inequalities for forward and backward increments.
  • D.1 DR-submodular toolbox: DR-submodularity makes the gradient antitone: u ≤ w implies ∇f(u) ≥ ∇f(w) coordinatewise.
  • D.1 DR-submodular toolbox: Concavity along a segment follows because the directional derivative is nonincreasing under gradient antitonicity.
  • D.1 DR-submodular toolbox: For any fixed y, the maps a ↦ f(a ⊙ y) and a ↦ f(a ⊕ y) remain nonnegative and DR-submodular.The proof represents both maps as affine compositions with nonnegative diagonal scalings and uses antitonicity of the gradient.

D.2 An exponential lower bound

The section proves a basic exponential bound for nonnegative DR-submodular functions and lifts it to a two-block form. The proof proceeds by finite induction and monotone convergence.

  • D.2 An exponential lower bound: The underlying engine is identified as Lemma 4.1 of [10], whose proof is reproduced for both comparisons.
  • D.2 An exponential lower bound: Lemma D.3 establishes a basic exponential bound for a nonnegative differentiable DR-submodular function under an integrable direction field.
  • D.2 An exponential lower bound: The proof establishes truncated bounds by induction and obtains the infinite-sum statement through monotone convergence.
  • D.2 An exponential lower bound: The base case uses the coordinatewise bounds e^-t ≤ e^-y(t) ≤ 1 and properties of nonnegative DR-submodular functions.
  • D.2 An exponential lower bound: The induction step differentiates g(t) = F(1 − a ⊙ e^-y(t)) and verifies feasibility of the resulting point.
  • D.2 An exponential lower bound: Lemma D.4 derives a two-block exponential bound by applying Lemma D.3 to a function on a 2d-dimensional ground set.The constructed function is shown to be DR-submodular because its argument is coordinatewise nondecreasing and ∇f is antitone.

D.3 A comparison lemma

Lemma D.5 provides a comparison inequality for a point x, a feasible increment, and nested comparator points. Its proof applies the forward-gradient property twice and uses nonnegativity.

  • D.3 A comparison lemma: Lemma D.5 compares f(x), f(o), f(x ⊕ o), and f(o − o′) for feasible ∆ and o′ ≤ o.
  • D.3 A comparison lemma: The first application of (P1) uses base point o − o′ and increment o′ + (1 − x) ⊙ ∆.Feasibility follows because the resulting point is at most 1.
  • D.3 A comparison lemma: The second application of (P1) uses base point o and increment (1 − x) ⊙ ∆, with feasibility checked through 1 − (x ⊕ o).
  • D.3 A comparison lemma: Adding the two inequalities yields the first comparison bound, while f(0) ≥ 0 gives the second.

D.4 The two comparisons

Lemmas D.6 and D.7 establish early and late comparisons uniformly for every x and comparator o in [0,1]^d. Their proof splits the integral terms by whether coordinates fall before or after the delay s, using nonnegativity and DR-submodularity to control the residual terms.

  • Comparison lemmas: Lemmas D.6 and D.7 provide early and late comparison bounds for every x, o ∈ [0,1]^d and the corresponding time ranges.The early comparison applies for τ ∈ [0,s), while the late comparison applies for τ ∈ [s,1].
  • Early comparison: The early phase represents P_τ as Y_τ ⊕ o − x ⊙ o and applies Lemma D.4 with a zero first direction and x as the second direction.The proof substitutes Y_τ=(1−x)⊙(1−e^−τx) and uses the resulting decomposition.
  • Early comparison: The early proof uses item (P1) on base point (1−x) ⊙ o and increment x ⊙ o, whose sum with the larger base point is o ≤ 1.This yields the required bound from the base term f((1−x)⊙o).
  • Late comparison: The late phase has ω_τ=1−Y_τ, so Y_τ+ω_τ⊙o=Y_τ⊕o; its comparison expression is expanded into two exponential terms.The proof applies Lemma D.4 using both directions equal to x and coefficients 1−o.
  • Case analysis: For higher-order terms, the proof separates all coordinates before s, the single late coordinate case, and mixed cases, bounding the latter using only nonnegativity.Cases (a) and (b) contribute f(o)−f(x⊕o) and f(x⊕o), respectively, while case (c) uses Ξ_i(ς)≥0.
  • Implication: The two lemmas require only nonnegativity and DR-submodularity of f, with arbitrary o∈[0,1]^d and no additional property of K.This comparator-uniformity is identified as the basis for the online argument.
Loading 2609.02145v1…