Maximizing a nonnegative DR-submodular function over a down-closed convex set is the continuous counterpart of non-monotone submodular set-function maximization. It appears in MAP inference for determinantal point processes, revenue maximization, and the continuous relaxations used to round set-function problems. In the online version, an adversary chooses a sequence of such objectives, the learner commits a feasible action before seeing each one, and the quality measure is the -regret against the best fixed feasible point.
Online and offline algorithms in this setting are commonly built from a comparison: an objective-independent recovery map and a vector field such that for every pair of points (Pedramfar and Aggarwal, NeurIPS 2024, arXiv:2405.00065). Once such a comparison holds, any online linear-optimization learner fed with estimates of yields -regret, and online-to-batch conversion yields an offline -approximation. The coefficient is therefore the quantity of interest.
Timeline. For compact convex down-closed subsets of the cube, Buchbinder and Feldman (STOC 2024, arXiv:2311.01129) obtained an offline coefficient for smooth objectives, with a smoothness-dependent additive error. Online, Lu, Jadav, Pedramfar, Singh and Aggarwal (ICML 2026) showed the problem is -linearizable. Aggarwal and Lu (arXiv:2610.00545, Corollary 4.2) established coefficient for a comparison of the form above and proved the oracle upper bound (Corollary 6.4, Proposition 7.3). Aggarwal and Du (arXiv:2610.21072) construct a comparison with coefficient
which this mission formalizes.
Let . Vector inequalities are coordinatewise. A function is continuously differentiable on when its derivatives extend continuously to the boundary, and DR-submodular when implies for . Every objective is nonnegative on .
Fix , and , so that . The recovery map acts coordinatewise: for and for .
For a state the coordinates split into small ones and large ones . The comparison field of (24) is assembled from:
Then . Every one of these objects is a separate definition of the mission, under the names used in the paper.
The paper presents three theorem-level main results: refTheorem 4.1 gives the explicit affine comparison at coefficient ; refTheorem 6.3 gives uniform offline approximation with polynomial oracle counts independent of coordinate widths, gradient magnitudes, or smoothness; and refTheorem B.1 determines sharp objective-independent downward recovery and bounded comparisons at . The platform allows one goal, so Theorem 4.1 remains the goal while the other two are milestones of equal standing among the paper’s main results.
The milestones from Section 6.2 and Appendix B were added on 2026-11-15, so the mission now covers every theorem of the paper.
For every nonnegative continuously differentiable DR-submodular ,
is linear in for fixed , and both and are Borel measurable. The constant is exact; the field is the defined object of (24), not an existentially quantified vector.
Lemma 3.2(i)–(ii) (concavity along sign-definite directions; affine reparametrization), Lemma 4.3 (affine normalization), Lemma 4.4 (signed endpoint inequality), Lemma 4.5 (ordered large-coordinate comparison), the boundary inequalities (33)–(35), Lemma 4.6 (path comparisons with nonnegative remainders), Lemma 4.8 (ordered integral representation), and the scalar chain of Lemmas A.1–A.6 culminating in Lemma 4.7 (scalar averaging inequality (47)).
Theorem 4.1 gives coefficient for general nonnegative DR-submodular maximization over down-closed convex sets. Combined with the OMBQ reduction of Pedramfar and Aggarwal (Theorem 1 of arXiv:2405.00065), it yields -regret with one noisy gradient query per round, and through online-to-batch conversion a uniform offline -approximation; rounding gives matroid and knapsack consequences. The coefficient lies between the barrier for objective-independent downward maps measured against the concave closure (Appendix B of the paper) and the oracle bound .
The result is proved on paper with exact rational constants. No part of it has a machine-checked proof. Formalizing it would certify a numerically delicate argument: the constant is earned in a scalar inequality (Lemma 4.7) whose proof rests on dozens of exact rational evaluations and polynomial sign tests, and on an averaging identity in which several remainders must cancel exactly.
The obvious argument fixes a comparator and integrates the gradient along a path from toward . That bounds only by a comparator-dependent vector, whereas the comparison requires one vector for all comparators. The construction therefore splits coordinates into two blocks with different recovery branches, compares each block against with remainders kept explicitly (Lemma 4.6), and averages these comparisons in time with weights chosen so that the cross-block terms cancel. What remains is a one-dimensional inequality over nonincreasing profiles (Lemma 4.7), and the margin there is small: at the inequality holds with equality on one family of profiles, and the chosen is only slightly larger.
is EuclideanSpace ℝ (Fin n), with coordinates indexed from and every tie broken by the order of Fin n. Every , including , is covered. The cube, the within-cube partial derivatives and DR-submodularity are the published definitions GeomDRSub.cube, GeomDRSub.pd, GeomDRSub.gradQ, GeomDRSub.IsDRSubmodular. Derivatives are taken within the closed cube, because the field evaluates gradients at boundary points. Nonnegativity of is a separate hypothesis.
The dummy large coordinate of the paper is not a coordinate of . It enters only as label of the large order with weight ; all its terms vanish and are dropped. The crossing point is an infimum over and assumes nothing about existence. Path derivatives are derivWithin on . The field's integral is taken coordinatewise.
The statement cannot be trivialized: the field is a fixed definition, so (25) cannot be met by choosing , and is an exact rational. Linearity is required over all functions continuously differentiable on .
A complete development needs calculus within the closed cube (chain rule along affine maps, concavity along monotone segments), Fubini on , layer-cake representations of monotone functions, and exact polynomial arithmetic with Taylor bounds for . The scalar lemmas A.1–A.6 depend only on the schedule and can be attacked independently of the field. Lemmas 3.2 and 4.4 hold for every DR-submodular function and are reusable.
namespace DRSub4633
/-- **Theorem 4.1 (Affine comparison on the cube).** Aggarwal–Du, *0.4633-Approximation for Online and Offline Non-Monotone DR-Submodular
Maximization*, arXiv:2610.21072, Theorem 4.1, p.13: "For every
nonnegative continuously differentiable DR-submodular `f : Q → ℝ`, the field `g(f, x)` in (24)
satisfies `f(o) ≤ Γf(h(x)) + ⟨g(f, x), o − x⟩` (`x, o ∈ Q`). (25) For fixed `x`, `g(f, x)` is linear
in `f`. Both `h` and `g(f, ·)` are Borel measurable."
Here `Γ = 1 + b + 1/(4b) = 117486474169/54440750000` (8), `h` is the recovery map (9) and `g` the
field (24).
**Formalization Note.** `Q = [0, 1]^n ⊆ EuclideanSpace ℝ (Fin n)`, every `n`. Continuously
differentiable DR-submodular is `GeomDRSub.IsDRSubmodular` (`C¹` on the cube, derivatives within
the cube). Linearity in `f` is additivity and real homogeneity, for every `x ∈ Q`, over functions
continuously differentiable on `Q` (the domain on which (24) is defined). Measurability of
`g(f, ·)` is of its restriction to the state cube `Q`; `h` is measurable on all of `ℝⁿ`. -/
theorem theorem_4_1 {n : ℕ} :
(∀ f : EuclideanSpace ℝ (Fin n) → ℝ, (∀ y ∈ GeomDRSub.cube n, 0 ≤ f y) →
GeomDRSub.IsDRSubmodular f →
∀ x ∈ GeomDRSub.cube n, ∀ o ∈ GeomDRSub.cube n,
f o ≤ Gam * f (hRec x) + inner ℝ (field f x) (o - x)) ∧
(∀ x ∈ GeomDRSub.cube n, ∀ (a c : ℝ) (f₁ f₂ : EuclideanSpace ℝ (Fin n) → ℝ),
ContDiffOn ℝ 1 f₁ (GeomDRSub.cube n) → ContDiffOn ℝ 1 f₂ (GeomDRSub.cube n) →
field (a • f₁ + c • f₂) x = a • field f₁ x + c • field f₂ x) ∧
Measurable (hRec : EuclideanSpace ℝ (Fin n) → EuclideanSpace ℝ (Fin n)) ∧
(∀ f : EuclideanSpace ℝ (Fin n) → ℝ, (∀ y ∈ GeomDRSub.cube n, 0 ≤ f y) →
GeomDRSub.IsDRSubmodular f →
Measurable ((GeomDRSub.cube n).domRestrict (field f))) := by sorry
end DRSub4633
Let , , the recovery map (9) and the comparison field (24). For every nonnegative, continuously differentiable, DR-submodular ,
For fixed , is linear in . Both and are Borel measurable.
Equivalently with : a single vector, independent of the comparator, certifies the approximation coefficient . Through online-to-offline reductions this gives the paper's online and offline -approximations.
Differences from the source:
No submissions yet on this mission's goal. Log in and be the first to prove it.