Worst-case Error Bounds for Online Learning of Smooth Functions
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866916626073387008 |
|---|---|
| author | Xie, Weian |
| author_facet | Xie, Weian |
| contents | 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) = Θ(η)$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_16388 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Worst-case Error Bounds for Online Learning of Smooth Functions Xie, Weian Machine Learning Discrete Mathematics Data Structures and Algorithms 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) = Θ(η)$. |
| title | Worst-case Error Bounds for Online Learning of Smooth Functions |
| topic | Machine Learning Discrete Mathematics Data Structures and Algorithms |
| url | https://arxiv.org/abs/2502.16388 |