Online Learning with Optimism and Delay

1. Introduction

• DORM, DORM+, and AdaHedgeD achieve optimal worst-case regret rates under delay, use every observation, and require no parameters to tune.The paper validates them on subseasonal forecasting, where feedback is delayed and semimonthly evaluation may provide only 26 forecasts per year.Source: §1 · pp. 1–2
• The paper reduces delayed online learning to optimistic online learning, using the “delay-as-optimism” perspective to develop its algorithms.The initial presentation assumes constant delay, with extensions to variable and unbounded delays in Appendix O.Source: §1 · p. 1
• The work tightens optimistic regret bounds to show robustness to inaccurate hints and provides analyses of FTRL and OMD with optimism and delay.It also introduces a meta-algorithm for learning a low-regret optimism strategy under delay.Source: §1 · pp. 1–2
• Subseasonal forecasting tests the algorithms under delayed feedback, short horizons, and a practical need to avoid difficult-to-tune parameters.The task predicts precipitation and temperature 2–6 weeks ahead; the paper reports consistently low regret relative to the best forecasting models.Source: §1 · p. 2

2. Preliminaries: Optimistic Online Learning

• An optimistic learner receives a pseudo-loss hint before choosing its play, and standard formulations add that pseudo-loss to the FTRL or OMD regularized objective.This yields optimistic FTRL (OFTRL) and single-step optimistic OMD (SOOMD).Source: §2 · p. 2
• Regret is reduced when the hint subgradient is close to the true loss subgradient.The stated error measure is the dual norm of their difference.Source: §2 · p. 2
• Setting optimistic hints to zero recovers the standard FTRL and OMD updates.Source: §2 · p. 2

3.1. Delay as Optimism

• Delayed ODFTRL and DOOMD are optimistic FTRL and SOOMD with hints that omit unobserved loss subgradients, so their undelayed regret bounds transfer to delayed learning.The useful hints can approximate the summed subgradients of delayed and future losses.Source: §3 · p. 2, §3.1 · p. 3

3.2. Delayed and Optimistc Regret Bounds

• A robust Huber penalty replaces squared hint error, tightening optimistic regret bounds and supporting optimal regret guarantees under delay despite inaccurate hints.The paper uses this robustness to handle large hint errors in its delayed-learning analysis.Source: §3.2 · p. 3
• O(√((D + 1)T)) regret is minimax optimal under delay; poor proxies for missing gradients still incur only the minimax optimal √(D + 1) penalty.The bounds compound delay when hints or hint changes have the stated bounded sizes.Source: §3.2 · p. 3
• Unlike replication, which splits data among D + 1 isolated learners, the proposed non-replicated strategies use every observation and combine optimistic hinting with self-tuned regularization.Replication can leave each learner with only a small fraction of the losses, a drawback for short prediction horizons.Source: §3.2 · pp. 3–4

3.3. Tuning Regularizers with Optimism and Delay

• DORM and DORM+ are tuning-free, while AdaHedgeD is self-tuning; all three support optimism and achieve the minimax optimal regret rate under delay.The paper introduces DORM and DORM+ as tuning-free variants and AdaHedgeD as an adaptive ODFTRL variant.Source: §3.3 · p. 4

4. Tuning-free Learning with Optimism and Delay

• DORM and DORM+ generalize regret matching and regret matching+ to optimistic delayed feedback.They are connected to ODFTRL and DOOMD, respectively, to obtain delayed-feedback regret guarantees.Source: §4 · p. 4, §4.1 · p. 4

4.1. Tuning-free Regret Bounds

• DORM and DORM+ iterates are independent of λ, so they are automatically optimally tuned even with the default λ = 1.The paper identifies this parameter independence as the basis of their tuning-free property.Source: §4.1 · p. 5
• Choosing q = argmin_{q′≥2} d^{2/q′}(q′ − 1) yields minimax optimal p log²(d) dependence on the number of experts.The paper also suggests predicting the sum of unobserved instantaneous regrets as a hinting strategy.Source: §4.1 · p. 5

5.1. Conservative Tuning with Delayed Upper Bound

• DUB’s conservative tuning requires an a priori upper bound on possible subgradient norms, which can cause extreme over-regularization.The bound uses B0 as a uniform upper bound on unobserved terms.Source: §5.1 · p. 6
• DUB uses only observed terms and achieves optimal regret scaling with delay, but its bounds can be loose.The approach avoids upper bounds on future losses; the next section refines its regularization using AdaHedgeD.Source: §5.1 · p. 6

5.2. Refined Tuning with AdaHedgeD

• The AdaHedgeD analysis yields minimax-optimal O((D + 1)T + D) dependence on delay and nearly matches the optimal constant-λ tuning bound.The section also recommends α = ln(d) on the simplex, yielding minimax-optimal ln(d) dependence on d.Source: §5.2 · p. 6
• AdaHedgeD achieves the same regret bound as DUB, with regularization values that can be orders of magnitude smaller.Its tighter bound enables more adaptive settings of λt.Source: §5.2 · p. 6
• Unlike prior adaptive tuning approaches under delay, DUB and AdaHedgeD incorporate optimism and need no prior knowledge of future subgradients.Their regret guarantees are comparable to one another.Source: §5.2 · p. 6

• The hinting problem combines each hinter’s estimate of missing subgradients into a hint for the base learner.The target is low regret against the best fixed combination of hinters.Source: §6 · p. 7
• DORM+ learns convex-combination weights over candidate hint strategies, and the resulting hints perform nearly as well as the best constant combination in hindsight.The hint learner uses a convex loss that upper bounds the base learner’s regret.Source: §6 · p. 7
• For the DORM base learner, learning to hint adds O(T^1/4(D + 1)^3/4) regret under the stated hinter-loss construction.The passage notes the relevant loss term can be Θ((D + 1)^2).Source: §6 · p. 7
• The learning-to-hint strategy preserves minimax-optimal regret rates when D = o(T).The paper contrasts it with prior work that does not accommodate delay and analyzes only single hint strategies.Source: §6 · p. 7

• The evaluation combines six models across four temperature and precipitation tasks, with delays of D = 2 or 3 and T = 26 semimonthly forecasts per year.The loss is geographic RMSE over 514 locations in the Western United States; results cover 2011–2020.Source: §7 · p. 7
• DORM+ tracks the best input model on all tasks except Temp. 5-6w, and online learners achieve negative regret on both precipitation tasks.Across years, DORM+ has consistently low regret; AdaHedgeD performs comparably to optimally tuned DORM.Source: §7 · pp. 7–8, Table 1 · p. 8
• In Temp. 3-4w, DUB’s λT = 142.881 produces nearly uniform weights, while AdaHedgeD’s λT = 3.005 yields more aggressive plays and higher average RMSE.DORM+ uses λt-free updates and produces more moderately regularized plays.Source: §7 · p. 8, Figure 2 · p. 8, Figure 3 · p. 9
• In Temp. 5-6w, DORM+ outperforms replicated DORM+, with average RMSE of 2.303 versus 2.315.The replicated learner’s staggered, separate plays are visible in the weight plots.Source: §7 · p. 8, Figure 4 · p. 9
• Adaptive hinting avoids the worst individual hinter’s performance in a given year but does not beat the dominant recent-g strategy overall.Several hint strategies outperform using no hint.Source: §7 · p. 9, Figure 5 · p. 9

8. Conclusion

• The delay-as-optimism reduction and refined optimistic-learning analysis produce novel regret bounds for optimistic and delayed online learning.For subseasonal forecasting, delayed methods produce zero-regret ensembles with robust year-to-year performance; DORM+ is highlighted for being tuning-free and having small tracking regret.Source: §8 · p. 9

A.1. General online learning

• The appendix recommends standard monographs and textbooks as surveys of online learning and modular algorithm analyses.Source: §A.1 · p. 12

A.2. Online learning with optimism but without delay

• Prior optimistic-learning work without delay studied optimistic FTRL and mirror descent, while other work combined optimism and adaptivity.The cited examples include Syrgkanis et al. (2015) and Steinhardt & Liang (2014).Source: §A.2 · p. 12

A.3. Online learning with delay but without optimism

• Prior delayed-learning reviews cover delayed online learning, while cited stochastic-optimization studies do not treat the adversarial setting considered here.The passage also notes that FTRL-Prox analyses did not study the standard FTRL algorithms considered in this work.Source: §A.3 · p. 12

A.4. Self-tuned online learning without delay or optimism

• Other FTRL variants self-tune learning rates in the absence of both delay and optimism.Source: §A.4 · p. 12

A.5. Online learning without delay for climate forecasting

• Earlier climate-model ensembling used online learning to track changing best models, but relied on feedback without delay.The cited work used historical temperature data from 20 climate models and Bayesian updates based on a hidden best-model identity.Source: §A.5 · p. 12

B. Proof of Thm. 3: OFTRL regret

• Theorem 14 bounds OAFTRL regret for nonnegative regularizer ψ and non-decreasing λ_t, with terms reflecting hint error and loss-gradient norms.The stated fixed-λ choice yields Theorem 3.Source: B. Proof of Thm. 3: OFTRL regret · pp. 12, 14
• The proof decomposes regret into auxiliary OAFTRL regret and drift between the original and auxiliary iterates.The auxiliary sequence uses subgradient hints; the drift is bounded using the OAFTRL difference lemma.Source: B. Proof of Thm. 3: OFTRL regret · p. 13

B.1. Proof of Lem. 15: OAFTRL difference bound

• Lemma 15 bounds the difference between OAFTRL iterates with differing losses but common regularizers, using strong convexity and the diameter of W.The diameter bound supplies the second half of the target difference bound.Source: B. Proof of Thm. 3: OFTRL regret · p. 13, §B.1 · p. 14

C. Proof of Thm. 4: SOOMD regret

• Theorem 16 bounds ASOOMD regret using the delayed-gradient and hint differences, under proper differentiable regularizer increments and the stated terminal-hint condition.The fixed-λ choice yields Theorem 4.Source: C. Proof of Thm. 4: SOOMD regret · pp. 14–15
• The proof controls iterate drift with a bound scaling as 1/λ_{t+1} times the norm of the gradient and hint changes.The subsequent norm-constrained conjugate lemma is used to bound the regret summands.Source: C. Proof of Thm. 4: SOOMD regret · pp. 15–16

D. Proof of Lem. 8: DORM is ODAFTRL and DORM + is DOOMD

• DORM is shown as an ODAFTRL instance with hint −h_{t+1}, while DORM+ is shown equivalent to DOOMD after transforming its unnormalized iterates.For DORM+, the proof uses p=q/(q−1) and establishes the iterate relation by induction.Source: §D.1 · p. 17, §D.2 · p. 17

E. Proof of Lem. 7: DORM and DORM+ are independent of λ

• Under the stated dependence assumptions and an initial scaled iterate independent of λ, λ^{q−1} times each DORM or DORM+ unnormalized iterate remains independent of λ.The played iterates are consequently independent of λ as well.Source: E. Proof of Lem. 7: DORM and DORM+ are… · p. 18

F. Proof of Cor. 9: DORM and DORM+ regret

• The DORM and DORM+ regret proofs use their ODFTRL and DOOMD representations, then take an infimum over λ because the played sequences are invariant to its choice.The derivation also invokes p-norm equivalence relations.Source: F. Proof of Cor. 9: DORM and DORM+… · pp. 18–19

G. Proof of Thm. 10: ODAFTRL regret

• The ODAFTRL regret result follows by viewing ODAFTRL as OAFTRL with a hint adjusted by the delayed loss gradients.The passage identifies the adjusted hint as h_{t+1} minus the gradients from t−D+1 through t.Source: G. Proof of Thm. 10: ODAFTRL regret · p. 19

H. Proof of Thm. 11: DUB Regret; I. Proof of Thm. 12: AdaHedgeD Regret

• The DUB and AdaHedgeD regret proofs bound their regularization sequences using a tuning lemma and the non-decreasing regularization condition, respectively.The DUB proof invokes its style-specific tuning bound; the AdaHedgeD proof uses Theorem 14.Source: H. Proof of Thm. 11: DUB Regret · p. 19, §I · p. 20

J. Proof of Thm. 13: Learning to hint regret

• The hinting-problem regret bound for DORM+ yields a bound on HintRegret_T when q is chosen by the stated dimension-dependent minimization.A separate lemma bounds each β_{t,∞} term using hinting-problem subgradients.Source: J. Proof of Thm. 13: Learning to hint… · p. 21

K. Examples: Learning to Hint with DORM+ and AdaHedgeD

• For the hinting examples, AdaHedgeD and DORM+ define hinting losses from gradient and delayed-regret information, and the resulting subgradients admit an ∞-norm bound.The bound depends on d^{1/q}, the base gradient norm, and the hint matrix’s maximum absolute entry.Source: K. Examples: Learning to Hint with… · pp. 21–22

L.1. Subseasonal Forecasting Application; L.2. Problem Definition

• The application evaluates adaptive ensembles of six input models across four tasks, with delays of two forecasts for 3–4 week horizons and three for 5–6 week horizons.The tasks combine precipitation or temperature forecasts across two horizons, with 26 semimonthly forecasts per model.Source: §L.2 · p. 23

M.2. Impact of Regularization

• DUB and AdaHedgeD appear respectively over- and under-regularized relative to DORM+, while DUB’s plays remain close to the uniform ensemble.The passage notes that uniform ensembling is competitive here, especially for 5–6 week horizons.Source: §M.2 · p. 27

M.3. To Replicate or Not to Replicate

• Standard DORM+ outperforms its replicated variant on all tasks; replication limits each learner to T/(D+1) opportunities to learn.The authors connect this limitation to the short T=26 forecasting horizon.Source: §M.3 · p. 29

M.4. Learning to Hint

• The learned hint strategy’s regret generally falls between the best and worst constant strategies, but its learner optimizes only a loose upper bound on base regret.The authors identify more accurate hint-learning loss functions as a next step.Source: §M.4 · p. 30

M.5. Impact of Different Forms of Optimism

• Across tasks, every tested optimism setting improves on the non-optimistic algorithm, and future-loss hints outperform past-loss hints.Hints for both past and future losses improve further except on Temp. 5–6w; larger future-hint weights help some tasks.Source: §M.5 · p. 30

N.4. Proof of Lem. 28: Negative entropy properties

• The negative-entropy proof derives the Fenchel-conjugate expression through constrained convex optimization and conjugate properties.Source: §N.4 · p. 32

O. Extension to Variable and Unbounded Delays

• The extension defines last(t) as the latest loss prefix observable at time t, and first(t) as the first time the full prefix through t becomes observable.Source: O. Extension to Variable and Unbounded… · p. 34

O.1. Regret of DOOMD with variable delays

• With differentiable ψ and a terminal hint set to the remaining unobserved gradients, the variable-delay DOOMD theorem gives a regret bound.The theorem follows by treating variable-delay DOOMD as SOOMD with a hint that omits unobserved loss subgradients.Source: §O.1 · p. 34

O.2. Regret of ODAFTRL with variable delays

• For nonnegative ψ and non-decreasing λ_t, the variable-delay ODAFTRL iterates satisfy a regret bound for every comparator u in W.Source: §O.2 · p. 35

O.3. Regret of DUB with variable delays

• Under nonnegative ψ, the variable-delay DUB theorem bounds regret using its delay-dependent tuning sequence and the quantities a_t,F and b_t,F.The tuning bound is established using a separate lemma for nonnegative sequences.Source: §O.3 · p. 35

O.4. Proof of Lem. 35: DUB with variable delays-style tuning bound

• The DUB variable-delay tuning bound is proved by induction, summing inequalities and solving a quadratic inequality.Source: §O.3 · p. 35, §O.4 · p. 36

O.5. Regret of AdaHedgeD with variable delays

• For nonnegative ψ, the variable-delay AdaHedgeD theorem gives a regret bound for every comparator u in W.Source: §O.5 · p. 37
• The AdaHedgeD variable-delay analysis applies its non-decreasing regularization sequence within the ODAFTRL regret bound.Source: §O.5 · p. 37