Learning-Rate Selection Without a Known Horizon

Why a Doubling Schedule?

A learning rate for Hedge is often chosen using the number of rounds in advance. In many sequential problems that number is not available: data collection may stop when a budget is exhausted, a study ends, or an external decision is made. Choosing a very small learning rate to protect against a long run can make early predictions unnecessarily slow to adapt. A doubling schedule resolves this tension by restarting the expert algorithm at predetermined times, using an interval-specific learning rate that depends only on the interval’s planned length.

The restart has a cost in the analysis. A single fixed-horizon regret guarantee applies within one interval, not automatically to the entire run. The total guarantee must add the regret bounds from every interval reached before stopping. The geometric growth of the intervals keeps that sum controlled.

Protocol and Algorithm

There are countably many experts, indexed by \(i\), and a fixed prior distribution \(\pi=(\pi_i)\), where \(\pi_i>0\) and \(\sum_i\pi_i=1\). On round \(t\), expert \(i\) incurs loss \(\ell_{t,i}\in[0,1]\). The learner observes the experts’ losses and predicts with a probability distribution over them; its loss is the corresponding weighted average. The regret to expert \(i\) through round \(T\) is the learner’s cumulative loss minus \(\sum_{t=1}^T\ell_{t,i}\). All guarantees below hold for every sequence of expert losses in \([0,1]\), so they do not require a probabilistic model for the losses.

The displayed rate uses the comparator’s prior weight. It is a way to state the guarantee for each expert; the algorithm itself must be specified without knowing which expert will later be used as comparator. One implementation runs a grid of learning rates with a suitable prior over that grid. Alternatively, for a finite expert set, a learning rate can be selected using the prior’s entropy or a common upper bound on the comparator complexity. The result below describes the comparator-dependent Hedge guarantee in each interval; it does not imply that the learner may change its learning rate after learning the comparator.

For clarity, the basic interval guarantee is first stated for Hedge initialized at \(\pi\) with a fixed rate \(\eta>0\). On local round \(s\), its distribution is proportional to \(\pi_i\exp(-\eta\sum_{r<s}\ell_{r,i})\). With countably many experts, the normalization is finite and positive because the prior sums to one and all cumulative losses are nonnegative.

The One-Interval Bound

The key inequality is Hoeffding’s lemma: if a random variable \(X\) takes values in \([0,1]\), then for every real \(s\), \( \log E[\exp(s(X-E[X]))]\leq s^2/8. \) One short derivation makes the constant explicit. Let \(\psi(s)=\log E[\exp(s(X-E[X]))]\). Since \(X\) is bounded, differentiation under the expectation is valid on every bounded interval of \(s\). Then \(\psi(0)=\psi'(0)=0\), and \(\psi''(s)\) is the variance of \(X\) under the exponentially tilted distribution. Any random variable in \([0,1]\) has variance at most \(1/4\): its variance is no greater than its mean squared distance from \(1/2\), which is at most \(1/4\). Thus \(\psi''(s)\leq1/4\). Integrating twice from zero, for either sign of \(s\), gives \(\psi(s)\leq s^2/8\).

To prove the lemma, let \(Z_s=\sum_i\pi_i\exp(-\eta\sum_{r=1}^s\ell_{r,i})\), with \(Z_0=1\). Write \(q_s\) for Hedge’s distribution just before loss round \(s\). Applying Hoeffding’s lemma to the losses under \(q_s\) gives \( \log(Z_s/Z_{s-1})=\log\sum_i q_{s,i}\exp(-\eta\ell_{s,i})\leq-\eta\sum_iq_{s,i}\ell_{s,i}+\eta^2/8. \) Summing this inequality over the interval yields \(\log Z_m\leq-\eta L_{\mathrm{alg}}+\eta^2m/8\), where \(L_{\mathrm{alg}}\) is Hedge’s cumulative loss there. On the other hand, the \(i\)-th term in \(Z_m\) gives \(Z_m\geq\pi_i\exp(-\eta L_i)\), where \(L_i\) is expert \(i\)’s interval loss. Combining the two bounds on \(\log Z_m\), then rearranging, proves \( L_{\mathrm{alg}}-L_i\leq\log(1/\pi_i)/\eta+\eta m/8. \) This argument uses only nonnegative summands in the countable partition function, so the comparison with any particular expert remains valid. \(\square\)

Summing Regret Across Restarts

For a given expert \(i\), write \(K=\log(1/\pi_i)\). If \(K>0\), use the rate \(\eta_j=\sqrt{8K/2^j}\) in interval \(I_j\). If stopping occurs after \(m_j\leq2^j\) rounds of that interval, the one-interval lemma gives \( R_{i,j}\leq K/\eta_j+\eta_jm_j/8\leq K/\eta_j+\eta_j2^j/8=\sqrt{K2^j/2}. \) Here \(R_{i,j}\) is the learner’s loss minus expert \(i\)’s loss within \(I_j\). The last equality follows because each of the two terms is \(\sqrt{K2^j/8}\).

Proof. Let \(J\) be the index of the interval containing round \(T\). Then \(2^J\leq T\), since the interval starts at round \(2^J\). Regret adds over the disjoint intervals, and the same comparator \(i\) is used in each one. Therefore

The strict inequality follows by dropping the minus one and using \(2^{(J+1)/2}=\sqrt2\sqrt{2^J}\). If \(K=0\), then \(\pi_i=1\); all other experts have zero weight, so Hedge always predicts with expert \(i\) and incurs zero regret. This handles the case excluded when choosing a positive learning rate. \(\square\)

The theorem does not assume that the learner knows \(T\). The interval boundaries and rates are fixed in advance, and the proof applies to whichever interval contains the eventual stopping round. In particular, if stopping is determined by the observed history, the same pathwise guarantee applies to the realized finite sequence.

Common Pitfall: Forgetting the Earlier Intervals

A tempting but incorrect argument is to select the learning rate for the interval containing \(T\), apply its regret bound, and call that a bound for the whole run. That calculation omits losses and regret from every interval before the last one. A related error is to apply one potential argument across all rounds as if the weights had never been reset. After a reset, the potential at the start of the new interval is based on \(\pi\), not on the weights at the end of the preceding interval; a single uninterrupted potential calculation no longer describes the algorithm.

The correction is to bound each interval against the same fixed expert and add those bounds. Because the planned lengths grow geometrically, the sum of their square roots is controlled by the square root of the last planned length. This is why the cost of not knowing the horizon is a constant factor in the regret bound rather than a factor that grows with the number of restarts.