Transductive and Learning-Augmented Online Regression

## Abstract

Abstract Motivated by the predictable nature of real-life in data streams, we study online regression when the learner has access to predictions about future examples. In the extreme case, called transductive online learning, the sequence of examples is revealed to the learner before the game begins. For this setting, we fully characterize the minimax expected regret in terms of the fat-shattering dimension, establishing a separation between transductive online regression and (adversarial) online regression. Then, we generalize this setting by allowing for noisy or imperfect predictions about future examples. Using our results for the transductive online setting, we develop an online learner whose minimax expected regret matches the worst-case regret, improves smoothly with prediction quality, and significantly outperforms the worst-case regret when future example predictions are precise, achieving performance similar to the transductive online learner. This enables learnability for previously unlearnable classes under predictable examples, aligning with the broader learning-augmented model paradigm.

## 1 Introduction

Online learning is framed as a sequential game between a learner and an adversary.
In each round, the learner first makes a prediction after which the adversary evaluates the learner’s prediction, typically by producing a ground-truth label.
In contrast to the classical batch learning setting, where one places distributional assumptions on the data-generating process, in online learning, we place no assumptions on the data-generating process, even allowing the adversary to be adaptive to the past actions of the learner.
Due to its level of generality, online learning has received substantial attention over the years.
While online learning literature is too vast to review comprehensively, we include a detailed discussion of the most relevant works in [Section 1.2](https://arxiv.org/html/2510.03917v1#S1.SS2).

In this work, we focus on online *regression*, where the learner’s predictions are measured via a well-structured loss function $\ell(\cdot,\cdot)$, e.g., the $\ell_{1}$-loss $\ell(y,\widehat{y})=|y-\widehat{y}|$.
The online regression problem is formally defined as the following $T$-round interactions between the learner ${\mathcal{A}}$ and the adversary: In each round $t\in[T]$, the adversary picks a labeled example $(x_{t},y_{t})$ from ${\mathcal{X}}\times{\mathcal{Y}}$ and reveals the example $x_{t}$ to the learner.
The learner then predicts $\widehat{y}_{t}$ based on historical observations $(x_{1},y_{1}),\ldots,(x_{t-1},y_{t-1})$ and the current example $x_{t}$.
Finally, the adversary reveals the actual label $y_{t}$ to the learner, and the learner suffers loss $\ell(\widehat{y}_{t},y_{t})$.
Given a function class ${\mathcal{F}}\subset{\mathcal{Y}}^{{\mathcal{X}}}$, the goal of the learner is to minimize the minimax expected regret

$$ $R_{{\mathcal{A}}}(T,{\mathcal{F}}):=\sup_{(x_{1},\ldots,x_{T})\subset{{\mathcal{X}}}}\sup_{(y_{1},\ldots,y_{T})\subset{{\mathcal{Y}}}}\left(\mathbb{E}_{{\mathcal{A}}}\left[\sum_{t=1}^{T}\ell({\mathcal{A}}_{t},y_{t})\right]-\inf_{f\in{\mathcal{F}}}\sum_{t=1}^{T}\ell(f(x_{t}),y_{t})\right),$ $$

which is defined as the difference between the cumulative loss of the learner ${\mathcal{A}}$ and the cumulative loss of the best function in ${\mathcal{F}}$.
We say that a function class ${\mathcal{F}}$ is online learnable if $\inf_{{\mathcal{A}}}R_{{\mathcal{A}}}(T,{\mathcal{F}})=o(T)$, that is, there exists a learner who achieves average regret that is sublinear in $T$ for all possible choices of labeled examples given by the adversary.

Rakhlin et al. (2015a) showed that a combinatorial parameter called the sequential fat-shattering dimension fully characterizes learnability – a class is online learnable if and only if its sequential fat shattering dimension is finite. However, this result is discouraging given the restrictive nature of the sequential fat shattering dimension. For instance, even simple function classes, such as functions with bounded variation in $[0,1]$, have infinite sequential fat-shattering dimensions, which means that they are not online learnable.
This challenge arises from worst-case scenarios, as the adversary is allowed to choose any labeled example sequences, potentially adapting to the learner’s output.
In practice, however, data streams often exhibit predictable patterns, so the worst-case assumption can be relaxed (Raman and Tewari, 2024).
Given this intuition, we investigate online regression with various levels of prior knowledge about the sequence of examples $x_{1},\ldots,x_{T}$.
As motivation, consider the following example.

###### Example 1.1 .

A smart building management system models energy consumption $y_{t}\in\mathbb{R}$ as a function of features $x_{t}\in\mathbb{R}^{d}$, such as temperature and occupancy count, to estimate daily energy usage.
If predicted consumption significantly deviates from actual consumption $y_{t}$, either underestimation causes energy shortages or overestimation wastes resources, incurring a loss $\ell(y_{t},\widehat{y}_{t})$.

In practice, the system has prior knowledge of daily occupancy schedules and weather forecasts.
However, it does not know exactly the energy consumption $y_{t}$ due to variable factors such as occupant behavior, equipment usage, or unexpected events.
Thus, it predicts energy consumption based on its knowledge of the sequence of examples $x_{1}\ldots x_{T}$, which forms an online regression problem.

Real-world scenarios, like the example above, have inspired recent research on learning-augmented algorithms (Mitzenmacher and Vassilvitskii, 2020), which enhances the algorithm’s performance using additional information about the problem instance given by machine-learned predictions.
For example, machine-learned predictions have been utilized to achieve more efficient data structures (Mitzenmacher, 2018; Lin et al., 2022; Fu et al., 2025), algorithms with faster runtimes (Dinitz et al., 2021; Chen et al., 2022c; Davies et al., 2023), mechanisms with better accuracy-privacy tradeoffs (Khodak et al., 2023), streaming algorithms with better accuracy-space tradeoffs (Hsu et al., 2019; Indyk et al., 2019; Jiang et al., 2020; Chen et al., 2022b, a; Li et al., 2023), and accuracy guarantees beyond NP hardness (Braverman et al., 2025; Ergun et al., 2022; Nguyen et al., 2023; Karthik C. S. et al., 2025).
A more detailed summary is deferred to [Section 1.2](https://arxiv.org/html/2510.03917v1#S1.SS2).
Motivated by work on learning-augmented algorithms, in this paper, we study the following question:

*Can predictions about the future examples be used to get better-than-worst-case regret bounds for online regression?*

Rakhlin and Sridharan (2013) studied this question in the context of online linear optimization.
Specifically if the sequence encountered by the learner is described well by a known “predictable process”, their algorithms enjoy tighter bounds as compared to the typical worst case bounds.
Additionally, their methods achieved the usual worst-case regret bounds if the sequence is not benign.
More recently, Raman and Tewari (2024) studied this question in the context of online *classification*.
Their proposed algorithm performs optimally when the predictions are nearly exact, while ensuring the worst-case guarantee.
Furthermore, they characterize the expected number of mistakes as a function of the quality of predictions, interpolating between instance and worst-case optimality.
In this work, we study this same question in the more general setting of online (non-parametric) *regression*.
We demonstrate that learning-augmented algorithms achieve better minimax expected regret compared to the online learner under worst-case scenarios.
We consider two settings where we apply the learning-augmented framework: the transductive online regression setting where the learner has full knowledge about the sequence of examples; and the online regression with predictions setting, where the learner has access to a Predictor for future examples.

###### Example 1.1 .

#### Transductive online learning.

In transductive online learning, initially introduced by Ben-David et al. (1997) and recently studied by Hanneke et al. (2024a), the entire sequence of examples $x_{1},\ldots,x_{T}$ picked by the adversary is revealed to the learner before the game starts. In each round $t\in[T]$, the learner makes a prediction $\widehat{y}_{t}$ using the information from $(x_{1},y_{1}),\ldots,(x_{t},y_{t}),x_{t+1},\ldots,x_{T}$.
Lastly, the adversary reveals the actual label $y_{t}$ to the learner, and the learner suffers a loss.
In many situations, however, we do not have full access to the examples $x_{1},\ldots,x_{T}$. This motivates a generalization where the learner has access to potentially noisy predictions of future examples.

#### Online regression with predictions.

In online learning with predictions (Raman and Tewari, 2024), the learner has access to a Predictor ${\mathcal{P}}$, which observes the past examples $x_{1},\ldots,x_{t}$ and predicts future examples.
In each round $t\in[T]$, the learner ${\mathcal{A}}$ queries the Predictor and receives potentially noisy predictions $\widehat{x}_{t+1},\ldots,\widehat{x}_{T}$. The learner ${\mathcal{A}}$ then makes a prediction $\widehat{y}_{t}$ based on the current example $x_{t}$, the predictions $\widehat{x_{t+1}},\ldots,\widehat{x}_{t}$, and the previous labeled-examples $(x_{1},y_{1}),\ldots(x_{t-1},y_{t-1})$.
We allow the Predictor to be adaptive, which means that can change its predictions about future examples based on the current example $x_{t}.$
We quantify the performance of a Predictor ${\mathcal{P}}$ using two metrics: the zero-one metric that counts the number of times its prediction of the next example is wrong and the $\varepsilon$-ball metric that counts the number of times its prediction of the next example is sufficiently far away from the true next example with respect to some metric of interest.

### 1.1 Our Results

In this work, we seek to understand how the regret scales as a function of the quality of the predictions.
In particular, under what circumstances can we do better than the worst-case regret?
Motivated by this question, we provide the following result for transductive online regression.

###### Theorem 1.2 (Transductive online regression, informal statement for Theorem 3.3 ) .

A function class ${\mathcal{F}}\subseteq[0,1]^{\mathcal{X}}$ is transductive online learnable under the $\ell_{1}$-loss if and only if its fat-shattering dimension is finite.

This result establishes a separation between transductive online regression and online regression for function classes with finite fat-shattering dimensions but infinite sequential fat-shattering dimensions, e.g., the class of functions with bounded variations.
Specifically, any function classes with infinite sequential fat-shattering dimension is not online learnable due to the lower bound in Rakhlin et al. (2015a), but can be transductive online learnable if it has finite fat-shattering dimension. As a corollary of [Theorem 1.2](https://arxiv.org/html/2510.03917v1#S1.Thmtheorem2), we get that while the class of functions with $V$-bounded variations is not online learning, it is transductive online learnable with minimax regret scaling like $\tilde{O}({\sqrt{VT}}).$

Motivated by scenarios where having full access to $x_{1},\dots,x_{T}$ is unrealistic, our second result studies online regression with predictions, where instead of having access to $x_{1},\dots,x_{T}$, the learner has black-box access to a Predictor ${\mathcal{P}}$ and a transductive online learner ${\mathcal{B}}$.
In this more general setting, we give an online transductive learner whose minimax expected regret can be written a function of the mistake-bound of ${\mathcal{P}}$ and interpolates between instance and worst-case optimality depending on the quality of ${\mathcal{P}}$’s predictions, (see [Theorem 4.1](https://arxiv.org/html/2510.03917v1#S4.Thmtheorem1) for a precise statement).
Our learning algorithm is *consistent* in that it has the same minimax expected regret as ${\mathcal{B}}$ when the predictions are exact, and is *robust* in that it never has worse regret than the minimax optimal regret in the fully adversarial online learning model.

We measure the mistake-bound of ${\mathcal{P}}$ with respect to two different metrics.
The first is the *zero-one metric*, which measures the expected number of incorrect predictions $\widehat{x}_{t}\neq x_{t}$.
As examples are often noisy in real-world applications, perfectly predicting the next example is unlikely.
As a result, our second metric is the *$\varepsilon$-ball metric*, which measures the expected number of predictions that are outside of the $\varepsilon$-ball of the actual example.
To get a sense of how the minimax expected regret of our learner scales with the mistake-bound of our Predictor, [Corollary 1.3](https://arxiv.org/html/2510.03917v1#S1.Thmtheorem3) provides upper bounds on the minimax expected regret of our online learner for both mistake-bound guarantees for the Predictor.
Here, we omit the polylogarithmic factors in $T$.

###### Corollary 1.3 (Informal statement for online regression with predictions) .

Given a Predictor ${\mathcal{P}}$ and a transductive online learner ${\mathcal{B}}$ with minimax expected regret $R_{{\mathcal{B}}}^{\mathbf{tr}}\left(T,{\mathcal{F}}\right)$:

- •
If ${\mathcal{P}}$ makes $\mathcal{O}\left(T^{p}\right)$ mistakes under the zero-one metric, then for any function class ${\mathcal{F}}\subseteq[0,1]^{{\mathcal{X}}}$, there is an online learner ${\mathcal{A}}$ whose minimax expected regret under the $\ell_{1}$ loss is at most
$\mathcal{O}\left(T^{p}\right)R_{{\mathcal{B}}}^{\mathbf{tr}}\left(T^{1-p},{\mathcal{F}}\right)+\sqrt{T\log^{2}T}.$
- •
If ${\mathcal{P}}$ makes $M_{{\mathcal{P}}}(\varepsilon,x_{1:T})=\mathcal{O}\left(\frac{T^{p}}{\varepsilon^{q}}\right)$ mistakes under the $\varepsilon$-ball metric, then for any $L_{\mathbf{hyp}}$-Lipschitz function class ${\mathcal{F}}\subseteq[0,1]^{{\mathcal{X}}}$, there is an online learner ${\mathcal{A}}$ whose minimax expected regret under the $\ell_{1}$ loss is at most
$\inf_{\varepsilon>0}\left\{\mathcal{O}\left(\frac{T^{p}}{\varepsilon^{q}}\right)R_{{\mathcal{B}}}^{\mathbf{tr}}\left(\varepsilon^{q}T^{1-p},{\mathcal{F}}\right)+\varepsilon L_{\mathbf{hyp}}\cdot T+\sqrt{T\log^{2}T}\right\}.$

[Corollary 1.3](https://arxiv.org/html/2510.03917v1#S1.Thmtheorem3) is a combination of [Theorem 4.10](https://arxiv.org/html/2510.03917v1#S4.Thmtheorem10) (minimax expected regret under the zero-one metric) and [Theorem 4.12](https://arxiv.org/html/2510.03917v1#S4.Thmtheorem12) (minimax expected regret under the $\varepsilon$-ball metric).
As a concrete example, we show that the function class with bounded variation is online learnable if the sequence of examples is predictable
under the zero-one metric, that is, the number of mistakes of the Predictor grows sublinearly with the time horizon (see [Corollary 4.13](https://arxiv.org/html/2510.03917v1#S4.Thmtheorem13)).
In addition, we identify a subclass of functions with bounded variation and a large Lipschitz constant (see [Definition 4.14](https://arxiv.org/html/2510.03917v1#S4.Thmtheorem14)), such that it is not online learnable under the worst case, but online learnable given a Predictor with small error rate under the $\varepsilon$-ball metric.
These results establish a separation between online regression with predictions and online regression for various function classes.
We note that our results answer the open question in Section 4 of Raman and Tewari (2024) about the learnability of online regression under general measures of predictability.

###### Theorem 1.2 (Transductive online regression, informal statement for Theorem 3.3 ) .

###### Corollary 1.3 (Informal statement for online regression with predictions) .

### 1.2 Related Work

In this section, we present the related work.

#### Algorithms with predictions.

Machine learning models have achieved remarkable success across a wide range of application domains, often delivering predictions and decisions of impressive quality in practice.
However, despite these empirical advances, such models rarely come with provably correct worst-case guarantees, and can result in embarrassingly inaccurate predictions when generalizing to previously unseen distributions (Szegedy et al., 2014).
Learning-augmented algorithms (Mitzenmacher and Vassilvitskii, 2020) combine predictive models with principled algorithmic design to achieve provable worst-case guarantees while still benefiting from the strengths of data-driven approaches.
The line of work most relevant to our setting is the direction of online algorithms with predictions, which achieve better performance than information-theoretic limits (Anand et al., 2021, 2022; Khodak et al., 2022; Antoniadis et al., 2023b).
Specific applications include ski rental (Purohit et al., 2018; Gollapudi and Panigrahi, 2019; Anand et al., 2020; Wang et al., 2020; Wei and Zhang, 2020; Shin et al., 2023), scheduling, caching, and paging (Lattanzi et al., 2020; Lykouris and Vassilvitskii, 2021; Scully et al., 2022), covering and packing (Bamas et al., 2020; Im et al., 2021; Grigorescu et al., 2022, 2025), various geometric and graph objectives (Aamand et al., 2022; Almanza et al., 2021; Azar et al., 2022; Jiang et al., 2022; Antoniadis et al., 2023a).
More recently, Eliás et al. (2024) proposed a model in which the predictor can learn and adjust its predictions dynamically based on the data observed during execution.
This approach differs from earlier work on learning-augmented online algorithms, where predictions are generated by machine learning models trained solely on historical data and remain fixed, lacking adaptability to the current input sequence.
Eliás et al. (2024) examined several fundamental problems, such as caching and scheduling, demonstrating that carefully designed adaptive predictors can yield stronger performance guarantees.
We adopt a similar model established by (Raman and Tewari, 2024), where we assume our algorithms have black-box access to an external mechanism that produces predictions about the examples, which evolve in response to the actual data encountered by the learning algorithm.

#### Online classification.

Motivated by applications such as spam filtering, image recognition, and language modeling, online classification has a rich history in statistical learning theory.
Building on foundational concepts like the VC dimension (Vapnik and Chervonenkis, 1971) that characterize learnability in batch settings, (Littlestone, 1987) introduced the Littlestone dimension to precisely characterizes which binary hypothesis classes are online learnable in the realizable setting.
This was subsequently extended to agnostic learning (Ben-David et al., 2009) and multiclass settings with finite and unbounded label spaces (Daniely et al., 2011; Hanneke et al., 2023a).
More recently, (Hanneke et al., 2023b, 2024b) developed the theory of transductive online classification, providing performance guarantees for both binary and multiclass problems where the learner has access to the entire unlabeled input sequence before making predictions.

Unfortunately, the Littlestone dimension is often regarded as an impossibility result, as it rules out even simple classes such as threshold functions for online learning.
This barrier is due to worst-case analyses where an adversary can select any sequence of labeled examples, potentially adapting future choices based on the previous learner choices.
In practice, however, many data sequences are far from adversarial and often exhibit regularity or structure that worst-case models fail to capture.
For example, when predicting short-term stock price movements, prices often follow temporal trends and correlations that predictive models can exploit.
Motivated by beyond-worst-case analyses of such scenarios, Raman and Tewari (2024) explored online classification with predictive advice, showing that learning-augmented algorithms can achieve improved performance given predictions about the examples that need to be classified, complementing transductive frameworks.

#### Online regression.

While online regression extends online classification to sequential prediction with continuous outcomes, analyzing the complexity of the corresponding real-valued function classes often requires different tools than in classification.
The fat-shattering dimension (Alon et al., 1997) generalizes the VC dimension to continuous-valued functions and plays a key role in bounding sample complexity and learnability.
Data-dependent capacity measures such as Rademacher complexity (Bartlett and Mendelson, 2002) have been adapted to online settings through sequential Rademacher complexity and sequential fat-shattering dimension (Rakhlin et al., 2010, 2015a), capturing the difficulty of learning under adversarial data streams.
More recent advances use generic chaining and majorizing measures to tightly control worst-case sequential Rademacher complexity (Block et al., 2021), establishing sharp uniform convergence and bounds that are robust to adversarial data.
However, these results share a common limitation: they provide worst-case guarantees that often fail to capture improved performance on “easy” or structured data sequences.

#### Smoothed Online Learning.

In addition to auxiliary predictions, *smoothed analysis* is another framework for studying beyond-worst-case guarantees (Spielman and Teng, 2004, 2009). In the context of online regression, smoothed analysis involves placing some distributional assumptions on the data generation process. In particular, in each round, a smoothed adversary must choose and sample from a distribution belonging to a sufficiently anti-concentrated family of distributions. This allows one to go beyond the worst-case results in the fully adversarial model, where the adversary can pick any sequence of examples.

In the past couple years, there have been flurry papers studying online learnability under a smoothed adversary (Rakhlin et al., 2011; Haghtalab, 2018; Haghtalab et al., 2020; Block et al., 2022; Haghtalab et al., 2022; Blanchard, 2025; Blanchard and Kpotufe, 2025). We review the most relevant ones here. In the context of binary classification, Haghtalab (2018) and Haghtalab et al. (2020) show that this restriction on the adversary is enough for the VC dimension of a binary hypothesis class to be sufficient for online learnability. Block et al. (2022) and Blanchard (2025) extend these results to online regression and prove an analogous result – under a smoothed adversary, the fat-shattering dimension is sufficient for online learnability. In both cases, these results show that by placing some distributional assumptions on the input, online learning becomes as easy as batch learning. In this paper, we show a similar phenomena without needing any distributional assumptions on the examples, but given predictions about the future examples we will need to make predictions about.

## 2 Preliminaries

Let ${\mathcal{X}}$ denote the example space, let ${\mathcal{Y}}=[0,1]$ denote the label space, let ${\mathcal{F}}\subset{\mathcal{Y}}^{{\mathcal{X}}}$ denote the function class, and let $\ell$ be the loss function.
Note that in [Section 1.1](https://arxiv.org/html/2510.03917v1#S1.SS1), we present the results under the $\ell_{1}$-loss function $\ell(\widehat{y},y)=|\widehat{y}-y|$, we consider a more general notion of convex and $L_{\mathbf{los}}$-Lipschitz loss function in the following sections.
Let $T$ denote the length of the sequence of examples.
Let $z_{1:T}$ denote the sequence of items $z_{1},\ldots,z_{T}$.
Let $\tilde{\mathcal{O}}\left(f\right)=f\cdot\operatorname*{polylog}(f)$.
Given some event ${\mathcal{E}}$, let ${\bf 1}_{{\mathcal{E}}}$ be the indicator function, which is $1$ if ${\mathcal{E}}$ holds, and 0 otherwise.
Next, we introduce the formal definitions of the minimax expected regret and important complexity measures.

### 2.1 Online Learning

In the standard online learning setting, the game proceeds over $T$ rounds of interactions between the learner ${\mathcal{A}}$ and the adversary: In each round $t\in[T]$, the adversary picks a labeled example $(x_{t},y_{t})\in{\mathcal{X}}\times{\mathcal{Y}}$ and reveals $x_{t}$ to the learner. The learner then produces a prediction $\widehat{y}_{t}$ and receives the true label $y_{t}$.
Given a function class ${\mathcal{F}}\subset{\mathcal{Y}}^{{\mathcal{X}}}$, the learner aims to minimize the expected regret,

$$ $R^{\mathbf{ol}}_{\mathcal{A}}(T,{\mathcal{F}}):=\sup_{x_{1:T}\in\mathcal{X}^{T}}\sup_{y_{1:T}\in\mathcal{Y}^{T}}\left(\mathbb{E}\left[\sum_{t=1}^{T}\left|\mathcal{A}\left(x_{t}\right)-y_{t}\right|\right]-\inf_{h\in{\mathcal{F}}}\sum_{t=1}^{T}\left|h\left(x_{t}\right)-y_{t}\right|\right),$ $$

where the expectation is over randomness of the learner.
We say that a function class ${\mathcal{F}}$ is online learnable if $\inf_{\mathcal{A}}R^{\mathbf{ol}}_{\mathcal{A}}(T,{\mathcal{F}})=o(T)$.

#### Sequential fat-shattering dimension.

The online learnability is characterized by the sequential fat-shattering dimension, a variant of the fat-shattering dimension (see [Definition 2.4](https://arxiv.org/html/2510.03917v1#S2.Thmtheorem4)) in the online setting, which captures the sequential dependence of the interaction between the adversary and the online learner.
To understand this dimension, we begin with the notion of the Littlestone tree (Littlestone, 1987; Rakhlin and Sridharan, 2014; Rakhlin et al., 2015a; Raman and Tewari, 2024), which encrypts the sequentially dependence of the examples.

###### Definition 2.1 (The Littlestone tree, (Littlestone, 1987 ) ) .

A ${\mathcal{X}}$-valued Littlestone tree $x$ of depth $T$ is a complete binary tree of depth $T$, where the nodes are labeled by examples $x\in{\mathcal{X}}$ and the outgoing edges to the left and right of the nodes are labeled by $-1$ and $1$ respectively.
Given a binary string $\sigma=(\sigma_{1},\ldots,\sigma_{T})\in\{-1,1\}^{T}$ of depth $T$, we define a path $x(\sigma)$ induced by $\sigma$ to be $\{(x_{i},\sigma_{i})\}_{i=1}^{T}$, where $x_{i}$ is the example labeling the node following the prefix edges $(\sigma_{1},\ldots,\sigma_{i-1})$ down the tree.

For simplicity, we use $x_{t}(\sigma)$ to denote the example at the $t$-th entry of a path $x(\sigma)$, but we remark that $x_{t}(\sigma)$ depends only on the prefix path $(\sigma_{1},\ldots,\sigma_{i-1})$.
Following this notion, we introduce the sequential fat-shattering dimension.

###### Definition 2.2 (Sequential fat-shattering dimension, (Rakhlin et al., 2015a ) ) .

We say that a ${\mathcal{X}}$-valued Littlestone tree of depth $T$ is $\alpha$-shattered by a function class ${\mathcal{F}}\subset{\mathcal{Y}}^{{\mathcal{X}}}$ if there exists a ${\mathcal{Y}}$-valued tree $y$ of depth $T$ such that

$$ $\forall\sigma\in\{-1,1\}^{T},~\exists f\in{\mathcal{F}},~~\text{s.t.}~~\forall t\in[T],~\sigma_{t}(f(x_{t}(\sigma))-y_{t}(\sigma))\geq\alpha/2.$ $$

Here, the tree $y$ is called the witness of shattering.
The sequential fat-shattering dimension $\mathrm{fat}^{\mathbf{seq}}_{\alpha}({\mathcal{F}})$ is defined as the largest $T$ such that ${\mathcal{F}}$ $\alpha$-shatters a ${\mathcal{X}}$-valued tree of depth $T$. In addition, $\mathrm{fat}^{\mathbf{seq}}_{\alpha}({\mathcal{F}})=\infty$ if ${\mathcal{F}}$ $\alpha$-shatters a ${\mathcal{X}}$-valued tree of arbitrary depth.

Rakhlin et al. (2015a) showed that, in the online setting, the expected regret is controlled by the sequential fat-shattering dimension, as stated below.

###### Theorem 2.3 (Online learning, see Proposition 9 in (Rakhlin et al., 2015a ) ) .

For any function class ${\mathcal{F}}\subset[0,1]^{{\mathcal{X}}}$ and $L_{\mathbf{los}}$-Lipschitz and convex loss function $\ell$, the expected regret of online learning satisfies

$$ $\inf_{{\mathcal{A}}}\text{R}_{{\mathcal{A}}}(T,{\mathcal{F}})\leq 2L_{\mathbf{los}}T\cdot\inf_{\alpha\geq 0}\left(4\alpha+\frac{12}{\sqrt{T}}\int_{\alpha}^{1}\sqrt{\mathrm{fat}^{\mathbf{seq}}_{\beta/4}({\mathcal{F}})\log\frac{2eT}{\beta}}\mathrm{d}\beta\right),$ $$

where the infimum is taken on all online learner ${\mathcal{A}}$. We denote this quantity by $\text{R}^{\mathbf{ol}}(T,{\mathcal{F}})$.

###### Definition 2.1 (The Littlestone tree, (Littlestone, 1987 ) ) .

###### Definition 2.2 (Sequential fat-shattering dimension, (Rakhlin et al., 2015a ) ) .

###### Theorem 2.3 (Online learning, see Proposition 9 in (Rakhlin et al., 2015a ) ) .

### 2.2 Transductive Online Learning.

In transductive online learning, unlike online learning, the adversary first reveals the entire sequence of unlabeled examples $x_{1},\ldots,x_{T}$ to the learner at the beginning.
The interaction then proceeds in $T$ rounds: In each round, the learner predicts a label $\widehat{y}_{t}$ for the current example $x_{t}$, using information from the past labeled examples $(x_{1},y_{1}),\ldots,(x_{t},y_{t})$ and the future unlabeled examples $x_{t+1},\ldots,x_{T}$. After the prediction, the adversary reveals the true label $y_{t}$.
For a transductive online learner ${\mathcal{B}}$, we define its minimax expected regret as

$$ $R^{\mathbf{tr}}_{\mathcal{B}}(T,{\mathcal{F}}):=\sup_{x_{1:T}\in\mathcal{X}^{T}}\sup_{y_{1:T}\in\mathcal{Y}^{T}}\left(\mathbb{E}\left[\sum_{t=1}^{T}\left|\mathcal{B}_{x_{1:T}}\left(x_{t}\right)-y_{t}\right|\right]-\inf_{h\in{\mathcal{F}}}\sum_{t=1}^{T}\left|h\left(x_{t}\right)-y_{t}\right|\right),$ $$

where again the expectation is over the randomness of the learner.
We say that a function class ${\mathcal{F}}$ is transductive online learnable if $\inf_{\mathcal{B}}R^{\mathbf{ol}}_{{\mathcal{B}}}(T,{\mathcal{F}})=o(T)$.

#### Fat-shattering dimension.

In this paper, we characterize the learnability of transductive online regression by the fat-shattering dimension, a scale-sensitive version of the Vapnik-Chervonenkis (VC) dimension (Vapnik and Chervonenkis, 1971), which is also used to characterize PAC learnability (Alon et al., 1997).

###### Definition 2.4 (Fat-shattering dimension, (Alon et al., 1997 ) ) .

A sequence $x=x_{1:T}$ is defined to be $\alpha$-shattered by ${\mathcal{F}}$ if there exists a sequence of real numbers $y=y_{1:T}$ such that for each binary string $\sigma\in\{-1,1\}^{T}$, there is a function $f\in{{\mathcal{F}}}$ that satisfies

$$ $\forall t\in[T],~~\sigma_{t}\cdot(f(x_{t})-y_{t})\geq\alpha/2.$ $$

Here, the sequence $y$ is called the witness of shattering.
Then, the fat-shattering dimension $\mathrm{fat}_{\alpha}({\mathcal{F}})$ is defined as the largest $T$ such that ${\mathcal{F}}$ $\alpha$-shatters a sequence $x\subset{\mathcal{X}}$ of length $T$. In addition, $\mathrm{fat}_{\alpha}({\mathcal{F}})=\infty$ if for every finite $T$, there is a sequence of length $T$ that is $\alpha$-shattered by ${\mathcal{F}}$.

###### Definition 2.4 (Fat-shattering dimension, (Alon et al., 1997 ) ) .

#### Covering number.

Given a function class ${\mathcal{F}}\subset{\mathcal{Y}}^{{\mathcal{X}}}$, we introduce the classical notion of the covering number, which defines the “effective” size of the function class on ${\mathcal{X}}$.

###### Definition 2.5 (Covering number) .

A set ${\mathcal{V}}\subset\mathbb{R}^{T}$ is an $\alpha$-cover on a sequence $x=x_{1:T}$ with respect to the $\ell_{p}$ norm if for each $f\in{\mathcal{F}}$, there exist an item $v_{1:T}\in{\mathcal{V}}$ such that

$$ $\forall t\in[T],~~\left(\frac{1}{T}\sum_{t=1}^{T}|f(x_{t})-v_{t}|^{p}\right)^{1/p}\leq\alpha.$ $$

Similarly, a set ${\mathcal{V}}\subset\mathbb{R}^{T}$ is a $\alpha$-cover on a sequence $x=x_{1:T}$ with respect to the $\ell_{\infty}$ norm if for each $f\in{\mathcal{F}}$, there exist an item $v_{1:T}\in{\mathcal{V}}$ such that

$$ $\forall t\in[T],~~|f(x_{t})-v_{t}|\leq\alpha.$ $$

Then the covering number ${\mathcal{N}}_{p}(T,{\mathcal{F}},x,\alpha)$ of ${\mathcal{F}}$ on $x$ is defined as the minimum size of the $\alpha$-cover with respect to the $\ell_{p}$ norm.
It is known that ${\mathcal{N}}_{p}(T,{\mathcal{F}},x,\alpha)\leq{\mathcal{N}}_{q}(T,{\mathcal{F}},x,\alpha)$ for $1\leq p\leq q\leq\infty$.

In addition, we define the covering number ${\mathcal{N}}_{p}(T,{\mathcal{F}},\alpha)$ of ${\mathcal{F}}$ on the example space ${\mathcal{X}}$ as the supremum of all choices of sequence $x$: ${\mathcal{N}}_{p}(T,{\mathcal{F}},\alpha)=\sup_{x\subset{\mathcal{X}}}{\mathcal{N}}_{p}(T,{\mathcal{F}},x,\alpha)$.

The next statement upper bounds the $\alpha$-covering number by the fat-shattering dimension, which is applied to upper bound the expected regret of our online learner.

###### Theorem 2.6 (See Theorem 12.8 in (Anthony and Bartlett, 1999 ) ) .

For any function class ${\mathcal{F}}\subset[0,1]^{{\mathcal{X}}}$ and $\alpha>0$, we have

$$ $\log{\mathcal{N}}_{\infty}(T,{\mathcal{F}},\alpha)\leq\mathrm{fat}_{\alpha/4}({\mathcal{F}})\cdot c\log^{2}\frac{T}{\alpha},$ $$

where $c$ is some universal constant.

###### Definition 2.5 (Covering number) .

###### Theorem 2.6 (See Theorem 12.8 in (Anthony and Bartlett, 1999 ) ) .

#### Rademacher complexity.

We then introduce the Rademacher complexity of a function class, which is closely related to the fat-shattering dimension.
Let $\sigma_{1},\ldots,\sigma_{T}$ be independent Rademacher random variables.
We define the Rademacher complexity of a function class ${\mathcal{F}}\subset[0,1]^{{\mathcal{X}}}$ on an example sequence $x_{1:T}$ as

$$ ${\mathcal{R}}(T,{\mathcal{F}},x)=\mathbb{E}\left[\sup_{f\in{\mathcal{F}}}\frac{1}{T}\sum_{t=1}^{T}\sigma_{t}f(x_{t})\right].$ $$

Then, we define the Rademacher complexity as ${\mathcal{R}}(T,{\mathcal{F}})=\sup_{x_{1:T}\subset{\mathcal{X}}}{\mathcal{R}}(T,{\mathcal{F}},x)$.
We state the entropy bound on the Rademacher complexity in the following statement.
Together with [Theorem 2.6](https://arxiv.org/html/2510.03917v1#S2.Thmtheorem6), it gives an upper bound on Rademacher complexity by the fat-shattering dimension, which is used to characterize the learnability of tranductive online regression in later sections.

###### Theorem 2.7 (See Theorem 12.4 in (Rakhlin and Sridharan, 2014 ) ) .

For any sequence $x_{1:T}$ and function class ${\mathcal{F}}\subset[0,1]^{{\mathcal{X}}}$, we have

$$ ${\mathcal{R}}(T,{\mathcal{F}},x)\leq\inf_{\alpha\geq 0}\left(4\alpha+\frac{12}{\sqrt{T}}\int_{\alpha}^{1}\sqrt{\log{\mathcal{N}}_{2}(T,{\mathcal{F}},x,\beta)}\mathrm{d}\beta\right).$ $$

###### Theorem 2.7 (See Theorem 12.4 in (Rakhlin and Sridharan, 2014 ) ) .

### 2.3 Online Learning with Predictions

Since in practice, the sequence of examples often follows predictable patterns, we study the setting of online learning with predictions (Raman and Tewari, 2024). Here, the learner has access to a Predictor ${\mathcal{P}}$.
${\mathcal{P}}$ which predicts the sequence of examples $x_{1},\ldots x_{T}$ adaptively: at each round $t\in[T]$, the adversary reveals the example $x_{t}$ to ${\mathcal{P}}$, then ${\mathcal{P}}$ reports the predictions of the *entire* sequence $\widehat{x}_{1},\ldots\widehat{x}_{T}$ based on the past examples $x_{1},\ldots,x_{t}$.
We assume that ${\mathcal{P}}$ predicts the entire sequence for notational convenience, since it can set $\widehat{x}_{c}=x_{c}$ for each $c\in[t]$.
We denote the prediction of $x_{t^{\prime}}$ at time $t$ as ${\mathcal{P}}(x_{1:t})_{t^{\prime}}$.
Given the predictions, the learner predicts a label $\widehat{y}_{t}$ for the current example $x_{t}$, using information from the past labeled examples $(x_{1},y_{1}),\ldots,(x_{t},y_{t})$ and the predictions of future examples $\widehat{x}_{t+1},\ldots,\widehat{x}_{T}$.
Here, we consider the standard adversarial setting in online learning, where the sequence of examples is *not* revealed to the learner in advance, and similarly, we measure the minimax expected regret by $R^{\mathbf{ol}}_{\mathcal{A}}(T,{\mathcal{F}})$.
In this paper, we show that given a Predictor ${\mathcal{P}}$ with specific mistake-bounds, the minimax expected regret is characterized by the fat-shattering dimension but not the sequential version, and thus separate this setting from the standard online learning setting.

## 3 Minimax Regret of Transductive Online Regression

In this section, we give near-matching upper and lower bounds on the minimax expected transductive regret in terms of the fat-shattering dimension.
Like the fully adversarial online setting, our proof for the upper bound is non-constructive and relies on minimax arguments.
To that end, we also give an explicit a transductive online learner with sub-optimal regret based on the multiplicative weights algorithm (MWA).

### 3.1 Transductive Online Learner

In this section, we present a concrete learning algorithm based on MWA, which randomly samples the advice of $K$ experts in an online manner.
Since we know the exact input sequence of examples $x_{1:T}$, we define the $K$ experts in MWA by the minimal $\alpha$-cover on $x_{1:T}$ with respect to the $\ell_{\infty}$ norm.
We remark that this construction does not match our optimal upper bound on the minimax expected regret, but it provides intuitions on how we use the knowledge of the sequence of examples: When we know $x_{1:T}$, we can build a net with better coverage to apply canonical algorithms in online learning.
Our transductive online learner is presented in [Algorithm 1](https://arxiv.org/html/2510.03917v1#alg1).
Next, we state the formal theorem for MWA.

###### Theorem 3.1 (See e.g. Section 4 in (Cesa-Bianchi and Lugosi, 2006 ) and Theorem 2.1 in (Arora et al., 2012 ) ) .

Given $K$ experts such that for each expert $k\in K$, the loss in each round $t$ is $\ell(k_{t},y_{t})$, suppose that the loss ranges from $[0,1]$, then there is a multiplicative weights algorithm ${\mathcal{Q}}$ with minimax expected regret $\eta=\sqrt{\frac{8\log K}{T}}$ that satisfies

$$ $\mathbb{E}\left[\sum_{t=1}^{T}\ell({\mathcal{Q}}(x_{t}),y_{t})\right]\leq\inf_{k\in[K]}\left(\sum_{t=1}^{T}\ell(k_{t},y_{t})\right)+\sqrt{\frac{T\log K}{2}}.$ $$

Figure: Algorithm 1 Transductive Online Learner

The next theorem upper bounds the minimax expected regret of [Algorithm 1](https://arxiv.org/html/2510.03917v1#alg1).

###### Theorem 3.2 .

For any function class ${\mathcal{F}}\subset[0,1]^{{\mathcal{X}}}$, $L_{\mathbf{los}}$-Lipschitz loss function $\ell$, set of examples $\{x_{1},\ldots,x_{T}\}$, and sequence of labels $y_{1},\ldots,y_{T}$, the minimax expected regret of [Algorithm 1](https://arxiv.org/html/2510.03917v1#alg1) is bounded by

$$ $\inf_{\alpha>0}\left(\alpha L_{\mathbf{los}}T+\sqrt{\frac{T\cdot\mathrm{fat}_{\alpha/4}({\mathcal{F}})\cdot c\log^{2}\frac{T}{\alpha}}{2}}\right),$ $$

where $c$ is a universal constant.

###### Proof.

Let ${\mathcal{B}}$ be the learner in [Algorithm 1](https://arxiv.org/html/2510.03917v1#alg1).
From the guarantee of MWA (see [Theorem 3.1](https://arxiv.org/html/2510.03917v1#S3.Thmtheorem1)), we have

$$ $\displaystyle\mathbb{E}\left[\sum_{t=1}^{T}\ell({\mathcal{B}}(x_{t}),y_{t})\right]$ $\displaystyle\leq\inf_{k\in[K]}\left(\sum_{t=1}^{T}\ell(k_{t},y_{t})\right)+\sqrt{\frac{T\log K}{2}}$ $\displaystyle=\inf_{v^{k}\in{\mathcal{V}}}\left(\sum_{t=1}^{T}\ell(v^{k}_{t},y_{t})\right)+\sqrt{\frac{T\log K}{2}}.$ $$

Recall that ${\mathcal{V}}$ is a $\alpha$-cover of ${\mathcal{F}}$ on $x_{1:T}$, then for each $f\in{\mathcal{F}}$, there is a $v^{k}\in{\mathcal{V}}$ such that
$|v^{k}_{t}-f(x_{t})|<\alpha$ for each $t\in[T]$.
Since the loss function is $L_{\mathbf{los}}$-Lipschitz, we have

$$ $\ell(v^{k}_{t},y_{t})\leq\ell(f(x_{t}),y_{t})+\alpha L_{\mathbf{los}}.$ $$

Summing over each $t\in[T]$ gives us

$$ $\sum_{t=1}^{T}\ell(v^{k}_{t},y_{t})\leq\sum_{t=1}^{T}\ell(f(x_{t}),y_{t})+\alpha L_{\mathbf{los}}T.$ $$

Therefore, for each $f\in{\mathcal{F}}$, we have

$$ $\inf_{v^{k}\in{\mathcal{V}}}\left(\sum_{t=1}^{T}\ell(v^{k}_{t},y_{t})\right)\leq\sum_{t=1}^{T}\ell(f(x_{t}),y_{t})+\alpha L_{\mathbf{los}}T.$ $$

Taking the infimum across $h$ on the RHS, we have

$$ $\inf_{v^{k}\in{\mathcal{V}}}\left(\sum_{t=1}^{T}\ell(v^{k}_{t},y_{t})\right)\leq\inf_{f\in{\mathcal{F}}}\left(\sum_{t=1}^{T}\ell(f(x_{t}),y_{t})\right)+\alpha L_{\mathbf{los}}T.$ $$

Then the expected loss satisfies

$$ $\mathbb{E}\left[\sum_{t=1}^{T}\ell({\mathcal{B}}(x_{t}),y_{t})\right]\leq\inf_{f\in{\mathcal{F}}}\left(\sum_{t=1}^{T}\ell(f(x_{t}),y_{t})\right)+\alpha L_{\mathbf{los}}T+\sqrt{\frac{T\log K}{2}}.$ $$

Therefore, by definition the minimax expected regret of ${\mathcal{B}}$ is at most

$$ $\alpha L_{\mathbf{los}}T+\sqrt{\frac{T\log K}{2}}.$ $$

Last, we note that $K\leq{\mathcal{N}}_{\infty}(T,{\mathcal{F}},\alpha)$ since we define the experts by a minimum $\alpha$-cover ${\mathcal{F}}^{\prime}$ on $x_{1:T}$ (see [Definition 2.5](https://arxiv.org/html/2510.03917v1#S2.Thmtheorem5)).
By [Theorem 2.6](https://arxiv.org/html/2510.03917v1#S2.Thmtheorem6), we have

$$ $\log{\mathcal{N}}_{\infty}(T,{\mathcal{F}},\alpha)\leq\mathrm{fat}_{\alpha/4}({\mathcal{F}})\cdot c\log^{2}\frac{T}{\alpha}.$ $$

Therefore, the minimax expected regret is at most

$$ $\alpha L_{\mathbf{los}}T+\sqrt{\frac{T\cdot\mathrm{fat}_{\alpha/4}({\mathcal{F}})\cdot c\log^{2}\frac{T}{\alpha}}{2}}.$ $$

Our result then follows from the fact that the above equation holds for an arbitrary $\alpha$.
∎

###### Theorem 3.1 (See e.g. Section 4 in (Cesa-Bianchi and Lugosi, 2006 ) and Theorem 2.1 in (Arora et al., 2012 ) ) .

###### Theorem 3.2 .

###### Proof.

### 3.2 Upper Bounds on the Minimax Expected Regret

As the algorithm in the previous section does not obtain the optimal minimax regret for transductive online regression, in this section, we we give a non-constructive upper bound on the minimax value, and we will demonstrate its tightness by a lower bound in the following section.
Note that our upper bound is in terms of the fat-shattering dimension of ${\mathcal{F}}$, as opposed to the sequential fat-shattering dimension in the online setting, thus our rate is better since many function classes have a finite fat-shattering dimension but an infinite sequential fat-shattering dimension.

Our approach extends from the randomized learner framework in (Rakhlin et al., 2015a): Suppose that ${\mathcal{Q}}$ is a weakly compact set of probability measures on ${\mathcal{F}}$, then in each round $t$, ${\mathcal{A}}$ selects a probability measure $q_{t}\in{\mathcal{Q}}$ and outputs ${\mathcal{A}}_{t}=f_{t}(x_{t})$, where $f_{t}\sim q_{t}$.
We write ${\mathcal{A}}_{t}\sim q_{t}$ in the following for simplicity.
Then, the expected regret is represented as a minimax value, which encrypts the interaction of the learner and the adversary in each round:

$$ $\inf_{{\mathcal{A}}}\text{R}_{{\mathcal{A}}}(T,{\mathcal{F}})=\sup_{x_{1:T}}\inf_{q_{1}\in\mathcal{Q}}\sup_{y_{1}\in{\mathcal{Y}}}\underset{{\mathcal{A}}_{1}\sim q_{1}}{\mathbb{E}}\cdots\inf_{q_{T}\in\mathcal{Q}}\sup_{y_{T}\in\mathcal{Y}}\underset{{\mathcal{A}}_{T}\sim q_{T}}{\mathbb{E}}\left[\sum_{f_{T}\sim q_{T}}^{T}\ell\left({\mathcal{A}}_{t},y_{t}\right)-\inf_{f\in\mathcal{F}}\sum_{t=1}^{T}\ell\left(f(x_{t}),y_{t}\right)\right].$ $$

Our key observation is that, since we have full access to $x_{1:T}$, $\sup_{x_{1:T}}$ is written in front of the minimax value in the above formula.
Thus, we ultimately get an upper bound by the Rademacher complexity, instead of the sequential Rademacher complexity in (Rakhlin et al., 2015a).
Then, applying the entropy bound in [Theorem 2.7](https://arxiv.org/html/2510.03917v1#S2.Thmtheorem7) gives us an upper bound in terms of the fat-shattering dimension.
We state the formal guarantees in the following theorem.

###### Theorem 3.3 (Upper bound) .

For any function class ${\mathcal{F}}\subset[0,1]^{{\mathcal{X}}}$ and $L_{\mathbf{los}}$-Lipschitz and convex loss function $\ell$, the expected regret of transductive online learning is bounded by the Rademacher complexity:

$$ $\inf_{{\mathcal{A}}}\text{R}_{{\mathcal{A}}}(T,{\mathcal{F}})\leq 2L_{\mathbf{los}}T\cdot{\mathcal{R}}(T,{\mathcal{F}})\leq 2L_{\mathbf{los}}T\cdot\inf_{\alpha\geq 0}\left(4\alpha+\frac{12}{\sqrt{T}}\int_{\alpha}^{1}\sqrt{\mathrm{fat}_{\beta/4}({\mathcal{F}})\cdot c\log^{2}\frac{T}{\beta}}\mathrm{d}\beta\right).$ $$

###### Proof.

Let $\ell^{\prime}(\widehat{y}_{t},y_{t})$ be a subgradient of the function $y\to\ell(\cdot,y_{t})$ at $y_{t}$. Then, since the loss function is convex, we have

$$ $\inf_{{\mathcal{A}}}R^{\mathbf{tr}}_{{\mathcal{A}}}(T,{\mathcal{F}})\leq\sup_{x_{1:T}}\inf_{q_{1}\in\mathcal{Q}}\sup_{y_{1}\in{\mathcal{Y}}}\underset{{\mathcal{A}}_{1}\sim q_{1}}{\mathbb{E}}\cdots\inf_{q_{T}\in\mathcal{Q}}\sup_{y_{T}\in\mathcal{Y}}\underset{{\mathcal{A}}_{T}\sim q_{T}}{\mathbb{E}}\left[\sup_{f\in\mathcal{F}}\sum_{t=1}^{T}\ell^{\prime}({\mathcal{A}}_{t},y_{t})\cdot({\mathcal{A}}_{t}-f(x_{t}))\right].$ $$

In addition, since the loss function satisfies the Lipschitz property, i.e., $|\ell^{\prime}({\mathcal{A}}_{t},y_{t})|<L_{\mathbf{los}}$, then we have

$$ $\inf_{{\mathcal{A}}}R^{\mathbf{tr}}_{{\mathcal{A}}}(T,{\mathcal{F}})\leq\sup_{x_{1:T}}\inf_{q_{1}\in\mathcal{Q}}\sup_{y_{1}\in{\mathcal{Y}}}\underset{{\mathcal{A}}_{1}\sim q_{1}}{\mathbb{E}}\sup_{s_{1}\in[-L,L]}\cdots\inf_{q_{T}\in\mathcal{Q}}\sup_{y_{T}\in\mathcal{Y}}\underset{{\mathcal{A}}_{T}\sim q_{T}}{\mathbb{E}}\sup_{s_{T}\in[-L,L]}\left[\sup_{f\in\mathcal{F}}\sum_{t=1}^{T}s_{t}\cdot({\mathcal{A}}_{t}-f(x_{t}))\right].$ $$

Here, we write $L_{\mathbf{los}}$ as $L$ for simplicity of notation.
We then simplify the above upper bound as follows since $y_{t}$ does not appear in the objective function

$$ $\sup_{x_{1:T}}\inf_{q_{1}\in\mathcal{Q}}\underset{{\mathcal{A}}_{1}\sim q_{1}}{\mathbb{E}}\sup_{s_{1}\in[-L,L]}\cdots\inf_{q_{T}\in\mathcal{Q}}\underset{{\mathcal{A}}_{T}\sim q_{T}}{\mathbb{E}}\sup_{s_{T}\in[-L,L]}\left[\sup_{f\in\mathcal{F}}\sum_{t=1}^{T}s_{t}\cdot({\mathcal{A}}_{t}-f(x_{t}))\right].$ $$

Next, since the family of probability measures ${\mathcal{Q}}$ contains the point distribution, we can write the operator $\underset{q_{t}\in\mathcal{Q}}{\inf}\underset{{\mathcal{A}}_{t}\sim q_{t}}{\mathbb{E}}$ as $\underset{{\mathcal{A}}_{t}\in[0,1]}{\inf}$. Similarly, let ${\mathcal{P}}$ denote the family of all possible distributions on $[-L,L]$, we can write $\underset{s_{t}\in[-L,L]}{\sup}$ as $\underset{p_{t}\in\mathcal{P}}{\sup}\underset{s_{t}\sim p_{t}}{\mathbb{E}}$. Then, the upper bound is equivalent to

$$ $\sup_{x_{1:T}}\inf_{{\mathcal{A}}_{1}\in[0,1]}\sup_{p_{1}\in\mathcal{P}}\underset{s_{1}\sim p_{1}}{\mathbb{E}}\cdots\inf_{{\mathcal{A}}_{T}\in[0,1]}\sup_{p_{T}\in\mathcal{P}}\underset{s_{T}\sim p_{T}}{\mathbb{E}}\left[\sum_{t=1}^{T}s_{t}\cdot{\mathcal{A}}_{t}-\inf_{f\in\mathcal{F}}\sum_{t=1}^{T}s_{t}\cdot f(x_{t})\right].$ $$

Notice that $\underset{s_{t}\sim p_{t}}{\mathbb{E}}\left[\sum_{t=1}^{T}s_{t}\cdot{\mathcal{A}}_{t}-\inf_{f\in\mathcal{F}}\sum_{t=1}^{T}s_{t}\cdot f(x_{t})\right]$ is concave in $p_{T}$ and convex in ${\mathcal{A}}_{T}$, then by the minimax theorem, we have

$$ $\displaystyle\inf_{{\mathcal{A}}_{T}\in[0,1]}\sup_{p_{T}\in\mathcal{P}}\underset{s_{T}\sim p_{T}}{\mathbb{E}}\left[\sum_{t=1}^{T}s_{t}\cdot{\mathcal{A}}_{t}-\inf_{f\in\mathcal{F}}\sum_{t=1}^{T}s_{t}\cdot f(x_{t})\right]$ $\displaystyle=$ $\displaystyle~\sup_{p_{T}\in\mathcal{P}}\inf_{{\mathcal{A}}_{T}\in[0,1]}\underset{s_{T}\sim p_{T}}{\mathbb{E}}\left[\sum_{t=1}^{T}s_{t}\cdot{\mathcal{A}}_{t}-\inf_{f\in\mathcal{F}}\sum_{t=1}^{T}s_{t}\cdot f(x_{t})\right]$ $\displaystyle=$ $\displaystyle~\sum_{t=1}^{T-1}s_{t}\cdot{\mathcal{A}}_{t}+\sup_{p_{T}\in\mathcal{P}}\underset{s_{T}\sim p_{T}}{\mathbb{E}}\left[\inf_{{\mathcal{A}}_{T}\in[0,1]}\underset{s_{T}\sim p_{T}}{\mathbb{E}}s_{T}\cdot{\mathcal{A}}_{T}-\inf_{f\in\mathcal{F}}\sum_{t=1}^{T}s_{t}\cdot f(x_{t})\right].$ $$

Similarly, $\underset{s_{T}\sim p_{T}}{\mathbb{E}}\left[\inf_{{\mathcal{A}}_{T}\in[0,1]}\underset{s_{T}\sim p_{T}}{\mathbb{E}}s_{t}\cdot{\mathcal{A}}_{t}-\inf_{f\in\mathcal{F}}\sum_{t=1}^{T}s_{t}\cdot f(x_{t})\right]$ is concave in $p_{T-1}$ and convex in ${\mathcal{A}}_{T-1}$, then again by the minimax theorem, we have

$$ $\displaystyle\sup_{p_{T-1}\in\mathcal{P}}\inf_{{{\mathcal{A}}}_{T-1}\in[0,1]}\underset{s_{T-1}\sim p_{T-1}}{\mathbb{E}}\left[\sum_{t=1}^{T-1}s_{t}\cdot{\mathcal{A}}_{t}+\sup_{p_{T}\in\mathcal{P}}\underset{s_{T}\sim p_{T}}{\mathbb{E}}\left[\inf_{{\mathcal{A}}_{T}\in[0,1]}\underset{s_{T}\sim p_{T}}{\mathbb{E}}s_{t}\cdot{\mathcal{A}}_{t}-\inf_{f\in\mathcal{F}}\sum_{t=1}^{T}s_{t}\cdot f(x_{t})\right]\right]$ $\displaystyle=$ $\displaystyle~\inf_{{{\mathcal{A}}}_{T-1}\in[0,1]}\sup_{p_{T-1}\in\mathcal{P}}\underset{s_{T-1}\sim p_{T-1}}{\mathbb{E}}\left[\sum_{t=1}^{T-1}s_{t}\cdot{\mathcal{A}}_{t}+\sup_{p_{T}\in\mathcal{P}}\underset{s_{T}\sim p_{T}}{\mathbb{E}}\left[\inf_{{\mathcal{A}}_{T}\in[0,1]}\underset{s_{T}\sim p_{T}}{\mathbb{E}}s_{t}\cdot{\mathcal{A}}_{t}-\inf_{f\in\mathcal{F}}\sum_{t=1}^{T}s_{t}\cdot f(x_{t})\right]\right]$ $\displaystyle=$ $\displaystyle~\sum_{t=1}^{T-2}s_{t}\cdot{\mathcal{A}}_{t}+\sup_{p_{T-1}\in\mathcal{P}}\underset{s_{T-1}\sim p_{T-1}}{\mathbb{E}}\sup_{p_{T}\in\mathcal{P}}\underset{s_{T}\sim p_{T}}{\mathbb{E}}\left[\sum_{t=T-1}^{T}\inf_{{\mathcal{A}}_{t}\in[0,1]}\underset{s_{t}\sim p_{t}}{\mathbb{E}}s_{t}\cdot{\mathcal{A}}_{t}-\inf_{f\in\mathcal{F}}\sum_{t=1}^{T}s_{t}\cdot f(x_{t})\right].$ $$

Proceeding with this transformation, we have that the minimax expected regret is upper bounded by

$$ $\sup_{x_{1:T}}\sup_{p_{1}\in\mathcal{P}}\underset{s_{1}\sim p_{1}}{\mathbb{E}}\cdots\sup_{p_{T}\in\mathcal{P}}\underset{s_{T}\sim p_{T}}{\mathbb{E}}\left[\sum_{t=1}^{T}\inf_{{\mathcal{A}}_{t}\in[0,1]}\underset{s_{t}\sim p_{t}}{\mathbb{E}}s_{t}\cdot{\mathcal{A}}_{t}-\inf_{f\in\mathcal{F}}\sum_{t=1}^{T}s_{t}\cdot f(x_{t})\right].$ $$

Replacing ${\mathcal{A}}_{t}$ by a potential suboptimal choice $f(x_{t})$, we obtain an upper bound

$$ $\displaystyle\sup_{x_{1:T}}\sup_{p_{1}\in\mathcal{P}}\underset{s_{1}\sim p_{1}}{\mathbb{E}}\cdots\sup_{p_{T}\in\mathcal{P}}\underset{s_{T}\sim p_{T}}{\mathbb{E}}\left[\sup_{f\in\mathcal{F}}\left[\sum_{t=1}^{T}\left(\underset{s_{t}\sim p_{t}}{\mathbb{E}}s_{t}-s_{t}\right)\cdot f(x_{t})\right]\right]$ $\displaystyle=$ $\displaystyle~\sup_{x_{1:T}}\sup_{p_{1}\in\mathcal{P}}\underset{s_{1},s^{\prime}_{1}\sim p_{1}}{\mathbb{E}}\cdots\sup_{p_{T}\in\mathcal{P}}\underset{s_{T},s^{\prime}_{T}\sim p_{T}}{\mathbb{E}}\left[\sup_{f\in\mathcal{F}}\left[\sum_{t=1}^{T}(s^{\prime}_{t}-s_{t})\cdot f(x_{t})\right]\right].$ $$

Since the objective function in the expectation is symmetric with respect to $s^{\prime}_{t}$ and $s_{t}$, it equals to

$$ $\sup_{x_{1:T}}\sup_{p_{1}\in\mathcal{P}}\underset{s_{1},s^{\prime}_{1}\sim p_{1}}{\mathbb{E}}\underset{\sigma_{1}}{\mathbb{E}}\cdots\sup_{p_{T}\in\mathcal{P}}\underset{s_{T},s^{\prime}_{T}\sim p_{T}}{\mathbb{E}}\underset{\sigma_{T}}{\mathbb{E}}\left[\sup_{f\in\mathcal{F}}\left[\sum_{t=1}^{T}\sigma_{t}(s^{\prime}_{t}-s_{t})\cdot f(x_{t})\right]\right],$ $$

where $\sigma_{t}$ are Rademacher variables.
Since $s_{t}\in[-L,L]$, we obtain an upper bound

$$ $\sup_{x_{1:T}}\sup_{s_{1}\in[-2L,2L]}\underset{\sigma_{1}}{\mathbb{E}}\cdots\sup_{s_{T}\in[-2L,2L]}\underset{\sigma_{T}}{\mathbb{E}}\left[\sup_{f\in\mathcal{F}}\left[\sum_{t=1}^{T}\sigma_{t}s_{t}\cdot f(x_{t})\right]\right].$ $$

Note that for each $t\in[T]$, the objective is convex in $s_{t}$, and so the supremum is achieved at the endpoints, therefore, we have an upper bound

$$ $\displaystyle\sup_{x_{1:T}}\sup_{s_{1}\in\{-2L,2L\}}\underset{\sigma_{1}}{\mathbb{E}}\cdots\sup_{s_{T}\in\{-2L,2L\}}\underset{\sigma_{T}}{\mathbb{E}}\left[\sup_{f\in\mathcal{F}}\left[\sum_{t=1}^{T}\sigma_{t}s_{t}\cdot f(x_{t})\right]\right]$ $\displaystyle=$ $\displaystyle~2L\cdot\sup_{x_{1:T}}\sup_{s_{1}\in\{-1,1\}}\underset{\sigma_{1}}{\mathbb{E}}\cdots\sup_{s_{T}\in\{-1,1\}}\underset{\sigma_{T}}{\mathbb{E}}\left[\sup_{f\in\mathcal{F}}\left[\sum_{t=1}^{T}\sigma_{t}s_{t}\cdot f(x_{t})\right]\right].$ $$

Now, for an arbitrary function $g:\{\pm 1\}\to\mathbb{R}$, we have that

$$ $\sup_{s_{T}\in\{-1,1\}}\underset{\sigma}{\mathbb{E}}[g(s\sigma)]=\sup_{s_{T}\in\{-1,1\}}\frac{1}{2}g(s)+g(-s)=\underset{\sigma}{\mathbb{E}}[g(\sigma)].$ $$

Therefore, the above quantity equals to

$$ $2L\cdot\sup_{x_{1:T}}\underset{\sigma}{\mathbb{E}}\left[\sup_{f\in\mathcal{F}}\left[\sum_{t=1}^{T}\sigma_{t}f(x_{t})\right]\right]=2LT\cdot{\mathcal{R}}(T,{\mathcal{F}}),$ $$

which upper bounds the minimax expected regret by the Rademacher complexity.
Combining [Theorem 2.6](https://arxiv.org/html/2510.03917v1#S2.Thmtheorem6) and [Theorem 2.7](https://arxiv.org/html/2510.03917v1#S2.Thmtheorem7), we have the following entropy bound on the Rademacher complexity, which is associated with the fat-shattering dimension.

$$ ${\mathcal{R}}(T,{\mathcal{F}})\leq\inf_{\alpha\geq 0}\left(4\alpha+\frac{12}{\sqrt{T}}\int_{\alpha}^{1}\sqrt{\mathrm{fat}_{\beta/4}({\mathcal{F}})\cdot c\log^{2}\frac{T}{\beta}}\mathrm{d}\beta\right),$ $$

which gives our final result.
∎

We note that the above upper bound is in terms of the fat-shattering dimension of ${\mathcal{F}}$, as opposed to the sequential fat-shattering dimension in the online setting.
Thus, our rate is better since many function classes have a finite fat-shattering dimension but an infinite sequential fat-shattering dimension, e.g., the class of functions with bounded variation.

To get a better sense of how the upper bound in [Theorem 3.3](https://arxiv.org/html/2510.03917v1#S3.Thmtheorem3) scales with $T$, we present the explicit expected regret of three concrete function classes: $L$-Lipschitz functions, $k$-fold aggregations, and functions with $V$-bounded variation.

###### Theorem 3.3 (Upper bound) .

###### Proof.

#### Lipschitz function.

We consider the class of $L_{\mathbf{hyp}}$-Lipschitz functions.
The next statement upper bounds the fat-shattering dimension for such classes.

###### Theorem 3.4 (See corollary 1 in (Gottlieb et al., 2014 ) ) .

Let ${\mathcal{X}}$ be a metric space with diameter $\mathrm{diam}\left({\mathcal{X}}\right)$ and doubling dimension $\mathrm{ddim}\left({\mathcal{X}}\right)$. For any function class ${\mathcal{F}}\subset[0,1]^{{\mathcal{X}}}$ of $L_{\mathbf{hyp}}$-Lipschitz function and parameter $\alpha$, we have

$$ $\mathrm{fat}_{\alpha}({\mathcal{F}})\leq\left(\frac{L_{\mathbf{hyp}}\cdot\mathrm{diam}\left({\mathcal{X}}\right)}{\alpha}\right)^{\mathrm{ddim}\left({\mathcal{X}}\right)}.$ $$

With the above upper bound, we provide the minimax expected regret for Lipschitz function classes explicitly in the next statement.
Here, we consider the dimension $n$ and the diameter $\mathrm{diam}\left({\mathcal{X}}\right)$ as finite constants.

###### Corollary 3.5 (Upper bound, Lipschitz function) .

Let ${\mathcal{X}}\subset\mathbb{R}^{n}$ be a metric space of finite diameter $\mathrm{diam}\left({\mathcal{X}}\right)$.
For any function class ${\mathcal{F}}\subset[0,1]^{{\mathcal{X}}}$ of $L_{\mathbf{hyp}}$-Lipschitz function and any $L_{\mathbf{los}}$-Lipschitz and convex loss function $\ell$, the minimax expected regret of the transductive online regression satisfies

$$ $R^{\mathbf{tr}}(T,{\mathcal{F}})=\begin{cases}\tilde{\mathcal{O}}\left(L_{\mathbf{los}}\sqrt{L_{\mathbf{hyp}}}\cdot\sqrt{T}\right),&n=1\\ \tilde{\mathcal{O}}\left(L_{\mathbf{los}}L_{\mathbf{hyp}}\cdot\sqrt{T}\right),&n=2\\ \tilde{\mathcal{O}}\left(L_{\mathbf{los}}L_{\mathbf{hyp}}\cdot T^{\frac{n}{n+1}}\right),&n\geq 3\end{cases}.$ $$

That is, the class of Lipschitz functions is transudctive online learnable.

###### Proof.

By [Theorem 3.3](https://arxiv.org/html/2510.03917v1#S3.Thmtheorem3), the minimax expected regret is upper bounded by

$$ $2L_{\mathbf{los}}T\cdot\inf_{\alpha\geq 0}\left(4\alpha+\frac{12}{\sqrt{T}}\int_{\alpha}^{1}\sqrt{\mathrm{fat}_{\beta/4}({\mathcal{F}})\cdot c\log^{2}\frac{T}{\beta}}\mathrm{d}\beta\right).$ $$

Then, since ${\mathcal{F}}$ is a class of $L_{\mathbf{hyp}}$-Lipschitz function, by [Lemma 3.4](https://arxiv.org/html/2510.03917v1#S3.Thmtheorem4) we have

$$ $\mathrm{fat}_{\alpha}({\mathcal{F}})\leq\left(\frac{L_{\mathbf{hyp}}\cdot\mathrm{diam}\left({\mathcal{X}}\right)}{\alpha}\right)^{\mathrm{ddim}\left({\mathcal{X}}\right)},$ $$

where $\mathrm{ddim}\left({\mathcal{X}}\right)\leq n$ is the doubling dimension for the metric space ${\mathcal{X}}\subset\mathbb{R}^{n}$.
Then, for $n=1$, taking $\alpha=\frac{1}{\sqrt{T}}$, the minimax expected regret is upper bounded by

$$ $\mathcal{O}\left(L_{\mathbf{los}}\right)\cdot\left(\sqrt{T}+\sqrt{TL_{\mathbf{hyp}}}\cdot\int_{1/\sqrt{T}}^{1}\frac{1}{\beta^{1/2}}\cdot\sqrt{c}\log\frac{T}{\beta}\mathrm{d}\beta\right)=\tilde{\mathcal{O}}\left(L_{\mathbf{los}}\sqrt{L_{\mathbf{hyp}}}\cdot\sqrt{T}\right).$ $$

Similarly, for $n=2$, taking $\alpha=\frac{1}{\sqrt{T}}$, the minimax expected regret is upper bounded by

$$ $\mathcal{O}\left(L_{\mathbf{los}}\right)\cdot\left(\sqrt{T}+L_{\mathbf{hyp}}\sqrt{T}\cdot\int_{1/\sqrt{T}}^{1}\frac{1}{\beta}\cdot\sqrt{c}\log\frac{T}{\beta}\mathrm{d}\beta\right)=\tilde{\mathcal{O}}\left(L_{\mathbf{los}}L_{\mathbf{hyp}}\cdot\sqrt{T}\right).$ $$

Last, for $n>2$, taking $\alpha=\frac{L_{\mathbf{hyp}}}{T^{1/n}}$, the minimax expected regret is upper bounded by

$$ $\displaystyle\mathcal{O}\left(L_{\mathbf{los}}\right)\cdot\left(\alpha T+\sqrt{T}L_{\mathbf{hyp}}^{\frac{n}{2}}\cdot\int_{\alpha}^{1}\frac{1}{\beta^{\frac{n}{2}}}\cdot\sqrt{c}\log\frac{T}{\beta}\mathrm{d}\beta\right)$ $\displaystyle=$ $\displaystyle~\mathcal{O}\left(L_{\mathbf{los}}\right)\cdot\operatorname*{polylog}(T)\cdot\left(\alpha T+\sqrt{T}L_{\mathbf{hyp}}^{\frac{n}{2}}\cdot\alpha^{1-\frac{n}{2}}\right)=\tilde{\mathcal{O}}\left(L_{\mathbf{los}}L_{\mathbf{hyp}}\cdot T^{\frac{n}{n+1}}\right).$ $$

Thus, we show the desired result.
∎

Note that for Lipschitz classes, the above result does not essentially give us a better rate for transductive online learning, since the sequential fat-shattering dimension of Lipschitz classes are roughly equivalent to their fat-shattering dimension (Rakhlin et al., 2015b).
In contrast, the class of $k$-fold aggregations and the class of functions with bounded variation both have infinite sequential fat-shattering dimension, so they are not online learnable in the worst case. For these classes, our results establishes a separation between online learning and transductive online learning.

###### Theorem 3.4 (See corollary 1 in (Gottlieb et al., 2014 ) ) .

###### Corollary 3.5 (Upper bound, Lipschitz function) .

###### Proof.

#### k k -fold aggregations.

We study the function class induced by $k$-fold aggregation, which is a mapping $G:\mathbb{R}^{k}\to[0,1]$.
Given $k$ function classes ${\mathcal{F}}_{1},\ldots,{\mathcal{F}}_{k}$ in $\mathbb{R}$, the function class defined by $G$ is

$$ $G({\mathcal{F}}_{1},\ldots,{\mathcal{F}}_{k}):=\{x\to G(F_{1}(x),\ldots,F_{k}(x)):F_{\kappa}\in{\mathcal{F}}_{\kappa},\forall\kappa\in[k]\}.$ $$

Let ${\mathbf{e}}$ be the all-one vector.
The mapping $G:\mathbb{R}^{k}\to[0,1]$ commutes with shifts if

$$ $G(v)-r=G(v-r\cdot{\mathbf{e}}),~~~\forall~v\in\mathbb{R}^{k},r\in\mathbb{R}.$ $$

The above property is possessed by many natural aggregation mappings, including the maximum, minimum, median, and mean.
The next statement provides an upper bound on the fat-shattering dimension of $k$-fold aggregations on general function classes.

###### Theorem 3.6 (See Theorem 1 in (Attias and Kontorovich, 2024 ) ) .

Given function classes ${\mathcal{F}}_{1},\ldots,{\mathcal{F}}_{k}$, and an aggregation mapping $G$ that commutes with shifts, we have

$$ $\mathrm{fat}_{\alpha}(G({\mathcal{F}}_{1},\ldots,{\mathcal{F}}_{k}))\leq cd_{\alpha}\log^{2}d_{\alpha},$ $$

where $d_{\alpha}=\sum_{\kappa\in[k]}\mathrm{fat}_{\alpha}({\mathcal{F}}_{\kappa})$ and $c$ is some universal constant.

Now, we compute the minimax expected regret for $k$-fold aggregations in Lipschitz function classes.
Here, we fix the range of function classes to $[0,1]$ for simplicity of calculation.
Indeed, the results hold for all Lipschitz functions with bounded ranges by linear transformation.

###### Corollary 3.7 (Upper bound, $k$ -fold aggregations) .

Let ${\mathcal{X}}\subset\mathbb{R}^{n}$ be a metric space of finite diameter $\mathrm{diam}\left({\mathcal{X}}\right)$.
For any bounded $L_{\mathbf{hyp}}$-Lipschitz function classes ${\mathcal{F}}_{1},\ldots,{\mathcal{F}}_{k}\subset[0,1]^{\mathcal{X}}$, aggregation mapping $G$ that commutes with shifts, and any $L_{\mathbf{los}}$-Lipschitz and convex loss function $\ell$, the minimax expected regret of the transductive online regression for $G({\mathcal{F}}_{1},\ldots,{\mathcal{F}}_{k})$ satisfies

$$ $R^{\mathbf{tr}}(T,G({\mathcal{F}}_{1},\ldots,{\mathcal{F}}_{k}))=\begin{cases}\tilde{\mathcal{O}}\left(\sqrt{k}L_{\mathbf{los}}\sqrt{L_{\mathbf{hyp}}}\cdot\sqrt{T}\right),&n=1\\ \tilde{\mathcal{O}}\left(\sqrt{k}L_{\mathbf{los}}L_{\mathbf{hyp}}\cdot\sqrt{T}\right),&n=2\\ \tilde{\mathcal{O}}\left(\sqrt{k}L_{\mathbf{los}}L_{\mathbf{hyp}}\cdot T^{\frac{n}{n+1}}\right),&n\geq 3\end{cases}.$ $$

That is, the class of $k$-fold aggregations on Lipschitz functions is transudctive online learnable.

###### Proof.

By [Lemma 3.4](https://arxiv.org/html/2510.03917v1#S3.Thmtheorem4), we have for all $\kappa\in[k]$,

$$ $\mathrm{fat}_{\alpha}({\mathcal{F}}_{\kappa})\leq\left(\frac{L_{\mathbf{hyp}}\cdot\mathrm{diam}\left({\mathcal{X}}\right)}{\alpha}\right)^{\mathrm{ddim}\left({\mathcal{X}}\right)}.$ $$

In addition, by [Theorem 3.6](https://arxiv.org/html/2510.03917v1#S3.Thmtheorem6) we have

$$ $\mathrm{fat}_{\alpha}(G({\mathcal{F}}_{1},\ldots,{\mathcal{F}}_{k}))\leq\tilde{\mathcal{O}}\left(k\cdot\left(\frac{L_{\mathbf{hyp}}}{\alpha}\right)^{\mathrm{ddim}\left({\mathcal{X}}\right)}\right).$ $$

Therefore, the upper bounds can be computed using the same analysis as in [Corollary 3.5](https://arxiv.org/html/2510.03917v1#S3.Thmtheorem5).
∎

###### Theorem 3.6 (See Theorem 1 in (Attias and Kontorovich, 2024 ) ) .

###### Corollary 3.7 (Upper bound, k k -fold aggregations) .

###### Proof.

#### Functions with bounded variation.

We consider the class of functions with bounded variation.
Specifically, let ${\mathcal{F}}^{*}$ be the set of all functions $f:[0,1]\to[0,1]$ with total variation of at most $V$.
Here, for a $f\in{\mathcal{F}}^{*}$, we define its total variation as

$$ $\mathrm{TV}(f)=\sup_{p\in P}\sum_{i=0}^{n_{p-1}}|f(x_{i+1})-f(x_{i})|,$ $$

where the supremum is taken over the set $P=\{(x_{0},\ldots,x_{n_{p}}),0\leq x_{1}\leq\cdots\leq x_{n_{p}}\leq 1\}$ of all partitions of $[0,1]$.
For a given parameter $\alpha>0$, we define the metric covering number ${\mathcal{N}}({\mathcal{F}}^{*},\alpha,\mu)$ as the smallest number of sets of radius $\alpha$ under metric $\mu$ whose union contains ${\mathcal{F}}^{*}$.
We remark that this definition is different from our previous definition of a $\ell_{p}$-covering number on a sequence of example $x$.
We introduce it to bound the fat-shattering dimension of the class of bounded variation.
Now, we investigate the covering number under $L_{1}(\mathrm{d}{\mathcal{P}})$ metrics, where ${\mathcal{P}}$ is a probability distribution on $[0,1]$.
The following statement provides an upper bound.

###### Theorem 3.8 (See Theorem 1 in (Bartlett et al., 2006 ) ) .

Let ${\mathcal{F}}^{*}$ be the set of all functions $f:[0,1]\to[0,1]$ with total variation of at most $V$, we have

$$ $\sup_{{\mathcal{P}}}\log_{2}{\mathcal{N}}({\mathcal{F}}^{*},\alpha,L_{1}(\mathrm{d}{\mathcal{P}}))=\frac{12V}{\alpha}.$ $$

The next statement upper bounds the fat-shattering dimension of ${\mathcal{F}}^{*}$ by the covering number.

###### Theorem 3.9 (See Theorem 2 in (Bartlett et al., 2006 ) ) .

Let ${\mathcal{F}}^{*}$ be the set of all functions $f:[0,1]\to[0,1]$ with total variation of at most $V$, we have

$$ $\mathrm{fat}_{4\alpha}({\mathcal{F}}^{*})\leq 32\cdot\sup_{{\mathcal{P}}}\log_{2}{\mathcal{N}}({\mathcal{F}}^{*},\alpha,L_{1}(\mathrm{d}{\mathcal{P}})).$ $$

Note that the fat-shattering dimension of class of functions with bounded variation satisfies $\mathrm{fat}_{\alpha}({\mathcal{F}}^{*})=\mathcal{O}\left(\frac{\mathrm{TV}(f)}{\alpha}\right)$, leading to the minimax expected regret in the following theorem.

###### Corollary 3.10 (Upper bound, bounded variation) .

Let ${\mathcal{F}}^{*}$ be the set of all functions $f:[0,1]\to[0,1]$ with total variation of at most $V$. Let $\ell$ be a $L_{\mathbf{los}}$-Lipschitz loss function.
The minimax expected regret of the transductive online regression for ${\mathcal{F}}^{*}$ under loss $\ell$ satisfies $R^{\mathbf{tr}}(T,{\mathcal{F}}^{*})=\tilde{\mathcal{O}}\left(L_{\mathbf{los}}\cdot\sqrt{VT}\right)$.
That is, the class of functions with bounded variation on $[0,1]$ is transudctive online learnable.

###### Proof.

Combining [Theorem 3.8](https://arxiv.org/html/2510.03917v1#S3.Thmtheorem8) and [Theorem 3.9](https://arxiv.org/html/2510.03917v1#S3.Thmtheorem9), we have that the fat-shattering dimension of ${\mathcal{F}}^{*}$ satisfies

$$ $\mathrm{fat}_{\alpha}({\mathcal{F}}^{*})=\mathcal{O}\left(\frac{V}{\alpha}\right).$ $$

By [Theorem 3.3](https://arxiv.org/html/2510.03917v1#S3.Thmtheorem3), the minimax expected regret is upper bounded by

$$ $2L_{\mathbf{los}}T\cdot\inf_{\alpha\geq 0}\left(4\alpha+\frac{12}{\sqrt{T}}\int_{\alpha}^{1}\sqrt{\mathrm{fat}_{\beta/4}({\mathcal{F}})\cdot c\log^{2}\frac{T}{\beta}}\mathrm{d}\beta\right).$ $$

Then, taking $\alpha=\frac{1}{\sqrt{T}}$, the minimax expected regret is upper bounded by

$$ $\mathcal{O}\left(L_{\mathbf{los}}\right)\cdot\left(\sqrt{T}+\sqrt{VT}\cdot\int_{1/\sqrt{T}}^{1}\frac{1}{\beta^{1/2}}\cdot\sqrt{c}\log\frac{T}{\beta}\mathrm{d}\beta\right)=\tilde{\mathcal{O}}\left(L_{\mathbf{los}}\cdot\sqrt{VT}\right).$ $$

∎

###### Theorem 3.8 (See Theorem 1 in (Bartlett et al., 2006 ) ) .

###### Theorem 3.9 (See Theorem 2 in (Bartlett et al., 2006 ) ) .

###### Corollary 3.10 (Upper bound, bounded variation) .

###### Proof.

### 3.3 Lower Bounds on the Expected Regret

In this section, we complement our results by a lower bound under linear regression loss $\ell(y_{t},\widehat{y_{t}})=|y_{t}-\widehat{y_{t}}|$, showing that the fat-shattering dimension *fully* characterizes the learnability in the transductive online setting.
Our proof is inspired by the hard instance for transductive online binary classification (Hanneke et al., 2023b), where they construct the sequence of example by $k$ copies of sequence $x_{1}^{*},\ldots,x_{d}^{*}$ that is VC-shattered by the function class and then apply the anti-concentration property of Rademacher variables (Khintchine’s inequality).
In our setting, we set $d$ as the fat-shattering dimension.
In addition, we apply the transformation $|a-b|=1-ab$ for $a,b\in[-1,1]$ to effectively apply the definition of $\alpha$-shattering.
The theorem statement is as follows.

###### Theorem 3.11 (Lower bound) .

Let the loss function be $\ell(y_{t},\widehat{y_{t}})=|y_{t}-\widehat{y_{t}}|$.
Then, for any function class ${\mathcal{F}}\subset[0,1]^{{\mathcal{X}}}$, the minimax regret to learn ${\mathcal{F}}$ in the transductive online regression setting satisfies

$$ ${\mathcal{R}}(T,{\mathcal{F}})\geq\sup_{\alpha}\frac{\alpha}{4}\cdot\sqrt{T\cdot\min\{\mathrm{fat}_{\alpha}({\mathcal{F}}),T\}}.$ $$

###### Proof.

Our proof is inspired by the hard instance for transductive online binary classification (Hanneke et al., 2023b), where they construct the sequence of example by $k$ copies of sequence $x_{1}^{*},\ldots,x_{d}^{*}$ that is VC-shattered by the function class and then apply the anti-concentration property of Rademacher variables.

We assume that the label space is $[-1,1]$ for simplicity of computation, which can be obtained by linear transformation.
First, we consider the case when $\mathrm{fat}_{\alpha}({\mathcal{F}})=d<T$, and we assume $T=kd$, where $k$ is an integer.
Let $\{x_{1},\ldots,x_{d}\}$ be a sequence $\alpha$-shattered by ${\mathcal{F}}$.
We define the input sequence of examples to be

$$ $x_{1}^{1},\ldots,x_{1}^{k},x_{2}^{1},\ldots,x_{2}^{k},\ldots x_{d}^{1},\ldots,x_{d}^{k},$ $$

where $x_{i}^{1}=\cdots=x_{i}^{k}=x_{i}$ for each $i\in[d]$.
We define the sequence of labels by generating i.i.d. random Rademacher variables, i.e., $y_{t}\in\{-1,1\}$.
Fix an arbitrary transductive learning algorithm ${\mathcal{A}}$, by the probabilistic method, it suffices to lower bound

$$ $\mathbb{E}_{{\mathcal{A}},y\sim\{-1,1\}^{T}}\left[\sum_{t=1}^{T}|{\mathcal{A}}(x_{t})-y_{t}|-\min_{f\in{\mathcal{F}}}\sum_{t=1}^{T}|f(x_{t})-y_{t}|\right].$ $$

First, note that we generate the random labels $y_{t}$ independently, and so

$$ $\mathbb{E}_{{\mathcal{A}},y\sim\{-1,1\}^{T}}\left[\sum_{t=1}^{T}|{\mathcal{A}}(x_{t})-y_{t}|\right]=T.$ $$

Next, since we have $|a-y_{t}|=1-ay_{t}$ for any $a\in[-1,1]$ and $y_{t}\in[-1,1]$, we have

$$ $\mathbb{E}_{{\mathcal{A}},y\sim\{-1,1\}^{T}}\left[\min_{f\in{\mathcal{F}}}\sum_{t=1}^{T}|f(x_{t})-y_{t}|\right]=T-\mathbb{E}_{y\sim\{-1,1\}^{T}}\left[\max_{f\in{\mathcal{F}}}\sum_{t=1}^{T}f(x_{t})y_{t}\right].$ $$

Therefore, we have

$$ $\mathbb{E}_{{\mathcal{A}},y\sim\{-1,1\}^{T}}\left[|{\mathcal{A}}(x)-y_{t}|-\min_{f\in{\mathcal{F}}}\sum_{t=1}^{T}|f(x_{t})-y_{t}|\right]\geq\mathbb{E}_{y\sim\{-1,1\}^{T}}\left[\max_{f\in{\mathcal{F}}}\sum_{t=1}^{T}f(x_{t})y_{t}\right].$ $$

Let $\{s_{1},\ldots,s_{d}\}$ be the witness of $\alpha$-shattering for set $\{x_{1},\ldots,x_{d}\}$.
Since $\mathbb{E}_{y\sim\{-1,1\}^{T}}\left[\sum_{t=1}^{T}y_{t}s_{\lceil\frac{t}{k}\rceil}\right]=0$, the above quantity is equal to

$$ $\mathbb{E}_{y\sim\{-1,1\}^{T}}\left[\max_{f\in{\mathcal{F}}}\sum_{t=1}^{T}y_{t}(f(x_{t})-s_{\lceil\frac{t}{k}\rceil})\right]=\mathbb{E}_{y\sim\{-1,1\}^{T}}\left[\max_{f\in{\mathcal{F}}}\sum_{i=1}^{d}\sum_{j=1}^{k}y_{i}^{j}(f(x_{i}^{j})-s_{i})\right].$ $$

Let $\sigma_{i}:=\text{sign}(\sum_{j=1}^{k}y_{i}^{j})$, which is the majority vote of the signs $y_{i}^{j}$ in block $i$.
Then, the above quantity is equal to

$$ $\mathbb{E}_{y\sim\{-1,1\}^{T}}\left[\max_{f\in{\mathcal{F}}}\sum_{i=1}^{d}\left|\sum_{j=1}^{k}y_{i}^{j}\right|\sigma_{i}(f(x_{i})-s_{i})\right].$ $$

Due to the definition of $\alpha$-shattering, there exists a function $\bar{f}\in{\mathcal{F}}$ that satisfies $\sigma_{i}(\bar{f}(x_{i})-s_{i})\geq\alpha/2$ for each $i\in[d]$, then we have

$$ $\displaystyle\mathbb{E}_{y\sim\{-1,1\}^{T}}\left[\max_{f\in{\mathcal{F}}}\sum_{i=1}^{d}\left|\sum_{j=1}^{k}y_{i}^{j}\right|\sigma_{i}(f(x_{i})-s_{i})\right]$ $\displaystyle\geq\mathbb{E}_{y\sim\{-1,1\}^{T}}\left[\sum_{i=1}^{d}\left|\sum_{j=1}^{k}y_{i}^{j}\right|\sigma_{i}(\bar{f}(x_{i})-s_{i})\right]$ $\displaystyle\geq\frac{\alpha}{2}\cdot\mathbb{E}_{y\sim\{-1,1\}^{T}}\left[\sum_{i=1}^{d}\left|\sum_{j=1}^{k}y_{i}^{j}\right|\right]$ $\displaystyle=\frac{\alpha d}{2}\cdot\mathbb{E}_{y\sim\{-1,1\}^{k}}\left[\left|\sum_{j=1}^{k}y_{i}^{j}\right|\right].$ $$

Then, by Khintchine’s inequality, we have

$$ $\frac{\alpha d}{2}\cdot\mathbb{E}_{y\sim\{-1,1\}^{k}}\left[\left|\sum_{j=1}^{k}y_{i}^{j}\right|\right]\geq\frac{\alpha d}{2}\cdot\sqrt{\frac{k}{2}}=\frac{\alpha d}{2}\cdot\sqrt{\frac{T}{2d}}=\alpha\cdot\sqrt{\frac{T\cdot\mathrm{fat}_{\alpha}({\mathcal{F}})}{8}}.$ $$

Recall that we assume $T=kd$, now, for a general $T$, we take $T^{\prime}=kd>T/2$ and apply the same analysis as above.
Thus, we have

$$ ${\mathcal{R}}(T,{\mathcal{F}})\geq\sup_{\alpha:\mathrm{fat}_{\alpha}({\mathcal{F}})<T}\frac{\alpha}{4}\cdot\sqrt{T\cdot\mathrm{fat}_{\alpha}({\mathcal{F}})}$ $$

Last, for $\mathrm{fat}_{\alpha}({\mathcal{F}})\geq T$, we take the sequence of examples to be the set $\{x_{1},\ldots,x_{T}\}$ $\alpha$-shattered by ${\mathcal{F}}$ with witness $\{s_{1},\ldots,s_{T}\}$. Then, by the definition of $\alpha$-shattering, we have

$$ $\mathbb{E}_{y\sim\{-1,1\}^{T}}\left[\sum_{t=1}^{T}y_{t}(f(x_{t})-s_{t})\right]\geq\frac{\alpha T}{2}.$ $$

Therefore, we have

$$ $R^{\mathbf{tr}}(T,{\mathcal{F}})\geq\sup_{\alpha}\left(\frac{\alpha}{4}\cdot\sqrt{T\cdot\min\{\mathrm{fat}_{\alpha}({\mathcal{F}}),T\}}\right).$ $$

∎

###### Theorem 3.11 (Lower bound) .

###### Proof.

## 4 Minimax Expected Regret Bounds for Online Regression with Predictions

In this section, we consider the more general online regression with predictions setting. We construct learning algorithms given black-box access to a Predictor ${\mathcal{P}}$ and a transductive online learner ${\mathcal{B}}$.
We compute the minimax expected regret in terms of the quality of ${\mathcal{P}}$ and ${\mathcal{B}}$.

We measure the performance of the Predictor ${\mathcal{P}}$ using two different metrics:

- (1)
Zero-one metric $M_{\mathcal{P}}(x_{1:T})$ which measures the expected number of incorrect predictions $\widehat{x}_{t}\neq x_{t}$, i.e., $M_{{\mathcal{P}}}(x_{1:T}):=\mathbb{E}\left[\sum_{t=2}^{T}{\bf 1}_{{\mathcal{P}}(x_{1:t-1})_{t}\neq x_{t}}\right]$.
- (2)
$\varepsilon$-ball metric $M_{\mathcal{P}}(\varepsilon,x_{1:T})$ which measures the expected number of times that the prediction is outside the $\varepsilon$-ball: ${\mathrm{d}}(\widehat{x}_{t},x_{t})\geq\varepsilon$, where ${\mathrm{d}}$ is the metric on ${\mathcal{X}}$, i.e., $M_{{\mathcal{P}}}(\varepsilon,x_{1:T}):=\mathbb{E}\left[\sum_{t=2}^{T}{\bf 1}_{{\mathrm{d}}({\mathcal{P}}(x_{1:t-1})_{t},x_{t})\geq\varepsilon}\right]$.

Our main result in this section is [Theorem 4.1](https://arxiv.org/html/2510.03917v1#S4.Thmtheorem1), which bounds the minimax expected regret in terms of the mistake-bound of the Predictor and the regret of the transductive online learner.

###### Theorem 4.1 (Online regression with predictions) .

For every function class ${\mathcal{F}}\subset{\mathcal{Y}}^{{\mathcal{X}}}$, Predictor ${\mathcal{P}}$, transductive online learner ${\mathcal{B}}$ and $L_{\mathbf{los}}$-Lipschitz loss function $\ell$, there exists an online learner ${\mathcal{A}}$ such that for every data stream $(x_{1},y_{1}),\ldots,(x_{T},y_{T})$ given by the adversary, the minimax expected regret of ${\mathcal{A}}$ is at most

$$ $\displaystyle\min\Bigg\{$ $\displaystyle\underbrace{R^{\mathbf{ol}}(T,{\mathcal{F}})}_{(a)},\underbrace{2(M_{{\mathcal{P}}}(x_{1:T})+1)R_{{\mathcal{B}}}\left(\frac{T}{M_{{\mathcal{P}}}(x_{1:T})+1}+1,{\mathcal{F}}\right)}_{(b)}\Bigg\}+2\sqrt{T\log T}$ $$

In addition, if the functions in the class are $L_{\mathbf{hyp}}$-Lipschitz, the minimax expected regret is also upper bounded by

$$ $\displaystyle\underbrace{2(M_{{\mathcal{P}}}(\varepsilon,x_{1:T})+1)R_{{\mathcal{B}}}\left(\frac{T}{M_{{\mathcal{P}}}(\varepsilon,x_{1:T})+1}+1,{\mathcal{F}}\right)+\varepsilon L_{\mathbf{los}}L_{\mathbf{hyp}}\cdot T}_{(c)}+2\sqrt{T\log T}.$ $$

We highlight the implications of each error bound.
Firstly, the expected error of our algorithm is at most the worst-case error bound $(a)$ in the online setting.
Secondly, the bound $(b)$ interpolates between the worst-case minimax expected regret and the tranductive online minimax expected regret as a function of $M_{\mathcal{P}}(x_{1:T})$, and when the Predictor is exact, i.e., $M_{\mathcal{P}}(x_{1:T})=0$, we get the same error bound as in the transductive online setting up to constants.
Lastly, the bound $(c)$ relaxes the bounds of the Predictor to the more general $\varepsilon$-ball metric.
Given a Lipschitz function class, our online learner has an expected regret sublinear in $T$ if the Predictor has sufficiently small error scales in terms of $\varepsilon$ and $T$.
In [Section 4.3](https://arxiv.org/html/2510.03917v1#S4.SS3), we explicitly compute the rates in $(b)$ and $(c)$, giving the sufficient conditions on the Predictors to achieve online learnability.
Furthermore, we identify a class of functions with bounded variations that are not online learnable in the worst case but online learnable given desirable Predictors, and we highlight that existing Predictors suffice for the sequence of examples $x_{1:T}$ defined by a linear dynamical system.

###### Theorem 4.1 (Online regression with predictions) .

#### Overview of the algorithms.

We give an overview of our online learners.
Under the zero-one metric $M_{{\mathcal{P}}}(x_{1:T})$, our online learner mainly follows from the construction in (Raman and Tewari, 2024) for online classification.
We suppose that the prediction is incorrect at times $t_{1},\ldots t_{c}\in[T]$ and correct at all other times.
In the first algorithm, whenever ${\mathcal{P}}$ makes a mistake, the learner queries its new sequence of predictions and starts a transductive online learner ${\mathcal{B}}$ to predict $\widehat{y}_{t}$ until the next time ${\mathcal{P}}$ makes a mistake.
This gives an error rate of roughly $M_{{\mathcal{P}}}(x_{1:T})\cdot R^{\mathbf{tr}}_{{\mathcal{B}}}(T,{\mathcal{F}})$.

However, a crucial drawback of this algorithm is that, when $M_{{\mathcal{P}}}(x_{1:T})$ is large (e.g., $\Omega(\sqrt{T})$), the upper bound is suboptimal.
To overcome this, in the second algorithm, we partition the time duration $[T]$ to $c$ equi-distant intervals and run a fresh copy of the first algorithm for each interval.
Then we run MWA using experts with all $c\in[T-1]$ as inputs.
We show that the minimax expected regret for each expert with input $c$ is roughly $(M_{{\mathcal{P}}}(x_{1:T})+c)\cdot R_{{\mathcal{B}}}^{\mathbf{tr}}\left(\frac{T}{c},{\mathcal{F}}\right)$, which is $2M_{{\mathcal{P}}}(x_{1:T})\cdot\bar{R}^{\mathbf{tr}}_{{\mathcal{B}}}\left(\frac{T}{M_{{\mathcal{P}}}(x_{1:T})},{\mathcal{F}}\right)$ for the expert with $c=M_{{\mathcal{P}}}(x_{1:T})$, thus MWA gives an minimax expected regret having $M_{{\mathcal{P}}}(x_{1:T})$ as an interpolation factor and only loses an additive $\sqrt{T\log^{2}T}$ factor, achieving better performance when $M_{{\mathcal{P}}}(x_{1:T})$ is large.
Here, we assume that $R^{\mathbf{tr}}_{{\mathcal{B}}}(T,{\mathcal{F}})$ is a concave function, which can be extended to any sublinear functions by standard results.

Next, we extend the above algorithm for ${\mathcal{P}}$ with the $\varepsilon$-ball metric, which is specific for our regression setting.
Suppose that the prediction is outside the $\varepsilon$-ball at times $t_{1},\ldots t_{c}\in[T]$, i.e., ${\mathrm{d}}({\mathcal{P}}(x_{1:t-1})_{t},x_{t})\geq\varepsilon$ for $t\in\{t_{1},\ldots t_{c}\}$,
then we run a separate transductive online learner ${\mathcal{B}}$ for each duration $t_{j},t_{j}+1\ldots,t_{j+1}$ for $j\in[c]$, i.e., we start a new instance whenever the prediction is outside the $\varepsilon$-ball.
Since the prediction is always inside the $\varepsilon$-ball between $t_{j}$ and $t_{j+1}$, then if the function class is $L$-Lipschitz, our error bound has an additional $\varepsilon LT$ factor.
That is, the minimax expected regret is upper bounded by $M_{{\mathcal{P}}}(\varepsilon,x_{1:T})R_{{\mathcal{B}}}^{\mathbf{tr}}\left(T,{\mathcal{F}}\right)+\varepsilon L_{\mathbf{los}}L_{\mathbf{hyp}}\cdot T$.
We note that this algorithm can also be improved by the equi-distant partition of the time interval and MWA, as discussed earlier
which achieves better performance when $M_{{\mathcal{P}}}(\varepsilon,x_{1:T})$ is large.

The above online learners take $\varepsilon$ as an input, so it is desirable to implement with an $\varepsilon$ that gives the optimal minimax expected regret.
Then, if we know the explicit formula of the measure of predictability $M_{{\mathcal{P}}}(\varepsilon,x_{1:T})$, we can first compute the optimal choice of $\varepsilon$ and then implement the algorithms.
In contrast, when $M_{{\mathcal{P}}}(\varepsilon,x_{1:T})$ have a complicated structure that makes it impossible to identify this $\varepsilon$, we can “guess” the optimal $\varepsilon$ geometrically in the range of $(0,\operatorname*{poly}(T))$.
That is, we run MWA using experts with all $\varepsilon\in\{2^{i},2^{i}<\operatorname*{poly}(T),i\in\mathbb{Z}\}$ as inputs.
This achieves the same asymptotic bound as the optimal $\varepsilon$ when $M_{{\mathcal{P}}}(\varepsilon,x_{1:T})$ has linear or polynomial dependency on $\varepsilon$, ensuring the effectiveness of our algorithm in real-world applications.
Next, we present the explicit minimax expected regret under both metrics, representing the minimax expected regret as a function of the mistake-bounds of the Predictor.

Next, we formally present the online learner under the zero-one metric in [Section 4.1](https://arxiv.org/html/2510.03917v1#S4.SS1); and the online learner under the $\varepsilon$-ball metric in [Section 4.2](https://arxiv.org/html/2510.03917v1#S4.SS2).

### 4.1 Online Learner under Zero-One Metric

In this section, we quantify the performance of a Predictor ${\mathcal{P}}$ as the expected number of mistakes that ${{\mathcal{P}}}$ makes, which is

$$ $M_{{\mathcal{P}}}(x_{1:T}):=\mathbb{E}\left[\sum_{t=2}^{T}{\bf 1}_{{\mathcal{P}}(x_{1:t-1})_{t}\neq x_{t}}\right],$ $$

where we use ${\mathcal{P}}(x_{1:t-1})_{1:T}$ to denote its predictions $\widehat{x_{1:T}}$ given the previous examples $x_{1:t-1}$, and the expectation is taken only over the randomness of ${\mathcal{P}}$.
We make assumptions about the consistency and the laziness of the Predictor ${\mathcal{P}}$ (see Section 2.2 in (Raman and Tewari, 2024)), which are defined below.

###### Definition 4.2 (Consistency) .

For every sequence $x_{1:T}\in{\mathcal{X}}^{T}$ and for each time $t\in[T]$, ${\mathcal{P}}$ is consistent if its prediction $\widehat{x_{1:T}}^{t}$ satisfies ${\mathcal{P}}(x_{1:t})_{1:t}=x_{1:t}$.

The assumption about consistency is natural, since we can hard code the prediction of $x_{1:t}$ to be the input.
Next, we introduce the definition of laziness.

###### Definition 4.3 (Laziness) .

${\mathcal{P}}$ is consistent if its prediction satisfies the following property.
For every sequence $x_{1:T}\in{\mathcal{X}}^{T}$ and for each time $t\in[T]$, if ${\mathcal{P}}(x_{1:t-1})_{t}=x_{t}$, then ${\mathcal{P}}(x_{1:t})={\mathcal{P}}(x_{1:t-1})$. That is, ${\mathcal{P}}$ does not change its prediction if it is correct.

The assumption about laziness is also mild, since non-lazy online Predictors can be converted into lazy ones (Littlestone, 1989).
Recall that we suppose that ${\mathcal{P}}$ makes mistakes at times $t_{1},\ldots t_{c}\in[T]$, due to the assumption of laziness and consistency, the predictions of ${\mathcal{P}}$ between $t_{j}$ and $t_{j+1}$ are correct and unchanged for all $j\in[c]$.
Thus, whenever we detect a mistake, we notify ${\mathcal{P}}$ and retrieve its new sequence of predictions, and we initialize a new transductive online learner ${\mathcal{B}}$ with the new predictions
Our algorithm is presented in [Algorithm 2](https://arxiv.org/html/2510.03917v1#alg2).

Figure: Algorithm 2 Online Learner with Prediction

The next statement upper bounds the expected error of [Algorithm 2](https://arxiv.org/html/2510.03917v1#alg2).

###### Lemma 4.4 (Analogous to Lemma 20 in (Raman and Tewari, 2024 ) ) .

Given a Predictor ${\mathcal{P}}$ and an transductive online learner ${\mathcal{B}}$, for any function class ${\mathcal{F}}\subset{\mathcal{Y}}^{{\mathcal{X}}}$, loss function $\ell$, and data stream $(x_{1},y_{1}),\ldots,(x_{T},y_{T})$, the minimax expected regret of [Algorithm 2](https://arxiv.org/html/2510.03917v1#alg2) is bounded by $(M_{{\mathcal{P}}}(x_{1:T})+1)R^{\mathbf{tr}}_{{\mathcal{B}}}(T,{\mathcal{F}})$.

###### Proof.

The proof is similar to (Raman and Tewari, 2024), we keep it here for completeness.
Let ${\mathcal{A}}$ be the learner in [Algorithm 2](https://arxiv.org/html/2510.03917v1#alg2).
Let $c$ be the random variable that denotes the total number of mistakes made by ${\mathcal{P}}$, and let $t_{1},\ldots,t_{c}$ be the random time points at which these errors occur.
Without loss of generality, we assume $c>0$, since otherwise, due to the consistency and laziness of ${\mathcal{P}}$ (see [Definition 4.2](https://arxiv.org/html/2510.03917v1#S4.Thmtheorem2) and [Definition 4.3](https://arxiv.org/html/2510.03917v1#S4.Thmtheorem3)), ${\mathcal{P}}(x_{1:1})=x_{1:T}$ for every $t\in[T]$.
Thus, we only run one transductive online learner ${\mathcal{B}}^{1}$, and so the regret is at most $R^{\mathbf{tr}}_{{\mathcal{B}}}(T,{\mathcal{F}})$.

Now, we partition the sequence of time points into disjoint intervals $(t_{0},\ldots,t_{1}-1),(t_{1},\ldots,t_{2}-1),\ldots,(t_{c},\ldots,t_{c+1}-1)$, where $t_{0}:=1$ and $t_{c+1}-1:=T$.
Fix an arbitrary $i\in[c]$.
Due to our algorithm construction, for each $j\in\{t_{i},\ldots,t_{i+1}-1\}$, we have ${\mathcal{P}}(x_{1:j})_{1:t_{i+1}-1}=x_{1:t_{i+1}-1}$.
Thus, the transductive online learner ${\mathcal{B}}_{i}$ is applied in the example stream

$$ $x_{t_{i}},\ldots,x_{t_{i+1}-1},{\mathcal{P}}(x_{1:t_{i}})_{t_{i+1}},\ldots,{\mathcal{P}}(x_{1:t_{i}})_{t_{T}}.$ $$

Let $h^{i}\in\operatorname*{argmin}_{f\in{\mathcal{F}}}\sum_{t=t_{i}}^{t_{i+1}-1}\ell(f(x_{t}),y_{t})$ be an optimal function for duration $(t_{i},\ldots,t_{i+1}-1)$.
Let $y_{t}^{i}=y_{t}$ for all $t_{i}\leq t\leq t_{i+1}-1$ and $y_{t}^{i}=h^{i}({\mathcal{P}}(x_{1:t_{i}})_{t})$ for all $t\geq t_{i+1}$.
Then, we observe that

$$ $\inf_{f\in{\mathcal{F}}}\sum_{t_{i}}^{T}\ell(f({\mathcal{P}}(x_{1:t_{i}})_{t}),y_{t}^{i})=\sum_{t=t_{i}}^{t_{i+1}-1}\ell(h^{i}(x_{t}),y_{t})=\inf_{f\in{\mathcal{F}}}\sum_{t=t_{i}}^{t_{i+1}-1}\ell(f(x_{t}),y_{t}).$ $$

Next, we consider the hypothetical labeled stream

$$ ${\mathcal{S}}=(x_{t_{i}},y_{t_{i}}^{i}),\ldots,(x_{t_{i+1}-1},y_{t_{i+1}-1}^{i}),({\mathcal{P}}(x_{1:t_{i}})_{t_{i+1}},y_{t_{i+1}}^{i})\ldots,({\mathcal{P}}(x_{1:t_{i}})_{t_{T}},y_{T}^{i})$ $$

Then, from the definition of the minimax expected regret $R^{\mathbf{tr}}_{{\mathcal{B}}}(T,{\mathcal{F}})$, the expected loss ${\mathcal{B}}^{i}$ has in the stream $S$ is at most

$$ $R_{{\mathcal{B}}}^{\mathbf{tr}}(T-t_{i}+1,{\mathcal{F}})+\inf_{f\in{\mathcal{F}}}\sum_{t_{i}}^{T}\ell(f({\mathcal{P}}(x_{1:t_{i}})_{t}),y_{t}^{i})=R_{{\mathcal{B}}}^{\mathbf{tr}}(T-t_{i}+1,{\mathcal{F}})+\inf_{f\in{\mathcal{F}}}\sum_{t=t_{i}}^{t_{i+1}-1}\ell(f(x_{t}),y_{t}).$ $$

Thus, ${\mathcal{A}}$ has loss at most $R^{\mathbf{tr}}_{{\mathcal{B}}}(T,{\mathcal{F}})+\inf_{f\in{\mathcal{F}}}\sum_{t=t_{i}}^{t_{i+1}-1}\ell(f(x_{t}),y_{t})$ during $(t_{i},t_{i+1}-1)$ in expectation.
Then, we have

$$ $\displaystyle\mathbb{E}\left[\sum_{t=1}^{T}\ell({\mathcal{A}}_{t},h^{*}(x_{t}))\right]$ $\displaystyle=\sum_{i=0}^{c}\left(\mathbb{E}\left[\sum_{t=t_{i}}^{t_{i+1}-1}\ell({\mathcal{A}}_{t},h^{*}(x_{t}))\right]\right)$ $\displaystyle\leq\sum_{i=0}^{c}\left(R^{\mathbf{tr}}_{{\mathcal{B}}}(T,{\mathcal{F}})+\inf_{f\in{\mathcal{F}}}\sum_{t=t_{i}}^{t_{i+1}-1}\ell(f(x_{t}),y_{t})\right)$ $\displaystyle\leq(c+1)R^{\mathbf{tr}}_{{\mathcal{B}}}(T,{\mathcal{F}})+\inf_{f\in{\mathcal{F}}}\sum_{t=1}^{T}\ell(f(x_{t}),y_{t}),$ $$

where the expectation is only on the randomness of each ${\mathcal{B}}^{i}$.
Last, since $\mathbb{E}\left[c\right]=M_{{\mathcal{P}}}(x_{1:T})$, taking an outer expectation of the randomness of ${\mathcal{P}}$, we show that the minimax expected regret of ${\mathcal{A}}$ is at most $(M_{{\mathcal{P}}}(x_{1:T})+1)R^{\mathbf{tr}}_{{\mathcal{B}}}(T,{\mathcal{F}})$.
∎

We next provide the online learner by partitioning the time-interval and applying MWA, which has better expected regret when the predictions are inaccurate.
We present the algorithm for each expert in [Algorithm 3](https://arxiv.org/html/2510.03917v1#alg3) and MWA in [Algorithm 4](https://arxiv.org/html/2510.03917v1#alg4).
Before introducing the error bound, we state a lemma that upper bounds a positive sublinear function with countable domain by a concave sublinear function.
We use this result to upper bound the transductive online regret $R^{\mathbf{tr}}_{{\mathcal{B}}}(T,{\mathcal{F}})$ by a concave sublinear function $\bar{R}^{\mathbf{tr}}_{{\mathcal{B}}}(T,{\mathcal{F}})$.

###### Lemma 4.5 (see Lemma 5.17 in (Ceccherini-Silberstein et al., 2017 ) ) .

Let $g:\mathbb{Z}_{+}\to\mathbb{R}_{+}$ be a positive sublinear function. Then $g$ is bounded from above by a concave sublinear function $\bar{g}:\mathbb{R}_{+}\to\mathbb{R}_{+}$.

Figure: Algorithm 3 Expert$(c)$

Figure: Algorithm 4 Online Learner with Prediction

Next, we compute the minimax expected regret of [Algorithm 4](https://arxiv.org/html/2510.03917v1#alg4).

###### Lemma 4.6 (Analogous to bound(ii) in Theorem 16 in (Raman and Tewari, 2024 ) ) .

Given a Predictor ${\mathcal{P}}$ and an transductive online learner ${\mathcal{B}}$, for any function class ${\mathcal{F}}\subset{\mathcal{Y}}^{{\mathcal{X}}}$, loss function $\ell$, and data stream $(x_{1},y_{1}),\ldots,(x_{T},y_{T})$, the minimax expected regret of [Algorithm 4](https://arxiv.org/html/2510.03917v1#alg4) is bounded by

$$ $2(M_{{\mathcal{P}}}(x_{1:T})+1)\bar{R}^{\mathbf{tr}}_{{\mathcal{B}}}\left(\frac{T}{M_{{\mathcal{P}}}(x_{1:T})+1}+1,{\mathcal{F}}\right)+\sqrt{T\log T}.$ $$

###### Proof.

We note that it suffices to show that the minimax expected regret of the expert $c$ is at most $(M_{{\mathcal{P}}}(x_{1:T})+c+1)\bar{R}^{\mathbf{tr}}_{{\mathcal{B}}}\left(\frac{T}{c+1}+1,{\mathcal{F}}\right)$ for every $c\in[T-1]$, then by the guarantee of MWA (see [Theorem 3.1](https://arxiv.org/html/2510.03917v1#S3.Thmtheorem1)), we have our desired upper bound taking $c=\lceil M_{{\mathcal{P}}}(x_{1:T})\rceil$.

Now, we fix a $c\in[T-1]$. Let $\tilde{t}_{j}=j\left\lceil\frac{T}{c+1}\right\rceil$ for each $j\in[c],\tilde{t}_{0}=0$, and $\tilde{t}_{c+1}=T$. Let ${\mathcal{E}}$ denote the expert with input $c$ in [Algorithm 3](https://arxiv.org/html/2510.03917v1#alg3), then we have

$$ $\mathbb{E}\left[\sum_{i=1}^{T}\ell({\mathcal{E}}(x_{t}),y_{t})\right]=\mathbb{E}\left[\sum_{j=0}^{c}\sum_{t=\tilde{t}_{j}+1}^{\tilde{t}_{j+1}}\ell({\mathcal{A}}^{j}(x_{t}),y_{t})\right],$ $$

where ${\mathcal{A}}^{j}$ is the learner with time duration $[\tilde{t}_{j}+1,\tilde{t}_{j+1}]$.
Let $m_{i}$ be the number of mistakes that Predictor ${\mathcal{P}}$ makes in ${\mathcal{A}}^{j}$.
Then, by the bound in [Lemma 4.4](https://arxiv.org/html/2510.03917v1#S4.Thmtheorem4), we have

$$ $\displaystyle\mathbb{E}\left[\sum_{i=1}^{T}\ell({\mathcal{E}}(x_{t}),y_{t})\right]$ $\displaystyle\leq\mathbb{E}\left[\sum_{j=1}^{c}(m_{j}+1)\bar{R}^{\mathbf{tr}}_{{\mathcal{B}}}(\tilde{t}_{j+1}-\tilde{t}_{j},{\mathcal{F}})+\inf_{f\in{\mathcal{F}}}\sum_{t=\tilde{t}_{j}+1}^{\tilde{t}_{j+1}}\ell(f(x_{t}),y_{t})\right]$ $\displaystyle\leq\mathbb{E}\left[\sum_{j=1}^{c}(m_{j}+1)\bar{R}^{\mathbf{tr}}_{{\mathcal{B}}}(\tilde{t}_{j+1}-\tilde{t}_{j},{\mathcal{F}})\right]+\inf_{f\in{\mathcal{F}}}\sum_{t=1}^{T}\ell(f(x_{t}),y_{t}).$ $$

Then, it suffices to bound the first term $\mathbb{E}\left[\sum_{j=1}^{c}(m_{j}+1)\bar{R}^{\mathbf{tr}}_{{\mathcal{B}}}(\tilde{t}_{j+1}-\tilde{t}_{j},{\mathcal{F}})\right]$ by $(M_{{\mathcal{P}}}(x_{1:T})+c+1)\bar{R}^{\mathbf{tr}}_{{\mathcal{B}}}(\frac{T}{c+1}+1,{\mathcal{F}})$.
Note that $\bar{R}^{\mathbf{tr}}_{{\mathcal{B}}}(T,{\mathcal{F}})$ is a concave function in $T$ by our construction, then by Jensen’s inequality, we have

$$ $\mathbb{E}\left[\sum_{j=1}^{c}(m_{j}+1)\bar{R}^{\mathbf{tr}}_{{\mathcal{B}}}(\tilde{t}_{j+1}-\tilde{t}_{j},{\mathcal{F}})\right]\leq\mathbb{E}\left[\left(\sum_{j=1}^{c}(m_{j}+1)\right)\cdot\bar{R}^{\mathbf{tr}}_{{\mathcal{B}}}\left(\frac{\sum_{j=1}^{c}(m_{j}+1)(\tilde{t}_{j+1}-\tilde{t}_{j})}{\sum_{j=1}^{c}(m_{j}+1)},{\mathcal{F}}\right)\right].$ $$

Let $M=\sum_{j=1}^{c}m_{j}$ such that $\mathbb{E}\left[M\right]=M_{{\mathcal{P}}}(x_{1:T})$, then we have

$$ $\frac{\sum_{j=1}^{c}(m_{j}+1)(\tilde{t}_{j+1}-\tilde{t}_{j})}{\sum_{j=1}^{c}(m_{j}+1)}=\frac{T+\sum_{j=1}^{c}(m_{j})(\tilde{t}_{j+1}-\tilde{t}_{j})}{M+c+1}=\frac{T+\sum_{j=1}^{c}m_{j}\cdot\left\lceil\frac{T}{c+1}\right\rceil}{M+c+1},$ $$

where the last step follows from our definition of $\tilde{t}_{j}=\left\lceil\frac{T}{c+1}\right\rceil$.
Then, we have

$$ $\frac{\sum_{j=1}^{c}(m_{j}+1)(\tilde{t}_{j+1}-\tilde{t}_{j})}{\sum_{j=1}^{c}(m_{j}+1)}=\frac{T+M\cdot\left\lceil\frac{T}{c+1}\right\rceil}{M+c+1}\leq\frac{T}{c+1}+1.$ $$

Therefore, we have

$$ $\displaystyle\mathbb{E}\left[\sum_{j=1}^{c}(m_{j}+1)\bar{R}^{\mathbf{tr}}_{{\mathcal{B}}}(\tilde{t}_{j+1}-\tilde{t}_{j},{\mathcal{F}})\right]$ $\displaystyle\leq\mathbb{E}\left[\left(M+c+1\right)\cdot\bar{R}^{\mathbf{tr}}_{{\mathcal{B}}}\left(\frac{T}{c+1}+1,{\mathcal{F}}\right)\right]$ $\displaystyle=\left(M_{{\mathcal{P}}}(x_{1:T})+c+1\right)\cdot\bar{R}^{\mathbf{tr}}_{{\mathcal{B}}}\left(\frac{T}{c+1}+1,{\mathcal{F}}\right).$ $$

This proves our desired bound.
∎

###### Definition 4.2 (Consistency) .

###### Definition 4.3 (Laziness) .

###### Lemma 4.4 (Analogous to Lemma 20 in (Raman and Tewari, 2024 ) ) .

###### Proof.

###### Lemma 4.5 (see Lemma 5.17 in (Ceccherini-Silberstein et al., 2017 ) ) .

###### Lemma 4.6 (Analogous to bound(ii) in Theorem 16 in (Raman and Tewari, 2024 ) ) .

###### Proof.

### 4.2 Online Learner under ε \varepsilon -Ball Metric

In this section, we quantify the performance of a Predictor ${\mathcal{P}}$ as the expected number of times that its prediction ${{\mathcal{P}}}$ is outside the $\varepsilon$-ball of the real input $x_{t}$.
Consider a metric space $({\mathcal{X}},{\mathrm{d}})$ of examples, the $\varepsilon$-ball of a $x\in{\mathcal{X}}$ is $B(x):=\{x^{\prime}\in{\mathcal{X}},{\mathrm{d}}(x^{\prime},x)<\varepsilon\}$.
Then, our $\varepsilon$-ball metric for the Predictor is defined as

$$ $M_{{\mathcal{P}}}(\varepsilon,x_{1:T}):=\mathbb{E}\left[\sum_{t=2}^{T}{\bf 1}_{{\mathrm{d}}({\mathcal{P}}(x_{1:t-1})_{t},x_{t})\geq\varepsilon}\right],$ $$

where the expectation is taken only over the randomness of ${\mathcal{P}}$.
We extend the notion of laziness from the previous sections in the sense of $\varepsilon$-ball.

###### Definition 4.7 (Laziness) .

${\mathcal{P}}$ is consistent if its prediction satisfies the following property.
For every sequence $x_{1:T}\in{\mathcal{X}}^{T}$ and for each time $t\in[T]$, if ${\mathrm{d}}({\mathcal{P}}(x_{1:t-1})_{t},x_{t})\leq\varepsilon$, then ${\mathcal{P}}(x_{1:t})={\mathcal{P}}(x_{1:t-1})$. That is, ${\mathcal{P}}$ does not change its prediction if it is inside the $\varepsilon$-ball.

We extend [Algorithm 2](https://arxiv.org/html/2510.03917v1#alg2) to construct an online learner under the $\varepsilon$-ball metric, as shown in [Algorithm 5](https://arxiv.org/html/2510.03917v1#alg5).

Figure: Algorithm 5 Online Learner with Prediction

We upper bound the minimax expected regret of [Algorithm 5](https://arxiv.org/html/2510.03917v1#alg5) in the next lemma.

###### Lemma 4.8 .

Given a Predictor ${\mathcal{P}}$ and an transductive online learner ${\mathcal{B}}$, for any function class ${\mathcal{F}}\subset{\mathcal{Y}}^{{\mathcal{X}}}$ of $L_{\mathbf{hyp}}$-Lipschitz function, $L_{\mathbf{los}}$-Lipschitz loss function $\ell$, and data stream $(x_{1},y_{1}),\ldots,(x_{T},y_{T})$, the minimax expected regret of [Algorithm 5](https://arxiv.org/html/2510.03917v1#alg5) is bounded by $(M_{{\mathcal{P}}}(\varepsilon,x_{1:T})+1)R^{\mathbf{tr}}_{{\mathcal{B}}}(T,{\mathcal{F}})+\varepsilon L_{\mathbf{los}}L_{\mathbf{hyp}}\cdot T$.

###### Proof.

This proof is extended from [Lemma 4.4](https://arxiv.org/html/2510.03917v1#S4.Thmtheorem4).
Let ${\mathcal{A}}$ be the learner in [Algorithm 5](https://arxiv.org/html/2510.03917v1#alg5).
Let $c$ be the random variable denoting the total number of times that the prediction is outside the $\varepsilon$-ball, and let $t_{1},\ldots,t_{c}$ be the random time points at which these errors occur.

First, we consider the case that $c=0$, then due to the laziness of ${\mathcal{P}}$ (see [Definition 4.7](https://arxiv.org/html/2510.03917v1#S4.Thmtheorem7)), $|{\mathcal{P}}(x_{1:1})_{t}-x_{t}|\leq\varepsilon$ for every $t\in[T]$.
Thus, we only run one transductive online learner ${\mathcal{B}}^{1}$, and so we have

$$ $\mathbb{E}\left[\sum_{t=1}^{T}\ell({\mathcal{A}}_{t},y_{t})\right]=\mathbb{E}\left[\sum_{t=1}^{T}\ell({\mathcal{B}}^{1}({\mathcal{P}}(x_{1:1})_{t}),y_{t})\right]\leq\inf_{f\in{\mathcal{F}}}\left(\sum_{t=1}^{T}\ell(f({\mathcal{P}}(x_{1:1})_{t}),y_{t})\right)+R^{\mathbf{tr}}_{{\mathcal{B}}}(T,{\mathcal{F}}).$ $$

Since we assume that ${\mathcal{F}}$ is a class of $L_{\mathbf{hyp}}$-Lipschitz function, we have for each $f\in{\mathcal{F}}$ and $t\in[T]$, $|f({\mathcal{P}}(x_{1:1})_{t})-f(x_{t})|\leq\varepsilon L_{\mathbf{hyp}}$.
Additionally, since we also assume that the loss function is $L_{\mathbf{los}}$-Lipschitz, we have for each $f\in{\mathcal{F}}$ and $t\in[T]$, $|\ell(f({\mathcal{P}}(x_{1:1})_{t}),y_{t})-\ell(f(x_{t}),y_{t})|\leq\varepsilon L_{\mathbf{los}}L_{\mathbf{hyp}}$.
Therefore, we have

$$ $\inf_{f\in{\mathcal{F}}}\left(\sum_{t=1}^{T}\ell(f({\mathcal{P}}(x_{1:1})_{t}),y_{t})\right)\leq\inf_{f\in{\mathcal{F}}}\left(\sum_{t=1}^{T}\ell(f(x_{t}),y_{t})\right)+\varepsilon L_{\mathbf{los}}L_{\mathbf{hyp}}\cdot T.$ $$

Thus, the minimax expected regret of ${\mathcal{A}}$ is at most $R^{\mathbf{tr}}_{{\mathcal{B}}}(T,{\mathcal{F}})+\varepsilon L_{\mathbf{los}}L_{\mathbf{hyp}}\cdot T$.

Next, we consider the case that $c>0$. We partition the sequence of time points into disjoint intervals $(t_{0},\ldots,t_{1}-1),(t_{1},\ldots,t_{2}-1),\ldots,(t_{c},\ldots,t_{c+1}-1)$, where $t_{0}:=1$ and $t_{c+1}-1:=T$.
Fix an arbitrary $i\in[c]$.
By our algorithm construction, the transductive online learner ${\mathcal{B}}_{i}$ is applied in the example stream ${\mathcal{P}}(x_{1:t_{i}})_{t_{i}},\ldots,{\mathcal{P}}(x_{1:t_{i}})_{t_{T}}$.
Let $h^{i}\in\operatorname*{argmin}_{f\in{\mathcal{F}}}\sum_{t=t_{i}}^{t_{i+1}-1}\ell(f({\mathcal{P}}(x_{1:t_{i}})_{t}),y_{t})$ be an optimal function for duration $(t_{i},\ldots,t_{i+1}-1)$.
Let $y_{t}^{i}=y_{t}$ for all $t_{i}\leq t\leq t_{i+1}-1$ and $y_{t}^{i}=h^{i}({\mathcal{P}}(x_{1:t_{i}})_{t})$ for all $t\geq t_{i+1}$.
Then we observe that

$$ $\inf_{f\in{\mathcal{F}}}\sum_{t_{i}}^{T}\ell(f({\mathcal{P}}(x_{1:t_{i}})_{t}),y_{t}^{i})=\sum_{t=t_{i}}^{t_{i+1}-1}\ell(h^{i}({\mathcal{P}}(x_{1:t_{i}})_{t}),y_{t})=\inf_{f\in{\mathcal{F}}}\sum_{t=t_{i}}^{t_{i+1}-1}\ell(f({\mathcal{P}}(x_{1:t_{i}})_{t}),y_{t}).$ $$

Next, we consider the hypothetical labeled stream

$$ ${\mathcal{S}}=({\mathcal{P}}(x_{1:t_{i}})_{t_{i}},y_{t_{i+1}}^{i})\ldots,({\mathcal{P}}(x_{1:t_{i}})_{t_{T}},y_{T}^{i})$ $$

Then, from the definition of the minimax expected regret $R^{\mathbf{tr}}_{{\mathcal{B}}}(T,{\mathcal{F}})$, the expected loss ${\mathcal{B}}^{i}$ has in the stream $S$ is at most

$$ $R_{{\mathcal{B}}}^{\mathbf{tr}}(T-t_{i}+1,{\mathcal{F}})+\inf_{f\in{\mathcal{F}}}\sum_{t_{i}}^{T}\ell(f({\mathcal{P}}(x_{1:t_{i}})_{t}),y_{t}^{i})=R_{{\mathcal{B}}}^{\mathbf{tr}}(T-t_{i}+1,{\mathcal{F}})+\inf_{f\in{\mathcal{F}}}\sum_{t=t_{i}}^{t_{i+1}-1}\ell(f({\mathcal{P}}(x_{1:t_{i}})_{t}),y_{t}).$ $$

Now, since we use the same Predictor ${\mathcal{P}}$ during $(t_{i},t_{i+1}-1)$, which means that ${\mathrm{d}}({\mathcal{P}}(x_{1:t_{i}})_{t},x_{t})\leq\varepsilon$ for every $t\in(t_{i},t_{i+1}-1)$.
Then, by a similar Lipschitz argument, we have

$$ $\inf_{f\in{\mathcal{F}}}\left(\sum_{t=t_{i}}^{t_{i+1}-1}\ell(f({\mathcal{P}}(x_{1:t_{i}})_{t}),y_{t})\right)\leq\inf_{f\in{\mathcal{F}}}\left(\sum_{t=t_{i}}^{t_{i+1}-1}\ell(f(x_{t}),y_{t})\right)+\varepsilon L_{\mathbf{los}}L_{\mathbf{hyp}}\cdot(t_{i+1}-t_{i}).$ $$

Therefore, ${\mathcal{A}}$ has loss at most $R^{\mathbf{tr}}_{{\mathcal{B}}}(T,{\mathcal{F}})+\inf_{f\in{\mathcal{F}}}\left(\sum_{t=t_{i}}^{t_{i+1}-1}\ell(f(x_{t}),y_{t})\right)+\varepsilon L_{\mathbf{los}}L_{\mathbf{hyp}}\cdot(t_{i+1}-t_{i})$ during $(t_{i},t_{i+1}-1)$ in expectation.
Then, we have

$$ $\displaystyle\mathbb{E}\left[\sum_{t=1}^{T}\ell({\mathcal{A}}_{t},h^{*}(x_{t}))\right]$ $\displaystyle=\sum_{i=0}^{c}\left(\mathbb{E}\left[\sum_{t=t_{i}}^{t_{i+1}-1}\ell({\mathcal{A}}_{t},h^{*}(x_{t}))\right]\right)$ $\displaystyle\leq\sum_{i=0}^{c}\left(R^{\mathbf{tr}}_{{\mathcal{B}}}(T,{\mathcal{F}})+\inf_{f\in{\mathcal{F}}}\left(\sum_{t=t_{i}}^{t_{i+1}-1}\ell(f(x_{t}),y_{t})\right)+\varepsilon L_{\mathbf{los}}L_{\mathbf{hyp}}\cdot(t_{i+1}-t_{i})\right)$ $\displaystyle\leq(c+1)R^{\mathbf{tr}}_{{\mathcal{B}}}(T,{\mathcal{F}})+\inf_{f\in{\mathcal{F}}}\left(\sum_{t=1}^{T}\ell(f(x_{t}),y_{t})\right)+\varepsilon L_{\mathbf{los}}L_{\mathbf{hyp}}T,$ $$

where the expectation is only on the randomness of each ${\mathcal{B}}^{i}$.
Last, since $\mathbb{E}\left[c\right]=M_{{\mathcal{P}}}(\varepsilon,x_{1:T})$, taking an outer expectation of the randomness of ${\mathcal{P}}$, we show that the minimax expected regret of ${\mathcal{A}}$ is at most $(M_{{\mathcal{P}}}(\varepsilon,x_{1:T})+1)R^{\mathbf{tr}}_{{\mathcal{B}}}(T,{\mathcal{F}})+\varepsilon L_{\mathbf{los}}L_{\mathbf{hyp}}T$.
∎

Next, we extend [Algorithm 4](https://arxiv.org/html/2510.03917v1#alg4) under the notion of $\varepsilon$-ball metric, where we construct each expert by the subroutine in [Algorithm 5](https://arxiv.org/html/2510.03917v1#alg5).
The algorithm is presented in [Algorithm 6](https://arxiv.org/html/2510.03917v1#alg6).

Figure: Algorithm 6 Online Learner with Prediction

The following statement bounds the minimax expected regret of [Algorithm 6](https://arxiv.org/html/2510.03917v1#alg6).

###### Lemma 4.9 .

Given a Predictor ${\mathcal{P}}$ and an transductive online learner ${\mathcal{B}}$, for any function class ${\mathcal{F}}\subset{\mathcal{Y}}^{{\mathcal{X}}}$ of $L_{\mathbf{hyp}}$-Lipschitz function, $L_{\mathbf{los}}$-Lipschitz loss function $\ell$, and data stream $(x_{1},y_{1}),\ldots,(x_{T},y_{T})$, the minimax expected regret of [Algorithm 6](https://arxiv.org/html/2510.03917v1#alg6) is bounded by

$$ $2(M_{{\mathcal{P}}}(\varepsilon,x_{1:T})+1)\bar{R}^{\mathbf{tr}}_{{\mathcal{B}}}\left(\frac{T}{M_{{\mathcal{P}}}(\varepsilon,x_{1:T})+1}+1,{\mathcal{F}}\right)+\varepsilon L_{\mathbf{los}}L_{\mathbf{hyp}}\cdot T+\sqrt{T\log T}.$ $$

###### Proof.

This proof is an extension of the proof of [Lemma 4.6](https://arxiv.org/html/2510.03917v1#S4.Thmtheorem6).
We note that it suffices to show that the minimax expected regret of the expert $c$ is at most $(M_{{\mathcal{P}}}(\varepsilon,x_{1:T})+c+1)\bar{R}^{\mathbf{tr}}_{{\mathcal{B}}}\left(\frac{T}{c+1}+1,{\mathcal{F}}\right)+\varepsilon L_{\mathbf{los}}L_{\mathbf{hyp}}\cdot T$ for every $c\in[T-1]$, then by the guarantee of MWA (see [Theorem 3.1](https://arxiv.org/html/2510.03917v1#S3.Thmtheorem1)), we have our desired upper bound taking $c=\lceil M_{{\mathcal{P}}}(\varepsilon,x_{1:T})\rceil$.

Now, we fix a $c\in[T-1]$. Let $\tilde{t}_{j}=j\left\lceil\frac{T}{c+1}\right\rceil$ for each $j\in[c],\tilde{t}_{0}=0$, and $\tilde{t}_{c+1}=T$. Let ${\mathcal{E}}$ denote the expert with input $c$ in [Algorithm 3](https://arxiv.org/html/2510.03917v1#alg3), then we have

$$ $\mathbb{E}\left[\sum_{i=1}^{T}\ell({\mathcal{E}}(x_{t}),y_{t})\right]=\mathbb{E}\left[\sum_{j=0}^{c}\sum_{t=\tilde{t}_{j}+1}^{\tilde{t}_{j+1}}\ell({\mathcal{A}}^{j}(x_{t}),y_{t})\right],$ $$

where ${\mathcal{A}}^{j}$ is the learner with time duration $[\tilde{t}_{j}+1,\tilde{t}_{j+1}]$.
Let $m_{i}$ be the number of mistakes that Predictor ${\mathcal{P}}$ makes in ${\mathcal{A}}^{j}$.
Then, by the bound in [Lemma 4.8](https://arxiv.org/html/2510.03917v1#S4.Thmtheorem8), we have the expected loss of ${\mathcal{E}}$ is at most

$$ $\displaystyle\mathbb{E}\left[\sum_{j=1}^{c}\left((m_{j}+1)\bar{R}^{\mathbf{tr}}_{{\mathcal{B}}}(\tilde{t}_{j+1}-\tilde{t}_{j},{\mathcal{F}})+\inf_{f\in{\mathcal{F}}}\left(\sum_{t=\tilde{t}_{j}+1}^{\tilde{t}_{j+1}}\ell(f(x_{t}),y_{t})\right)+\varepsilon L_{\mathbf{los}}L_{\mathbf{hyp}}\cdot(\tilde{t}_{j+1}-\tilde{t}_{j})\right)\right]$ $\displaystyle\leq~$ $\displaystyle\mathbb{E}\left[\sum_{j=1}^{c}(m_{j}+1)\bar{R}^{\mathbf{tr}}_{{\mathcal{B}}}(\tilde{t}_{j+1}-\tilde{t}_{j},{\mathcal{F}})\right]+\inf_{f\in{\mathcal{F}}}\left(\sum_{t=1}^{T}\ell(f(x_{t}),y_{t})\right)+\varepsilon L_{\mathbf{los}}L_{\mathbf{hyp}}\cdot T.$ $$

From the analysis of [Lemma 4.6](https://arxiv.org/html/2510.03917v1#S4.Thmtheorem6), we have

$$ $\mathbb{E}\left[\sum_{j=1}^{c}(m_{j}+1)\bar{R}^{\mathbf{tr}}_{{\mathcal{B}}}(\tilde{t}_{j+1}-\tilde{t}_{j},{\mathcal{F}})\right]\leq(M_{{\mathcal{P}}}(\varepsilon,x_{1:T})+c+1)\bar{R}^{\mathbf{tr}}_{{\mathcal{B}}}(\frac{T}{c+1}+1,{\mathcal{F}}),$ $$

which proves our desired bound.
∎

###### Definition 4.7 (Laziness) .

###### Lemma 4.8 .

###### Proof.

###### Lemma 4.9 .

###### Proof.

### 4.3 Explicit bounds on the Minimax Expected Regret

In this section, we provide sufficient conditions on the mistake-bound of the Predictor to enable faster rates compared to online learning in the worst-case scenario.
As a result, we identify function classes that are online learnable with predictions but not online learnable otherwise.

#### Minimax regret under zero-one metric

We first consider the minimax expected regret under zero-one metric.
Assuming that the Predictor has a rate of $\tilde{\mathcal{O}}\left(T^{p}\right)$ where $p<1$, the following theorem derives the upper bound on the minimax expected regret.

###### Theorem 4.10 (Zero-one metric) .

Let $x_{1:T}$ be a sequence of examples, let $y_{1:T}$ be a sequence of labels, and let $\ell$ be the loss function.
Suppose that there is a Predictor that satisfies $M_{{\mathcal{P}}}(x_{1:T})=\tilde{\mathcal{O}}\left(T^{p}\right)$, then for any function class ${\mathcal{F}}\subset[0,1]^{{\mathcal{X}}}$, there is an online learner ${\mathcal{A}}$ with minimax expected regret at most $\tilde{\mathcal{O}}\left(T^{p}\right)R_{{\mathcal{B}}}^{\mathbf{tr}}\left(T^{1-p},{\mathcal{F}}\right)+\sqrt{T\log^{2}T}$.

###### Proof.

By [Lemma 4.6](https://arxiv.org/html/2510.03917v1#S4.Thmtheorem6), for any function class ${\mathcal{F}}\subset{\mathcal{Y}}^{{\mathcal{X}}}$, loss function $\ell$, and data stream $(x_{1:T},y_{1:T})$, the minimax expected regret of [Algorithm 4](https://arxiv.org/html/2510.03917v1#alg4) is bounded by

$$ $2(M_{{\mathcal{P}}}(x_{1:T})+1)\bar{R}^{\mathbf{tr}}_{{\mathcal{B}}}\left(\frac{T}{M_{{\mathcal{P}}}(x_{1:T})+1}+1,{\mathcal{F}}\right)+\sqrt{T\log^{2}T}.$ $$

Inputting $M_{{\mathcal{P}}}(x_{1:T})=\tilde{\mathcal{O}}\left(T^{p}\right)$ to the above bound gives us

$$ $R^{\mathbf{ol}}(T,{\mathcal{F}})=\tilde{\mathcal{O}}\left(T^{p}\right)\bar{R}^{\mathbf{tr}}_{{\mathcal{B}}}\left(T^{1-p},{\mathcal{F}}\right)+\sqrt{T\log^{2}T}.$ $$

∎

We remark that a Predictor satisfying the mistake-bound conditions in [Theorem 4.10](https://arxiv.org/html/2510.03917v1#S4.Thmtheorem10) is possible if, for example, the sequence of examples $x_{t}\in\mathbb{R}^{n}$ are generated by a noise-free linear dynamical system (LDS) where system identification is possible in finite time.
See Van Overschee and De Moor (2012); Green and Moore (1986) for further discussion for sufficient conditions under which system identification is possible.

As a Corollary, our next result shows that the minimax expected regret for the class of functions ${\mathcal{F}}^{*}$ on $[0,1]$ with bounded variation is roughly $T^{\frac{1+p}{2}}$.

###### Corollary 4.11 (Function class with bounded variation, zero-one metric) .

Let ${\mathcal{F}}^{*}$ be a set of functions $f:[0,1]\to[0,1]$ with total variation of at most $V$, let $x_{1:T}\subset[0,1]$ be a sequence of examples, let $y_{1:T}$ be a sequence of labels, and let $\ell$ be an $L_{\mathbf{los}}$-Lipschitz and convex loss function.
Suppose that there is a Predictor that satisfies $M_{{\mathcal{P}}}(x_{1:T})=\tilde{\mathcal{O}}\left(T^{p}\right)$, then there is an online learner ${\mathcal{A}}$ with minimax expected regret satisfying $R^{\mathbf{ol}}(T,{\mathcal{F}}^{*})=\tilde{\mathcal{O}}\left(L_{\mathbf{los}}\cdot T^{\frac{1+p}{2}}\right)$.
That is, ${\mathcal{F}}^{*}$ is online learnable with predictions if $p<1$.

###### Proof.

By [Corollary 3.10](https://arxiv.org/html/2510.03917v1#S3.Thmtheorem10), the minimax expected regret of the transductive online regression for ${\mathcal{F}}^{*}$ satisfies $R^{\mathbf{tr}}(T,{\mathcal{F}}^{*})=\tilde{\mathcal{O}}\left(L_{\mathbf{los}}\cdot\sqrt{VT}\right)$. Combining with the bound in [Theorem 4.10](https://arxiv.org/html/2510.03917v1#S4.Thmtheorem10), we upper bound the minimax expected regret by

$$ $\tilde{\mathcal{O}}\left(T^{p}\cdot L_{\mathbf{los}}\cdot\sqrt{VT^{1-p}}\right)+\sqrt{T\log^{2}T}=\tilde{\mathcal{O}}\left(L_{\mathbf{los}}\cdot T^{\frac{1+p}{2}}\right),$ $$

which proves our desired bound.
Additionally, we assume that the sequence of examples is predictable in our setting, i.e., $p<1$.
Thus, the minimax expected regret of our algorithm is $o(T)$.
∎

We assume that there is a Predictor ${\mathcal{P}}$ that satisfies, for any sequence $x_{1:T}\subset{\mathcal{X}}$, its mistake-bound is sublinear in $T$ under the zero-one metric.
Then the class of functions with bounded variation is online learnable.
This implies a gap between online regression with predictions and online regression in the worst-case scenario, since ${\mathcal{F}}^{*}$ has an infinite sequential fat-shattering dimension, which characterizes online learnability.

###### Theorem 4.10 (Zero-one metric) .

###### Proof.

###### Corollary 4.11 (Function class with bounded variation, zero-one metric) .

###### Proof.

#### Minimax regret under ε \varepsilon -ball metric.

Now, we compute the minimax expected regret under the $\varepsilon$-ball metric.
In the following theorem, we assume that the rate of Predictor is $M_{{\mathcal{P}}}(\varepsilon,x_{1:T})=\tilde{\mathcal{O}}\left(\frac{T^{p}}{\varepsilon^{q}}\right)$.

###### Theorem 4.12 ( $\varepsilon$ -ball metric) .

Let $x_{1:T}$ be a sequence of examples, let $y_{1:T}$ be a sequence of labels, and let $\ell$ be an $L_{\mathbf{los}}$-Lipschitz and convex loss function.
Suppose that there is a Predictor that satisfies $M_{{\mathcal{P}}}(\varepsilon,x_{1:T})=\tilde{\mathcal{O}}\left(\frac{T^{p}}{\varepsilon^{q}}\right)$, then for any $L_{\mathbf{hyp}}$-Lipschitz function class ${\mathcal{F}}\subset[0,1]^{{\mathcal{X}}}$, there is an online learner ${\mathcal{A}}$ with minimax expected regret at most

$$ $\inf_{\varepsilon>0}\left\{\tilde{\mathcal{O}}\left(\frac{T^{p}}{\varepsilon^{q}}\right)R_{{\mathcal{B}}}^{\mathbf{tr}}\left(\varepsilon^{q}T^{1-p},{\mathcal{F}}\right)+\varepsilon L_{\mathbf{los}}L_{\mathbf{hyp}}\cdot T+\sqrt{T\log^{2}T}\right\}.$ $$

###### Proof.

By [Lemma 4.9](https://arxiv.org/html/2510.03917v1#S4.Thmtheorem9), for any function class ${\mathcal{F}}\subset{\mathcal{Y}}^{{\mathcal{X}}}$ of $L_{\mathbf{hyp}}$-Lipschitz function, $L_{\mathbf{los}}$-Lipschitz and convex loss function $\ell$, and data stream $(x_{1},y_{1}),\ldots,(x_{T},y_{T})$, the expected loss of [Algorithm 6](https://arxiv.org/html/2510.03917v1#alg6) is bounded by

$$ $2(M_{{\mathcal{P}}}(\varepsilon,x_{1:T})+1)\bar{R}^{\mathbf{tr}}_{{\mathcal{B}}}\left(\frac{T}{M_{{\mathcal{P}}}(\varepsilon,x_{1:T})+1}+1,{\mathcal{F}}\right)+\varepsilon L_{\mathbf{los}}L_{\mathbf{hyp}}\cdot T+\sqrt{T\log^{2}T}.$ $$

Inputting $M_{{\mathcal{P}}}(\varepsilon,x_{1:T})=\tilde{\mathcal{O}}\left(\frac{T^{p}}{\varepsilon^{q}}\right)$ to the above bound gives

$$ $R^{\mathbf{ol}}(T,{\mathcal{F}})=\inf_{\varepsilon>0}\left\{\tilde{\mathcal{O}}\left(\frac{T^{p}}{\varepsilon^{q}}\right)\bar{R}^{\mathbf{tr}}_{{\mathcal{B}}}\left(\varepsilon^{q}T^{1-p},{\mathcal{F}}\right)+\varepsilon L_{\mathbf{los}}L_{\mathbf{hyp}}\cdot T+\sqrt{T\log^{2}T}\right\}.$ $$

Thus, we finish the proof.
∎

Like before, we remark that a Predictor satisfying the conditions in [Theorem 4.12](https://arxiv.org/html/2510.03917v1#S4.Thmtheorem12) can be constructed, if for example, the sequence of examples $x_{t}\in\mathbb{R}^{n}$ are generated by a noise-less dynamical system which need not be perfectly identifiable, but identifiable up to an error of $\varepsilon$ in finite time (Jansson and Wahlberg, 1998; Hazan et al., 2017).

The next statement shows the minimax expected regret for the class of functions ${\mathcal{F}}^{*}$ on $[0,1]$ with bounded variation.

###### Corollary 4.13 (Function class with bounded variation, $\varepsilon$ -ball metric) .

Let ${\mathcal{F}}^{*}$ be a set of $L_{\mathbf{hyp}}$-Lipschitz $f:[0,1]\to[0,1]$ with total variation of at most $V$, let $x_{1:T}\subset[0,1]$ be a sequence of examples, let $y_{1:T}$ be a sequence of labels, and let $\ell$ be an $L_{\mathbf{los}}$-Lipschitz and convex loss function.
Suppose that there is a Predictor that satisfies $M_{{\mathcal{P}}}(\varepsilon,x_{1:T})=\tilde{\mathcal{O}}\left(\frac{T^{p}}{\varepsilon^{q}}\right)$, then there is an online learner ${\mathcal{A}}$ with minimax expected regret satisfying

$$ $R^{\mathbf{ol}}(T,{\mathcal{F}}^{*})=\tilde{\mathcal{O}}\left(L_{\mathbf{los}}L_{\mathbf{hyp}}^{\frac{q}{q+2}}\cdot T^{\frac{p+q+1}{q+2}}\right).$ $$

That is, if the length of sequence is chosen as $T^{c}\operatorname*{polylog}(T)\geq L_{\mathbf{hyp}}$ for some constant $c$, then ${\mathcal{F}}^{*}$ is online learnable with prediction if $p+cq<1$.

###### Proof.

By [Corollary 3.10](https://arxiv.org/html/2510.03917v1#S3.Thmtheorem10), the minimax expected regret of the transductive online regression for ${\mathcal{F}}^{*}$ satisfies $R^{\mathbf{tr}}(T,{\mathcal{F}}^{*})=\tilde{\mathcal{O}}\left(L_{\mathbf{los}}\cdot\sqrt{VT}\right)$.
Combining with the bound in [Theorem 4.12](https://arxiv.org/html/2510.03917v1#S4.Thmtheorem12), we upper bound the minimax expected regret by

$$ $\inf_{\varepsilon>0}\left\{\tilde{\mathcal{O}}\left(\frac{T^{\frac{1+p}{2}}}{\varepsilon^{\frac{q}{2}}}\cdot L_{\mathbf{los}}\sqrt{V}\right)+\varepsilon L_{\mathbf{los}}L_{\mathbf{hyp}}\cdot T+\sqrt{T\log^{2}T}\right\}=\tilde{\mathcal{O}}\left(L_{\mathbf{los}}L_{\mathbf{hyp}}^{\frac{q}{q+2}}\cdot T^{\frac{p+q+1}{q+2}}\right).$ $$

Suppose that $L_{\mathbf{hyp}}=\tilde{\mathcal{O}}\left(T^{c}\right)$ for some constant $c$, then we have $R^{\mathbf{ol}}(T,{\mathcal{F}})=\tilde{\mathcal{O}}\left(T^{\frac{p+(c+1)q+1}{q+2}}\right)$, so ${\mathcal{F}}^{*}$ is learnable if $p+cq<1$.
∎

This result implies that the minimax expected regret of our algorithm scales with the quality of the Predictor.
Now, we construct a class of functions with bounded variation, such that it is not online learnable in the worst case but online learnable given a good Predictor.
Unfortunately, our algorithm requires Lipschitzness of the function classes, and the sequential fat-shattering dimension is equivalence to the fat-shattering dimension for Lipschitz classes up to negligible factors, so we do not achieve better rates for general Lipschitz classes.

The key observation here is that the rate of the transductive online learner for functions with bounded variation has no dependence on the Lipschitz factors (see [Corollary 3.10](https://arxiv.org/html/2510.03917v1#S3.Thmtheorem10)).
Thus, if the error scale of the Predictor is sufficiently small, e.g., the extreme case when $M_{\mathcal{P}}(\varepsilon,x_{1:T})=\mathcal{O}\left(1\right)$, we get rid of the Lipschitz dependence of the minimax expected regret of our algorithm.
Then, we observe a gap between online learning in the worst case and online learning with prediction for classes with large Lipschitz constants.
For instance, we consider the following class of ramp functions.

###### Definition 4.14 (Class of ramp functions) .

We define the class of ramp functions to consist of all functions

$$ $f_{a,b}(x)=\begin{cases}0&\text{if }0<x<a,\\ \frac{x-a}{b-a}&\text{if }a\leq x\leq b,\\ 1&\text{if }b<x<1,\end{cases}$ $$

with $0<a<b<1$ and $b=a+\frac{1}{M}$.

Note that by [Theorem 2.3](https://arxiv.org/html/2510.03917v1#S2.Thmtheorem3) the minimax expected regret is roughly $\sqrt{L_{\mathbf{hyp}}T}=\sqrt{MT}$ in the online setting, then suppose that the length of sequence $T$ is chosen as $T=M$ by the adversary, we have no guarantee of the learnability of the function class in [Definition 4.14](https://arxiv.org/html/2510.03917v1#S4.Thmtheorem14) in the worst-case scenario.
However, suppose that we have a Predictor satisfying $p+q<1$, then by [Corollary 4.13](https://arxiv.org/html/2510.03917v1#S4.Thmtheorem13), the function class is learnable with prediction using our online learners.

###### Theorem 4.12 ( ε \varepsilon -ball metric) .

###### Proof.

###### Corollary 4.13 (Function class with bounded variation, ε \varepsilon -ball metric) .

###### Proof.

###### Definition 4.14 (Class of ramp functions) .

## 5 Conclusions

In this paper, we study the problem of online regression in both the transductive and learning-augmented settings.
In the transductive setting, we establish near-tight bounds on the minimax expected regret under the $\ell_{1}$-loss, showing that it is characterized by the fat-shattering dimension rather than the more restrictive sequential fat-shattering dimension. This separates transductive online learnability with online learnability for several critical function classes.
In the online regression with predictions setting, we design algorithms whose regret adapts smoothly to the quality of the Predictor, interpolating between the worst-case and the transductive regime.
We identify sufficient conditions on the Predictor that ensure the online learnability.

Our results provide a unified theoretical framework that separates these settings for online regression and opens several directions for future work, including empirical validation of our methods and further exploration of Predictors under general metrics.
To complement our theoretical analysis, we included in the Appendix experiments on specific function classes. These illustrate that having prior information of the sequence of examples enables better empirical performance.
While our small-scale experiments highlight the potential practical gains of our framework, a more systematic and large-scale empirical validation remains an important direction for future work.
In addition, extending our framework to accommodate Predictors under more general metrics could yield deeper insights into the practical effectiveness of the learning-augmented online regression framework.

## References

- Aamand et al. [2022]
Anders Aamand, Justin Y. Chen, and Piotr Indyk.
(optimal) online bipartite matching with degree information.
In *Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems, NeurIPS*, 2022.
- Almanza et al. [2021]
Matteo Almanza, Flavio Chierichetti, Silvio Lattanzi, Alessandro Panconesi, and Giuseppe Re.
Online facility location with multiple advice.
In *Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems, NeurIPS*, pages 4661–4673, 2021.
- Alon et al. [1997]
Noga Alon, Shai Ben-David, Nicolò Cesa-Bianchi, and David Haussler.
Scale-sensitive dimensions, uniform convergence, and learnability.
*J. ACM*, 44(4):615–631, 1997.
- Anand et al. [2020]
Keerti Anand, Rong Ge, and Debmalya Panigrahi.
Customizing ML predictions for online algorithms.
In *Proceedings of the 37th International Conference on Machine Learning, ICML*, pages 303–313, 2020.
- Anand et al. [2021]
Keerti Anand, Rong Ge, Amit Kumar, and Debmalya Panigrahi.
A regression approach to learning-augmented online algorithms.
In *Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems, NeurIPS*, pages 30504–30517, 2021.
- Anand et al. [2022]
Keerti Anand, Rong Ge, Amit Kumar, and Debmalya Panigrahi.
Online algorithms with multiple predictions.
In *International Conference on Machine Learning, ICML*, pages 582–598, 2022.
- Anthony and Bartlett [1999]
Martin Anthony and Peter L. Bartlett.
*Neural Network Learning: Theoretical Foundations*.
Cambridge University Press, 1999.
- Antoniadis et al. [2023a]
Antonios Antoniadis, Christian Coester, Marek Eliás, Adam Polak, and Bertrand Simon.
Online metric algorithms with untrusted predictions.
*ACM Trans. Algorithms*, 19(2):19:1–19:34, 2023a.
- Antoniadis et al. [2023b]
Antonios Antoniadis, Themis Gouleakis, Pieter Kleer, and Pavel Kolev.
Secretary and online matching problems with machine learned advice.
*Discret. Optim.*, 48(Part 2):100778, 2023b.
- Arora et al. [2012]
Sanjeev Arora, Elad Hazan, and Satyen Kale.
The multiplicative weights update method: a meta-algorithm and applications.
*Theory Comput.*, 8(1):121–164, 2012.
- Attias and Kontorovich [2024]
Idan Attias and Aryeh Kontorovich.
Fat-shattering dimension of k-fold aggregations.
*J. Mach. Learn. Res.*, 25:144:1–144:29, 2024.
URL [https://jmlr.org/papers/v25/21-1193.html](https://jmlr.org/papers/v25/21-1193.html).
- Azar et al. [2022]
Yossi Azar, Debmalya Panigrahi, and Noam Touitou.
Online graph algorithms with predictions.
In *Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA*, pages 35–66, 2022.
- Bamas et al. [2020]
Étienne Bamas, Andreas Maggiori, and Ola Svensson.
The primal-dual method for learning augmented algorithms.
In *Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems, NeurIPS*, 2020.
- Bartlett et al. [2006]
P. L. Bartlett, S. R. Kulkarni, and S. E. Posner.
Covering numbers for real-valued function classes.
*IEEE Trans. Inf. Theor.*, 43(5):1721–1724, September 2006.
ISSN 0018-9448.
- Bartlett and Mendelson [2002]
Peter L. Bartlett and Shahar Mendelson.
Rademacher and gaussian complexities: Risk bounds and structural results.
*J. Mach. Learn. Res.*, 3:463–482, 2002.
- Ben-David et al. [1997]
Shai Ben-David, Eyal Kushilevitz, and Yishay Mansour.
Online learning versus offline learning.
*Mach. Learn.*, 29(1):45–63, 1997.
- Ben-David et al. [2009]
Shai Ben-David, Dávid Pál, and Shai Shalev-Shwartz.
Agnostic online learning.
In *COLT 2009 - The 22nd Conference on Learning Theory*, 2009.
- Blanchard [2025]
Moïse Blanchard.
Agnostic smoothed online learning.
In *Proceedings of the 57th Annual ACM Symposium on Theory of Computing*, pages 1997–2006, 2025.
- Blanchard and Kpotufe [2025]
Moïse Blanchard and Samory Kpotufe.
Distributionally-constrained adversaries in online learning.
*arXiv preprint arXiv:2506.10293*, 2025.
- Block et al. [2021]
Adam Block, Yuval Dagan, and Alexander Rakhlin.
Majorizing measures, sequential complexities, and online learning.
In Mikhail Belkin and Samory Kpotufe, editors, *Conference on Learning Theory, COLT*, pages 587–590, 2021.
- Block et al. [2022]
Adam Block, Yuval Dagan, Noah Golowich, and Alexander Rakhlin.
Smoothed online learning is as easy as statistical learning.
In *Conference on Learning Theory*, pages 1716–1786. PMLR, 2022.
- Braverman et al. [2025]
Vladimir Braverman, Jon C. Ergun, Chen Wang, and Samson Zhou.
Learning-augmented hierarchical clustering.
In *International Conference on Machine Learning, ICML*, 2025.
- Ceccherini-Silberstein et al. [2017]
T. Ceccherini-Silberstein, M. Salvatori, and E. Sava-Huss.
Groups, graphs and random walks.
In *London Mathematical Society Lecture Note Series*. Cambridge University Press, 2017.
doi: 10.1017/9781316576571.
- Cesa-Bianchi and Lugosi [2006]
Nicolò Cesa-Bianchi and Gábor Lugosi.
*Prediction, learning, and games*.
Cambridge University Press, 2006.
ISBN 978-0-521-84108-5.
doi: 10.1017/CBO9780511546921.
URL [https://doi.org/10.1017/CBO9780511546921](https://doi.org/10.1017/CBO9780511546921).
- Chen et al. [2022a]
Justin Y. Chen, Talya Eden, Piotr Indyk, Honghao Lin, Shyam Narayanan, Ronitt Rubinfeld, Sandeep Silwal, Tal Wagner, David P. Woodruff, and Michael Zhang.
Triangle and four cycle counting with predictions in graph streams.
In *The Tenth International Conference on Learning Representations, ICLR*, 2022a.
- Chen et al. [2022b]
Justin Y. Chen, Piotr Indyk, and Tal Wagner.
Streaming algorithms for support-aware histograms.
In *International Conference on Machine Learning, ICML*, pages 3184–3203, 2022b.
- Chen et al. [2022c]
Justin Y. Chen, Sandeep Silwal, Ali Vakilian, and Fred Zhang.
Faster fundamental graph algorithms via learned predictions.
In *International Conference on Machine Learning, ICML*, pages 3583–3602, 2022c.
- Daniely et al. [2011]
Amit Daniely, Sivan Sabato, Shai Ben-David, and Shai Shalev-Shwartz.
Multiclass learnability and the ERM principle.
In *COLT - The 24th Annual Conference on Learning Theory*, pages 207–232, 2011.
- Davies et al. [2023]
Sami Davies, Benjamin Moseley, Sergei Vassilvitskii, and Yuyan Wang.
Predictive flows for faster ford-fulkerson.
In *International Conference on Machine Learning, ICML*, volume 202, pages 7231–7248, 2023.
- Dinitz et al. [2021]
Michael Dinitz, Sungjin Im, Thomas Lavastida, Benjamin Moseley, and Sergei Vassilvitskii.
Faster matchings via learned duals.
In *Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems, NeurIPS*, pages 10393–10406, 2021.
- Eliás et al. [2024]
Marek Eliás, Haim Kaplan, Yishay Mansour, and Shay Moran.
Learning-augmented algorithms with explicit predictors.
In *Advances in Neural Information Processing Systems 38: Annual Conference on Neural Information Processing Systems 2024, NeurIPS*, 2024.
- Ergun et al. [2022]
Jon C. Ergun, Zhili Feng, Sandeep Silwal, David P. Woodruff, and Samson Zhou.
Learning-augmented $k$-means clustering.
In *The Tenth International Conference on Learning Representations, ICLR*, 2022.
- Fu et al. [2025]
Chunkai Fu, Brandon G. Nguyen, Jung Hoon Seo, Ryan S. Zesch, and Samson Zhou.
Learning-augmented search data structures.
In *The Thirteenth International Conference on Learning Representations, ICLR*, 2025.
- Gollapudi and Panigrahi [2019]
Sreenivas Gollapudi and Debmalya Panigrahi.
Online algorithms for rent-or-buy with expert advice.
In *Proceedings of the 36th International Conference on Machine Learning, ICML*, pages 2319–2327, 2019.
- Gottlieb et al. [2014]
Lee-Ad Gottlieb, Aryeh Kontorovich, and Robert Krauthgamer.
Efficient classification for metric data.
*IEEE Trans. Inf. Theory*, 60(9):5750–5759, 2014.
- Green and Moore [1986]
Michael Green and John B Moore.
Persistence of excitation in linear systems.
*Systems & control letters*, 7(5):351–360, 1986.
- Grigorescu et al. [2022]
Elena Grigorescu, Young-San Lin, Sandeep Silwal, Maoyuan Song, and Samson Zhou.
Learning-augmented algorithms for online linear and semidefinite programming.
In *NeurIPS*, 2022.
- Grigorescu et al. [2025]
Elena Grigorescu, Young-San Lin, and Maoyuan Song.
Learning-augmented algorithms for online concave packing and convex covering problems.
In *International Conference on Artificial Intelligence and Statistics, AISTATS*, pages 1072–1080, 2025.
- Haghtalab [2018]
Nika Haghtalab.
*Foundation of Machine Learning, by the People, for the People*.
PhD thesis, Carnegie Mellon University, 2018.
- Haghtalab et al. [2020]
Nika Haghtalab, Tim Roughgarden, and Abhishek Shetty.
Smoothed analysis of online and differentially private learning.
*Advances in Neural Information Processing Systems*, 33:9203–9215, 2020.
- Haghtalab et al. [2022]
Nika Haghtalab, Yanjun Han, Abhishek Shetty, and Kunhe Yang.
Oracle-efficient online learning for smoothed adversaries.
*Advances in Neural Information Processing Systems*, 35:4072–4084, 2022.
- Hanneke et al. [2023a]
Steve Hanneke, Shay Moran, Vinod Raman, Unique Subedi, and Ambuj Tewari.
Multiclass online learning and uniform convergence.
In *The Thirty Sixth Annual Conference on Learning Theory*, pages 5682–5696, 2023a.
- Hanneke et al. [2023b]
Steve Hanneke, Shay Moran, and Jonathan Shafer.
A trichotomy for transductive online learning.
In *Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems, NeurIPS*, 2023b.
- Hanneke et al. [2024a]
Steve Hanneke, Shay Moran, and Jonathan Shafer.
A trichotomy for transductive online learning.
*Advances in Neural Information Processing Systems*, 36, 2024a.
- Hanneke et al. [2024b]
Steve Hanneke, Vinod Raman, Amirreza Shaeiri, and Unique Subedi.
Multiclass transductive online learning.
In Amir Globersons, Lester Mackey, Danielle Belgrave, Angela Fan, Ulrich Paquet, Jakub M. Tomczak, and Cheng Zhang, editors, *Advances in Neural Information Processing Systems 38: Annual Conference on Neural Information Processing Systems 2024, NeurIPS 2024, Vancouver, BC, Canada, December 10 - 15, 2024*, 2024b.
- Hazan et al. [2017]
Elad Hazan, Karan Singh, and Cyril Zhang.
Learning linear dynamical systems via spectral filtering.
*Advances in Neural Information Processing Systems*, 30, 2017.
- Hsu et al. [2019]
Chen-Yu Hsu, Piotr Indyk, Dina Katabi, and Ali Vakilian.
Learning-based frequency estimation algorithms.
In *7th International Conference on Learning Representations, ICLR*, 2019.
- Im et al. [2021]
Sungjin Im, Ravi Kumar, Mahshid Montazer Qaem, and Manish Purohit.
Online knapsack with frequency predictions.
In *Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems, NeurIPS*, pages 2733–2743, 2021.
- Indyk et al. [2019]
Piotr Indyk, Ali Vakilian, and Yang Yuan.
Learning-based low-rank approximations.
In *Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS*, pages 7400–7410, 2019.
- Jansson and Wahlberg [1998]
Magnus Jansson and Bo Wahlberg.
On consistency of subspace methods for system identification.
*Automatica*, 34(12):1507–1519, 1998.
- Jiang et al. [2022]
Shaofeng H.-C. Jiang, Erzhi Liu, You Lyu, Zhihao Gavin Tang, and Yubo Zhang.
Online facility location with predictions.
In *The Tenth International Conference on Learning Representations, ICLR*, 2022.
- Jiang et al. [2020]
Tanqiu Jiang, Yi Li, Honghao Lin, Yisong Ruan, and David P. Woodruff.
Learning-augmented data stream algorithms.
In *8th International Conference on Learning Representations, ICLR*, 2020.
- Karthik C. S. et al. [2025]
Karthik C. S., Euiwoong Lee, Yuval Rabani, Chris Schwiegelshohn, and Samson Zhou.
On approximability of $\ell_{2}^{2}$ min-sum clustering.
In *41st International Symposium on Computational Geometry, SoCG*, pages 62:1–62:18, 2025.
- Khodak et al. [2023]
Mikhail Khodak, Kareem Amin, Travis Dick, and Sergei Vassilvitskii.
Learning-augmented private algorithms for multiple quantile release.
In *International Conference on Machine Learning, ICML 2023*, pages 16344–16376, 2023.
- Khodak et al. [2022]
Misha Khodak, Maria-Florina Balcan, Ameet Talwalkar, and Sergei Vassilvitskii.
Learning predictions for algorithms with predictions.
In *Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems, NeurIPS*, 2022.
- Lattanzi et al. [2020]
Silvio Lattanzi, Thomas Lavastida, Benjamin Moseley, and Sergei Vassilvitskii.
Online scheduling via learned weights.
In *Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA*, pages 1859–1877, 2020.
- Li et al. [2023]
Yi Li, Honghao Lin, Simin Liu, Ali Vakilian, and David P. Woodruff.
Learning the positions in countsketch.
In *The Eleventh International Conference on Learning Representations, ICLR*, 2023.
- Lin et al. [2022]
Honghao Lin, Tian Luo, and David P. Woodruff.
Learning augmented binary search trees.
In *International Conference on Machine Learning, ICML*, pages 13431–13440, 2022.
- Littlestone [1989]
Nicholas Littlestone.
*Mistake Bounds and Logarithm Linear-Threshold Learning Algorithms*.
PhD thesis, University of California, Santa Cruz, 1989.
- Littlestone [1987]
Nick Littlestone.
Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm.
*Mach. Learn.*, 2(4):285–318, 1987.
- Lykouris and Vassilvitskii [2021]
Thodoris Lykouris and Sergei Vassilvitskii.
Competitive caching with machine learned advice.
*J. ACM*, 68(4):24:1–24:25, 2021.
- Mitzenmacher [2018]
Michael Mitzenmacher.
A model for learned bloom filters and optimizing by sandwiching.
In *Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems, NeurIPS*, pages 462–471, 2018.
- Mitzenmacher and Vassilvitskii [2020]
Michael Mitzenmacher and Sergei Vassilvitskii.
Algorithms with predictions.
In Tim Roughgarden, editor, *Beyond the Worst-Case Analysis of Algorithms*, pages 646–662. Cambridge University Press, 2020.
- Nguyen et al. [2023]
Thy Dinh Nguyen, Anamay Chaturvedi, and Huy L. Nguyen.
Improved learning-augmented algorithms for k-means and k-medians clustering.
In *The Eleventh International Conference on Learning Representations, ICLR*, 2023.
- Purohit et al. [2018]
Manish Purohit, Zoya Svitkina, and Ravi Kumar.
Improving online algorithms via ML predictions.
In *Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS*, pages 9684–9693, 2018.
- Rakhlin and Sridharan [2013]
Alexander Rakhlin and Karthik Sridharan.
Online learning with predictable sequences.
In *Conference on Learning Theory*, pages 993–1019. PMLR, 2013.
- Rakhlin and Sridharan [2014]
Alexander Rakhlin and Karthik Sridharan.
*Statistical learning and sequential prediction*, 2014.
- Rakhlin et al. [2010]
Alexander Rakhlin, Karthik Sridharan, and Ambuj Tewari.
Online learning: Random averages, combinatorial parameters, and learnability.
In John D. Lafferty, Christopher K. I. Williams, John Shawe-Taylor, Richard S. Zemel, and Aron Culotta, editors, *Advances in Neural Information Processing Systems 23: 24th Annual Conference on Neural Information Processing Systems 2010. Proceedings of a meeting held 6-9 December 2010, Vancouver, British Columbia, Canada*, pages 1984–1992. Curran Associates, Inc., 2010.
- Rakhlin et al. [2011]
Alexander Rakhlin, Karthik Sridharan, and Ambuj Tewari.
Online learning: Stochastic, constrained, and smoothed adversaries.
*Advances in neural information processing systems*, 24, 2011.
- Rakhlin et al. [2015a]
Alexander Rakhlin, Karthik Sridharan, and Ambuj Tewari.
Online learning via sequential complexities.
*J. Mach. Learn. Res.*, 16:155–186, 2015a.
- Rakhlin et al. [2015b]
Alexander Rakhlin, Karthik Sridharan, and Ambuj Tewari.
Online learning via sequential complexities.
*J. Mach. Learn. Res.*, 16(1):155–186, 2015b.
- Raman and Tewari [2024]
Vinod Raman and Ambuj Tewari.
Online classification with predictions.
In *Advances in Neural Information Processing Systems 38: Annual Conference on Neural Information Processing Systems, NeurIPS*, 2024.
- Scully et al. [2022]
Ziv Scully, Isaac Grosof, and Michael Mitzenmacher.
Uniform bounds for scheduling with job size estimates.
In *13th Innovations in Theoretical Computer Science Conference, ITCS*, pages 114:1–114:30, 2022.
- Shin et al. [2023]
Yongho Shin, Changyeol Lee, Gukryeol Lee, and Hyung-Chan An.
Improved learning-augmented algorithms for the multi-option ski rental problem via best-possible competitive analysis.
In *International Conference on Machine Learning, ICML*, pages 31539–31561, 2023.
- Spielman and Teng [2004]
Daniel A Spielman and Shang-Hua Teng.
Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time.
*Journal of the ACM (JACM)*, 51(3):385–463, 2004.
- Spielman and Teng [2009]
Daniel A Spielman and Shang-Hua Teng.
Smoothed analysis: an attempt to explain the behavior of algorithms in practice.
*Communications of the ACM*, 52(10):76–84, 2009.
- Szegedy et al. [2014]
Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian J. Goodfellow, and Rob Fergus.
Intriguing properties of neural networks.
In *2nd International Conference on Learning Representations, ICLR, Conference Track Proceedings*, 2014.
- Van Overschee and De Moor [2012]
Peter Van Overschee and BL0888 De Moor.
*Subspace identification for linear systems: Theory—Implementation—Applications*.
Springer Science & Business Media, 2012.
- Vapnik and Chervonenkis [1971]
V. N. Vapnik and A. Ya. Chervonenkis.
On the uniform convergence of relative frequencies of events to their probabilities.
*Theory of Probability & Its Applications*, 16(2):264–280, 1971.
doi: 10.1137/1116025.
URL [https://doi.org/10.1137/1116025](https://doi.org/10.1137/1116025).
- Wang et al. [2020]
Shufan Wang, Jian Li, and Shiqiang Wang.
Online algorithms for multi-shop ski rental with machine learned advice.
In *Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems, NeurIPS*, 2020.
- Wei and Zhang [2020]
Alexander Wei and Fred Zhang.
Optimal robustness-consistency trade-offs for learning-augmented online algorithms.
In *Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems, NeurIPS*, 2020.

## Appendix A Experiments

In this section, we present experiments to justify our theoretical results.
The experiments are conducted using an Apple M2 CPU, with 16 GB RAM and 8 cores.

#### Experiment Setup.

We generate the sequence of examples $x_{1:T}\subset\mathbb{R}^{d}$ by a linear dynamical system: $x_{t+1}=Ax_{t}$, where $A\in\mathbb{R}^{d\times d}$ is a random stable matrix.
We restrict each example to having a support size $c<d$.
In particular, we randomly select $c$ indices from $[d]$ and set $x_{t}(i)=0$ for all other indices and $t\in[T]$.
We also set the transition matrix $A$ to have the same support as $x_{t}$.
This construction captures the sparse nature of the sequence of examples in various applications.
For instance, in energy management (see [Example 1.1](https://arxiv.org/html/2510.03917v1#S1.Thmtheorem1)), a list of variables $x_{t}\in\mathbb{R}^{d}$ can affect the energy consumption $y_{t}$, however, in specific circumstances, only $c$ of these variables have a significant influence (e.g., the temperature may change by only a few during a month), so the others are set to 0 in $x_{t}$.
In the experiment, we compare the accumulative loss in the transductive online setting, where the learner knows the sequence of examples $x_{1:T}$ in advance, and the online setting, where the learner does not have additional information.
We show that the learner achieves better performance in the transductive online setting.

We choose the ground-truth function class ${\mathcal{F}}$ to be all $c$-junta hyperplanes in $\mathbb{R}^{d}$ with coefficients in $\{-1+0.4\cdot i,i\in[5]\}$.
We consider the regression problem under the additive noise model, i.e., we choose the target function $f^{*}$ from ${\mathcal{F}}$ randomly and assign the label $y_{t}$ to each example $x_{t}$ by $f^{*}(x_{t})+g_{t}$, where $g_{t}\in\mathcal{N}(0,0.01)$ is random Gaussian noise, representing noisy measurements in real-life scenarios.
We evaluate the learner using the $\ell_{1}$-loss function: $\ell(y,\widehat{y})=|y-\widehat{y}|$.
We choose the parameters $d=8,c=4$, and $T=1000$.

#### Methods.

In the experiment, we implement the multiplicative weight algorithm (MWA), which randomly samples the advice of $K$ experts.
For the baseline method, we set the experts as the entire function class ${\mathcal{F}}$, since the learner does not have information on $x_{1:T}$ in the online setting.
In contrast, in the transductive online setting, the learner observes $x_{1:T}$ in advance, and so it knows the support $\{i_{1},\ldots,i_{c}\}\subset[d]$ of $x_{t}$.
Thus, we implement MWA on the restricted function class, which is a subset of ${\mathcal{F}}$ and has $c$-juntas being $\{i_{1},\ldots,i_{c}\}$.
We compute the total $\ell_{1}$-loss of both methods at all times $t\in[T]$.
We run $10$ repetitions and plot the mean loss curve.

#### Results.

As shown in [Figure 1](https://arxiv.org/html/2510.03917v1#A1.F1), MWA with the restricted net (red line) exhibits a much steeper initial decline in cumulative loss compared to MWA on the entire net (blue line), indicating faster convergence toward the ground-truth function.
In addition, the restricted net consistently maintains a lower error throughout all rounds, with the gap widening over time.

The experiment demonstrates that using the support information of the input sequence of examples significantly improves learning outcomes.
The result highlights the empirical separation between the standard online setting and the transductive online setting: access to the example sequence allows the learner to focus on a refined function class, thereby achieving lower regret in practice.

Figure: Fig. 1: Comparison between the performance of MWA on the entire net and the restricted net. The blue line is the entire net, and the red line is the restricted net.
Refer to caption: output.png

## Peer Reviews

confidence: 4
contribution: 2
initial_rating: 6
presentation: 3
questions: Could you please elaborate on the novelty and the technical contributions?
soundness: 3
strengths: - Online Regression is a classical topic with vast applicability.
- The theoretical results are sound and complete. In particular, the general result for transductive learning is nearly tight. 
- The main body is generally well written.
summary: This paper studies online regression beyond the standard adversarial setting. In particular, the authors provide results for two settings: 
- The transductive setting, where the sequence of examples (but not their corresponding labels) is revealed up front, 
- The prediction setting, where the learner has access to a predictor of the sequence of examples, and its performance depends on the accuracy of such predictors.

For the transductive setting, the authors prove that the combinatorial parameter underlying learnability is the fat-shattering dimension, which is strictly smaller than the sequential fat-shattering dimension, which characterizes online learnability in general. This result is existential, as it follows from a minimax argument. The authors also provide a simple learning algorithm (compute an eps-cover of the examples in the sequence and run MWU on them) with a suboptimal rate. 

The authors also provide positive results for the learning augmented setting, where the learner receives predictions on the examples in advance. Here, two metrics of the predictor sub-routines are used: the $0/1$ loss, and the $\varepsilon$-ball loss.
weaknesses: - The regret rate for the transductive setting is only existential. This fact should be stressed earlier in the paper, at least in the introduction. It is now only mentioned in Section 3. 
- I find it challenging to assess the novelty and technical contribution of the paper:
- The transductive result seems to follow easily from the adversarial analysis, replacing the sequential Rademacher complexity with its non-sequential version, and using that the sequence of examples is known in advance. The practical algorithm for that setting is also fairly simple. 
- The algorithm for the 0/1 loss (which is then also used for the eps-ball loss) seems to heavily rely on Raman & Tewari.

Minor Comments: 
- line 130 “online learning” -> “online learnable” 
- line 159: L_{loss} is defined a couple of pages later
- The bibliography is disorganized: multiple styles are used. In particular, the NeurIPS 23 paper by Hanneke et al is cited in two different entries, the JMLR 15 by Rakhlin et al is also cited twice, while the citation in lines 684 and 685 is missing the name of the journal/conference.

---

confidence: 3
contribution: 2
initial_rating: 6
presentation: 3
questions: Please address the concerns raised above.
soundness: 3
strengths: - Clear theoretical separation: transductive regret depends on fat shattering (not sequential), enabling new learnability results for key classes
- Interpolation guarantees with concrete mistake models (0-1 and eps-ball) and constructive algorithms (restarts + MW over interval counts)
- Useful instantiations (Lipschitz, k-fold aggregations, bounded variation) with near-matching bounds that make the results tangible
summary: The paper studies online regression when the learner has access to predictions (ranging from full knowledge of the unlabeled input sequence to noisy/evolving forecasts). It proves that in the transductive setting the minimax expected regret is governed by the fat shattering dimension, allowing learning and yielding tighter rates for classes like bounded variation. It then designs learning augmented algorithms with restarts and multiplicative weights over interval granularities so that regret interpolates between worst case and transductive bounds as predictor quality improves. A small synthetic experiment qualitatively illustrates the gap.
weaknesses: - Practicality/constructiveness: the main transductive upper bound is largely minimax style; the explicit MWA-based learner is suboptimal, and computational aspects (cover construction, oracle assumptions, runtime/memory) are under-specified. It'd be useful to clarify its feasibility and provide a practical surrogate.
- Empirics are thin: only a single synthetic study; no evaluation that varies predictor quality M or eps, or uses no real data streams, or compares to strong online baselines with imperfect forecasts. A more systematic experimental section would greatly strengthen the paper.

---

confidence: 3
contribution: 2
initial_rating: 4
presentation: 3
questions: Refer to __Weakness__
soundness: 2
strengths: * The paper is well organized and easy to follow. The authors also provide several applications of the online regression setting.
* The theoretical results resolve an open problem left by previous studies.
* The work presents a unified and elegant theoretical framework.
* The paper also includes numerical experiments to support the theoretical claims.
summary: This paper investigates the online regression in both the transductive and learning augmented settings.  In the transductive setting, it establishes the near-optimal regret bound for $\ell_1$ loss. In the online regression with predictions setting, it proposes the algorithms that adapt smoothly to the quality of the Predictor. They also conduct numerical experiments to verify the effectiveness of their methods.
weaknesses: **W1.** I am confused about the motivation of this paper, especially in Lines 80–83. Why do the authors investigate the use of future examples to obtain better-than-worst-case regret bounds?

**W2.** In Line 131, the authors note that the setting where the learner has access to samples is unrealistic. Therefore, I wonder whether the contribution of the first results is actually limited.

**W3.** What is the valid range of $p$ in Corollary 1.3?

**W4.** The equation in Lines 252–255 exceeds the column width.

**W5.** The algorithm design and analysis of this paper are largely based on Raman & Tewari (2024), so I have serious concerns about the novelty of this work. I hope the authors can highlight what specific challenges arise in the online regression setting compared with prior work.

**W6.** Can the authors conduct experiments on real-world datasets to further validate their method?

**W7.** The authors place the pseudocode of the algorithm in the appendix, but I believe it should be included in the main text for better readability.

---

confidence: 3
contribution: 2
initial_rating: 4
presentation: 3
questions: Could you clarify the claimed novelty of your transductive minimax regret result?
soundness: 3
strengths: 1. The main contribution, as I understand it, is the learning-augmented setting, which extends the classification scenario from Raman & Tewari (2024) to regression.  

2. The paper introduces some new techniques for handling the regression case and connects it to the concept of transductive regret.
summary: This paper studies online learning under two related settings: the *transductive* setting, where the entire sequence of features or contexts is revealed to the learner in advance, and the *learning-augmented* setting, where the learner has access to a predictor that provides (possibly noisy) forecasts of future examples. The authors analyze two types of prediction errors—the zero-one error and the $\epsilon$-ball error defined with respect to a metric on the context space. The main contributions are a minimax-optimal bound for the transductive setting and upper bounds for online learning with imperfect predictions, where the latter scale with the transductive regret multiplied by a term that depends on the predictor’s error.
weaknesses: 1. I have a major concern regarding the claimed novelty of the minimax regret result and its connection to the fat-shattering dimension in transductive regression. This connection, in my understanding, was already established in Lemma 11 and Lemma 12 of A. Rakhlin, O. Shamir, and K. Sridharan, *“Relax and Randomize: From Value to Algorithms,”* NeurIPS 2012. Their work derived a minimax-optimal regret bound for the transductive setting expressed via the (classical) Rademacher complexity, and it is a standard argument to convert such Rademacher-based bounds into equivalent statements in terms of the fat-shattering dimension, as done in the present paper. Moreover, Rakhlin et al. not only established this characterization but also provided an oracle-efficient algorithm achieving the optimal regret, whereas the current submission only re-derives the bound without offering a constructive realization.

2. Given point 1 above, the actual contribution of the paper lies in the learning-augmented setting, where the authors establish only an upper bound. However, it remains unclear how tight this bound is with respect to both the prediction error and the transductive regret. Moreover, the overall results seems (conceptually) largely follows Raman & Tewari (2024).