在实数轴上在线学习光滑函数，提出三种新机制应对无限损失问题。
Online learning of smooth functions on $\mathbb{R}$
- 限制查询距离或加权损失，避免远距离查询导致的灾难性误差。
- 当权重指数衰减时，二次损失下可获得有限且最优的学习保证。
- 高维情况下（d≥2）任何改进都无法阻止对手引发无限损失。
我们研究在实数轴上对实值函数进行对抗性在线学习。每轮中，学习者在点 $x_t\in\mathbb{R}$ 被询问，预测 $\hat y_t$，随后观察真实值 $f(x_t)$；性能以累积 $p$-损失 $\sum_{t\ge 1}|\hat y_t-f(x_t)|^p$ 衡量。针对绝对连续函数类 $\mathcal{G}_q=\{f:\mathbb{R}\to\mathbb{R}: \int_{\mathbb{R}}|f'(x)|^q\,dx\le 1\}$，我们发现标准模型在 $\mathbb{R}$ 上会退化：对任意 $p\ge 1$ 且 $q>1$，对手可强制产生无限损失。为此，我们分析了三种修改后的学习场景，限制远离历史输入的查询影响。场景1要求新查询与之前某次查询距离不超过1；场景2允许任意查询，但仅对距历史查询距离≤1的回合计算损失；场景3将每轮损失乘以权重 $g(\min_{j<t}|x_t-x_j|)$。我们对场景1-2在多个参数范围内给出精确刻画。对于场景3，识别出清晰的阈值现象：若 $g$ 衰减过慢，则对手仍可迫使加权损失无限大；而当 $g(z)=e^{-cz}$ 等快速衰减时，$p=q=2$ 情况下可得有限且紧致的保证。最后，我们研究了 $\mathbb{R}^d$ 上的多变量切片推广 $\mathcal{G}_{q,d}$，并揭示尖锐二分：尽管一维情形在某些参数下存在有限最优值，但对于所有 $d\ge 2$，该类函数过于宽松，即使在场景1-3下对手仍能引发无限损失。
原文摘要 · Abstract (English)
We study adversarial online learning of real-valued functions on $\mathbb{R}$. In each round the learner is queried at $x_t\in\mathbb{R}$, predicts $\hat y_t$, and then observes the true value $f(x_t)$; performance is measured by cumulative $p$-loss $\sum_{t\ge 1}|\hat y_t-f(x_t)|^p$. For the class \[ \mathcal{G}_q=\Bigl\{f:\mathbb{R}\to\mathbb{R}\ \text{absolutely continuous}:\ \int_{\mathbb{R}}|f'(x)|^q\,dx\le 1\Bigr\}, \] we show that the standard model becomes ill-posed on $\mathbb{R}$: for every $p\ge 1$ and $q>1$, an adversary can force infinite loss. Motivated by this obstruction, we analyze three modified learning scenarios that limit the influence of queries that are far from previously observed inputs. In Scenario 1 the adversary must choose each new query within distance $1$ of some past query. In Scenario 2 the adversary may query anywhere, but the learner is penalized only on rounds whose query lies within distance $1$ of a past query. In Scenario 3 the loss in round $t$ is multiplied by a weight $g(\min_{j<t}|x_t-x_j|)$. We obtain sharp characterizations for Scenarios 1-2 in several regimes. For Scenario 3 we identify a clean threshold phenomenon: if $g$ decays too slowly, then the adversary can force infinite weighted loss. In contrast, for rapidly decaying weights such as $g(z)=e^{-cz}$ we obtain finite and sharp guarantees in the quadratic case $p=q=2$. Finally, we study a natural multivariable slice generalization $\mathcal{G}_{q,d}$ of $\mathcal{G}_q$ on $\mathbb{R}^d$ and show a sharp dichotomy: while the one-dimensional case admits finite opt-values in certain regimes, for every $d\ge 2$ the slice class $\mathcal{G}_{q,d}$ is too permissive, and even under Scenarios 1-3 an adversary can force infinite loss.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。