PaperlayerView exact revision on arXiv

Source-linked AI summary

Geometry-Dependent Approximation for Non-Monotone $k$-Submodular Maximization

Vaneet Aggarwal

arXiv:2610.04049v2cs.DScs.LGmath.OC

TL;DR

Non-monotone k-submodular maximization under support constraints lacks guarantees that reflect how much of the ground set may be selected. The paper derives a continuous, diagonal-level-dependent approximation profile from a comparator-uniform inequality for the multilinear extension. It reports positive zero-level coefficients, with values reaching 1/2 above explicit levels for finite k≥3, and extends guarantees to online optimization and constrained rounding.

  • Problem

    Existing constrained guarantees do not reflect how much of the ground set a support constraint permits, despite that range extending from selecting a small fraction to selecting all candidates.

    Source: §1 · p. 4

  • Method

    A comparator-uniform multilinear-extension inequality yields a diagonal-level-dependent profile using an objective-independent action and a comparator-independent update direction.

    Source: §1 · pp. 4, 6

  • Results

    At ζ=0, the coefficients are 0.4456... for k=2 and 0.4541... for k≥3; for finite k≥3, they reach 1/2 above an explicit level.

    Source: §1 · pp. 4–5

  • Takeaways & Limitations

    The guarantees extend to online optimization and rounded matroid and knapsack solutions, including high-probability offline matroid guarantees.

    Source: §1 · p. 7, §6 · p. 42

    The online bound has an additive term independent of T that can exceed the leading-term gain at short horizons.

    Source: §4.2 · p. 34

Abstract

from arXiv · show

We study the maximization of a nonnegative $k$-submodular function, not assumed monotone, in which each of $n$ elements receives one of $k\ge2$ labels or stays unselected and the selected elements must satisfy a constraint. For a compact convex down-closed region $P\subseteq[0,1]^n$ of fractional selection vectors, the diagonal level $\zeta(P)=\max\{t\in[0,1]:t(1,\ldots,1)\in P\}$ is the largest selection probability that can be given to all elements at once; it equals $r/n$ for a uniform matroid of rank $r$, and $\zeta(P)=1$ means that the constraint is vacuous. We give approximation coefficients that increase continuously with $\zeta$. They come from one inequality for the multilinear extension of the objective: the algorithm computes an action without querying the objective, and objective feedback gives a comparator-independent update direction. For $k\ge3$, feasibility of the action reduces to three polynomial inequalities in one variable; for $k=2$ the profile is closed form. At $\zeta=0$ the coefficients are $0.4456\ldots$ for $k=2$ and $0.4541\ldots$ for every $k\ge3$. For every finite $k\ge3$ they reach $1/2$ above an explicit level, which is $0.4026\ldots$ for $k=3,4,5$, and at $\zeta=1$ they reach $1/2$ for $k=2$, $(\sqrt{17}-3)/2$ for $k=3,4$, and $k/(2k-1)$ for $k\ge5$. Online linear optimization gives $O(\sqrt T)$ approximate regret, with gradient feedback or with value queries made after each action. The coefficients carry over to matroids, with expected and high-probability guarantees, and to any fixed number of knapsacks: the zero-level coefficients hold on every instance, and the larger ones when items are small or when prefix enumeration keeps the diagonal level on one branch. For one budget the enumeration exponent is $O(1/\varepsilon)$.

1. Introduction

The paper develops approximation guarantees for nonnegative, non-monotone k-submodular maximization whose coefficients depend on the support region’s diagonal level. A comparator-uniform inequality for the multilinear extension supports fractional and online optimization, with rounding extending guarantees to matroids and knapsacks.

1. Introduction

  • The objective assigns each selected element one of k labels, and support constraints determine which elements may be selected regardless of their labels.The nonnegative objective class is not assumed to be monotone.Source: §1 · p. 4
  • The approximation profile α_k(ζ) is continuous and nondecreasing, linking the support constraint’s diagonal level to the coefficient guaranteed for fractional and integral solutions.For a uniform matroid of rank r, the diagonal level is r/n; level 1 means the support constraint is vacuous.Source: §1 · p. 4
  • At ζ=0, the coefficients are 0.4456... for k=2 and 0.4541... for k≥3; for finite k≥3, they reach 1/2 above explicit levels.The level is 0.4026818391... for k=3, 4, and 5, and increases with k thereafter.Source: §1 · pp. 4–5
  • A comparator-uniform inequality uses an objective-independent feasible action and a comparator-independent update direction to reduce approximation to linear optimization over the feasible region.The inequality retains a term involving f(0), the objective value of the empty labeling.Source: §1 · p. 6
  • For k≥3, action feasibility is certified by three polynomial tests in one variable, corresponding to uniform, two-label, and pure-label mass distributions.For a parameter choice valid across label counts, the tests reduce to an endpoint inequality and a cubic.Source: §1 · pp. 6–7
  • The same field supports fractional and online guarantees under full-prefix, gradient, and value feedback; online approximate regret is O(√T).Value queries may be made after the action is committed, including at labelings other than the played one.Source: §1 · pp. 7–8
  • Conditional label sampling and rounding extend guarantees to matroid and knapsack constraints, including high-probability matroid guarantees and small-item or prefix-enumeration knapsack guarantees.For one budget, the enumeration exponent is O(1/ε).Source: §1 · pp. 5, 7, 8

2. Problem Setup

The section formalizes nonnegative, potentially non-monotone k-submodular maximization over label-independent feasible supports, then lifts the problem to a multilinear relaxation over fractional supports.

2.1. The discrete maximization problem

  • The discrete problem assigns each element one of k labels or 0 and maximizes a nonnegative k-submodular objective over a down-closed, label-independent support family.Source: §2.1 · pp. 9–10
  • Its marginal characterization combines orthant diminishing returns with pairwise monotonicity, permitting negative gains for a label when another label compensates.Source: §2.1 · p. 9

2.2. The multilinear extension

  • The multilinear extension F(x) is the expected objective under independent per-element label draws, equals f on integral labelings, and is block-multiaffine.Source: §2.2 · pp. 10–11
  • Its gradients decrease as coordinates grow, and F is concave along nonnegative or nonpositive directions; fixed-label restrictions are submodular.Source: §2.2 · p. 11

2.3. Support geometry

  • A convex relaxation P induces feasible fractional labelings through support-mass vectors, and its diagonal level is the largest ζ such that ζ1 belongs to P.Source: §2.3 · p. 11
  • For a uniform matroid of rank r, the diagonal level is r/n; for a general matroid it is the minimum rank-to-size ratio over nonempty subsets.Source: §2.3 · p. 12

3. Comparator-Uniform Linearization

This section constructs objective-independent actions and comparator-independent linear update fields that support a comparison guarantee for every feasible comparator. It certifies these guarantees with polynomial conditions and develops continuous, nondecreasing coefficient profiles over diagonal levels, including endpoint guarantees and sufficient levels for a 1/2 coefficient.

3.1. From block inequalities to a comparator-uniform comparison

  • For every x,y in D, F(y) + C f(0) ≤ (1 + C + W)F(p(x)) + ⟨g_F(x), y − x⟩, with the same action and field for all comparators.The action and field depend on the input state and objective, but not on the comparator.Source: §3.1 · p. 13
  • If |p(z)| ≤ μ|z| + (1 − μ)ζ for every input block, then p maps K(P) into K(P); mass-preserving rules also preserve arbitrary convex support regions.The mass bound combines convexity of P, its diagonal point ζ1, and down-closedness.Source: §3.1 · p. 14

3.2. Weighted block rules and their polynomial certificates

  • For k ≥ 3, the weighted level rule raises tail probabilities from floors until resource surplus covers the block demands; when its action mass is at most one, it satisfies (B0)–(B2).Its mass requirement reduces to two scalar inequalities per block.Source: §3.2 · pp. 17–18
  • For k = 2, the pairing cone is a ray, and the rule instead solves explicitly for the action imbalance and total mass.The imbalance and mass are determined by the input mass, label imbalance, and parameters.Source: §3.2 · p. 19
  • For k ≥ 3, the weighted level rule’s mass certificate reduces to three one-variable tests and yields coefficient (1 − ω)/(1 + c) while preserving K(P).The same parameters work for every label count from 3 through k.Source: §3.2 · pp. 19–21

3.3. The certified approximation profile

  • For every admissible parameter triple, the action is objective-independent and the linear field gives a comparator-uniform inequality while preserving feasibility in K(P).The coefficient is α = (1 − ω)/(1 + c), and the field coordinates are linear in the objective.Source: §3.3 · p. 22

Proposition 2 (Zero-diagonal parameters)

  • At ζ = 0, the two-label coefficient is 0.4456016834…, and its certified profile is nondecreasing and reaches 1/2 at ζ = 1.The coefficient stays constant through ζ = t2; the profile is C1 on [0, 1].Source: Proposition 2 (Zero-diagonal parameters) · pp. 23–24
  • For k ≥ 3, the supporting-line construction gives continuous, nondecreasing profiles that are nonincreasing in k, with identical profiles for k = 3 and k = 4.Between the plateau and ζ0, the transition branch is independent of k.Source: Proposition 2 (Zero-diagonal parameters) · p. 25
  • The profile uses a zero-diagonal plateau through t3, a weighted transition through ζ0, and pure-label or balanced tangencies on stated intervals.The plateau and transition join with matching first derivatives on their stated initial ranges; the pure and balanced coefficient formulas increase strictly on accepted ranges.Source: Proposition 2 (Zero-diagonal parameters) · pp. 26–27
  • At ζ=0, α2(0)=0.4456016834… and αk(0)=0.4541264676… for k≥3; profiles are continuous and nondecreasing, with those for k≥3 nested and α3=α4 on [0,1].Source: Proposition 2 (Zero-diagonal parameters) · p. 28
  • For 3 ≤ k ≤12, an unweighted comparison certifies α = 1/2 when ζ(P) ≥ 49/100.A separate example gives α = 45/86 for 3 ≤ k ≤10 when ζ(P) ≥ 9/10.Source: Proposition 2 (Zero-diagonal parameters) · p. 30
  • For every finite k ≥3, a coefficient of 1/2 is certified whenever ζ ≥ ζ1/2(k); the sufficient level is 0.402682 for k = 3–5 and increases toward 1 as k grows.The listed levels include 0.408161 for k = 6, 0.475074 for k = 11, and 0.4878056924… for k = 12.Source: Proposition 2 (Zero-diagonal parameters) · p. 31

4. Fractional Optimization and Online Learning

The section turns comparator-independent objective feedback into fractional approximations and online regret guarantees, with field estimates available through gradient and value-query models. Coordinate normalization and removal of inactive elements can improve the diagonal level used by the guarantees.

4. Fractional Optimization and Online Learning

  • The field controls the nonlinear reward of the played action by a linear function of any comparator, enabling online linear optimization to yield approximation and regret guarantees.The action is computed without querying the objective, and the field does not depend on the comparator.Source: §4 · p. 31, §4.2 · p. 32

4.1. Access model and field estimators

  • One-gradient, two-value, one-value, and full-prefix feedback each give unbiased field estimates, with the full-prefix scan evaluating all nk marginals using nk + 1 values.The first-order query is made at a feasible lower-chain point; value-based estimates use discrete marginal queries.Source: §4.1 · p. 32

4.2. Fractional optimization and online guarantees

  • Theorem 9 uses entropy mirror ascent with full-prefix feedback to obtain a fractional approximation, while Theorem 10 extends the same field-based approach to online approximate regret.The online protocol commits an action before current-round feedback; the same expected guarantees hold for objective-independent matroid rounding.Source: §4.2 · pp. 33–34
  • Entropy and Euclidean projected ascent provide online guarantees with different horizon requirements, and exact two-value feedback admits a local-norm bound.The Euclidean horizon is larger by a factor k/log(k + 1); the local-norm result assumes an oblivious sequence, exact two-value feedback, and bounded support mass.Source: §4.2 · pp. 33–34

4.3. Coordinate capacities and inactive elements

  • Rescaling coordinates by their feasible capacities gives a normalized diagonal level at least as large as the original, and the profile guarantee applies at that level.The capacities must be supplied or computed with additional geometric access; a projection oracle alone does not provide them.Source: §4.3 · pp. 35–36
  • Removing inactive elements can increase the diagonal level without changing the optimum for down-closed support families; a uniform matroid with m active elements has level r/m instead of r/n.Online removal requires an element to be inactive for every objective in the sequence.Source: §4.3 · p. 37

5. Integral Guarantees

The fractional guarantees transfer to feasible labelings through conditional-label rounding, with matroid guarantees retaining the extension value in expectation. Knapsack guarantees use small-item rounding or prefix enumeration, with stronger diagonal-dependent coefficients subject to the stated conditions.

5.1. Matroids

  • A matroid support constraint admits a randomized (α−ε)-approximation, with expected guarantees also extending to exact bases through objective-independent completion.The expected guarantee uses O(nkr^2 log(enk/r)/ε^2) value queries for rank r, followed by one final matroid rounding.Source: §5.1 · p. 38
  • For uniform matroids, r/n ≥ ζ1/2(k) gives a (1/2−ε)-approximation for every k ≥3; for 3 ≤k ≤10, r/n ≥9/10 gives a (45/86−ε)-approximation.Here the diagonal level of a rank-r uniform matroid is r/n.Source: §5.1 · p. 38

5.2. Knapsacks

  • For one budget, small-item rounding is objective-independent and loses a linear factor in the item threshold, yielding an O(1/ε) prefix-enumeration exponent.When every cost is at most a δ fraction of capacity, the rounding acts on the scaled point (1−δ)p.Source: §5.2 · p. 39
  • With general knapsack costs, larger diagonal-dependent coefficients require a prefix branch whose residual region retains the chosen diagonal level; zero-level triples satisfy the condition on every instance.The one-budget enumeration exponent is O(1/ε); for several budgets, the explicit enumeration length is set by the stated loss bound.Source: §5.2 · pp. 40–41
  • For several budgets with small items, the coefficient approaches α at the original diagonal level as δ and ν tend to zero, with rounding loss linear in δ + κ_dδ.For d ≥2, the stated offline result requires s > 0.Source: §5.2 · pp. 41–42

6. Conclusion

The paper gives geometry-dependent approximation profiles for non-monotone k-submodular maximization and extends its guarantees to online learning and constrained rounding. Its conclusion also places these results alongside later approximation improvements and oracle lower bounds.

6. Conclusion

  • The approximation profile is continuous and nondecreasing in the diagonal level, with guarantees for fractional optimization and feasible labelings.For one knapsack, the prefix-enumeration exponent is O(1/ε); for several budgets, the stated exponent is O(1/ε^2).Source: §6 · p. 42
  • Matroid rounding preserves the online protocol and gives a high-probability offline guarantee; knapsack guarantees depend on item size or prefix enumeration.The several-budget result has a δ + κδ loss, and budget guarantees retain an explicit nonnegative initial-value term.Source: §6 · p. 42
  • Later work improved geometry-independent offline guarantees, but does not provide this paper’s objective-independent actions and comparator-uniform fields for online guarantees.The cited later results include 1/2 under cardinality and one-knapsack constraints, 0.48 under one matroid, and (1/2 − ε) under a fixed number of knapsacks.Source: §6 · p. 42
  • For fixed k ≥ 5, the paper’s coefficient matches the stated value-oracle upper bound up to arbitrarily small error, while k = 3, 4 retain a gap.For k = 2, the coefficient 1/2 was already known to be tight.Source: §6 · pp. 42–43

AI Disclosure

The appendix discloses AI-assisted proof and manuscript review, then derives the multilinear extension properties used in the paper’s analysis from the k-submodularity conditions.

AI Disclosure

  • GPT and Claude were used to check and refine proofs and to audit and revise the manuscript.Source: AI Disclosure · p. 43

A.1. Proof of Lemma 1 (continuous structure of the extension)

  • Most of Lemma 1’s extension properties were established in prior work, while this appendix derives each assertion from conditions (4) and (5).The cited prior results include affinity, derivative identities and signs, pairwise monotonicity, and a reduction to submodular functions.Source: §A.1 · p. 45
  • Conditioning on the other elements makes each extension derivative the expected marginal gain and shows it is independent of that element’s own label vector.Source: §A.1 · p. 45
  • The k-submodularity conditions yield decreasing derivatives across elements and nonnegative sums of derivatives for distinct labels.These properties establish antitone gradients and pairwise monotonicity for the extension.Source: §A.1 · pp. 45–46
  • The extension is concave along sign-definite directions, and conditioning on labels reduces it to an expectation of ordinary submodular multilinear extensions.Source: §A.1 · p. 46

A.2. Auxiliary uniform marginal-sample bound (Lemma A.1), used in Sections 4 and 5

This section establishes a uniform bound on sampled marginals and derivatives and develops proof tools and certificates for the block rules. It covers cone characterization and constructions for multi-label and two-label cases, polynomial certificates for dominant-head cases, a nondominant-head certificate, and a floor certificate across label counts.

A.2. Auxiliary uniform marginal-sample bound (Lemma A.1), used in Sections 4 and 5

  • Every marginal and multilinear-extension derivative lies in [−L_e, L_e], where L_e ≥ 0; if L = 0 the objective is constant, and feasible singletons imply L ≤ OPT − f(0).These singleton quantities bound marginals even on labelings with infeasible support.Source: §A.2 · pp. 46–47

B.1. Proof of Lemma 2 (pairing cone)

  • The dual of the cone generated by e_i + e_j for i ≠ j is exactly the set of pairwise-monotone vectors, and the cone equals the nonnegative vectors whose largest coordinate is at most half their total.The proof uses the bipolar theorem to establish the cone equality.Source: §B.1 · pp. 47–48

B.2. Proof of Lemma 3 (weighted level comparison)

  • For k ≥ 3, the weighted-level construction finds a least feasible level by scanning sorted breakpoints, with O(k log k) total running time.The resource-minus-demand difference is continuous and nondecreasing; the scan updates affine pieces between events and locates their intersection.Source: §B.2 · pp. 48–49

B.3. Proof of Lemma 4 (two-label rule)

  • For two labels, the balance equation has a unique solution d, which defines nonnegative action probabilities and yields a mass bound under the stated scalar conditions.The action uses p_1 = (r + d)/2 and p_2 = (r − d)/2; the proof establishes feasibility and |p| = r ≤ χ(Z).Source: §B.3 · pp. 50–52

B.4. Proof of Theorem 2 (univariate polynomial certificate)

  • When the head is nondominant, the balanced requirement and 2z_1/(c + z_1) ≤ r ensure the surplus in (35) is nonnegative for every ω ≥ 0.The lemma assumes z is sorted, Z > 0, c ≥ c_0, r ∈ [0, 1], and ∑_i z_i/(c + z_i) ≤ r.Source: §B.4 · p. 52
  • The three univariate tests certify the dominant-head case, and a floor certificate for k0 implies the corresponding test for every 3 ≤ k ≤ k0.The proof checks the four penalty-term cases and uses the joint polynomial certificate for the case with both penalties.Source: §B.4 · pp. 57–58

B.5. Proof of Lemma 5 (floor certificate across label counts)

  • When c(µ + v) ≥ 1, the floor certificate holds for every k; otherwise, every positive integer k ≤ floor(K) satisfies it.In the latter case, the threshold follows by minimizing Φ over (s0, 1], with the infimum attained at min{τ, 1}.Source: §B.5 · p. 59

B.6. Proof of Corollary 1 (cubic certificate for every k ≥3)

The proof verifies the mass bound for every finite k ≥ 3 by reducing its requirements to a limiting floor condition, a balanced condition, and a pure polynomial test. It then applies the block inequalities to obtain the comparison coefficient.

B.6. Proof of Corollary 1 (cubic certificate for every k ≥3)

  • If χ(1) = μ + (1 − μ)ζ ≥ 1/c and R is nonnegative on [0, 1], the floor requirement holds throughout the interval and the pure polynomial test completes the mass bound.The proof establishes the balanced test algebraically, so Theorem 2 applies for every finite k ≥ 3.Source: §B.6 · pp. 59–60
  • The block inequalities and the choices C = c/(1 − ω), W = ω/(1 − ω) yield comparison coefficient (1 − ω)/(1 + c) and preserve K(P).Source: §B.6 · p. 60

Appendix C. Proofs for Section 3.3: Analytical Profiles

  • The analytical-profile parameters are verified by polynomial identities and sign arguments, including zero-diagonal constants, the two-label profile, and weighted transitions for three or more labels.Tangent lines to the three mass requirements provide the affine mass bounds.Source: Appendix C · p. 60

C.1. Proof of Proposition 2 (zero-diagonal parameters)

The proof constructs an admissible rational family for the two-label test and uses it to establish the zero-diagonal parameters. It also verifies a separate all-level construction for every finite k ≥3.

C.1. Proof of Proposition 2 (zero-diagonal parameters)

  • The rational family is admissible and makes Q_z(r)(Z) a perfect square, with coefficient A(r) = (1 − w(r))/(1 + c(r)).At r = r*, its parameters match (c2, ω2, 1), with z(r*) = t2 and A(r*) = α*.Source: §C.1 · pp. 60, 62
  • At r = r*, the triple (c2, ω2, 1) is admissible at every diagonal level and certifies coefficient α*.With μ = 1, the target is χ(Z) = Z, so the quadratic and side condition do not depend on ζ.Source: §C.1 · pp. 62–63
  • For every finite k ≥3, the triple (c3, ω3, 1) is admissible at every diagonal level.The proof establishes the pure-label polynomial inequality and the endpoint condition, with c3 ∈ (101/100, 51/50) and ω3 ∈ (2/25, 9/100).Source: §C.1 · pp. 63–64

C.2. Proof of Theorem 4: the two-label profile

The two-label profile is assembled from a plateau, a weighted transition, and later branches. The proof matches the branches at their junctions and establishes a continuously differentiable, nondecreasing profile.

C.2. Proof of Theorem 4: the two-label profile

  • The transition uses the admissible rational family, whose double-root condition determines its parameters and whose coefficient is α(˜cζ, ζ).The family maps ζ to z(r) and selects the unique positive root of gζ for ˜cζ.Source: §C.2 · pp. 64–65
  • The plateau uses (c2, ω2, 1), while the pure branch sets ω = 0 and the chord branch is admissible for ζb ≤ ζ < 1.The proof identifies the pure-branch parameter as cP(ζ) = √(2(1 − ζ)) and verifies the chord branch's side condition and quadratic.Source: §C.2 · pp. 65–66
  • At ζ = 1, the limiting two-label parameters give coefficient 1/2.The proof checks the limiting quadratic and side condition at that endpoint.Source: §C.2 · p. 66
  • The profile is continuously differentiable and nondecreasing across its junctions.The proof matches values and derivatives at the junctions and establishes that each branch is nondecreasing.Source: §C.2 · pp. 66–67

C.3. Proof of Theorem 6(a),(d): weighted regimes and unrestricted level

  • The weighted transition is specified by one quadratic root and two rational parameter formulas, with an explicit endpoint inequality.The proof overview says the plateau and transition are joined by matching values and first derivatives.Source: §C.2 · p. 64, §C.3 · p. 67

C.3.1. PROOF OF THEOREM 6(A): PLATEAU AND WEIGHTED TRANSITION

The proof verifies the weighted transition by bounding its parameters and endpoint inequality, then checks admissibility at the unrestricted level.

C.3.1. PROOF OF THEOREM 6(A): PLATEAU AND WEIGHTED TRANSITION

  • On the weighted transition, 1 < c < 6/5, 0 ≤ ω < 1/4, and 0 < μ ≤ 1, with c increasing and μ and ω decreasing.The transition also satisfies μ + (1 − μ)z > 1/c.Source: §C.3.1 · p. 68
  • The endpoint inequality holds throughout the transition, establishing the required mass bound for its parameters.The proof shows S1 > 0 from a polynomial-division identity and sign bounds on the transition interval.Source: §C.3.1 · p. 70
  • The transition's double-root construction verifies the pure-label test, and the parameter ranges and mass bound make it admissible for every finite k ≥3.The proof also checks the floor and balanced tests.Source: §C.3.1 · pp. 70–71

C.3.2. PROOF OF THEOREM 6(D): UNRESTRICTED LEVEL

  • At ζ = 1, choosing c = 1 with ω = μ = 0 gives coefficient 1/2 for every finite k ≥3.The proof verifies the floor, balanced, and pure polynomial tests for this choice.Source: §C.3.2 · p. 72

C.4. Proofs of Lemma 6 and Theorem 5: the supporting-line construction

The supporting-line construction characterizes the least feasible cost by optimizing a slope against three mass requirements. Its contact analysis supports the theorem's degree bound and level and k dependence.

C.4. Proofs of Lemma 6 and Theorem 5: the supporting-line construction

  • Concavity makes contact conditions characterize the maxima; clearing denominators reduces the cases to polynomial equations and inequalities, with degree four slope conditions and cubic value conditions.The requirements are concave on [0, 1], and strictly concave for finite k.Source: §C.4 · pp. 72, 74
  • The least feasible cost is attained by minimizing over slopes that satisfy the three sufficient mass tests, and it certifies coefficient 1/(1 + c).The proof establishes continuity and attainment of the minimizing cost.Source: §C.4 · pp. 73–74
  • The unrestricted coefficient is nonincreasing in k, while the k = 3 and k = 4 coefficients coincide.For k = 3, 4, the balanced requirement implies the floor requirement.Source: §C.4 · p. 75

C.4.1. PROOF OF THEOREM 6(B)–(C): PURE AND BALANCED SINGLE-CONTACT BRANCHES

  • The pure and balanced single-contact branches have coefficients that increase strictly with ζ.A tangent at mass ζ supports the selected requirement, while a separate support inequality checks the other requirement and the bound k ≤ KH(ζ) checks the floor.Source: §C.4.1 · p. 76

C.4.2. PROOF OF COROLLARY 2: EXPLICIT PURE AND BALANCED INTERVALS

The proof verifies the pure, balanced, and floor inequalities by rational parameterizations and exact polynomial comparisons. These checks establish the stated pure intervals and balanced-branch tests.

C.4.2. PROOF OF COROLLARY 2: EXPLICIT PURE AND BALANCED INTERVALS

  • The pure interval extends through ζ = 61/200 for k ≤ 5 and through ζ = 3/10 for k ≤ 6.Monotonicity and the pure comparison propagate the verified floor inequalities to these parameter ranges.Source: §C.4.2 · p. 78
  • The pure and balanced parameterizations use different rational coordinates, with the balanced coordinate increasing across the stated ζ range.The balanced branch’s pure comparison is checked by a polynomial gap and completion of squares.Source: §C.4.2 · pp. 76, 78, 79
  • On the balanced branch, the pure inequality holds throughout the asserted interval, and the k = 5 floor inequality is verified through ζ = 31/40.The proof checks the pure requirement on the full balanced interval and uses a floor test at a rational anchor, then extends it by target monotonicity.Source: §C.4.2 · p. 79
  • For k ≤ 4, the balanced requirement dominates the floor on [0, 1] when c ≥ c0 > 1/2.For k = 5, the proof instead checks the floor directly on the scaled-mass range x ≥ 1.Source: §C.4.2 · p. 79

C.4.3. PROOF OF EXAMPLE 2: FIVE-LABEL COMMON TANGENT AND TERMINAL BRANCH

For the five-label example, a common tangent to the balanced and floor requirements defines a first branch, followed by a terminal branch. The proof also verifies rational parameter choices for Examples 3 and 4.

C.4.3. PROOF OF EXAMPLE 2: FIVE-LABEL COMMON TANGENT AND TERMINAL BRANCH

  • 41/45 < t < 23/25 and 49/60 < p < 131/160 bound the five-label common-tangent parameters.The line of slope p^2 is tangent to the balanced requirement at t and to the floor requirement at its contact point.Source: §C.4.3 · pp. 80–81
  • For ζL ≤ ζ ≤ ζU, the balanced and floor contact masses bracket ζ, and the cost c(ζ) decreases from b(t)/t to p.The proof bounds these contact masses within [0, 1] on the first branch.Source: §C.4.3 · p. 81
  • On the terminal branch, the floor tangent also majorizes the balanced requirement, so all three requirements hold across both branches.For 3 ≤ k < 5, the floor requirement is weaker than for k = 5.Source: §C.4.3 · pp. 81–82

C.4.4. PROOFS OF EXAMPLES 3 AND 4: RATIONAL PARAMETER CHOICES

  • At ζ = 49/100, a ten-label parameter choice verifies the requirements and gives 1/(1 + c) = 45/86.Source: §C.4.4 · pp. 83–84
  • For k = 12, the stated parameters satisfy the three requirements, and Proposition 1 extends their validity to every larger diagonal level.The parameters are c = 1, ω = 0, and μ = 17/20 at ζ = 49/100.Source: §C.4.4 · p. 83

C.5. Proof of Theorem 8: a half-coefficient family for every label count

These proofs establish regret bounds and unbiased feedback methods for limited-feedback online learning, including an exact two-value local-norm variant, and transfer those bounds to fractional approximation guarantees and integral rewards. They also construct tangent-line majorants yielding a coefficient of 1/2 for every finite k ≥ 3 above a sufficient diagonal level, with exact-value query costs for full-prefix feedback.

C.5. Proof of Theorem 8: a half-coefficient family for every label count

  • For k = 3, 4, and 5, a unique common tangent contact in (3/10, 61/200) majorizes the pure, balanced, and floor requirements.The contact is obtained by matching the pure tangent slope to a balanced supporting line; the floor bound follows from B1 ≥ f5,1 ≥ fk,1.Source: §C.5 · p. 86
  • For 6 ≤ k ≤ 11, a unique contact τk in (1/4, 3/10) gives a tangent majorizing the pure and floor requirements, while the pure-tangent bound supplies the balanced requirement.The endpoint signs establish a root in that interval, and the contact is the supporting line of the floor with slope m(τk).Source: §C.5 · pp. 85–87
  • For k ≥ 12, a unique contact τk in (1/5, 1/4) makes the pure tangent pass through the floor endpoint at mass one and majorize all three requirements.The tangent has Lτk(1) = k/(k + 1); its slope is below the floor slope at one, and the balanced bound applies because τk < 3/10.Source: §C.5 · pp. 87–88
  • The constructed parameters give coefficient 1/2 at level z(τk), and Proposition 1 extends it to every larger level; these sufficient levels are equal for k = 3, 4, 5 and increase strictly thereafter.As k tends to infinity, the levels approach 1 with 1 − z1/2(k) ∼ 1/((1 − μ∞)k).Source: §C.5 · pp. 88–89

Appendix D. Proofs for Section 4: Fractional Optimization and Online Learning

  • The comparison-field estimators have conditional mean gF(x), and exact full-prefix feedback uses nk new values offline or nk + 1 values per online round.The moment bounds are stated for the oracle estimators; the exact-value query counts are given for complete prefix feedback.Source: Appendix D · pp. 90–91
  • For a single objective, a uniformly sampled iterate satisfies E[F(p_J)] ≥ αF(y) + αCf(0) − αR_T/T for every fixed feasible comparator y.Taking y to maximize F gives the same bound with F(y) = OPT_F(P).Source: Appendix D · p. 93

D.3. Entropy estimates (Lemma D.2), used for Theorems 9 and 10 and Corollaries 4 and 7

  • Entropy mirror ascent gives a pathwise regret bound that requires no almost-sure feedback bound, with support-sensitive diameter B_r = min{n log(k + 1), r log(en k/r)}.Inexact updates add the initialization residual and the sum of step residuals, each divided by η, to the bounds.Source: §D.3 · pp. 95–96

D.4. Proof of Theorem 9 (fractional optimization)

  • Theorem 9’s entropy-mirror-ascent analysis gives R_T/T = GΛ sqrt(2n log(k + 1)/T), yielding a feasible random iterate with an error that decreases as T grows.Initialization and each iteration use nk objective values, for at most nk + 1 + Tnk values total.Source: §D.4 · p. 97

D.5. Proof of Theorem 10 (online learning under limited feedback)

  • Taking expectations and using the conditional bound E[P_t,e ∥bgt,e∥² | H_t] ≤ V_j with the tower property, expected linear regret is at most B_0/η + ηTV_j/2, yielding sqrt(2B_0V_jT).Source: §D.5 · p. 98
  • The expectation argument permits hindsight comparator choice, while integral rewards preserve expected bounds, including zero-regret degenerate cases.When Vj = 0 or Uj = 0, the corresponding moment vanishes; singleton regions likewise yield zero regret.Source: §D.5 · pp. 98–99

D.6. Proof of Corollary 4 (local-norm bound for exact two-value feedback)

  • Expected linear regret is at most RT = 2√(BrVlocT) + āBr under the state-weighted moment bound.The estimate’s conditional moment is at most Vloc.Source: §D.6 · pp. 99–100
  • The unbiased estimate transfers this bound to α-approximate regret: Regα(T) + α∑t ft(0) ≤ αRT.The transfer applies the bound against every fixed feasible comparator.Source: §D.6 · p. 100

D.7. Proofs for Section 4.3 (coordinate capacities and inactive elements)

The proofs transform coordinate capacities and inactive elements into restricted instances, then establish how rounding guarantees transfer to constrained settings. They also show how prefix selection and retained candidates support the knapsack rounding analysis.

D.7. Proofs for Section 4.3 (coordinate capacities and inactive elements)

  • For coordinate capacities ρ, the proof defines a down-closed region Pρ and an averaged objective fρ whose singleton scales become ρeLe.The mapping u ↦ ρ ⊙ u is a bijection between the transformed and original comparison sets.Source: §D.7 · pp. 100–101
  • The transformed estimators scale each element’s gradient block by ρe, while the regret comparison maps plays and comparators between Pρ and P.The proof applies the online theorems on Pρ, with the transformed dimension |Vρ| and corresponding entropy diameter.Source: §D.7 · p. 101
  • When elements in D are inactive, restricting to V′ preserves the optimum and fractional objective, and the resulting guarantees transfer to the original down-closed instance.The restriction also transfers fractional and online guarantees; exact-base constraints require completion in the original matroid.Source: §D.7 · p. 102

Appendix E. Proofs for Section 5: Rounding

  • Conditional-label rounding reduces support rounding to ordinary submodular-function rounding, and its proofs retain the initial value in the residual guarantee.Source: Appendix E · p. 102

E.1. Proof of Corollary 6 (rounding transfer)

  • Objective-independent rounding gives a conditional expected-value inequality before feedback, yielding an online regret bound; objective-dependent rounding supports only an offline consequence.The rounding leaves the field oracle and its query budget unchanged.Source: §E.1 · p. 103
  • On sub-labelings of an optimal labeling, the objective is monotone despite f being non-monotone, so the largest remaining greedy marginal decreases along a prefix.The proof uses this structure to bound remaining marginals after selecting a greedy prefix.Source: §E.1 · pp. 103–104
  • Keeping evaluated feasible singleton candidates converts the residual solver’s additive singleton-scale loss into a multiplicative comparison for the returned candidate.The candidate pool includes the prefix and singleton extensions evaluated during residual initialization.Source: §E.1 · p. 104

E.3. Proof of Corollary 7 (matroid approximation)

This section establishes how fractional approximation guarantees transfer to feasible matroid and knapsack solutions using rounding and enumeration methods. It also covers exact bases, budget constraints, and the conditions and computational bounds for these guarantees.

E.3. Proof of Corollary 7 (matroid approximation)

  • Choosing ν = ε/(α−ε) yields expected returned value EbY ≥ (α−ε)OPT; the horizon is O(r²[log(enk/r)+log(2/β)]/ε²), and queries are O(nkr²log(enk/r)/ε²) when ε < α ≤ 1 and α, G are fixed.Source: §E.3 · pp. 106–107
  • The fractional and integral optima coincide for matroid constraints, and randomized pipage rounding produces feasible independent supports without querying the objective.Conditional label sampling turns the objective into a submodular function for rounding; stored singleton candidates absorb optimization error.Source: §E.3 · pp. 105–106

E.4. Proof of Corollary 7 (exact bases)

  • For exact bases, objective-independent augmentation preserves expected value, so the independent-set and base optima coincide and the (α−ε) guarantee carries over.For the offline high-probability guarantee, choosing the better of two fixed-label extensions at each augmentation never decreases value and uses at most 2r additional queries.Source: §E.4 · p. 108

E.5. Auxiliary conditioned-prefix bound (Lemma E.3), used for Corollaries 8 to 10

  • For d support budgets, conditioned-prefix enumeration gives the stated approximation when ϑ=d/(δρ)≤C+ν; if an optimum has at most ρ elements, enumeration includes it.The retained conditioned value, stored singleton candidates, and rounding baseline contribute C, ν/α, and (1−s)/(sα) to the threshold.Source: §E.5 · p. 108

E.6. Proofs of Lemma 7 and Corollary 8: cost-preserving rounding

  • For one budget, cost-preserving pipage rounding reserves capacity for a final fractional item, yielding feasible rounding that preserves or increases expected value and supports the (α−ε) guarantee.The cost-preserving direction is objective-independent; scaling the fractional point ensures the final item fits the reserved capacity.Source: §E.6 · pp. 110–111

E.7. Proof of Lemma 8 (random-priority prefix rounding)

  • In random-priority prefix rounding, acceptance and positive marginal decrease with earlier independent arrivals, and their positive correlation integrated over priority yields the bound.Source: §E.7 · p. 112
  • When δ=0, pruning does not lower the sampled set’s value in expectation; the accepted prefix is feasible, and the scan uses at most |V|+1 value queries.Nonnegative costs make feasible prefixes initial segments; the proof uses submodularity to show that skipped elements have nonpositive total marginal contribution.Source: §E.7 · pp. 112, 114

E.8. Proof of Corollary 9 (knapsack approximation)

  • The enumerated knapsack algorithm achieves the bound in (101), with approximation coefficient α−ε, and every stored candidate is feasible on every outcome.Its running time uses at most (nk+1)^ρ prefixes, with ρ = O(d log(2d)/ε^2).Source: §E.8 · p. 115

E.9. Proof of Corollary 10 (finite enumeration)

  • For finite enumeration, a short optimal labeling is found with value at least OPT; otherwise the proof combines the greedy prefix candidate with the rounded residual output to establish (103).The enumeration has at most (nk+1)^ρ labeled prefixes, and each branch’s returned candidate is feasible on every outcome.Source: §E.9 · pp. 115–116

E.10. Proof of Proposition 4 (small items)

  • For small items, the proof uses retention bounds and fractional optimization to establish (104); choosing ν makes sα/(1+sν) = sα−ε, and rounded candidates satisfy every budget on every outcome.The argument uses Lemma 7 for one budget and Lemma 8 for several budgets.Source: §E.10 · p. 117
Loading 2610.04049v2…