Capacity-Constrained Online Convex Optimization with Delayed Feedback

Scientific Impact Assessment

Core Contribution

This paper introduces and solves the problem of online convex optimization (OCO) and bandit convex optimization (BCO) under a hard capacity constraint on the number of simultaneously tracked pending observations. The key insight is that standard delayed online learning implicitly assumes unlimited tracking capacity — an assumption violated in many practical settings (clinical trials, resource-constrained systems). The paper extends the capacity-constrained framework of Ryabchenko, Attias, and Roy (2025), which handled finite-action settings (experts and multi-armed bandits), to continuous convex domains.

The technical approach involves a clean two-part decomposition: (1) a novel "delayed and weighted" OCO/BCO framework with algorithms (DW-FTRL and DW-FTBL), and (2) proxy-delay schedulers that reduce the capacity-constrained problem to this weighted problem via importance sampling. A key methodological contribution is the semi-clairvoyant delay model, which only reveals delays upon expiration rather than at prediction time — a more realistic assumption that aligns with standard delayed feedback settings.

Methodological Rigor

The theoretical development is thorough and carefully structured. Several aspects stand out:

Delayed-weighted regret analysis: The regret bounds for DW-FTRL (Theorem 3.1) and DW-FTBL (Theorem 3.2) cleanly characterize how time-varying importance weights interact with delayed feedback through pairwise terms $w_t{\sum }_{s\in B_t}{w}_{s}w\_t\; \backslash sum\_\{s\; \backslash in\; B\_t\}\; w\_s$. The bandit case introduces additional ${\mathrm{\ell }}_2\backslash ell\_2$ cross-terms $({\sum }_{s\in B_t}{w}_s^2{)}^{1\mathrm{/}2}(\{\backslash sum\_\{s\; \backslash in\; B\_t\}\; w\_s^2\})^\{1/2\}$ from variance accumulation of pending gradient estimators — a genuine technical challenge that the authors handle via Lemma C.1 (adapted from RAR26).

Scheduler design: The Chernoff-based saturation bound (Lemma 4.3) provides a clean sufficient condition for tracking set overflow probability $\le e^{-C}\backslash leq\; e^\{-C\}$. Two concrete schedulers — Pareto (adapted from prior work) and the novel Bernoulli scheduler — sit at different points of an adaptivity/uniformity tradeoff. The Bernoulli scheduler's uniform weights are essential for strongly convex and bandit guarantees, representing a genuine design innovation.

Doubling trick: The paper addresses the practical concern that ${\sigma }_{\max }\backslash sigma\_\{\backslash max\}$ may be unknown via a clean doubling trick (Appendix F) that preserves the asymptotic rates up to logarithmic factors.

The proofs are complete and self-contained in the appendices. The reduction structure is modular, making the analysis tractable and verifiable.

Potential Impact

Theoretical significance: The results demonstrate a surprising efficiency threshold: for first-order OCO, logarithmic capacity $C=\mathrm{\Omega }(\log T)C\; =\; \backslash Omega(\backslash log\; T)$ suffices to recover standard unconstrained delayed rates up to log factors. This is a strong positive result suggesting that even very limited tracking resources can preserve near-optimal learning. For BCO, the graceful degradation through factors of $(1+{\sigma }_{\max }\mathrm{/}C{)}^{1\mathrm{/}4}(1\; +\; \backslash sigma\_\{\backslash max\}/C)^\{1/4\}$ (convex) and $(1+{\sigma }_{\max }\mathrm{/}C{)}^{1\mathrm{/}3}(1\; +\; \backslash sigma\_\{\backslash max\}/C)^\{1/3\}$ (strongly convex) provides a clean quantitative picture of how capacity constraints affect learning.

Practical relevance: Capacity constraints naturally arise in clinical trials, A/B testing with limited monitoring infrastructure, and distributed systems. The connection to finite-buffer queueing systems (where jobs finding a full buffer are dropped) provides natural modeling motivation. The paper's use of ${\sigma }_{\max }\backslash sigma\_\{\backslash max\}$ (peak concurrency) rather than $d_{\max }d\_\{\backslash max\}$ (maximum delay) as the key complexity parameter is well-motivated for queueing-theoretic applications.

Broader framework value: The delayed-weighted OCO/BCO framework (Section 3) extends scale-free online learning to delayed settings and may find independent applications beyond the capacity-constrained setting. The proxy-delay scheduling framework is parameterized by general distributions, allowing future instantiations.

Timeliness & Relevance

The paper addresses a genuine practical gap in the online learning literature. Delayed feedback has received sustained attention, but the implicit assumption of unlimited tracking capacity has gone largely unquestioned until the recent work of RAR25. Extending this to continuous domains is a natural and timely next step, particularly given growing interest in resource-constrained learning systems. The connection between online learning and queueing theory highlighted by the authors represents a potentially fruitful research direction.

Strengths

1. Clean modular architecture: The scheduler/base-learner decomposition enables independent improvement of either component.

2. Comprehensive coverage: Results span four settings (convex/strongly convex × first-order/bandit), with explicit capacity dependence throughout.

3. Sharp thresholds: The $C=\mathrm{\Omega }(\log T)C\; =\; \backslash Omega(\backslash log\; T)$ sufficiency result for first-order OCO is elegant and practically encouraging.

4. Semi-clairvoyant model: Weakening the clairvoyant assumption from prior work without sacrificing rate quality is meaningful.

5. Graceful degradation: BCO bounds remain sublinear even when $C\ll {\sigma }_{\max }C\; \backslash ll\; \backslash sigma\_\{\backslash max\}$, avoiding catastrophic failure.

Limitations

1. No lower bounds: The paper establishes no information-theoretic lower bounds for capacity-constrained OCO/BCO. It is unclear whether the capacity-dependent factors $(1+{\sigma }_{\max }\mathrm{/}C{)}^{1\mathrm{/}4}(1\; +\; \backslash sigma\_\{\backslash max\}/C)^\{1/4\}$ and $(1+{\sigma }_{\max }\mathrm{/}C{)}^{1\mathrm{/}3}(1\; +\; \backslash sigma\_\{\backslash max\}/C)^\{1/3\}$ are tight.

2. Gap in BCO convex case: The delay-dependent term scales as $\sqrt{T{\sigma }_{\max }}\backslash sqrt\{T\backslash sigma\_\{\backslash max\}\}$ rather than the optimal $\sqrt{d_{\text{tot}}}\backslash sqrt\{d\_\{\backslash text\{tot\}\}\}$ from unconstrained settings. The authors acknowledge this gap but leave it open.

3. Oblivious adversary only: The framework assumes an oblivious adversary; extension to adaptive adversaries is left as future work and would require fundamentally different techniques.

4. No experiments: The paper is purely theoretical. Empirical validation on practical scenarios (e.g., clinical trial simulations) would strengthen the contribution.

5. Knowledge requirements: While the doubling trick removes dependence on ${\sigma }_{\max }\backslash sigma\_\{\backslash max\}$, some bounds still require knowledge of $d_{\text{tot}}d\_\{\backslash text\{tot\}\}$ or $TT$, handled via standard but cumbersome doubling.

Overall Assessment

This is a solid theoretical contribution that opens up the study of capacity-constrained online convex optimization. The results are the first of their kind, the technical machinery is sound and novel (particularly the delayed-weighted framework and Bernoulli scheduler), and the problem formulation is well-motivated. The main limitation is the absence of matching lower bounds, which prevents a complete characterization of the capacity-regret tradeoff. The paper makes meaningful progress on a practical and theoretically interesting problem.