Online learning is a sequential decision-making paradigm in which a learner is pitted against a potentially adversarial environment (Shalev-Shwartz, 2007;Orabona, 2019). At time t, the learner must select a play w t from some set of possible plays W. The environment then reveals the loss function ℓ t and the learner pays the cost ℓ t (w t ). The learner uses information collected in previous rounds to improve its plays in subsequent rounds. Optimistic online learners additionally make use of side-information or "hints" about expected future losses to improve their plays. Over a period of length T , the goal of the learner is to minimize regret, an objective that quantifies the performance gap between the learner and the best possible constant play in retrospect in some competitor set U: Regret T = sup u∈U T t=1 ℓ t (w t )-ℓ t (u). Adversar- ial online learning algorithms provide robust performance in many complex real-world online prediction problems such as climate or weather forecasting.
In traditional online learning paradigms, the loss for round t is revealed to the learner immediately at the end of round t. However, many real-world applications produce delayed feedback, i.e., the loss for round t is not available until round t + D for some delay period D.foot_0 Existing delayed online learning algorithms achieve optimal worst-case regret rates against adversarial loss sequences, but each has drawbacks when deployed for real applications with short horizons T . Some use only a small fraction of the data to train each learner (Weinberger & Ordentlich, 2002;Joulani et al., 2013); others tune their parameters using uniform bounds on future gradients that are often challenging to obtain or overly conservative in applications (McMahan & Streeter, 2014;Quanrud & Khashabi, 2015;Joulani et al., 2016;Korotin et al., 2020;Hsieh et al., 2020). Only the concurrent work of Hsieh et al. (2020, Thm. 13) can make use of optimistic hints and only for the special case of unconstrained online gradient descent.
In this work, we aim to develop robust and practical algorithms for real-world delayed online learning. To this end, we introduce three novel algorithms-DORM, DORM+, and AdaHedgeD-that use every observation to train the learner, have no parameters to tune, exhibit optimal worstcase regret rates under delay, and enjoy improved performance when accurate hints for unobserved losses are available. We begin by formulating delayed online learning as a special case of optimistic online learning and use this "delay-as-optimism" perspective to develop:
1. A formal reduction of delayed online learning to optimistic online learning (Lems. 1 and 2), 2. The first optimistic tuning-free and self-tuning algorithms with optimal regret guarantees under delay (DORM, DORM+, and AdaHedgeD), 3. A tightening of standard optimistic online learning regret bounds that reveals the robustness of optimistic algorithms to inaccurate hints (Thms. 3 and 4), 4. The first general analysis of follow-the-regularizedleader (Thms. 5 and 10) and online mirror descent algorithms (Thm. 6) with optimism and delay, and 5. The first meta-algorithm for learning a low-regret optimism strategy under delay (Thm. 13).
We validate our algorithms on the problem of subseasonal forecasting in Sec. 7. Subseasonal forecasting-predicting precipitation and temperature 2-6 weeks in advance-is a crucial task for allocating water resources and preparing for weather extremes (White et al., 2017). Subseasonal forecasting presents several challenges for online learning algorithms. First, real-time subseasonal forecasting suffers from delayed feedback: multiple forecasts are issued before receiving feedback on the first. Second, the regret horizons are short: a common evaluation period for semimonthly forecasting is one year, resulting in 26 total forecasts. Third, forecasters cannot have difficult-to-tune parameters in realtime, practical deployments. We demonstrate that our algorithms DORM, DORM+, and AdaHedgeD sucessfully overcome these challenges and achieve consistently low regret compared to the best forecasting models.
Our Python library for Optimistic Online Learning under Delay (PoolD) and experiment code are available at https://github.com/geflaspohler/poold.
Notation For integers a, b, we use the shorthand [b] {1, . . . , b} and g a:b b i=a g i . We say a function f is proper if it is somewhere finite and never -∞. We let ∂f (w) = {g ∈ R d : f (u) ≥ f (w) + g, uw , ∀u ∈ R d } denote the set of subgradients of f at w ∈ R d and say f is µ-strongly convex over a convex set W ⊆ int dom f with respect to • with dual norm • * if ∀w, u ∈ W and g ∈ ∂f (w), we have f (u) ≥ f (w) + g, uw + µ 2 wu 2 . For differentiable ψ, we define the Bregman divergence B ψ (w, u) ψ(w) -ψ(u) -∇ψ(u), wu . We define diam(W) = inf w,w ′ ∈W ww ′ , (r) + max(r, 0), and min(r, s) + (min(r, s)) + .
Standard online learning algorithms, such as follow the regularized leader (FTRL) and online mirror descent (OMD) achieve optimal worst-case regret against adversarial loss sequences (Orabona, 2019). However, many loss sequences encountered in applications are not truly adversarial. Optimistic online learning algorithms aim to improve performance when loss sequences are partially predictable, while remaining robust to adversarial sequences (see, e.g., Azoury & Warmuth, 2001;Chiang et al., 2012;Rakhlin & Sridharan, 2013b;Steinhardt & Liang, 2014). In optimistic online learning, the learner is provided with a "hint" in the form of a pseudo-loss lt at the start of round t that represents a guess for the true unknown loss. The online learner can incorporate this hint before making play w t .
In standard formulations of optimistic online learning, the convex pseudo-loss lt (w t ) is added to the standard FTRL or OMD regularized objective function and leads to optimistic variants of these algorithms: optimistic FTRL (OFTRL, Rakhlin & Sridharan, 2013a) and single-step optimistic OMD (SOOMD, Joulani et al., 2017, Sec. 7.2). Let gt ∈ ∂ lt (w t-1 ) and g t ∈ ∂ℓ t (w t ) denote subgradients of the pseudo-loss and true loss respectively. The inclusion of an optimistic hint leads to the following linearized update rules for play w t+1 :
with g0 = 0 and arbitrary w 0 (SOOMD) where gt+1 ∈ R d is the hint subgradient, λ ≥ 0 is a regularization parameter, and ψ is proper regularization function that is 1-strongly convex with respect to a norm • . The optimistic learner enjoys reduced regret whenever the hinting error g t+1 -gt+1 * is small (Rakhlin & Sridharan, 2013a;Joulani et al., 2017). Common choices of optimistic hints include the last observed subgradient or average of previously observed subgradients (Rakhlin & Sridharan, 2013a). We note that the standard FTRL and OMD updates can be recovered by setting the optimistic hints to zero.
In the delayed feedback setting with constant delay of length D, the learner only observes (ℓ i ) t-D i=1 before making play w t+1 . In this setting, we propose counterparts of the OFTRL and SOOMD online learning algorithms, which we call optimistic delayed FTRL (ODFTRL) and delayed optimistic online mirror descent (DOOMD) respectively:
with h 0 0 and arbitrary w 0 , (DOOMD)
for hint vector h t+1 . Our use of the notation h t+1 instead of gt+1 for the optimistic hint here is suggestive. Our regret analysis in Thms. 5 and 6 reveals that, instead of hinting only for the "future" missing loss g t+1 , delayed online learners should uses hints h t that guess at the summed subgradients of all delayed and future losses: h t = t s=t-D gs .
To analyze the regret of the ODFTRL and DOOMD algorithms, we make use of the first key insight of this paper:
Learning with delay is a special case of learning with optimism.
In particular, ODFTRL and DOOMD are instances of OFTRL and SOOMD respectively with a particularly "bad" choice of optimistic hint gt+1 that deletes the unobserved loss subgradients g t-D+1:t .
Lemma 1 (ODFTRL is OFTRL with a bad hint). ODFTRL
The implication of this reduction of delayed online learning to optimistic online learning is that any regret bound shown for undelayed OFTRL or SOOMD immediately yields a regret bound for ODFTRL and DOOMD under delay. As we demonstrate in the remainder of the paper, this novel connection between delayed and optimistic online learning allows us to bound the regret of optimistic, self-tuning, and tuning-free algorithms for the first time under delay.
Finally, it is worth reflecting on the key property of OFTRL and SOOMD that enables the delay-to-optimism reduction: each algorithm depends on g t and gt+1 only through the sum g 1:t + gt+1 . 2 For the "bad" hints of Lems. 1 and 2, these sums are observable even though g t and gt+1 are not separately observable at time t due to delay. A number of alternatives to SOOMD have been proposed for optimistic OMD (Chiang et al., 2012;Rakhlin & Sridharan, 2013a;b;Kamalaruban, 2016). Unlike SOOMD, these procedures all incorporate optimism in two steps, as in the updates w t+1/2 = argmin w∈W g t , w + B λψ (w, w t-1/2 ) and w t+1 = argmin w∈W gt+1 , w + B λψ (w, w t+1/2 ) (1) described in Rakhlin & Sridharan (2013a, Sec. 2.2). It is unclear how to reduce delayed OMD to an instance of one of these two-step procedures, as knowledge of the unobserved g t is needed to carry out the first step.
To demonstrate the utility of our delay-as-optimism perspective, we first present the following new regret bounds for OFTRL and SOOMD, proved in Apps. B and C respectively.
Theorem 3 (OFTRL regret). If ψ is nonnegative, then, for all u ∈ W, the OFTRL iterates w t satisfy
Theorem 4 (SOOMD regret). If ψ is differentiable and 2 For SOOMD, gt + gt+1 -gt = g1:t + gt+1 -(g1:t-1 + gt).
gT +1 0, then, ∀u ∈ W, the SOOMD iterates w t satisfy
Both results feature the robust Huber penalty (Huber, 1964) huber(x, y)
in place of the more common squared error term 1 2 g t -gt
2 * . As a result, Thms. 3 and 4 strictly improve the rate-optimal OFTRL and SOOMD regret bounds of Rakhlin & Sridharan (2013a); Mohri & Yang (2016); Orabona (2019, Thm. 7.28) and Joulani et al. (2017, Sec. 7.2) by revealing a previously undocumented robustness to inaccurate hints gt . We will use this robustness to large hint error g t -gt * to establish optimal regret bounds under delay.
As an immediate consequence of this regret analysis and our delay-as-optimism perspective, we obtain the first general analyses of FTRL and OMD with optimism and delay.
Theorem 5 (ODFTRL regret). If ψ is nonnegative, then, for all u ∈ W, the ODFTRL iterates w t satisfy
Theorem 6 (DOOMD regret). If ψ is differentiable and h T +1
g T -D+1:T , then, for all u ∈ W, the DOOMD iterates w t satisfy
Our results show a compounding of regret due to delay: the b t,F term of Thm. 5 is of size O(D + 1) whenever h t * = O(D + 1), and the same holds for b t,O of Thm. 6 if h t+1h t * = O(1). An optimal setting of λ therefore delivers O( (D + 1)T ) regret, yielding the minimax optimal rate for adversarial learning under delay (Weinberger & Ordentlich, 2002). Thms. 5 and 6 also reveal the heightened value of optimism in the presence of delay: in addition to providing an effective guess of the future subgradient g t , an optimistic hint can approximate the missing delayed feedback ( t-1 s=t-D g s ) and thereby significantly reduce the penalty of delay. If, on the other hand, the hints are a poor proxy for the missing loss subgradients, the novel huber term ensures that we still only pay the minimax optimal √ D + 1 penalty for delayed feedback.
Related work A classical approach to delayed feedback in online learning is the so-called "replication" strategy in which D + 1 distinct learners take turns observing and responding to feedback (Weinberger & Ordentlich, 2002;Joulani et al., 2013;Agarwal & Duchi, 2011;Mesterharm, 2005). While minimax optimal in adversarial settings, this strategy has the disadvantage that each learner only sees T D+1 losses and is completely isolated from the other replicates, exacerbating the problem of short prediction horizons.
In contrast, we develop and analyze non-replicated delayed online learning strategies that use a combination of optimistic hinting and self-tuned regularization to mitigate the effects of delay while retaining optimal worst-case behavior.
We are not aware of prior analyses of DOOMD, and, to our knowledge, Thm. 5 and its adaptive generalization Thm. 10 provide the first general analysis of delayed FTRL, apart from the concurrent work of Hsieh et al. (2020, Thm. 1). Hsieh et al. (2020, Thm. 13) and Quanrud & Khashabi (2015, Thm. 2.1) focus only on delayed gradient descent, Korotin et al. (2020) study General Hedging, andJoulani et al. (2016, Thm. 4) and Quanrud & Khashabi (2015, Thm. A.5) study non-optimistic OMD under delay. Thms. 5, 6, and 10 strengthen these results from the literature which feature a sum of subgradient norms (
Even in the absence of optimism, the latter can be significantly smaller: e.g., if the gradients g s are i.i.d. mean-zero vectors, the former has size Ω(D) while the latter has expectation O( √ D). In the absence of optimism, McMahan & Streeter (2014) obtain a bound comparable to Thm. 5 for the special case of one-dimensional unconstrained online gradient descent.
In the absence of delay, Cutkosky (2019) introduces metaalgorithms for imbuing learning procedures with optimism while remaining robust to inaccurate hints; however, unlike OFTRL and SOOMD, the procedures of Cutkosky require separate observation of gt+1 and each g t , making them unsuitable for our delay-to-optimism reduction.
The online learning algorithms introduced so far all include a regularization parameter λ. In theory and in practice, these algorithms only achieve low regret if the regularization parameter λ is chosen appropriately. In standard FTRL, for example, one such setting that achieves optimal regret is λ = T t=1 gt 2 * sup u∈U ψ(u) . This choice, however, cannot be used in practice as it relies on knowledge of all future unobserved loss subgradients. To make use of online learning algorithms, the tuning parameter λ is often set using coarse upper bounds on, e.g., the maximum possible subgradient norm. However, these bounds are often very conservative and lead to poor real-world performance.
In the following sections, we introduce two strategies for tuning regularization with optimism and delay. Sec. 4 introduces the DORM and DORM+ algorithms, variants of ODFTRL and DOOMD that are entirely tuning-free. Sec. 5 introduces the AdaHedgeD algorithm, an adaptive variant of ODFTRL that is self-tuning; a sequence of regularization parameters λ t are set automatically using new, tighter bounds on algorithm regret. All three algorithms achieve the minimax optimal regret rate under delay, support optimism, and have strong real-world performance as shown in Sec. 7.
Regret matching (RM) (Blackwell, 1956;Hart & Mas-Colell, 2000) and regret matching+ (RM+) (Tammelin et al., 2015) are online learning algorithms that have strong empirical performance. RM was developed to find correlated equilibria in two-player games and is commonly used to minimize regret over the simplex. RM+ is a modification of RM designed to accelerate convergence and used to effectively solve the game of Heads-up Limit Texas Hold'em poker (Bowling et al., 2015). RM and RM+ support neither optimistic hints nor delayed feedback, and known regret bounds have a suboptimal scaling with respect to the problem dimension d (Cesa- Bianchi & Lugosi, 2006;Orabona & Pál, 2015). To extend these algorithms to the delayed and optimistic setting and recover the optimal regret rate, we introduce our generalizations, delayed optimistic regret matching (DORM)
wt+1 max(0, (r 1:t-D + h t+1 )/λ) q-1 and delayed optimistic regret matching+ (DORM+) w t+1 = wt+1 / 1, wt+1 for h 0 = w0 0, (DORM+)
Each algorithm makes use of an instantaneous regret vector r t 1 g t , w tg t that quantifies the relative performance of each expert with respect to the play w t and the linearized loss subgradient g t . The updates also include a parameter q ≥ 2 and its conjugate exponent p = q/(q -1) that is set to recover the minimax optimal scaling of regret with the number of experts (see Cor. 9). We note that DORM and DORM+ recover the standard RM and RM+ algorithms when D = 0, λ = 1, q = 2, and h t = 0, ∀t.
To bound the regret of the DORM and DORM+ plays, we prove that DORM is an instance of ODFTRL and DORM+ is an instance of DOOMD. This connection enables us to immediately provide regret guarantees for these regretmatching algorithms under delayed feedback and with optimism. We first highlight a remarkable property of DORM and DORM+ that is the basis of their tuning-free nature.
Under mild conditions:
The normalized DORM and DORM+ iterates w t are independent of the choice of regularization parameter λ.
Lemma 7 (DORM and DORM+ are independent of λ). If the subgradient g t and hint h t+1 only depend on λ through (w s , λ q-1 ws , g s-1 , h s ) s≤t and (w s , λ q-1 ws , g s , h s ) s≤t respectively, then the DORM and DORM+ iterates (w t ) t≥1 are independent of the choice of λ > 0.
Lem. 7, proved in App. E, implies that DORM and DORM+ are automatically optimally tuned with respect to λ, even when run with a default value of λ = 1. Hence, these algorithms are tuning-free, a very appealing property for real-world deployments of online learning.
To show that DORM and DORM+ also achieve optimal regret scaling under delay, we connect them to ODFTRL and DOOMD operating on the nonnegative orthant with a special surrogate loss lt (see App. D for our proof):
Lemma 8 (DORM is ODFTRL and DORM+ is DOOMD).
The DORM and DORM+ iterates are proportional to ODFTRL and DOOMD iterates respectively with W R d + , ψ( w) = 1 2 w 2 p , and loss lt ( w) = w, -r t .
Lem. 8 enables the following optimally-tuned regret bounds for DORM and DORM+ run with any choice of λ:
Corollary 9 (DORM and DORM+ regret). Under the assumptions of Lem. 7, for all u ∈ △ d-1 and any choice of λ > 0, the DORM and DORM+ iterates w t satisfy
Cor. 9, proved in App. F, suggests a natural hinting strategy for reducing the regret of DORM and DORM+: predict the sum of unobserved instantaneous regrets t s=t-D r s . We explore this strategy empirically in Sec. 7. Cor. 9 also highlights the value of the q parameter in DORM and DORM+: using the easily computed value q = argmin q ′ ≥2 d 2/q ′ (q ′ -1) yields the minimax optimal log 2 (d) dependence of regret on dimension (Cesa-Bianchi & Lugosi, 2006;Orabona & Pál, 2015). By Lem. 8, setting q in this way is equivalent to selecting a robust 1 2 • 2 p regularizer (Gentile, 2003) for the underlying ODFTRL and DOOMD problems.
Related work Without delay, Farina et al. (2021) independently developed optimistic versions of RM and RM+ by reducing them to OFTRL and a two-step variant of optimistic OMD (1). Unlike SOOMD, this two-step optimistic OMD requires separate observation of gt+1 and g t , making it unsuitable for our delay-as-optimism reduction and resulting in a different algorithm from DORM+ even when D = 0. In addition, their regret bounds and prior bounds for RM and RM+ (special cases of DORM and DORM+ with q = 2) have suboptimal regret when the dimension d is large (Bowling et al., 2015;Zinkevich et al., 2007).
In this section, we analyze an adaptive version of ODFTRL with time-varying regularization λ t ψ and develop strategies for setting λ t appropriately in the presence of optimism and delay. We begin with a new general regret analysis of optimistic delayed adaptive FTRL (ODAFTRL)
where h t+1 ∈ R d is an arbitrary hint vector revealed before w t+1 is generated, ψ is 1-strongly convex with respect to a norm • , and λ t ≥ 0 is a regularization parameter.
Theorem 10 (ODAFTRL regret). If ψ is nonnegative and λ t is non-decreasing in t, then, ∀u ∈ W, the ODAFTRL iterates w t satisfy
The proof of this result in App. G builds on a new regret bound for undelayed optimistic adaptive FTRL (OAFTRL). In the absence of delay (D = 0), Thm. 10 strictly improves existing regret bounds (Rakhlin & Sridharan, 2013a;Mohri & Yang, 2016;Joulani et al., 2017) for OAFTRL by providing tighter guarantees whenever the hinting error h t -t s=t-D g t * is larger than the subgradient magnitude g t * . In the presence of delay, Thm. 10 benefits both from robustness to hinting error in the worst case and the ability to exploit accurate hints in the best case. The bounded-domain factors a t,F strengthen both standard OAFTRL regret bounds and the concurrent bound of Hsieh et al. (2020, Thm. 1) when diam(W) is small and will enable us to design practical λ t -tuning strategies under delay without any prior knowledge of unobserved subgradients. We now turn to these self-tuning protocols.
Setting aside the a t,F bounded-domain factors in Thm. 10 for now, the adaptive sequence λ t = t s=1 b s,F sup u∈U ψ(u) is known to be a near-optimal minimizer of the ODAFTRL regret bound (McMahan, 2017, Lemma 1). However, this value is unobservable at time t. A common strategy is to play the conservative value
, where B 0 is a uniform upper bound on the unobserved b s,F terms (Joulani et al., 2016;McMahan & Streeter, 2014). In practice, this requires computing an a priori upper bound on any subgradient norm that could possibly arise and often leads to extreme over-regularization (see Sec. 7).
As a preliminary step towards fully adaptive settings of λ t , we analyze in App. H a new delayed upper bound (DUB) tuning strategy which relies only on observed b s,F terms and does not require upper bounds for future losses.
Theorem 11 (DUB regret). Fix α > 0, and, for a t,F , b t,F as in (2), consider the delayed upper bound (DUB) sequence
If ψ is nonnegative, then, for all u ∈ W, the ODAFTRL iterates w t satisfy
As desired, the DUB setting of λ t depends only on previously observed a t,F and b t,F terms and achieves optimal regret scaling with the delay period D. However, the terms a t,F , b t,F are themselves potentially loose upper bounds for the instantaneous regret at time t. In the following section, we show how the DUB regularization setting can be refined further to produce AdaHedgeD adaptive regularization.
As noted by Erven et al. (2011);de Rooij et al. (2014); Orabona (2019), the effectiveness of an adaptive regularization setting λ t that uses an upper bound on regret (such as b t,F ) relies heavily on the tightness of that bound. In practice, we want to set λ t using as tight a bound as possible. Our next result introduces a new tuning sequence that can be used with delayed feedback and is inspired by the popular AdaHedge algorithm (Erven et al., 2011). It makes use of the tightened regret analysis underlying Thm. 10 to enable tighter settings of λ t compared to DUB, while still controlling algorithm regret (see proof in App. I).
Theorem 12 (AdaHedgeD regret). Fix α > 0, and consider the delayed AdaHedge-style (AdaHedgeD) sequence
ŵt argmin w∈W F t+1 (w, λ t ) + min( gt * ht-g t-D:t * , 1) h tg t-D:t , w , and F t+1 (w, λ t ) λ t ψ(w) + g 1:t , w .
If ψ is nonnegative, then, for all u ∈ W, the ODAFTRL iterates satisfy
Remarkably, Thm. 12 yields a minimax optimal O( (D + 1)T + D) dependence on the delay parameter and nearly matches the Thm. 5 regret of the optimal constant λ tuning. Although this regret bound is identical to that in Thm. 11, in practice the λ t values produced by AdaHedgeD can be orders of magnitude smaller than those of DUB, granting additional adaptivity. We evaluate the practical implications of these λ t settings in Sec. 7.
As a final note, when ψ is bounded on U, we recommend choosing α = sup u∈U ψ(u) so that ψ(u) α ≤ 1. For negative entropy regularization ψ(u) = Related work Our AdaHedgeD δ t terms differ from standard AdaHedge increments (see, e.g., Orabona, 2019, Sec. 7.6) due to the accommodation of delay, the incorporation of optimism, and the inclusion of the final two terms in the min. These non-standard terms are central to reducing the impact of delay on our regret bounds. Prior and concurrent approaches to adaptive tuning under delay do not incorporate optimism and require an explicit upper bound on all future subgradient norms, a quantity which is often difficult to obtain or very loose (McMahan & Streeter, 2014;Joulani et al., 2016;Hsieh et al., 2020). Our optimistic algorithms, DUB and AdaHedgeD, admit comparable regret guarantees (Thms. 11 and 12) but require no prior knowledge of future subgradients.
As we have seen, optimistic hints play an important role in online learning under delay: effective hinting can counteract the increase in regret under delay. In this section, we consider the problem of choosing amongst several competing hinting strategies. We show that this problem can again be treated as a delayed online learning problem. In the following, we will call the original online learning problem the "base problem" and the learning-to-hint problem the "hinting problem."
Suppose that, at time t, we observe the hints gt of m different hinters arranged into a d × m matrix H t . Each column of H t is one hinter's best estimate of the sum of missing loss subgradients g t-D:t . Our aim is to output a sequence of combined hints h t (ω t ) H t ω t with low regret relative to the best constant combination strategy ω ∈ Ω △ m-1 in hindsight. To achieve this using delayed online learning, we make use of a convex loss function l t (ω) for the hint learner that upper bounds the base learner regret. Assumption 1 (Convex regret bound). For any hint sequence (h t ) T t=1 and u ∈ Ω, the base problem admits the regret bound
As we detail in App. K, Assump. 1 holds for all of the learning algorithms introduced in this paper. For example, by Cor. 9, if the base learner is DORM, we may choose
For any base learner satisfying Assump. 1, we choose l t (ω) = f t (H t ω) as our hinting loss, use the tuning-free DORM+ algorithm to output the combination weights ω t on each round, and provide the hint h t (ω t ) = H t ω t to the base learner. The following result, proved in App. J, shows that this learning to hint strategy performs nearly as well as the best constant hint combination strategy in restrospect. Theorem 13 (Learning to hint regret). Suppose the base problem satisfies Assump. 1 and the hinting problem is solved with DORM+ hint iterates ω t , hinting losses l t (ω) = f t (H t ω), no meta-hints for the hinting problem, and q = argmin q ′ ≥2 m 2/q ′ (q ′ -1). Then the base problem with hints h
To quantify the size of this regret bound, consider again the DORM base learner with f t (h t ) = r t q h t -t s=t-D r s q . By Lem. 26 in App. K, γ t ∞ ≤ d 1/q H t ∞ r t q for H t ∞ the maximum absolute entry of H t . Each column of H t is a sum D + 1 subgradient hints, so H t ∞ is O(D + 1). Thus, for this choice of hinter loss, the huber(ξ t , ζ t ) term is O((D + 1)foot_1 ), and the hint learner suffers only O(T 1/4 (D + 1) 3/4 ) additional regret from learning to hint. Notably, this additive regret penalty is O( (D + 1)T ) if D = O(T ) (and o( (D + 1)T ) when D = o(T )), so the learning to hint strategy of Thm. 13 preserves minimax optimal regret rates. Rakhlin & Sridharan (2013a, Sec. 4.1) propose and analyze a method to learn optimism strategies for a two-step OMD base learner. Unlike Thm. 13, the approach does not accommodate delay, and the analyzed regret is only with respect to single hinting strategies ω ∈ {e j } j∈[m] rather than combination strategies, ω ∈ △ m-1 .
We now apply the online learning techniques developed in this paper to the problem of adaptive ensembling for subseasonal forecasting. Our experiments are based on the subseasonal forecasting data of Flaspohler et al. (2021) that provides the forecasts of d = 6 machine learning and physics-based models for both temperature and precipitation at two forecast horizons: 3-4 weeks and 5-6 weeks. In operational subseasonal forecasting, feedback is delayed; models make D = 2 or 3 forecasts (depending on the forecast horizon) before receiving feedback. We use delayed, optimistic online learning to play a time-varying convex combination of input models and compete with the best input model over a year-long prediction period (T = 26 semimonthly dates). The loss function is the geographic root-mean squared error (RMSE) across 514 locations in the Western United States.
We evaluate the relative merits of the delayed online learning techniques presented by computing yearly regret and mean RMSE for the ensemble plays made by the online leaner in each year from 2011-2020. Unless otherwise specified, all online learning algorithms use the recent g hint gs , which approximates each unobserved subgradient at time t with the most recent observed subgradient g t-D-1 . See App. L for full experimental details, App. N for algorithmic details, and App. M for extended experimental results.
Competing with the best input model The primary benefit of online learning in this setting is its ability to achieve small average regret, i.e., to perform nearly as well as the best input model in the competitor set U without knowing which is best in advance. We run our three delayed online learners-DORM, DORM+, and AdaHedgeD-on all four subseasonal prediction tasks and measure their average loss.
The average yearly RMSE for the three online learning algorithms and the six input models is shown in Table 1. The DORM+ algorithm tracks the performance of the best input model for all tasks except Temp. 5-6w. All online learning
We review here additional prior work not detailed in the main paper.
We recommend the monographs of Shalev-Shwartz (2012); Orabona (2019) and the textbook of Cesa-Bianchi & Lugosi (2006) for surveys of the field of online learning and Joulani et al. (2017); McMahan (2017) for widely applicable and modular analyses of online learning algorithms.
A.2. Online learning with optimism but without delay Syrgkanis et al. (2015) analyzed optimistic FTRL and two-step variant of optimistic MD without delay. The work focuses on a particular form of optimism (using the last observed subgradient as a hint) and shows improved rates of convergence to correlated equilibria in multiplayer games. In the absence of delay, Steinhardt & Liang (2014) A.5. Online learning without delay for climate forecasting Monteleoni et al. (2011) applied the Learn-α online learning algorithm of Monteleoni & Jaakkola (2004) to the task of ensembling climate models. The authors considered historical temperature data from 20 climate models and tracked the changing sequence of which model predicts best at any given time. In this context, the algorithm used was based on a set of generalized Hidden Markov Models, in which the identity of the current best model is the hidden variable and the updates are derived as Bayesian updates. This work was extended to take into account the influence of regional neighboring locations when performing updates (McQuade & Monteleoni, 2012). These initial results demonstrated the promise of applying online learning to climate model ensembling, but both methods rely on receiving feedback without delay.
We will prove the following more general result for optimistic adaptive FTRL (OAFTRL) w t+1 = argmin w∈W g 1:t + gt+1 , w + λ t+1 ψ(w), (OAFTRL) from which Thm. 3 will follow with the choice λ t = λ for all t ≥ 1. Theorem 14 (OAFTRL regret). If ψ is nonnegative and (λ t ) t≥1 is non-decreasing, then, ∀u ∈ W, the OAFTRL iterates w t satisfy,
.
To control the drift term we employ the following lemma, proved in App. B.1, which bounds the difference between two OAFTRL optimizers with different losses but common regularizers.
Lemma 15 (OAFTRL difference bound). The OAFTRL and auxiliary OAFTRL iterates (4), w t and w * t , satisfy
Letting a = diam(W) ∈ R ∪ {∞}, we now bound each drift term summand using the Fenchel-Young inequality for dual norms and Lem. 15:
To control the auxiliary regret, we begin by invoking the OAFTRL regret bound of Orabona (2019, proof of Thm. 7.28), the nonnegativity of ψ, and the assumption that (λ t ) t≥1 is non-decreasing:
We next bound the summands in this expression in two ways. Since w * t is the minimizer of F * t , we may apply the Fenchel-Young inequality for dual norms to conclude that
Moreover, by Orabona (2019, proof of Thm. 7.28) and the fact that wt minimizes F t+1 (•, λ t ) over W,
Our collective bounds establish that
To obtain an interpretable bound on regret, we will minimize the final expression over all convex combinations g * t of g t and gt . The optimal choice is given by
For this choice, we obtain the bound
and therefore
Since g * t is arbitrary, the advertised regret bounds follow as by the strong convexity of Ft .
Summing the above inequalities and applying the Fenchel-Young inequality for dual norms, we obtain
which yields the first half of our target bound after rearrangement. The second half follows from the definition of diameter, as w tw * t ≤ diam(W).
We will prove the following more general result for adaptive SOOMD (ASOOMD) w t+1 = argmin w∈W g t + gt+1 -gt , w + λ t+1 B ψ (w, w t ) with arbitrary w 0 and g 0 = g0 = 0 (ASOOMD) from which Thm. 4 will follow with the choice λ t = λ for all t ≥ 1.
Theorem 16 (ASOOMD regret). Fix any λ T +1 ≥ 0. If each (λ t+1 -λ t )ψ is proper and differentiable, λ 0 0, and gT +1 0, then, for all u ∈ W, the ASOOMD iterates w t satisfy
λt+1 huber( g t -gt * , g t + gt+1 -gt * ) .
Proof. Fix any u ∈ W, instantiate the notation of Joulani et al. (2017, Sec. 7.2), and consider the choices
• r 1 = λ 2 ψ, r t = (λ t+1 -λ t )ψ for t ≥ 2, so that r 1:t = λ t+1 ψ for t ≥ 1,
• q t = qt + gt+1 -gt , • for t ≥ 0,
• q0 (w) = λ 1 B ψ (w, w 0 ) and qt ≡ 0 for all t ≥ 1,
Since, for each t, δ t = 0 and ℓ t is convex, the ADA-MD regret inequality of Joulani et al. (2017, Eq. (24)) and the choice
To obtain our advertised bound, we begin with the expression ( 6) and invoke the 1-strong convexity of ψ and the nonnegativity of
We will bound the final sum in this expression using two lemmas. The first is a bound on the difference between subsequent ASOOMD iterates distilled from Joulani et al. (2016, proof of Prop. 2).
Lemma 17 (ASOOMD iterate bound (Joulani et al., 2016, proof of Prop. 2)). If ψ is differentiable and 1-strongly convex with respect to • , then the ASOOMD iterates satisfy
The second, proved in App. C.1, is a general bound on g, v -λ 2 v 2 under a norm constraint on v.
Lemma 18 (Norm-constrained conjugate). For any g ∈ R d and λ, c, b > 0, sup
By Lems. 17 and 18 and the definition of a diam(W), each summand in our regret bound (7) satisfies
yielding the advertised result.
C.1. Proof of Lem. 18: Norm-constrained conjugate
By the definition of the dual norm,
We compare to the values of less constrained optimization problems to obtain the final inequalities:
D. Proof of Lem. 8: DORM is ODAFTRL and DORM + is DOOMD Our derivations will make use of several facts about ℓ p norms, summarized in the next lemma.
Lemma 19 (ℓ p norm facts). For p ∈ (1, ∞), ψ(w) = 1 2 w 2 p , and any vectors w, v ∈ R d and w0
Proof. The fact (8) follows from the chain rule as
The fact (9) follows from Lem. 18 as • q is the dual norm of • p .
We now prove each claim in turn.
Fix p ∈ (1, 2], λ > 0, and t ≥ 0. The ODAFTRL iterate with hint -h t+1 , W R d + , ψ( w) = 1 2 w 2 p , loss subgradients g ODAFTRL 1:t-D = -r 1:t-D , and regularization parameter λ takes the form
proving the claim.
Fix p ∈ (1, 2] and λ > 0, and let ( wt ) t≥0 denote the unnormalized iterates generated by DORM+ with hints h t , instantaneous regrets r t , regularization parameter λ, and hyperparameter q. For p = q/(q -1), let ( wt ) t≥0 denote the sequence generated by DOOMD with w0 = 0, hints -h t , W R d + , ψ( w) = 1 2 w 2 p , loss subgradients g DOOMD t = -r t , and regularization parameter λ. We proceed by induction to show that, for each t, wt = wt wt p-2 p .
Base case By assumption, w0 = 0 = w0 w0 p-2 p , confirming the base case.
Inductive step Fix any t ≥ 0 and assume that for each s ≤ t, ws = ws ws p-2 p . Then, by the definition of DOOMD and our ℓ p norm facts, wt+1 = argmin
, completing the inductive step.
E. Proof of Lem. 7: DORM and DORM+ are independent of λ
We will prove the following more general result, from which the stated result follows immediately.
Lemma 20 (DORM and DORM+ are independent of λ). Consider either DORM or DORM+ plays wt as a function of λ > 0, and suppose that for all time points t, the observed subgradient g t and chosen hint h t+1 only depend on λ through (w s , λ q-1 ws , g s-1 , h s ) s≤t and (w s , λ q-1 ws , g s , h s ) s≤t respectively. Then if λ q-1 w0 is independent of the choice of λ > 0, then so is λ q-1 wt for all time points t. As a result, w t ∝ λ q-1 wt is also independent of the choice of λ > 0 at all time points.
Proof. We prove each result by induction on t.
E.1. Scaled DORM iterates λ q-1 wt are independent of λ Base case By assumption, h 1 is independent of the choice of λ > 0. Hence λ q-1 w1 = (h 1 ) q-1 + is independent of λ > 0, confirming the base case.
Inductive step Fix any t ≥ 0, suppose λ q-1 ws is independent of the choice of λ > 0 for all s ≤ t, and consider λ q-1 wt+1 = (r 1:t-D + h t+1 ) q-1 + .
Since r 1:t-D depends on λ only through w s and g s for s ≤ t -D, our λ dependence assumptions for (g s , h s+1 ) s≤t ; the fact that, for each s, w s ∝ λ q-1 ws ; and our inductive hypothesis together imply that λ q-1 wt+1 is independent of λ > 0.
E.2. Scaled DORM+ iterates λ q-1 wt are independent of λ Base case By assumption, λ q-1 w0 is independent of the choice of λ > 0, confirming the base case.
Inductive step Fix any t ≥ 0 and suppose λ q-1 ws is independent of the choice of λ > 0 for all s ≤ t. Since (p -1)(q -1) = 1,
Since r t-D depends on λ only through w t-D and g t-D , our λ dependence assumptions for (g s , h s+1 ) s≤t ; the fact that, for each s ≤ t, w s ∝ λ q-1 ws ; and our inductive hypothesis together imply that λ q-1 wt+1 is independent of λ > 0.
F. Proof of Cor. 9: DORM and DORM+ regret
Fix any λ > 0 and u ∈ △ d-1 , consider the unnormalized DORM or DORM+ iterates wt , and define wt = wt wt p-2 p for each t. For either algorithm, we will bound our regret in terms of the surrogate losses lt ( w)r t , w = g t , ww, 1 g t , w t defined for w ∈ R d + . Since lt (u) = g t , uw t , lt ( wt ) = 0, and each ℓ t is convex, we have
For DORM, Lem. 8 implies that ( wt ) t≥1 are ODFTRL iterates, so the ODFTRL regret bound (Thm. 5) and the fact that ψ is 1-strongly convex with respect to
Similarly, for DORM+, Lem. 8 implies that ( wt ) t≥0 are DOOMD iterates with w0 = 0, so the DOOMD regret bound (Thm. 6) and the strong convexity of ψ yield
Since, by Lem. 7, the choice of λ does not impact the iterate sequences played by DORM and DORM+, we may take the infimum over λ > 0 in these regret bounds. The second advertised inequality comes from the identity 1 p-1 = q -1 and the norm equivalence relations v q ≤ d 1/q v ∞ and v p ≤ v 1 = 1 for v ∈ R d , as shown in Lem. 21 below. The final claim follows as
Lemma 21 (Equivalence of p-norms). If x ∈ R n and q > q ′ ≥ 1, then x q ≤ x q ′ ≤ n (1/q ′ -1/q) x q . Proof. To show x q ≤ x q ′ for q > q ′ ≥ 1, suppose without loss of generality that x q ′ = 1. Then,
For the inequality x q ′ ≤ n 1/q ′ -1/q x q , applying Hölder's inequality yields
G. Proof of Thm. 10: ODAFTRL regret
Since ODAFTRL is an instance of OAFTRL with gt+1 = h t+1 -t s=t-D+1 g s , the ODAFTRL result follows immediately from the OAFTRL regret bound, Thm. 14.
Fix any u ∈ W. By Thm. 10, ODAFTRL admits the regret bound
To control the second term in this bound, we apply the following lemma proved in App. H.1.
Lemma 22 (DUB-style tuning bound). Fix any α > 0 and any non-negative sequences
Since λ T ≤ λ T +D+1 , the result now follows by setting a t = a t,F and b t = b t,F , so that
H.1. Proof of Lem. 22: DUB-style tuning bound
We prove the claim
by induction on t.
confirming the base case.
Inductive step Now fix any t + 1 ≥ D + 2 and suppose that
for all 1 ≤ i ≤ t. We apply this inductive hypothesis to deduce that, for each 0 ≤ i ≤ t,
Now, we sum this inequality over i = 0, . . . , t, to obtain
Solving this quadratic inequality and applying the triangle inequality, we have
I. Proof of Thm. 12: AdaHedgeD Regret Fix any u ∈ W. Since the AdaHedgeD regularization sequence (λ t ) t≥1 is non-decreasing, Thm. 14 gives the regret bound
and the proof of Thm. 14 gives the upper estimate (5):
Hence, it remains to bound λ T +D+1 . Since
Solving the above quadratic inequality for λ T +D+1 and applying the triangle inequality, we find
J. Proof of Thm. 13: Learning to hint regret
We begin by bounding the hinting problem regret. Since DORM+ is used for the hinting problem, the following result is an immediate corollary of Cor. 9.
Corollary 23 (DORM+ hinting problem regret). With convex losses l t (ω) = f t (H t ω) and no meta-hints, the DORM+ hinting problem iterates ω t satisfy, for each v ∈ △ m-1 ,
where ρ t 1 γ t , ω t -γ t for γ t ∈ ∂l t (ω t ) is the instantaneous hinting problem regret.
If, in addition, q = argmin q ′ ≥2 m 2/q ′ (q ′ -1), then HintRegret T (v) ≤ (2 log 2 (m) -1)
Our next lemma, proved in App. J.1, provides an interpretable bound for each β t,∞ term in terms of the hinting problem subgradients (γ t ) t≥1 .
Lemma 24 (Hinting problem subgradient regret bound). Under the notation and assumptions of Cor. 23,
Now fix any u ∈ W. We invoke Assump. 1, Cor. 23, and Lem. 24 in turn to bound the base problem regret
t=1 huber(ξ t , ζ t )) by Lem. 24.
The advertised bound now follows from the triangle inequality.
since ω t ∈ △ m-1 . We repeatedly apply this finding in conjunction with Jensen's inequality to conclude
K. Examples: Learning to Hint with DORM+ and AdaHedgeD By Thm. 12, AdaHedgeD satisfies Assump. 1 with
By Cor. 9, DORM+ satisfies Assump. 1 with f t (h) = r t-D + h t+1h t q h -t s=t-D r s q , C 0 (u) = 0, and C 1 (u) = u 2 p 2(p-1) . These choices give rise to the hinting losses
(12)
The following lemma, proved in App. K.1, identifies subgradients of these hinting losses.
Lemma 25 (Hinting loss subgradient). If l t (ω) = ḡt q H t ωv t q for some ḡt , v t ∈ R d and H t ∈ R d×m , then
Our next lemma, proved in App. K.2, bounds the ∞-norm of this hinting loss subgradient in terms of the base problem subgradients.
Lemma 26 (Hinting loss subgradient bound). Under the assumptions and notation of Lem. 25, the subgradient γ t satisfies γ t ∞ ≤ d 1/q ḡt q H t ∞ for H t ∞ the maximum absolute entry of H t .
K.1. Proof of Lem. 25: Hinting loss subgradient
The result follows immediately from the chain rule and the following lemma.
Lemma 27 (Subgradients of p-norms). Suppose w
Proof. Since 0 is a minimizer of • p , we have u p ≥ 0 p + 0, u -0 for any u ∈ R d and hence 0 ∈ ∂ 0 p .
For p ∈ [1, ∞), by the chain rule, if w p = 0,
For p = ∞, we have that w ∞ = max j∈[n] |w j |. By the Danskin-Bertsekas Theorem (Danskin, 2012) for subdifferentials,
where conv is the convex hull operation.
K.2. Proof of Lem. 26: Hinting loss subgradient bound
Htω-t s=t-D gs q-1 q H t ω -t s=t-D g s q-1 q by Hölder's inequality for (q, p)
≤ d 1/q ḡt q H t ∞ by Lem. 21.
If q = ∞, we have
L. Experiment Details L.1. Subseasonal Forecasting Application
We apply the online learning techniques developed in this paper to the problem of adaptive ensembling for subseasonal weather forecasting. Subseasonal forecasting is the problem predicting meteorological variables, often temperature and precipitation, 2-6 weeks in advance. These mid-range forecasts are critical for managing water resources and mitigating wildfires, droughts, floods, and other extreme weather events (Hwang et al., 2019). However, the subseasonal forecasting task is notoriously difficult due to the joint influences of short-term initial conditions and long-term boundary conditions (White et al., 2017).
To improve subseasonal weather forecasting capabilities, the US Department of Reclamation launched the Sub-Seasonal Climate Forecast Rodeo competition (Nowak et al., 2020), a yearlong real-time forecasting competition for the Western United States. Our experiments are based on Flaspohler et al. (2021), a snapshot of public subseasonal model forecasts including both physics-based and machine learning models. These models were developed for the subseasonal forecasting challenge and make semimonthly forecasts for the contest period (19 October 2019 -29 September 2020).
To expand our evaluation beyond the subseasonal forecasting competition, we used the forecasts in Flaspohler et al. (2021) for analogous yearlong periods (26 semi-monthly dates starting from the last Wednesday in October) beginning in Oct. 2010 and ending in Sep. 2020. Throughout, we refer to the yearlong period beginning in Oct. 2010 -Sep. 2011 as the 2011 year and so on for each subsequent year. For each forecast date t, the models in Flaspohler et al. (2021) were trained only on data available at time t and model hyper-parameters were tuned to optimize average RMSE loss on the 3-year period preceding the forecast date t. For a few of the forecast dates, one or more models had missing forecasts; only dates for which all models have forecasts were used in evaluation.
Denote the set of d = 6 input models {M 1 , . . . M d } with labels: llr (Model1), multillr (Model2), tuned catboost (Model3), tuned cfsv2 (Model4), tuned doy (Model5) and tuned salient fri (Model6).
On each semimonthly forecast date, each model M i makes a prediction for each of two meteorological variables (cumulative precipitation and average temperature over 14 days) and two forecasting horizons (3-4 weeks and 5-6 weeks). For the 3-4 week and 5-6 horizons respectively, the forecaster experiences a delay of D = 2 and D = 3 forecasts. Each model makes a total of T = 26 semimonthly forecasts for these four tasks.
At each time t, each input model M i produces a prediction at G = 514 gridpoints in the Western United States:
t ∈ R G×d be the matrix containing each input model's predictions as columns. The true meterological outcome for task c is y c t ∈ R G . As online learning is performed for each task separately, we drop the task superscript c in the following.
At each timestep, the online learner makes a forecast prediction ŷt by playing w t ∈ W = △ d-1 , corresponding to a convex combination of the individual models: ŷt = X t w t . The learner then incurs a loss for the play w t according to the root mean squared (RMSE) error over the geography of interest:
Our objective for the subseasonal forecasting application is to produce an adaptive ensemble forecast that competes with the best input model over the yearlong period. Hence, in our evaluation, we take the competitor set to be the set of individual models U = {e i : i ∈ [d]}.
Consider the ODAFTRL variable-delay generalization w t+1 = argmin w∈W g 1:last(t+1) + h t+1 , w + λ t+1 ψ(w).
(ODAFTRL with variable delays)
Since ODAFTRL with variable delays is an instance of OAFTRL with gt+1 = h t+1 -t s=last(t+1)+1 g s , the following result follows immediately from the OAFTRL regret bound, Thm. 14. confirming the base case.
Inductive step Now fix any t + 1 ≥ 2 and suppose that
for all 1 ≤ i ≤ t. Since first(last(i + 1)) ≤ i + 1 and λ s is non-decreasing in s, we apply this inductive hypothesis to deduce that, for each 0 ≤ i ≤ t, Proof. Fix any u ∈ W, and for each t, define λ ′ t+1 = 1 α t s=1 δ s so that α(λ ′ t+1 -λ ′ t ) = δ t . Since the AdaHedgeD with variable delays regularization sequence (λ t ) t≥1 is non-decreasing, last(T ) ≤ T , and hence λ T ≤ λ ′ T +1 , Thm. 14 gives the regret bound Regret T (u) ≤ λ T ψ(u)
and the proof of Thm. 14 gives the upper estimate (5):
Our initial presentation will assume constant delay D, but we provide extensions to variable and unbounded delays in App. O.
The alternative choice ft(ht) = 1 2 ht -t s=t-D rs 2 q also bounds regret but may have size Θ((D + 1) 2 ).