Last-Iterate Guarantees and Their Failure Modes

Why the Final Iterate Needs Its Own Argument

An online procedure produces a sequence \(f_1,\ldots,f_T\), where \(f_t\) is the predictor or decision used at round \(t\). A regret bound controls the cumulative losses of this sequence relative to a comparator. Under suitable sampling assumptions, that bound can yield a small average risk across the iterates. It does not, by itself, say that the last member \(f_T\) has small risk.

The distinction matters whenever the procedure must return one predictor. A low-risk average of several iterates, or a guarantee for an iterate chosen at random, is not automatically a guarantee for the final iterate. Convexity can help with an averaged predictor, but it does not make the last iterate equal to that average or ensure that its risk is representative of the sequence.

Definition: Let \(Z\) have distribution \(P\), and let \(\ell(f;z)\) be the loss of predictor \(f\) on observation \(z\). The population risk of a fixed predictor is \(R(f)=E[\ell(f;Z)]\), assuming this expectation exists. For an online sequence \(f_1,\ldots,f_T\), its average population risk is \(T^{-1}\sum_{t=1}^T R(f_t)\); its last-iterate risk is \(R(f_T)\). If \(f_t\) is random, these quantities are random, and one may instead study their expectations.

What Online Regret Does and Does Not Give

For observations \(Z_1,\ldots,Z_T\), define the regret against a fixed comparator \(f^\star\) by

\operatorname{Reg}_T(f^\star) = \sum_{t=1}^T \ell(f_t;Z_t) - \sum_{t=1}^T \ell(f^\star;Z_t).

If the observations are independent and identically distributed, a familiar online-to-batch step relates expected losses on the observed rounds to population risks. This step needs a precise nonanticipation condition. It is not enough merely to say that \(f_t\) is selected before the outcome is observed: the information used to select it must not reveal information correlated with that round’s observation.

Proposition: Suppose \(Z_1,\ldots,Z_T\) are independent with common distribution \(P\). Suppose \(f_t\) is measurable with respect to the past observations \(Z_1,\ldots,Z_{t-1}\) and algorithmic randomness independent of all the \(Z_s\). Assume the losses are measurable and the expectations below exist. Then \(E[\ell(f_t;Z_t)]=E[R(f_t)]\).

To prove the claim, condition on the past observations and the independent algorithmic randomness used to construct \(f_t\). Call this information \(\mathcal H_t\). The predictor \(f_t\) is \(\mathcal H_t\)-measurable, and \(Z_t\) is independent of \(\mathcal H_t\) with distribution \(P\). Therefore, for each realized value of \(f_t\), integrating the loss over the conditional distribution of \(Z_t\) gives \(R(f_t)\):

E[\ell(f_t;Z_t)\mid\mathcal H_t]=R(f_t).

Taking expectations of both sides proves the result. In particular, if \(f^\star\) is a fixed comparator, then \(E[\ell(f^\star;Z_t)]=R(f^\star)\). Thus an expected regret bound \(E[\operatorname{Reg}_T(f^\star)]\le B_T\) implies

\frac{1}{T}\sum_{t=1}^T E[R(f_t)] \le R(f^\star)+\frac{B_T}{T}.

This is a bound on average expected risk. The derivation contains no term that singles out \(R(f_T)\), so it cannot establish a last-iterate guarantee without further information about the sequence.

Worked Example: Small Average Risk and Poor Final Risk

Let the decision set be \([0,1]\), let the loss be \(\ell(f;z)=f\) for every observation \(z\), and consider the distribution concentrated on a single point. The loss is convex in \(f\), and the population risk is \(R(f)=f\), whose minimum over \([0,1]\) is \(R(f^\star)=0\) at \(f^\star=0\).

For any integer \(T\ge 2\), choose \(f_t=0\) for \(1\le t<T\) and \(f_T=1\). The cumulative loss of the sequence is

\sum_{t=1}^T \ell(f_t;Z_t) = \underbrace{0+\cdots+0}_{T-1\text{ terms}}+1=1.

The comparator’s cumulative loss is zero, so the regret is exactly \(1\), and the average risk is \(T^{-1}\sum_{t=1}^T R(f_t)=1/T\). This tends to zero as \(T\) increases. But the final iterate has risk \(R(f_T)=R(1)=1\), which does not decrease at all. Convexity of the loss and a vanishing average risk therefore do not suffice for a last-iterate conclusion.

Conditions That Do Support a Last-Iterate Bound

A direct way to control the last iterate is to know that risk decreases along the sequence. This condition is stronger than a regret bound: it concerns the order of the individual risks, not just their sum.

Theorem: If \(R(f_1)\ge R(f_2)\ge\cdots\ge R(f_T)\) for every realized sequence of iterates, then \(R(f_T)\le T^{-1}\sum_{t=1}^T R(f_t)\). Consequently, if \(E[T^{-1}\sum_{t=1}^T R(f_t)]\le R^\star+\varepsilon_T\), then \(E[R(f_T)]\le R^\star+\varepsilon_T\), where \(R^\star\) is any fixed lower bound on the risks, such as the minimum population risk when it exists.

For the pathwise inequality, monotonicity gives \(R(f_T)\le R(f_t)\) for each \(t\). Summing these \(T\) inequalities yields \(T R(f_T)\le\sum_{t=1}^T R(f_t)\); division by \(T\) proves the claim. Taking expectations preserves the inequality, which proves the stated consequence. The condition is sufficient, not necessary, and it must actually hold for the risks under consideration.

Worked Example: A Monotone Risk Sequence

Take the decision set \([0,1]\), the population risk \(R(f)=f^2\), and the sequence \(f_t=1/t\). The risk is nonincreasing because \(R(f_t)=1/t^2\). The final risk is \(R(f_T)=1/T^2\), and the average risk is

\frac{1}{T}\sum_{t=1}^T R(f_t) = \frac{1}{T}\sum_{t=1}^T\frac{1}{t^2} \le \frac{2}{T}.

For the inequality, the decreasing function \(x^{-2}\) gives \(\sum_{t=1}^T t^{-2}\le 1+\int_1^\infty x^{-2}\,dx=2\). In this example, the monotonicity theorem also gives \(1/T^2\le T^{-1}\sum_{t=1}^T t^{-2}\). The example illustrates a setting where an average-risk bound can control the last risk because there is additional structure, not because the average bound alone has that implication.

A second useful condition is asymptotic rather than finite-sample. Convergence of the average risks can identify the limiting risk if the individual risks themselves converge. This does not supply a finite-\(T\) bound unless a rate of convergence is separately available.

Proposition: Let \(a_t=E[R(f_t)]-R^\star\), where \(R^\star\) is a lower bound on the population risk. If \(a_t\) converges to a finite limit \(a\) and \(T^{-1}\sum_{t=1}^T a_t\to 0\), then \(a=0\), and hence \(E[R(f_T)]\to R^\star\).

Because \(a_t\to a\), their arithmetic means converge to the same limit. Explicitly, fix \(\delta>0\) and choose \(N\) such that \(|a_t-a|<\delta\) for \(t\ge N\). Then

\left|\frac{1}{T}\sum_{t=1}^T a_t-a\right| \le \frac{1}{T}\sum_{t=1}^{N-1}|a_t-a| + \frac{1}{T}\sum_{t=N}^T|a_t-a| \le \frac{1}{T}\sum_{t=1}^{N-1}|a_t-a|+\delta.

The first term tends to zero because it is a fixed finite sum divided by \(T\). Since \(\delta\) is arbitrary, the means converge to \(a\). By assumption they converge to zero, so \(a=0\). This proves the proposition. In applications, convergence of the risks may follow from convergence of the iterates and continuity of \(R\), but those properties must be established for the particular procedure and model.

When the Sampling Assumption Fails

The independence condition in the online-to-batch proposition is substantive. If the information used to choose \(f_t\) contains advance information correlated with \(Z_t\), then conditioning on that information changes the distribution of \(Z_t\). The conditional expected observed loss need not equal the population risk of the selected predictor.

Worked Example: Correlated Advance Information

Let \(Z\) be Bernoulli with \(P(Z=0)=P(Z=1)=1/2\). Use the convex squared loss \(\ell(f;z)=(f-z)^2\), with predictors \(f\in[0,1]\). If the procedure sees \(Z\) before choosing its predictor and sets \(f=Z\), its observed loss is always \((Z-Z)^2=0\).

For a fixed predictor \(f\), however, the population risk is

R(f) = \frac{1}{2}f^2+\frac{1}{2}(f-1)^2 = \left(f-\frac{1}{2}\right)^2+\frac{1}{4}.

The selected predictor is \(0\) or \(1\), each with probability \(1/2\), and either has population risk \(1/2\). Thus \(E[\ell(f;Z)]=0\), while \(E[R(f)]=1/2\). The equality fails because the selected predictor and the observation are dependent. This is why “chosen before the loss is recorded” is not enough: the predictor must be selected using information independent of the current observation, or a different conditional-risk argument must be supplied.

Common Mistake

A common but incorrect argument is: “The average risk is small, so the last iterate must be close to the average risk.” An average constrains the sum, not the position of a large term within that sum. The convex example above has average risk \(1/T\) and last risk \(1\). The correction is to add and verify a property that links the final term to the rest, such as nonincreasing risk, convergence of the risks in an asymptotic argument, or a direct bound on the last iterate. Convexity alone does not provide that link.

Key takeaway: Online regret can yield an average population-risk guarantee under an appropriate sampling condition. A last-iterate guarantee requires additional control of the sequence; it does not follow from average risk or convexity alone.

Check Your Understanding

Use the definitions and conditions above to answer these questions.

In the convex counterexample, what are the cumulative regret, average risk, and final risk for a general \(T\ge 2\)?
Why does measurability of \(f_t\) with respect to past observations and independent algorithmic randomness imply \(E[\ell(f_t;Z_t)\mid\mathcal H_t]=R(f_t)\)?
Suppose the risks are nonincreasing. State the pathwise inequality that bounds the final risk by the average risk, and explain why it holds.
Can an average-risk guarantee alone rule out a high-risk final iterate? Give the construction that supports your answer.
In the correlated-information example, compute \(R(0)\) and \(R(1)\), and explain why the observed loss is nevertheless zero.