PaperlayerView exact revision on arXiv

Source-linked AI summary

Beyond Peak Backlog: Conditional Energy and Temporal Geometry in Capacity-Constrained Delayed Bandit Optimization

Anling Xiang, Yuwen Yang, Yang Shen

arXiv:2608.16216v1cs.LG

TL;DR

Finite feedback capacity can discard delayed observations, leaving the right delay complexity unresolved. The paper introduces a scheduler-side conditional-energy interface and obtains total-delay and curvature-sensitive guarantees, while showing that timing can matter beyond aggregate delay summaries.

  • Problem

    Finite feedback buffers discard preempted observations, leaving open whether hard-capacity one-point bandit optimization can achieve total-delay rather than peak-backlog dependence.

  • Method

    The paper separates scheduler information from bandit randomization through a scheduler-side filtration and conditional energy envelope, yielding one adaptive delayed-weighted theorem.

  • Results

    O(sqrt(E_C d_tot)) replaces peak-backlog dependence for total delay, while same-summary delay vectors exhibit a polynomial minimax-regret separation under strong convexity.

  • Takeaways & Limitations

    Under curvature, delay timing can determine minimax regret even when delay multisets, total delay, peak backlog, and capacity agree.

  • Takeaways & Limitations

    The results do not provide a complete capacity-dependent bandit convex optimization minimax characterization and require C >= log T + 1 for the upper bounds.

Abstract

from arXiv · show

What is the right delay complexity when a learner can track only $C$ pending feedback items and discarded feedback is permanently lost? Existing one-point bandit convex optimization guarantees in this model pay $\sqrt{Tσ_{\max}}$, where $σ_{\max}$ is the peak backlog, although unlimited tracking admits the sharper $\sqrt{d_{\mathrm{tot}}}$ dependence on total delay. We introduce a scheduler-side conditional-energy interface that separates rate adaptation from the one-point perturbation filtration and handles the dependent importance weights created by randomized admission. Under the same semi-clairvoyant oracle and pathwise hard-capacity contract, this yields an untuned learner whose delay term scales as $O(\sqrt{E_C d_{\mathrm{tot}}})$, with only an explicit restart factor $E_C$; a public constant-factor peak bound removes this factor while $d_{\mathrm{tot}}$ remains unknown. Under strong convexity, the same interface yields the temporal cost $H_A(d)=\sum_t σ_t/(A+t)$. Two delay vectors with identical delay multisets, $d_{\mathrm{tot}}$, $σ_{\max}$, and capacity can nevertheless have polynomially different minimax regret, showing that timing matters under curvature even when aggregate delay summaries agree. Finally, a continuous hard family converts tracking capacity into a zeroth-order query budget and gives a complementary capacity-starvation lower endpoint. The upper bounds require $C\ge \ln T+1$ and do not constitute a complete capacity minimax characterization.

1 Introduction

The paper introduces a scheduler-side conditional-energy interface that safely handles randomized admission and enables total-delay bounds under finite feedback capacity. It also shows that curvature makes delay timing matter beyond aggregate summaries, alongside a complementary capacity-starvation lower endpoint.

  • Conditional-energy theorem: A scheduler-side filtration and conditional-energy envelope separate rate adaptation from one-point perturbation randomness, yielding an adaptive delayed-weighted FTBL interface.The paper gives a two-round counterexample showing why adapting to the full predictable history is invalid.
  • From peak backlog to total delay: O(√ECdtot) replaces √Tσmax for a hard-capacity learner that knows neither dtot nor σmax; a public constant-factor peak bound removes EC while dtot remains unknown.The restart scheme uses capacity-relative backlog scales, with EC = 1 + ⌈log2(1 + 16(σmax + 1)/C)⌉.
  • Temporal geometry under curvature: HA(d) = P t σt/(A+t) is the temporal cost delivered by the same interface under curvature.This harmonic cost captures the role of backlog placement over time rather than only its aggregate size.
  • Temporal geometry under curvature: Polynomially different minimax regret occurs for delay vectors sharing the same delay multiset, dtot, σmax, and capacity, proving timing remains consequential.Thus temporal placement matters even after standard aggregate delay summaries are fixed.
  • Capacity lower endpoint: A continuous hard family converts pathwise tracking capacity into a zeroth-order query budget, establishing a complementary capacity-starvation endpoint rather than matching the upper bound pointwise.The paper does not claim a complete capacity minimax characterization.

2 Model and notation

The model studies one-point bandit learning over a bounded convex domain with Lipschitz, bounded losses and adversarial delays. Feedback is retained only for tracked indices under a pathwise capacity limit, with permanently lost preempted feedback and expected guarantees.

  • Assumptions: The domain K is convex with diameter at most D and satisfies rB_k ⊆ K ⊆ RB_k; losses are differentiable, convex, G-Lipschitz, and bounded by M.An oblivious adversary fixes the losses f_t and delays d_t before play.
  • Feedback and capacity: Each round queries one point, while scalar feedback arrives at t + d_t only if its index remains in a pathwise tracking set of size at most C.Preempted indices cannot be reinstated, and every expiry returns either indexed feedback or ⊥.
  • Delay notation: The backlog at time t is B_t = {s < t : t ≤ s + d_s}, with σ_t = |B_t|.These quantities describe the pending-feedback profile induced by the delay sequence.
  • Analysis weights: Guarantees are taken in expectation over learner randomization, and analysis weights w_1:T are generated by the admission wrapper.A zero analysis weight does not eliminate true regret; the wrapper or explicit censoring charge accounts for it.

3 Scheduler-side conditional energy

This section defines a scheduler-side filtration that excludes perturbation directions and their generated feedback, enabling conditional-energy analysis for delayed weighted FTBL. It also establishes delay-clock padding and explains why unconditional energy moments fail under predictable-rate dependence.

  • Filtration: The scheduler-side filtration includes indexed expiry messages, tracking state, proxy coins, admissions, importance weights, public parameters, and scheduler randomness, but excludes perturbation directions and generated function values.Rates and energy envelopes are measurable with respect to this scheduler-side information.
  • Conditional energy: Theorem 1 gives scheduler-adaptive delayed weighted FTBL a conditional-energy guarantee for every u ∈ K under the stated nonnegative measurable envelope conditions.The supplied passage identifies the theorem and guarantee but truncates its displayed assumptions and bound.
  • Conditional energy: The analysis fixes A0 > 0 at run start and requires it to dominate all h_t in that run.This is the theorem’s stated initialization condition for the energy analysis.
  • Stopping and padding: Delay-clock stopping permits deterministic endpoints under fixed oblivious delays, and zero-padding preserves applicability of Lemma 11 and Theorem 1 after the run ends.The endpoint is independent of scheduler coins, perturbation directions, and loss values.
  • Why the filtration matters: Unconditional energy moments cannot generally be multiplied by predictable rates because dependence can destroy square-root cancellation for pending one-point estimators.For B ∼ Ber(ϵ), the passage gives EΞ2 = 1 and E[η1Ξ2] = 1, while Eη1EΞ2 ≤ 2ϵ.

4 Bernoulli proxy energy

The Bernoulli proxy tracks pending feedback through pathwise admission and inverse-probability weights, yielding an exact proxy-energy accounting without cross-time weight independence. With a public constant-factor peak bound and C ≥ ln T + 1, the untuned scheduler-side learner obtains a total-delay guarantee without knowing d_tot.

  • Pathwise proxy energy: The admission coin is I_t ∼ Ber(p), with weight w_t = Q_t I_t/p and Q_t = 1{|S_t| < C}.Feedback is tracked only when the admission coin succeeds and capacity is available.
  • Total-delay guarantee: C ≥ ln T + 1 and a public constant-factor upper bound on σ_max support a single-run untuned learner with a known-peak total-delay guarantee.The learner does not know d_tot, while the capacity term has the same order as the tuned source expression when the peak bound is constant-factor.
  • Untuned scheduling: The algorithm sets B_C = max{1, floor(C/8)} and doubles H_j until it covers the backlog, restarting the base after each increase.This restart mechanism adapts to unknown peak backlog while preserving the hard-capacity contract.
  • Total-delay guarantee: The learning rate is η_t = D/(G√A_t), with A_t updated from the exact proxy-energy lemma before the next center.The displayed radius balances the final nonconstant terms, while the clipped regime is handled by the trivial linear regret bound.

5 Untuned total-delay algorithm

The untuned hard-capacity algorithm achieves a total-delay guarantee when C ≥ ln T + 1, with delay dependence scaling as O(√(E_C d_tot)); the residual √E_C factor is attributed to independently restarted bases rather than shown minimax necessary.

  • Untuned total-delay algorithm: C ≥ ln T + 1 is sufficient for Algorithm 1, which requires neither d_tot nor σ_max.This is the stated condition and tuning-information guarantee for the untuned total-delay hard-capacity algorithm.
  • Untuned total-delay algorithm: O(√(E_C d_tot)) is the algorithm’s total-delay dependence under hard capacity.The bound is presented for Algorithm 1 in the total-delay hard-capacity BCO theorem.
  • Untuned total-delay algorithm: √E_C is the only epoch factor on the total-delay term, while one-point and smoothing terms carry no such factor.The passage explicitly separates the residual epoch factor from the one-point and smoothing terms.
  • Untuned total-delay algorithm: √E_C arises from summing comparator costs of independently restarted bases, and its minimax necessity is not claimed.Removing it would require a new nonrestart interface because the source FTBL interface assumes a nonincreasing smoothing radius.

6 Strong convexity and harmonic backlog

Under λ-strong convexity, Algorithm 2 achieves a harmonic-backlog regret bound when C ≥ ln T + 1 and a public upper bound ¯σ ≥ σmax is available. Matched delay vectors with identical aggregate summaries can nevertheless have polynomially different minimax regret because feedback timing matters.

  • Strong convexity and harmonic backlog: C ≥ ln T + 1 and public ¯σ ≥ σmax yield Algorithm 2’s harmonic-backlog strongly-convex BCO guarantee.The construction uses shifted rates with α1 = λ(A + 1) and αt = λ for t ≥ 2.
  • Strong convexity and harmonic backlog: The regret expression includes 1 + H_A(d) + A^1/3T^2/3, making the temporal cost depend on harmonic backlog.When A > T, the target is already at least linear and the trivial regret bound applies.
  • Same-summary minimax separation: Early and late delay vectors share the same delay multiset, d_tot = h^2, σmax = h, and capacity, yet their minimax regrets differ polynomially.The comparison uses the same public information and algorithm class on both sides.
  • Same-summary minimax separation: The early lower remains valid with unlimited capacity, showing that delayed information—not capacity alone—causes the early separation.The construction sets C = ⌊h/2⌋ < σmax, but the early lower persists even when the full delay vector is known in advance.
  • Same-summary minimax separation: O(T^2/3) bounds the late minimax regret, while the early minimax lower exceeds it by Ω(T^(β−2/3)) for β ∈ (2/3, 5/6).The late upper is C0[T^2/3 + h^2/T + 1] = O(T^2/3).

7 Complementary capacity-starvation endpoint

This section gives a complementary continuous capacity-starvation lower endpoint: hard capacity limits recoverable zeroth-order observations, establishing the model’s statistical relevance without matching the convex upper bound pointwise.

  • Interpretation: This endpoint is separate from the temporal-placement lower bound, not a third compiler application or a pointwise match to the convex upper.It supports the model’s statistical relevance by showing that capacity directly limits recoverable zeroth-order observations.
  • Hard instance: The hard instance delays the first N = ⌊T/2⌋ rounds by d and gives zero delay afterward, yielding d_tot = Θ(Td) and σ_max = Θ(d).The loss sequence is oblivious and the delay vector is public.
  • Proof idea: Before x_N is generated, each observed first-block item occupies one tracking slot continuously for d rounds, so hard capacity limits informative values.The proof simulates only this prefix and reduces the learner to a derivative-free procedure using at most the capacity-limited number of noisy value queries.
  • Proof idea: The proof uses Shamir’s smooth strongly-convex derivative-free family with compact mean-zero noise, whose m-query optimization error is at least a constant times min{1, k/√m}.The compact noise is chosen so translated Hellinger distance is quadratic.

8 Relation to prior work and scope … D Proof of charged censoring

The paper extends delayed one-point BCO under permanent-loss hard capacity through conditional energy, while distinguishing its contributions from imported interfaces and delimiting unresolved minimax questions. The proofs condition on scheduler trajectories, control proxy energy, and charge boundary censoring without altering the base run.

  • 8 Relation to prior work and scope: The hard-capacity model requires continuous slot occupancy until feedback arrives, and preempted feedback cannot be restored.This physical rule distinguishes the setting from label-efficient prediction, partial monitoring, side observations, and feedback graphs.
  • 8 Relation to prior work and scope: The known-peak corollary reaches the unconstrained-optimal √dtot delay scale, extending prior √Tσmax convex guarantees without claiming a complete capacity minimax rate.The paper does not establish necessity of the capacity-dependent one-point term.
  • 8 Relation to prior work and scope: The results are a capacity-preserving conditional-energy extension, with shifted primal harmonic bounds under one-point feedback, dependent importance weights, and permanent censoring.They are not presented as a new unconstrained delay reduction or the first time-weighted delay analysis.
  • A Imported source interfaces: The imported source interfaces provide weighted one-point inequalities and a Bernoulli wrapper that maintains |St| ≤ C pathwise under public backlog bound H.The source inequalities remain valid after conditioning when weights, rates, radii, and delays are fixed while perturbation directions remain independent and uniform.
  • B Proof of the conditional-energy compiler: Conditioning on the complete scheduler trajectory fixes weights, delays, rates, and smoothing radii while preserving independent uniform one-point directions for the conditional-energy compiler.The proof uses the scheduler filtration, telescoping, and Jensen’s inequality to obtain the theorem’s second display.
  • C Proof of the proxy-energy lemma: The proxy-energy lemma identifies expected tracked energy from Bernoulli admission and bounds its accumulated area using summation, Cauchy–Schwarz, and a uniform initial envelope.The tracking set is contained within locally pending indices whose proxy coin succeeded.
  • D Proof of charged censoring: Boundary censoring charges delay-clock boundary rounds separately, while assigning their eventual analysis weight zero preserves predictions, tracking decisions, envelopes, and updates.On complement rounds, the admission law, capacity indicator, importance weight, and saturation event remain unchanged, and fixed-horizon extension completes the proof.

E Proof details for the total-delay theorem · F Proof details for strong convexity

The proof of the total-delay theorem partitions pending-time pairs into epochs, bounds their aggregate delay by d_tot, and controls epoch and startup contributions. The strong-convexity proof bounds the remaining delay contribution by H_A(d), with saturation contributing O(G^2/λ).

  • E Proof details for the total-delay theorem: K ≤ E_C nonempty epochs because round–pending-time pairs are disjoint across epochs and Σ_j D_j ≤ d_tot.The proof uses B_C ≥ C/16 and H_{j+1} = 2^j B_C.
  • E Proof details for the total-delay theorem: The modified initial threshold allows p_0 = 1, while inverse proxies grow geometrically for j ≥ 1.This geometric growth supports the epoch-wise control of the one-point terms.
  • E Proof details for the total-delay theorem: The one-point and smoothing contributions share the same epoch-wise bound, with no epoch logarithm.Startup terms form a geometric series, and successive boundary-censored pending sets are disjoint with total size O(σ_max + 1) = O(√d_tot + 1).
  • E Proof details for the total-delay theorem: The total-delay proof concludes Theorem 6 after controlling startup and boundary terms; if the smoothing ratio clips at one, the target is already dominated by the trivial GDT bound.The startup contribution is a geometric series, and T e^−C ≤ e^−1.
  • F Proof details for strong convexity: The strongly-convex part of Lemma 11 supplies the starting inequality for the shifted-schedule analysis and its saturation-supported expectation.These ingredients are combined with the initial-term, proxy-moment, and learning-rate bounds to prove Theorem 8.
  • F Proof details for strong convexity: For strong convexity, the shifted schedule sets α_t = λ for t ≥ 2, and the corresponding expectation is supported on saturation.The saturation analysis uses V_t = (λ/2)∥y_t − u∥^2 and the pre-admission capacity indicator Q_t.
  • F Proof details for strong convexity: The extra initial term is at most λAD^2/2 ≤ 2G^2A/λ because D ≤ 2G/λ.The proxy moments and AM–GM provide the remaining parameter control.
  • F Proof details for strong convexity: The strong-convexity bound contains a 2A^1/3T^2/3 term, an exact remaining delay contribution H_A(d), and saturation cost O(G^2/λ).The proof also uses η_{t−1} ≤ 2/[λ(A + t)].

G Proof of the temporal separation

The temporal-separation proof contrasts an early delay vector, which forces regret of at least (h + 1)/8 before feedback arrives, with a late vector whose backlog is concentrated near the horizon and has area h2. With β > 2/3 and β < 5/6, the early lower bound exceeds the one-point term while the late harmonic term does not.

  • Early vector: (h + 1)/8 regret is forced for the early vector because delayed feedback leaves predictions through round h + 1 independent of the hidden sign.Even after the sign is revealed, remaining losses are at least −1/8, while the static comparator incurs −T/8.
  • Late vector: h2 total backlog area characterizes the late vector, whose nonzero backlog occurs only after T −2h.The late-vector construction concentrates all nonzero backlog near the horizon.
  • Exponent separation: β > 2/3 makes the early lower bound exceed the one-point term, while β < 5/6 keeps the late harmonic term no larger than it.Theorem 8 supplies the late upper bound used in this comparison.

H Proof of the capacity-starvation lower bound

The section proves capacity starvation by reducing a hard-capacity learner to an adaptive noisy-query procedure, then applying a strongly convex hard family whose indistinguishability forces regret. The reduction is pathwise and combines with an oblivious common-minimizer loss distribution to establish the lower bound.

  • Adaptive query lower bound: Lemma 13 constructs a noisy family of 1/2-strongly convex, 7/2-smooth, 4-Lipschitz functions that defeats procedures using at most m adaptive queries.The family uses compactly supported mean-zero noise, and the realized noisy functions remain uniformly bounded.
  • Adaptive query lower bound: When mµ^4 is sufficiently small, sequential Hellinger control and Assouad’s lemma leave a constant sign-error probability in every coordinate, which strong convexity converts into expected loss.The transcript squared Hellinger distance is at most c mµ^4 after m queries.
  • Capacity-to-query reduction: Lemma 14 shows pathwise that, before round-N feedback delivery, a capacity-C learner’s first-block behavior can be simulated using at most m0 adaptive oracle queries.The simulator queries only first-block points whose indices expire before the cut; deferred sampling preserves the prefix transcript law.
  • Capacity-to-query reduction: The reduction yields m0 ≤ min{N, CN/d}, because feedback retained until delivery occupies a tracking slot continuously for d rounds and preempted indices cannot be re-added.The argument is pathwise and counts delivered first-block indices at the prefix cut.
  • Theorem 10: Theorem 10 applies the hard family with N = ⌊T/2⌋ and independently sampled additive noise, producing an oblivious loss distribution with a common minimizer and completing the minimax lower-bound quantifiers.Averaging over the time-zero noise draw selects one deterministic realization with at least the same expected regret over the learner’s randomness.
Loading 2608.16216v1…