Technical Summary: Capacity-Constrained Online Convex Optimization with Delayed Feedback

1. Problem Statement

This paper addresses Online Convex Optimization (OCO) and Bandit Convex Optimization (BCO) under two simultaneous constraints: delayed feedback and limited tracking capacity.

In standard delayed online learning, a learner selects an action $x_t$ at round $t$, incurring a loss $f_t(x_t)$, but only receives feedback (gradient or scalar loss) at round $t + d_t$. Traditional literature assumes the learner has unlimited capacity to track all pending rounds until their feedback arrives. However, in practical scenarios (e.g., clinical trials with limited monitoring resources), the learner can only track a bounded number of pending rounds, denoted by capacity $C$. If a round is not tracked, its feedback is permanently lost.

The paper formalizes this as a game where:

• The adversary fixes convex losses $f_t$ and delays $d_t$.
• The player maintains a tracking set $S$ of size at most $C$.
• At each round, the player may preempt (drop) tracked rounds or add the current round to $S$.
• Feedback for round $s$ is observed at $s + d_s$ if and only if $s \in S$ at that time.
• The goal is to minimize regret $R_T = \sum_{t=1}^T (f_t(x_t) - f_t(x^*))$ against the best fixed action $x^*$ in hindsight.

The paper considers two information models regarding delays:

1. Clairvoyant: Delays $d_t$ are known at prediction time.
2. Semi-Clairvoyant: Delays are revealed only upon expiration (at $t+d_t$), consistent with standard delayed learning settings.

2. Methodology

The authors propose a reduction-based approach that decomposes the capacity-constrained problem into two components: a scheduler and a base learner.

2.1 The Reduction Framework

The core idea is to reduce the capacity-constrained problem to a novel "delayed and weighted" OCO problem.

• Scheduler: A wrapper algorithm manages the tracking set $S$. It uses a proxy-delay scheduling mechanism. For each round $t$, the scheduler samples a "proxy delay" $d'_t$ from a distribution $D_t$. Round $t$ is added to $S$ if $d'_t \ge 0$ and capacity permits. It is removed from $S$ at $t + d'_t + 1$ if feedback has not yet arrived.
• Importance Weighting: If feedback for round $s$ is observed (i.e., $s \in S$ and $d'_s \ge d_s$), the wrapper forwards the feedback to the base learner with an importance weight $w_s = 1 / P(d'_s \ge d_s)$. If feedback is lost (due to capacity saturation or early proxy timeout), the weight is set to 0.
• Base Learner: The learner receives a stream of delayed, weighted feedback. The paper introduces algorithms specifically designed to handle this weighted, delayed stream.

2.2 Base Algorithms: Delayed-Weighted FTRL

The paper introduces and analyzes two base algorithms for the weighted, delayed setting:

1. DW-FTRL (Delayed-Weighted Follow-the-Regularized-Leader): For first-order (gradient) feedback. It updates the iterate by minimizing a regularized objective that aggregates weighted gradients from all observed rounds.
2. DW-FTBL (Delayed-Weighted Follow-the-Bandit-Leader): For bandit (scalar loss) feedback. It uses the standard single-point gradient estimator (perturbing the center point) but applies it to the weighted, delayed feedback stream.

Theoretical analysis of these base algorithms establishes regret bounds that explicitly account for the interaction between time-varying weights and the backlog of pending observations. A key finding is that the regret depends on pairwise interactions of weights for rounds with overlapping delays.

2.3 Proxy Delay Schedulers

To ensure the reduction works, the scheduler must balance two competing goals: covering true delays (to observe feedback) and avoiding capacity saturation. The paper proposes two specific schedulers:

1. Pareto Scheduler: Adapts to individual delays $d_t$. It samples proxy delays from a shifted Pareto distribution, making the probability of tracking inversely proportional to the delay. This is suitable for general convex losses.
2. Bernoulli Scheduler: Calibrated to the maximum backlog $\sigma_{max}$ (the maximum number of pending observations at any time). It samples a proxy delay of $\infty$ with probability $p \approx C / \sigma_{max}$ and $-1$ otherwise. This yields uniform importance weights, a property crucial for achieving tight bounds in strongly convex and bandit settings.

3. Key Contributions

1. First Regret Guarantees for Capacity-Constrained OCO/BCO: The paper provides the first sublinear regret bounds for capacity-constrained online learning with delayed feedback in both convex and strongly convex domains, for both first-order and bandit feedback.
2. Delayed-Weighted OCO Framework: It introduces a new problem setting (delayed and weighted feedback) and analyzes FTRL variants for it. This framework is of independent interest for scale-free online learning under delays.
3. Unified Proxy-Delay Scheduling: The authors unify previous scheduling ideas and introduce a new scheduler (Bernoulli) that yields uniform weights, enabling stronger guarantees for strongly convex and bandit settings.
4. Handling Unknown Parameters: The framework accommodates the semi-clairvoyant model (delays unknown at prediction time) and uses a doubling trick to handle unknown $\sigma_{max}$ without prior knowledge.

4. Main Results

The regret bounds depend on the horizon $T$, dimension $k$, total delay $d_{tot}$, maximum backlog $\sigma_{max}$, and capacity $C$.

4.1 First-Order Feedback (OCO)

• Convex Losses: With capacity $C = \Omega(\log T)$, the regret matches the optimal unconstrained delayed rate up to logarithmic factors:
  $$\tilde{O}\left( G D \sqrt{d_{tot} + T} \right)$$
• Strongly Convex Losses: The regret is:
  $$\tilde{O}\left( \frac{G^2}{\lambda} (\sigma_{max} + 1) \log T \right)$$
  This matches the optimal dependence on $\sigma_{max}$ found in unconstrained settings.

4.2 Bandit Feedback (BCO)

For bandit feedback, the capacity constraint enters the dimension-dependent terms via factors of $(1 + \sigma_{max}/C)$.

• Convex Losses:
  $$\tilde{O}\left( GD \left( \sqrt{T \sigma_{max}} + T^{3/4} \left(1 + \frac{\sigma_{max}}{C}\right)^{1/4} \sqrt{\nu k} \right) \right)$$
  where $\nu$ is the scale ratio of function values to gradients. The bound degrades gracefully as $C$ decreases.
• Strongly Convex Losses:
  $$\tilde{O}\left( \frac{G^2}{\lambda} \left( \sigma_{max} \log T + (T^2 \log T)^{1/3} \left(1 + \frac{\sigma_{max}}{C}\right)^{1/3} (\nu k)^{2/3} \right) \right)$$

Key Observation: When $C \ge \sigma_{max}$, the bounds recover the unconstrained rates. When $C < \sigma_{max}$, the regret increases but remains sublinear. The dependence on $\sigma_{max}$ (peak concurrency) is shown to be more natural than dependence on $d_{max}$ (maximum delay) in queueing-like systems.

5. Significance and Claims

The paper claims to be the first to derive regret guarantees for capacity-constrained OCO and BCO. Its significance lies in:

• Bridging Theory and Practice: It addresses the realistic constraint that tracking resources are finite, a limitation ignored by most prior delayed learning literature which assumes infinite capacity.
• Refining the Delay Model: By adopting a semi-clairvoyant model (delays revealed only at expiration), the work aligns closer to standard delayed learning and online job scheduling realities than previous "clairvoyant" assumptions.
• Graceful Degradation: The results demonstrate that a logarithmic capacity ($C = \Omega(\log T)$) is sufficient to recover standard delayed rates for first-order feedback, while for bandit feedback, the performance degrades gracefully as capacity drops below the peak backlog.
• Theoretical Novelty: The introduction of the "delayed and weighted" OCO problem and the specific analysis of the interaction between weights and delays in FTRL provides new tools for analyzing online learning under resource constraints.

The authors note that while their bounds for convex bandit feedback scale with $\sqrt{T \sigma_{max}}$ rather than the optimal $\sqrt{d_{tot}}$ of the unconstrained setting, they still improve upon previous bounds depending on $\sqrt{T d_{max}}$. They identify closing this gap as an open problem. Additionally, they suggest that the structural similarity between their model and finite-buffer queueing systems warrants further exploration.