破解在线学习光滑函数的最坏误差难题，给出精确边界。
Worst-case Error Bounds for Online Learning of Smooth Functions
- 构建光滑函数类上的在线学习误差上界模型。
- 证明当 p,q 接近 1 时，最坏误差为 O(min(δ,ε)⁻¹)。
- 解决近30年未解问题，适用于理论研究者。
在线学习是一种基于序列反馈的机器学习模型。本文研究具有特定光滑性约束的实值函数在线学习的最坏情况误差。设 $\/mathcal{F}_q$ 为所有绝对连续函数 $f: [0, 1] \rightarrow \mathbb{R}$ 的集合，满足 $\|f'\|_q \le 1$，$\operatorname{opt}_p(\/mathcal{F}_q)$ 表示任意学习者在任意试验次数下，预测误差的 $p^\text{th}$ 次幂和的最优上界。我们证明：对任意 $δ, ε\in (0, 1)$，有 $\operatorname{opt}_{1+δ} (\/mathcal{F}_{1+ε}) = O(\min(δ, ε)^{-1})$。结合 Kimber 与 Long（1995）及 Geneson 与 Zhou（2023）的结果，我们完整刻画了 $p, q \ge 1$ 使得 $\operatorname{opt}_p(\/mathcal{F}_q)$ 有限的条件，解决了近30年悬而未决的问题。我们还研究了属于特定函数族（如多项式）的光滑函数学习场景，证明了 Geneson 与 Zhou（2023）关于多项式学习不更简单的猜想。此外，我们引入噪声模型，允许学习者最多收到 $η\ge 1$ 次错误反馈，定义最坏误差为 $\operatorname{opt}^{\text{nf}}_{p, η} (\/mathcal{F}_q)$。我们证明：当且仅当 $\operatorname{opt}_p(\/mathcal{F}_q)$ 有限时，$\operatorname{opt}^{\text{nf}}_{p, η} (\/mathcal{F}_q)$ 有限；并对所有 $p, q \ge 2$ 与 $η\ge 1$，有 $\operatorname{opt}^{\text{nf}}_{p, η} (\/mathcal{F}_q) = Θ(η)$。
原文摘要 · Abstract (English)
Online learning is a model of machine learning where the learner is trained on sequential feedback. We investigate worst-case error for the online learning of real functions that have certain smoothness constraints. Suppose that $\mathcal{F}_q$ is the class of all absolutely continuous functions $f: [0, 1] \rightarrow \mathbb{R}$ such that $\|f'\|_q \le 1$, and $\operatorname{opt}_p(\mathcal{F}_q)$ is the best possible upper bound on the sum of the $p^{\text{th}}$ powers of absolute prediction errors for any number of trials guaranteed by any learner. We show that for any $δ, ε\in (0, 1)$, $\operatorname{opt}_{1+δ} (\mathcal{F}_{1+ε}) = O(\min(δ, ε)^{-1})$. Combined with the previous results of Kimber and Long (1995) and Geneson and Zhou (2023), we achieve a complete characterization of the values of $p, q \ge 1$ that result in $\operatorname{opt}_p(\mathcal{F}_q)$ being finite, a problem open for nearly 30 years. We study the learning scenarios of smooth functions that also belong to certain special families of functions, such as polynomials. We prove a conjecture by Geneson and Zhou (2023) that it is not any easier to learn a polynomial in $\mathcal{F}_q$ than it is to learn any general function in $\mathcal{F}_q$. We also define a noisy model for the online learning of smooth functions, where the learner may receive incorrect feedback up to $η\ge 1$ times, denoting the worst-case error bound as $\operatorname{opt}^{\text{nf}}_{p, η} (\mathcal{F}_q)$. We prove that $\operatorname{opt}^{\text{nf}}_{p, η} (\mathcal{F}_q)$ is finite if and only if $\operatorname{opt}_p(\mathcal{F}_q)$ is. Moreover, we prove for all $p, q \ge 2$ and $η\ge 1$ that $\operatorname{opt}^{\text{nf}}_{p, η} (\mathcal{F}_q) = Θ(η)$.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。