PaperlayerView exact revision on arXiv

Source-linked AI summary

A 0.4584-approximation for DR-submodular maximization over down-closed convex sets

Donglei Du

arXiv:2610.21072v1cs.DS

TL;DR

The paper considers maximization of a nonnegative, continuously differentiable DR-submodular objective over a compact convex down-closed subset of the unit cube, in an oracle model with cube-wide value/full-gradient queries and linear maximization. A recovery map combining exponential and linear-fractional branches yields a cube-wide affine upper bound used by a Frank–Wolfe-type algorithm. The linear terminal branch reports α1 ≈ 0.4584057; a quadratic terminal branch raises the ratio to approximately 0.4584288.

  • Problem

    The paper considers maximization of a nonnegative, continuously differentiable DR-submodular objective over a compact convex down-closed subset of the unit cube, in an oracle model with cube-wide value/full-gradient queries and linear maximization.

    Source: §1 · p. 2

  • Method

    A recovery map combining exponential and linear-fractional branches yields a cube-wide affine upper bound used by a Frank–Wolfe-type algorithm.

    Source: §1 · pp. 2–3

  • Results

    The linear terminal branch reports α1 ≈ 0.4584057; a quadratic terminal branch raises the ratio to approximately 0.4584288.

    Source: §1 · p. 2

  • Takeaways & Limitations

    Standard multilinear sampling and extended randomized pipage rounding give an expected (α1 − ε)-approximation for nonnegative submodular set functions under a matroid constraint [18, Lemma B.3].

    Source: §1 · p. 3

    The guarantee is scoped to cube-wide value/full-gradient queries and ordinary linear maximization, with an additive error δLD^2.

    Source: §1 · p. 2

Abstract

from arXiv · show

We obtain a $0.4584$-approximation for nonnegative, non-monotone, $L$-smooth DR-submodular maximization over compact convex down-closed subsets of the unit cube, improving the $4/9\approx0.4444$ ratio of Aggarwal's projection-based algorithm~\cite{aggarwal2026geometry}. A recovery map combining exponential and linear-fractional branches admits a cube-wide affine upper bound. The resulting continuous-time Frank--Wolfe-type algorithm with randomized output and its randomized discrete-time implementation both satisfy $\E F(\widehat x)\ge(0.4584-\varepsilon)\OPT-\delta LD^2$; the implementation uses polynomially many cube-wide value/full-gradient queries and ordinary linear maximization calls, where $D$ is the feasible diameter and $\varepsilon,\delta>0$ are accuracy parameters. Our guarantee and Aggarwal's hardness bound~\cite{aggarwal2026geometry} place the optimal approximation ratio for cube-wide value/full-gradient queries and linear maximization, with additive error $\delta LD^2$, in $[0.4584,0.4705)$. Standard multilinear sampling and pipage rounding imply an expected $(0.4584-\varepsilon)$-approximation for nonnegative submodular set-function maximization under a matroid constraint \cite[Lemma B.3]{vondrak2013symmetry}.

1 Introduction

The paper studies nonnegative, smooth DR-submodular maximization over compact convex down-closed subsets of the unit cube, with cube-wide value/full-gradient queries and linear maximization. It combines a recovery map and affine upper bound with a Frank–Wolfe-type algorithm to improve the prior approximation guarantee.

1 Introduction

  • The guarantee is formulated for cube-wide value/full-gradient queries and ordinary linear maximization, with polynomial query complexity uniform across instances.The oracle model allows an additive error δLD^2 and uses the feasible diameter D.Source: §1 · p. 2
  • The recovery map combines exponential and linear-fractional branches and admits a cube-wide affine upper bound.Averaging the bound over reference points with average x cancels the common linear term; accumulated linear error is controlled by a quadratic potential along Frank–Wolfe directions.Source: §1 · pp. 2–3
  • 0.4584057 is the reported approximation ratio, improving on Aggarwal’s 4/9 ≈ 0.4444 ratio for this continuous optimization problem.The paper reports α1 ≈ 0.4584057; Aggarwal’s algorithm uses a projection oracle.Source: §1 · p. 2
  • Prior continuous DR-submodular algorithms reported ratios from 1/4 and 1/e to 0.4010 and 4/9, with different oracle or query-complexity conditions.Aggarwal’s 4/9 method uses a projection oracle, while its query bound can depend on gradient norm relative to a lower bound on the optimum.Source: §1 · p. 2
  • The randomized discrete-time implementation satisfies the same guarantee using O(n^5β^-4) value/full-gradient queries and O(n + n^4β^-4) linear maximization calls.Deterministic quadrature also gives a deterministic version with the same approximation guarantee.Source: §1 · p. 3
  • Standard multilinear sampling and extended randomized pipage rounding yield an expected (α1 − ε)-approximation for nonnegative submodular set functions under a matroid constraint [18, Lemma B.3].The guarantee is stated relative to the optimal independent-set value.Source: §1 · p. 3

2 Recovery map and affine upper bound

The paper mixes exponential and linear-fractional recovery branches to improve the affine upper bound while keeping the recovered point feasible. The resulting bound applies across the cube and supports the later optimization algorithm.

2 Recovery map and affine upper bound

  • Mixing exponential recovery for small coordinates with linear-fractional recovery for large ones yields the improved map.The exponential branch is downward feasible; the construction averages two affine bounds to establish the cube-wide bound.Source: §2 · pp. 3–4
  • Aggarwal’s linear-fractional recovery reaches 4/9 on the cut example, motivating a different recovery map.The paper notes that the alternative linear-fractional branch alone can violate downward feasibility.Source: §2 · p. 3
  • The recovery map stays coordinatewise below x and attains the inverse affine-bound factor on the two-variable cut example.At x = (1/2, 1/2), its cut value is 4b1/(2b1 + 1)^2 = Γ1^-1.Source: §2 · p. 4
  • Theorem 2.1 bounds every cube reference value by the recovered-point value plus a field inner product.The bound holds for all x and o in the unit cube.Source: §2 · p. 4

3 A continuous-time Frank–Wolfe-type algorithm

The algorithm uses coordinate normalization and a continuous-time Frank–Wolfe-type process to turn the affine upper bound into an expected-reward guarantee. Randomized output-time and action selection connect the trajectory to a feasible output.

3.1 Coordinate normalization

  • Coordinate normalization removes zero-width coordinates and rescales the remaining coordinates to define the normalized feasible set and objective.An LMO for the normalized set uses one LMO for the original set.Source: §3.1 · p. 5

3.2 Dynamics and output

  • The dynamics use compatible mixtures of limiting action–field pairs to preserve feasibility and the affine bound across discontinuities.The process admits an absolutely continuous execution; randomized output time and action realize its time-averaged reward.Source: §3.2 · p. 5

3.3 Approximation guarantee

  • A quadratic-distance potential converts LMO progress into a bound on accumulated linear error.The potential compares squared distances for the state and a reference point against their minimum over the feasible set.Source: §3.3 · pp. 5–6
  • The expected output reward is the time-averaged reward, with accumulated linear error bounded by the trajectory analysis.The resulting error is at most ε OPT + δLD^2 under the stated parameter choice.Source: §3.3 · p. 6

4 A two-variable cut example

A two-variable cut example evaluates the prescribed field at a mixed recovery state, then gives a simpler field and an explicit continuous-time trajectory. The trajectory’s recovered-point value approaches the coefficient α1.

4 A two-variable cut example

  • The example takes F(z) = z1 + z2 − 2z1z2 over the simplex z1 + z2 ≤ 1, with OPT = 1.The mixed state uses one small and one large coordinate.Source: §4 · p. 6, §4.1 · p. 7

4.1 The prescribed field at a mixed state

  • At the mixed state, the prescribed field’s averaged intercept is bounded by Γ1F(hb(x)).The evaluated expressions give (20/21)wJ(1/2) ≈ 0.4448 and q ≈ (0.9291, 0.9506).Source: §4.1 · pp. 7–8

4.2 A simpler field for the execution

  • For the cut example, the constant field (1, 1) yields an affine bound over feasible x and cube reference points o.Averaging the bound over e1, e2, and 0 cancels the field term.Source: §4.2 · p. 8

4.3 Continuous-time execution

  • As t approaches infinity, F(p(t), p(t)) approaches α1 along the explicit continuous-time trajectory.The trajectory uses z(t) = 1 − e^-t and switches recovery branches at t ≈ 0.2099.Source: §4.3 · p. 8

Formal verification

The paper reports a Lean development covering its numbered mathematical results, algorithms, and derivations. It also describes AI assistance and assigns responsibility for the paper’s content to the author.

Formal verification

  • The Lean development verifies 19 numbered mathematical results and supporting algorithms and derivations.It uses exact real arithmetic, 697 modules, and the stated axiom basis.Source: Formal verification · p. 8
  • ChatGPT assisted with literature review, averaging, exact-arithmetic checks, and Lean code; the author reviewed the arguments and takes full responsibility.The mixed recovery idea was motivated by the author’s working paper [8].Source: Formal verification · p. 8

A Proof of the affine upper bound

The proof constructs a cube-wide affine upper bound using a mixed recovery map, then averages two affine bounds to control its intercept. The resulting comparison yields the approximation coefficient 1/Γ.

A.1 Elementary bounds and the two blocks

  • DR bounds, retained nonnegative remainders, and interpolation combine the small- and large-coordinate estimates into affine bounds valid for every cube reference point.The T-bound uses a greedy affine lower bound; the J-bound uses an interpolated affine upper bound.Source: A Proof of the affine upper bound · p. 9, §A.1 · pp. 10, 12

A Proof of the affine upper bound

  • F(o) ≤ ΓF(hb(x)) + ⟨gb(F, x), o − x⟩ gives a cube-wide affine upper bound, with approximation coefficient 1/Γ.The proof averages two bounds to control the intercept by Γ times the recovered objective.Source: A Proof of the affine upper bound · p. 9

A.1 Elementary bounds and the two blocks

  • The two-block construction recovers small coordinates along an exponential path while keeping large coordinates fixed, reaching hb(x) at t = 1.Two affine bounds extend the large-coordinate bound to the full cube by controlling boundary objective terms.Source: §A.1 · pp. 10, 12

A.2 Averaging the two upper bounds

  • Nonnegative averaging weights and curvature and initial-value bounds reduce the intercept comparison to scalar sign conditions, which complete the affine-bound proof.The curvature and bounded-variation controls apply under C1 regularity.Source: §A.2 · pp. 12–13

A.3 Elementary weights and analytic verification

This section develops piecewise averaging weights and a curvature multiplier to form a feasible scalar certificate, then verifies the design parameter and required analytic conditions with rational bounds. It also describes bisection for implementing the parameter choice and a quadratic terminal-weight refinement.

Elementary weights and analytic verification

  • Piecewise linear and exponential averaging weights, paired with a homogeneous curvature-multiplier correction, cancel the residuals needed for Lemma A.6’s scalar certificate.The construction verifies normalized nonnegative weights and the residual sign conditions required by the lemma.Source: §A.3 · pp. 14–15
  • The terminal residual equation dW(b)=0 selects b, with its exact expression reduced to rational functions and exponentials of the design parameters.The expression uses four moments of wT.Source: §A.3 · pp. 14–16
  • dW(inf I) > 3/10000000 and dW(sup I) < −1/5000000, while the uniform bounds establish the required scalar signs and a unique b1 in I.The bounds include 0 < L2 < 1/2, Ψ(0) < −3/100, and µ′(0) > 1/10.Source: §A.3 · p. 16
  • Degree-16 Taylor remainder bounds and rational interval arithmetic certify the parameter signs for the exact exponential weight formulas and the boundary equation defining b1.The method bounds exponential and moment arguments uniformly over the selected parameter interval.Source: §A.3 · pp. 16–17

Uniqueness of the design parameter

  • A unique b1 in I follows from the endpoint signs and strict decrease of dW, establishing (22) and the conclusion (15).The certified derivative enclosure is −538/1000 < E′ < −532/1000.Source: §A.3 · p. 21

Computing the design parameter

  • Rational bisection computes an upper approximation eb and retains the expected guarantee (α1 − ε) OPT − δLD2 without oracle calls for parameter calculations.The bisection uses arbitrarily precise exponential enclosures; Algorithm 3 runs with parameter eb and accuracy ε/2, δ.Source: §A.3 · pp. 21–22

Analytic verification of the refinement

  • Inequalities (31), together with Lemma A.6, prove the analogue of (5) for quadratic-terminal weights; the resulting algorithmic approximation ratio is 1/Γ, where Γ = 1 + b + 1/(4b).The cited bounds include 47/100 < L2 < 12/25.Source: §A.3 · p. 24

Quadratic terminal refinement

  • The quadratic-terminal algorithm achieves ratio 1/Γ, improving on the linear-terminal ratio at the fifth decimal place.Its weights satisfy 0 ≤ wT, wJ ≤ 21/20, preserving the sampler's 21/20 envelope.Source: §A.3 · pp. 24–25

A.4 The field vector and its sampler

The field vector combines two weighted branches, and sampling a branch and parameter according to the corresponding weight density gives an unbiased estimate. Each returned sample has bounded norm and uses only cube-wide value and full-gradient queries.

The field vector and its sampler

  • Sampling a branch and parameter with the corresponding weight density yields an unbiased field estimate from one component evaluation.The rejection sampler terminates almost surely, using 21/10 scalar proposals on average before evaluating the field.Source: §A.4 · p. 25
  • The sampler accepts branch-parameter proposals with probability (20/21)w_B(t), producing the corresponding weighted branch distribution.Its average proposal count is 21/10, and rejected proposals require only scalar draws and weight evaluations.Source: §A.4 · p. 25
  • Every returned sample has norm at most (1 + 2/b)H and costs O(n) cube-wide value and full-gradient queries.The norm bound follows from coordinate-wise endpoint gradient bounds and the field components’ coefficients.Source: §A.4 · p. 25

B Discrete-time algorithm and supporting results

The discrete-time method samples an unbiased field and uses one linear maximization per step. Its linear-error bound leads to an approximation guarantee with polynomial oracle complexity.

B Discrete-time algorithm and supporting results

  • The section presents the finite-step algorithm and its error and oracle bounds, followed by a worked cut example and supporting results.The remaining results cover width normalization, flow existence, a matroid consequence, a 4/9 specialization, and deterministic quadrature.Source: B Discrete-time algorithm and… · p. 25

B.1 Randomized discrete-time Frank–Wolfe-type algorithm

  • Each iteration draws a fresh conditionally unbiased field sample, takes a Frank–Wolfe step of size 3/T, and records the recovered action’s value.The LMO uses the accumulated field and previous state; the algorithm returns the recorded action with maximum value.Source: §B.1 · p. 26

B.2 Linear bound with one maximization per iteration

  • Lemma B.1 bounds linear error using one LMO per iteration for compact convex K containing zero, bounded samples, and a fixed horizon.Its proof combines a quadratic-minimum bound and Frank–Wolfe tracking error in one potential.Source: §B.2 · p. 26

B.3 Approximation and oracle complexity √

  • The horizon in (33) yields loss at most ε OPT + δLD2, with O(n4β−4) iterations, one LMO per iteration, and O(n5β−4) total value and full-gradient queries.Here β = min{ε, δ}; the returned action is mapped back by W, and convex updates with downward recovery preserve feasibility.Source: §B.1 · p. 26, §B.3 · p. 27

B.4 Discrete-time execution of the cut example

The cut example has a fully described discrete trajectory whose best recorded action is a192. The section also bounds normalized gradients using feasible axis endpoints, smoothness, and DR-submodularity.

B.4 Discrete-time execution of the cut example

  • The unused simplex mass follows a recurrence that adds a geometric term whenever the LMO selects the origin.For Z = {3, 4, 7, 10}, the proposition concerns the best of the 192 recorded actions.Source: §B.4 · p. 28
  • F(a192) ≈ 0.4587, while 15α1/16 ≈ 0.4298; a192 is the unique recorded action of maximum value.The LMO choices alternate from t = 11 onward, and all positive coordinates except those of a5 and a6 use the linear-fractional branch.Source: §B.4 · pp. 28–29

B.5 Width normalization

  • Feasible axis endpoints control gradients at zero, while smoothness and DR bound gradients throughout the normalized cube; two full-gradient queries compute H.If H = 0, the normalized objective is constant.Source: §B.5 · p. 29

B.6 Existence and realization of the continuous flow

The continuous flow is obtained through compact convex velocity sets and measurable mixtures of feasible limiting action-field pairs. The section also derives a matroid consequence using randomized multilinear estimation and pipage rounding.

B.6 Existence and realization of the continuous flow

  • The limiting feasible action-field pairs satisfy the affine upper bound, and their convex hull provides the compact convex velocity sets used for flow existence.Carathéodory’s theorem represents each point of the hull with at most k + 2 pairs.Source: §B.6 · p. 30
  • For every horizon and scale, an absolutely continuous flow exists, and a distribution on at most k + 2 feasible limiting pairs realizes its objective values and vectors.The proof takes limits of feasible Euler trajectories and selects measurable mixtures realizing the limiting values and vectors.Source: §B.6 · p. 30

B.7 The standard matroid consequence

  • Randomized multilinear estimation and pipage rounding give Ef(S) ≥ (α1 − ε) OPTdisc for nonnegative submodular set functions under a matroid constraint.The multilinear sampler uses O(n2) set-value queries per sample; the complete method uses O(n10ε−4) value queries and polynomially many independence queries.Source: §B.7 · pp. 30–31

B.8 Uniform polynomial oracle complexity for Aggarwal’s 4/9 bound

This section adapts Aggarwal’s recovery map and field to obtain a uniform polynomial-oracle implementation of the 4/9 guarantee. Its randomized algorithm uses ordinary linear maximization calls and cube-wide value and full-gradient queries.

B.8 Uniform polynomial oracle complexity for Aggarwal’s 4/9 bound

  • Combining Aggarwal’s recovery h(x) = x/(1 + x) with width normalization and Algorithm 3 yields the 4/9 ratio with uniform polynomial oracle complexity.The implementation uses ordinary LMOs and cube-wide value/full-gradient queries.Source: §B.8 · p. 31
  • In the stated oracle model, Algorithm 3 specialized to Aggarwal’s recovery and field guarantees EF(bx) ≥ (4/9 − ε) OPT − δLD^2 with O(n^5β^-4) value/full-gradient queries and O(n + n^4β^-4) ordinary LMO calls.Source: §B.8 · p. 31
  • The proof samples coordinate derivatives on lower or upper segments to estimate the field, then runs Algorithm 3 with Γ = 9/4 and B = H.The sample uses k full gradients; the horizon is determined by k and β.Source: §B.8 · p. 31

B.9 Deterministic quadrature

This section replaces randomized field estimates with deterministic quadrature. The resulting deterministic variant preserves the approximation guarantee while using polynomially many value/full-gradient queries and LMO calls.

B.9 Deterministic quadrature

  • In the continuous optimization model of Theorem 1.1, Algorithm 3 has a deterministic variant guaranteeing F(bx) ≥ (α1 − ε) OPT − δLD2 with O(n6β−5) value/full-gradient queries and O(n + n4β−4) LMO calls.Source: §B.9 · p. 32
  • The quadrature uses nonnegative integrated weights summing to one, so its field estimate has norm at most CbH and costs O(kN) queries.Each interval is divided into N equal cells, and the weights are exactly computable.Source: §B.9 · p. 32
  • DR-submodularity makes coordinate-derivative averages nonincreasing along increasing paths, bounding their variation and controlling quadrature error.The analysis also bounds variation after multiplying by the coordinate-dependent factors and weights.Source: §B.9 · pp. 31–32
  • The deterministic mesh gives a field-estimation error of at most 14H/N, with N = O(kβ^−1), and the resulting approximation loss is bounded by ε OPT + δLD^2.The query analysis gives O(k^4β^−4) iterations.Source: §B.9 · p. 32

C Aggarwal’s hardness bounds in the continuous and discrete oracle models

The section establishes hardness ceilings for continuous and discrete DR-submodular optimization through symmetry gaps and replicated instances that hide nonsymmetric structure from oracle algorithms. Aggarwal’s threshold β* applies to the stated continuous oracle model and to discrete submodular maximization under three-block partition matroids.

C Aggarwal’s hardness bounds in the continuous and discrete oracle models

  • Aggarwal’s three-group family has symmetry gaps converging to β*, while polynomially many exact value/full-gradient queries cannot distinguish its instances from a symmetric reference.The gap is the ratio of the best symmetric value to the optimum.Source: C Aggarwal’s hardness bounds in the… · pp. 32–33
  • No polynomial-query algorithm in the stated continuous oracle model can guarantee a fixed ratio above β*, even with linear maximization over intersections with polynomially many supplied inequalities.The guarantee includes additive error δLD^2.Source: C Aggarwal’s hardness bounds in the… · p. 33
  • For discrete nonnegative submodular maximization, every fixed expected ratio above β* requires exp(Ω(|E|)) value queries, even for explicitly given three-block partition matroids.The lower bound allows unrestricted computation between queries.Source: C Aggarwal’s hardness bounds in the… · p. 33
  • β* is a smaller ceiling than Feldman–Kuhnle’s 8/17 ceiling for the set-function value-oracle model, though their hard instances use different constraint subclasses.Aggarwal’s threshold is established using three-block partition matroids.Source: C Aggarwal’s hardness bounds in the… · pp. 33–34
  • Smoothing and coordinate replication preserve a bounded L D^2 scale while producing instances with the same hardness threshold under the continuous guarantee with additive error δLD^2.The replicated objective has smoothness L0/m, and the squared diameter grows at most linearly with the number of copies.Source: C Aggarwal’s hardness bounds in the… · pp. 32, 34

Related papers

Loading 2610.21072v1…