PaperlayerView exact revision on arXiv

Source-linked AI summary

A Sharp Barrier for Consistent Submodular Maximization: Any Improvement over $2-\sqrt{2}$ Entails Exponential Queries or Linear Recourse

Shi Fu, Qixin Zhang, Dacheng Tao

arXiv:2609.09986v1cs.DScs.LG

TL;DR

The paper studies how approximation quality trades off against constant recourse when submodular solutions must remain stable as elements arrive. It proves a barrier to fixed improvements under polynomial query budgets, gives positive results for coverage, and separates certificate existence from efficient computation.

  • Problem

    Consistent submodular maximization asks how much value is lost when a maintained solution must change only a constant number of elements after each arrival.

  • Method

    The paper combines a barrier argument for hidden future complements with constructive algorithms and certificate analyses for general submodular objectives and structured classes.

  • Results

    Any fixed improvement requires exponentially many queries before a critical arrival or linear recourse there, while weighted coverage attains 1-1/e-epsilon with O(epsilon^-1) recourse.

  • Takeaways & Limitations

    Consistency imposes a joint information–movement threshold, while coverage and represented matroid-rank sums can recover stronger guarantees through explicit response structures.

  • Takeaways & Limitations

    The universal-price result is an existence proof: direct computation requires an exponential current value table and an exponential constraint system.

Abstract

from arXiv · show

Consistent submodular maximization studies the tradeoff between solution quality and stability when elements arrive over time. For a monotone submodular objective, which models diminishing returns, an algorithm maintains a set of at most $k$ available elements and changes only $O(1)$ elements after each insertion. Dütting et al. [2025] established a tight $2/3$ approximation with unrestricted computation and a polynomial-time $0.51$ approximation. They left open at STOC 2025 whether efficient algorithms can match the offline $1-1/e$ guarantee. We resolve this problem by proving that the supremum approximation achievable with polynomially many value queries and worst-case constant recourse is \[ β=2-\sqrt2\approx0.5858<1-1/e. \] For every $\varepsilon>0$, our randomized algorithm attains $β-\varepsilon$ with $O(\varepsilon^{-2})$ changes per insertion. Any fixed improvement requires exponentially many queries before one critical insertion or linear recourse of $Ω(k)$ changes at that insertion, even with unlimited queries afterwards. This gap quantifies the cost of consistency: the current oracle hides which elements will be needed after an arrival. We also determine the exact curvature-dependent threshold $1-(\sqrt2-1)\vartheta$, attain $1-1/e-\varepsilon$ for weighted coverage with $O(\varepsilon^{-1})$ recourse, and separate the existence of universal future-price certificates from their efficient computation. Our algorithm has a bounded-bit polynomial-time implementation for polynomial-bit rational oracle answers; the lower bound uses only logarithmic-bit rational answers.

1 Introduction

The paper resolves whether efficient consistent submodular maximization can match the offline guarantee, identifying a sharp threshold below 1−1/e and proving matching query–recourse barriers. It also extends the analysis to curvature, weighted coverage, and universal future-price certificates.

  • 1 Introduction: The algorithm attains β−ε with O(ε^−2) recourse per insertion using polynomially many current value queries.Under polynomial-bit rational oracle answers, it has a bounded-bit randomized polynomial-time implementation.
  • 1 Introduction: Any fixed improvement over β requires exponentially many queries before a critical arrival or Ω(k) changes at that arrival.The lower bound remains valid with unlimited queries and computation after the critical arrival.
  • 1.1 Our Results: For curvature bound ϑ, the exact threshold is 1−(√2−1)ϑ, with exact optimum at ϑ=0 and additional loss (√2−1−1/e)ϑ relative to the offline coefficient.The offline coefficient is 1−ϑ/e, and the threshold is attainable up to ε with O(ε^−2) recourse.
  • 1.1 Our Results: Weighted coverage attains 1−1/e−ε with O(ε^−1) recourse using only the aggregate value oracle.The paper also states that a fixed improvement in this setting would imply NP ⊆ BPP.
  • Proof strategy: The proof uses current-value-only randomized cores and checkpointed migration, while hidden-group instances establish the matching obstruction.A second certificate framework separates universal certificate existence at 1−1/e from efficient computation above 2−√2.

2 A Future-Robust Core and Its Online Implementation

The section constructs a future-robust core from current values using anchored greedy sampling, then converts it into an online algorithm with bounded recourse. The core achieves the sharp coefficient β against every legal future branch, while checkpointing provides explicit recourse guarantees.

  • 2.1 Anchoring a Greedy Prefix: Anchored samplers retain a greedy prefix and uniformly select additional elements, interpolating between certified endpoint values while keeping every output feasible.For 0 ≤ a < κ < b ≤ 2κ, the sampler retains G_a and selects a uniform (κ−a)-subset of G_b \ G_a.
  • 2.1 Anchoring a Greedy Prefix: The mixture linear program has an optimal solution supported on at most two labelled actions and can be computed in O(κ^2 log(κ + 1)) arithmetic operations.Its dual value is characterized by the upper hull of the labelled coefficient points.
  • 2.1 Anchoring a Greedy Prefix: A core mixture achieves E_h(A) ≥ βP_h for every legal future branch using O(|X|κ) current value queries and polynomial computation.The construction is based on anchored greedy samplers and a linear program over labelled actions.
  • 2.2 The Finite-Cardinality Constant: The upper-bound geometry yields β = 2−√2, while finite capacity admits a coefficient β_κ > β approaching β at rate Θ(1/κ).The paper does not claim optimality at fixed capacity.
  • 2.3 An Online Schedule with Hard Recourse: Checkpoint conversion turns any current-only sampler with guarantee α into an online algorithm with approximation α(1−2/B)(1−1/B) and hard symmetric recourse at most 8B^2 + 2.The schedule migrates between cores through a randomized window while recent arrivals preserve feasibility and a lazy superset controls changes.

3 A Matching Oracle Lower Bound

The lower bound hides a useful current k-set until a final arrival, showing that improving beyond the threshold requires either many pre-arrival queries or substantial recourse. A rational, monotone submodular oracle makes this obstruction exact while preserving the query–recourse tradeoff against adaptive algorithms.

  • 3.2 Exact Hiding and Adaptive Queries: The hard instance hides a uniformly random k-set A among (m + 1)k current elements, while answers on ordinary queries depend only on query size outside an exceptional band.The hidden partition is embedded in one monotone submodular function defined on the full ground set.
  • 3.1 Coupled Current and Future Profiles: The analytic construction couples current and future profiles through a supporting-line geometry whose balanced value approaches the threshold while the hidden complement has value near one.The rational finite oracle preserves the profile properties using clipping, regularization, and polynomial replacements for exponentials.
  • 3.2 Exact Hiding and Adaptive Queries: Transcript hiding ensures that, with probability at least 1 − 2(Q + 1)e^(-δ^2k/2), the algorithm’s pre-arrival transcript and output match a reference execution and have imbalance at most δ.The proof fixes the reference transcript before applying concentration, which handles adaptive queries.
  • 3.3 A Finite Query–Recourse Bound: The finite bound is at most R(T) + 76/m + 10(C + 1)/k + 2(Q + 1)e^(-k/(8192m^2)), with rational answers requiring only O_ζ(log n) bits after fixing the target improvement.The construction also supplies exact rational answers and applies to arbitrary value-query algorithms.
  • 3.3 A Finite Query–Recourse Bound: A single final arrival can force any fixed improvement beyond β to use exponentially many pre-arrival queries or Ω(k) changes.The tradeoff remains even with unrestricted queries after the arrival.

4 Universal Future Prices: Existence and Query Complexity

Universal future-price certificates exist at the offline coefficient 1−1/e, but constructing any bounded certificate above β requires exponentially many current queries. Below β, current-only price routines can be converted into future-robust feasible cores.

  • Certificate-to-core conversion: A price satisfying Equation (4.1) certifies a future-robust response whenever its gap at the current point is at most ηM, yielding Hh(x) ≥(α−ξ−η)Ph.The conversion uses the comparator maximizing Ph and the fact that Ph ≥M for capacity κ≥1.
  • Certificate-to-core conversion: Projected online linear optimization and future-oblivious rounding convert bounded current-only prices into a feasible core that works for every fixed future.The randomized routine uses at most 32κn/η^2 calls, while conditional validity is required for the stated high-probability guarantee.
  • Existence of universal prices: 1−1/e universal future-price certificates exist for every current function and fractional point, independently of the budget and compatible future.The selector depends only on the current restriction, and minimax plus compactness supplies a feasible bounded price.
  • Computational distinction: The price framework distinguishes certificate existence from efficient computation: direct feasibility optimization may require an exponential value table and constraint system.The universal-price theorem is therefore an existence result rather than a polynomial-size optimization formulation.
  • Query complexity: Exponential Ωα(n) current queries are required to find a bounded price above β with constant probability, even when constraints must hold simultaneously for all legal futures and comparators.The lower bound applies to arbitrary bounded vector outputs and permits unlimited computation after the current query phase.

5 The Exact Curvature Law

The paper derives an exact curvature-dependent approximation threshold by preserving modular value while applying the submodular core construction to the residual objective. The matching lower bound shows that improving this threshold requires linear recourse or exponentially many queries.

  • Implementation: The finite-bit implementation remains randomized polynomial time for polynomial-bit rational oracle answers, without changing feasibility or the pathwise recourse bound.Approximate stationarity, failure, rounding, and replacement errors are combined into the final additive guarantee.
  • Hybrid construction: The hybrid benchmark b(U)=ℓ(U)+βg(U) preserves the modular contribution exactly while applying the β guarantee to the submodular part.The modular identity requires suffix elements to be disjoint from the current snapshot, which is built into the checkpoint construction.
  • Checkpoint migration: Checkpoint migration maintains the hybrid guarantee with hard symmetric recourse at most 8B^2+2, using a core of capacity κ=k−2L and a lazy-superset update.The schedule reserves recent positions and migrates between checkpoint cores within randomized windows.
  • Lower bound: Any fixed improvement over the curvature threshold forces C=Ωϑ,ζ(k) recourse or Q=exp(Ωϑ,ζ(k)) queries on arbitrarily large instances.The lower-bound parameters are chosen so that approximation errors from the rational profile and finite-k normalization are below the prescribed improvement.

6 When Stronger Prices Are Accessible

This section shows that structural promises can make stronger future-price certificates efficiently accessible. Weighted coverage reaches the offline coefficient with aggregate queries, while matroid-rank sums do so with persistent component-rank access.

  • Coverage: 1−1/e−ε is attainable for weighted coverage with O(ε−1) recourse using only aggregate current-value queries.The implementation does not require the coverage representation and has polynomially bounded computation for polynomial-bit rational answers.
  • Coverage: Coverage’s aggregate oracle exposes the Poisson extension and gradient needed for certificate construction without revealing the underlying atoms.Although the proof uses an atom representation, the relevant quantities are determined by the current aggregate function.
  • Migration: Independent slots convert fractional cores into feasible sets while concavity preserves guarantees during migration between snapshots.For old and new cores x and y, the expected value is bounded through HR((1−λ)x+λy) and concavity.
  • Migration: At most c positions change per update, yielding a pathwise recourse bound for the consistent slot schedule.The maintained invariants include |Kt|≤κ, |Rt|≤2L, and at most c position changes per insertion.
  • Coverage: A fixed improvement above the coverage coefficient would imply NP ⊆ BPP, even without a recourse restriction.The reduction distinguishes YES and NO instances using repeated runs and Hoeffding’s inequality.
  • Matroid-rank sums: Matroid-rank sums also attain α0−ε with O(ε−1) hard recourse when persistent component rank oracles are supplied.The construction uses certificate and averaging arguments at nonsmooth points before applying the slot converter.

7 Discussion

The discussion interprets the threshold as an information–movement trade-off rather than merely an oracle or stability barrier. It also identifies scope limits and open questions about recourse, storage, update time, and broader structural classes.

  • Interpretation: The threshold reflects a joint information–movement constraint: useful old elements become identifiable only when bounded recourse leaves too little time to move.The obstruction persists despite unlimited post-arrival queries and computation, and does not require an adaptive adversary.
  • Certificates: Universal product-response certificates exist at 1−1/e, but computing them uniformly above 2−√2 requires exponentially many queries.This separates certificate existence from efficient certificate computation.
  • Structural promises: Coverage escapes the general price barrier through concavity, while represented matroid-rank sums use explicit principal-partition prices and persistent component access.Neither positive algorithm queries future arrivals or assumes a future-arrival distribution.
  • Scope: The results are limited to insertion-only streams, an oblivious adversary, fixed-time expected approximation, and pathwise symmetric recourse.They allow full-prefix retention, infeasible current queries, and polynomial rather than sublinear update work.
  • Open questions: Open problems include the minimum recourse needed near β, the approximation curve at fractional recourse, smaller storage and update time, and aggregate-query algorithms for matroid-rank sums.These questions concern regimes not resolved by the present results.
  • Implementation: The bounded-bit implementation assumes exact polynomial-bit rational current-oracle answers and caps randomized work deterministically.This specifies the computational model used for the algorithmic guarantees.

A.1 The Checkpoint Schedule

The checkpoint schedule maintains a feasible displayed set while migrating between anchored cores over randomized windows. It converts gradual target changes into a pathwise bounded-recourse update rule.

  • Feasibility: The lazy-superset rule preserves the target inside a feasible set of size at most k while deleting only enough retained elements to restore capacity.The number of deletions is bounded by the number of newly inserted target elements.
  • Schedule construction: A block uses L=⌊k/B⌋, κ=k−2L, W=⌊L/B⌋, and c=⌈κ/W⌉ to migrate core positions over a selected window.The schedule pads cores with nulls and keeps the window choice fixed throughout the block.
  • Recourse: At most c+1 target elements enter per update, including block boundaries, so the same bound applies throughout migration.The recent suffix gains one arrival while at most c core positions are replaced.
  • Schedule guarantee: 8B^2+2 bounds symmetric recourse pathwise, covering both the large-k checkpoint schedule and the small-k greedy branch.The lazy-superset rule doubles the target insertion bound, while small instances use recomputed greedy sets.
  • Random windows: Outside the selected migration window, the target is a complete old or new core; for a fixed time, the exceptional window event has probability at most 1/B.The disjoint windows ensure that a fixed position is exceptional for at most one window choice.
  • Approximation: The maintained target inherits an α-approximation to the κ-cardinality benchmark at every nonexceptional time, and κ-subset sampling relates that benchmark to the k-cardinality optimum.The first block is exact, while OPTκ(Xt)≥(1−2/B)OPTk(Xt).

A.2 The Anchored Core and Random Windows

The anchored-core implementation uses polynomial-query greedy-chain computations and finite-bit randomized sampling. Rounding mixture weights and window choices introduces controlled total-variation error without accumulating across checkpoints at a fixed time.

  • Core computation: The greedy chain uses O(nκ) oracle calls, while upper-hull processing uses O(κ^2 log(κ+1)) arithmetic operations.The implementation avoids exact optimization over unknown future scales.
  • Finite-bit sampling: Rounding mixture weights to multiples of 2^-ℓ changes the mixture law by at most 2^-ℓ in total variation.The remaining mass is assigned to the other action, preserving a finite-support sampling procedure.
  • Finite-bit sampling: Combination unranking uses polynomially many exact integer operations, even when the resulting sampling law is not exactly uniform.All combinations remain feasible under the residue-based sampling procedure.
  • Error control: The implemented core loses at most 2^(1−ℓ) in coefficient relative to the fixed-future benchmark.The error is measured relative to Ph rather than as an unbounded absolute function-value error.
  • Random windows: Window selection has probability at most 1/B+2^-2ℓ for each window, with randomness independent of core bits.The fixed-time comparison couples only variables determining the prescribed target time.
  • Error control: Choosing B=⌈6/ε⌉ and 2^(1−ℓ)≤ε/2 makes the total implementation loss at most ε-scale.The accompanying window error satisfies 2^-2ℓ≤ε/4.

A.3 A First-Order Gap in Polynomial Work

The routine constructs approximate gradients for several potentials, updates a capped-simplex point using estimated directions, and proves a first-order stopping guarantee with bounded polynomial work.

  • Gradient-based routine: The iterative method estimates gradients, moves toward their top-κ coordinates, and returns when the estimated directional gap is small.It starts from the uniform point and clips estimates to known nonnegative bounds.
  • First-order guarantee: At stopping, the true directional gap is at most 5ηM/8, while every nonstopping iteration improves the potential by a quantified amount.The proof controls estimation error using the ℓ1 diameter of the capped simplex and a Hessian bound.
  • Work bound: The potential range bounds the number of nonstopping iterations, so the method avoids global maximization of a nonconcave potential.This yields a deterministic iteration cap after accounting for the potential’s range.
  • Implementation: Fixed-bit sampling, dyadic exponential approximations, and rational iteration choices provide polynomial bit complexity and a bounded deterministic query count.Feasibility is preserved even when an estimate is inaccurate, without unbounded rejection sampling.
  • Sampling accuracy: Sampling estimates remain valid conditionally on adaptive optimization history, and a union bound makes all estimates accurate with probability at least 1−δfail.The estimator uses Hoeffding’s inequality and an integer logarithmic upper bound.

A.4 Rounding and the Hybrid Error Budget

The hybrid construction converts a fractional core into an integral feasible solution while budgeting approximation, subsampling, rounding, and bad-window losses within ε.

  • Rounding: Mean-preserving pair rounding uses convexity of the multilinear extension along exchange directions, so integral endpoints preserve or improve expected value.The argument applies after adjoining any fixed future set.
  • Hybrid error budget: Choosing η=δfail=ρ=ε/64 and T/(1+T) near β bounds the static hybrid-core loss by εOPTk(f,Xt)/16.The bound applies at a checkpoint where the recent set and core together fit within capacity.
  • Window losses: With B=⌈16/ε⌉, subsampling and bad-window losses combine with the static loss to remain below εOPTk(f).The random-window probabilities are bounded by 1/B+ε/64.
  • Recourse: The resulting recourse is 8B^2+2, yielding the explicit bound used in the main theorems.The choice B=⌈16/ε⌉ makes the dependence on ε explicit.
  • Finite-bit implementation: Dyadic probability rounding changes the ideal distribution by at most ρ/κ per draw and at most ρ jointly for active positions.Both coupled outputs remain feasible, so objective loss is bounded by ρOPTk.

A.7 The Finite-Capacity Gain

Finite capacity yields a strict improvement over the limiting coefficient through a two-action mixture, with an explicit gain that converges to β as capacity grows.

  • Finite-capacity guarantee: For every finite κ, the Equation (2.4) mixture guarantees Eh(A)≥βκPh for every legal future, with βκ>β.The construction uses the existing LP and sampling law and supports polynomial implementation.
  • Proof mechanism: The proof derives the gain by bounding grid-cell slack, integrating derivative inequalities, and optimizing over the dual multiplier.The argument separates the γ≥3/5 branch from the active radical branch.
  • Asymptotic gain: The finite-capacity coefficient approaches β at rate Θ(1/κ), although optimality at fixed capacity is not claimed.For sufficiently large κ, the radical branch is active in the minimum defining βκ.
  • Oracle setup: The oracle construction fixes rational parameters and piecewise profiles whose current and future expressions meet through tangent-based continuation.The profiles are designed to preserve the finite-capacity guarantee’s analytic structure.

B.1.1 Exact flattening and rational replacement

The lower-bound oracle uses an exactly flat information band and rational polynomial profiles, then verifies monotonicity, submodularity, compatibility, and finite-bit implementability.

  • Exact flattening: Exact flattening makes current oracle answers depend only on aggregate query size within a band, independently of the hidden partition.Approximate agreement would not suffice for an exact value oracle, so the construction enforces algebraic equality.
  • Profile construction: The profiles use clipping and tangency to connect the current and future branches while preserving derivative continuity at boundaries.The tangency point lies between the relevant profile arguments, and clipping keeps the construction within controlled segments.
  • Submodularity margins: A regularizer supplies positive gradients and negative Hessian bounds, ensuring coordinatewise diminishing returns for both current and future profiles.The resulting margins include gradients at least 16e−s/m and nonpositive second derivatives almost everywhere.
  • Rational replacement: Replacing exponentials by a fixed polynomial yields rational profiles that retain the exact flat band, monotonicity, diminishing gradients, and cross-future inequalities.Values and derivatives differ from their analytic counterparts by at most 4τ, while coordinate gradients remain in [0,5].
  • Discrete validity: Continuous derivative signs certify the discrete oracle globally, including finite differences crossing clipping and profile-piece boundaries.Absolute continuity permits integration of almost-everywhere second-derivative inequalities to obtain discrete diminishing returns.

B.3 A Certified Finite Degree and Exact Arithmetic

This section establishes finite-degree rational replacements whose signs and continuity preserve the analytic inequalities needed by the construction, while keeping oracle answers polynomial-time computable with logarithmic bit length.

  • Certified finite degree: Exact rational parameter tests certify the polynomial degree without numerical exponential evaluation, yielding D = O(m + log(1/τ)).The tests use exact rational arithmetic and bounds on factorials and successive terms.
  • Certified finite degree: Polynomial replacement preserves the derivative signs and analytic inequalities required throughout the construction.The tail has the needed signs through third order, and the resulting gradient and Hessian inequalities extend across piecewise boundaries.
  • Exact arithmetic: The construction retains exact flat-band identities and preserves the future-value inequalities needed for monotonicity and nonnegativity.The future inequality follows from exact signs, concavity of the new tail, and a tangent argument.
  • Exact arithmetic: All coefficients and breakpoints are fixed rationals, and each oracle answer has O_T,m,τ(log(k + 1)) bits computable in polynomial time.Queries use rational normalized counts and exact comparisons to select polynomial pieces.
  • Adaptive transcripts: Adaptive pre-arrival queries remain coupled to the reference execution except with probability 2(Q + 1)e^(-δ²k/2), even when queries are infeasible.Conditioning on the complete random tape fixes the queried sets independently of the hidden set.
  • Parameter order: For any fixed target gap ζ, parameter choices independent of k, the hidden set, and the random tape force exponential queries or linear final-update changes.The resulting exponent is c_ζ = 1/(8192m²), and the hard ground set has size Θ_ζ(k).

B.5 Expected Resources and Almost-Sure Termination

This section extends the lower-bound argument to expectation-based resource promises and almost-sure termination, while distinguishing uniform guarantees from guarantees restricted to the finite hard family.

  • Reference execution: The reference profile is a normalized nonnegative monotone submodular function with the same current answers, degree, and logarithmic answer-length bound as the hard family.This supplies an almost-surely terminating reference execution with expected pre-arrival query count at most Q under a uniform promise.
  • Almost-sure termination: The reference execution may fail to satisfy resource promises or terminate when those promises hold only on the hard family.A separate proposition handles this distinction under almost-sure termination on the finite hard family.
  • Expected resources: The expected-resource lower bound applies to algorithms with almost-sure termination and feasible outputs on every member of the finite hard family.The expected query and recourse bounds need not be deterministic.
  • Reference execution: Capped simulations make the reference transcript finite, allowing fixed-set concentration and a limit argument without any running-time moment bound.The computation cap is removed after taking its limit, followed by optimization over the query cap.
  • Expected resources: A fixed improvement over β requires linear expected final recourse or exponentially many expected pre-arrival queries under either expectation promise.The stronger exceptional term requires a uniform valid-instance query guarantee, whereas the hard-family proposition does not.

C.3 Exact Current-Rank Computation and the Online Theorem

This section gives an exact current-rank procedure for principal prices and derives an online theorem for persistent matroid-rank access with polynomial computation and hard recourse guarantees.

  • Exact current-rank computation: Maximum-density principal blocks are computed by binary-searching their rational densities through submodular minimization and exact rational reconstruction.Perturbation selects the maximum-cardinality minimizer, whose union is the unique maximal minimizer before contraction.
  • Exact current-rank computation: The procedure uses at most n blocks, with O(log(v(X) + 1) + log n) submodular minimizations per binary search.Clearing denominators yields integer-valued polynomial-encoding objectives without changing minimizers.
  • Implementation: Downward price approximation and component-rank access keep the aggregate computation polynomial in the number of components, weight bit length, and requested precision.Each component contributes through its rank oracle, and zero-load components contribute exactly zero.
  • Online theorem: The resulting deterministic fractional core reaches α0 − ε after slot conversion with B = ⌈2/ε⌉ and hard recourse 4B + 2.For k < 2B, the method recomputes ordinary greedy.
  • Scope: Maximum coverage is representable as a sum of explicit rank-one matroids, but the result is not a hardness theorem for recovering an unknown decomposition.It also does not establish a new lower bound on recourse.
Loading 2609.09986v1…