Minimax-optimal and Locally-adaptive Online Nonparametric Regression
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866917982194630656 |
|---|---|
| author | Liautaud, Paul Gaillard, Pierre Wintenberger, Olivier |
| author_facet | Liautaud, Paul Gaillard, Pierre Wintenberger, Olivier |
| contents | We study adversarial online nonparametric regression with general convex losses and propose a parameter-free learning algorithm that achieves minimax optimal rates. Our approach leverages chaining trees to compete against H{ö}lder functions and establishes optimal regret bounds. While competing with nonparametric function classes can be challenging, they often exhibit local patterns - such as local H{ö}lder continuity - that online algorithms can exploit. Without prior knowledge, our method dynamically tracks and adapts to different H{ö}lder profiles by pruning a core chaining tree structure, aligning itself with local smoothness variations. This leads to the first computationally efficient algorithm with locally adaptive optimal rates for online regression in an adversarial setting. Finally, we discuss how these notions could be extended to a boosting framework, offering promising directions for future research. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_03363 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Minimax-optimal and Locally-adaptive Online Nonparametric Regression Liautaud, Paul Gaillard, Pierre Wintenberger, Olivier Statistics Theory Machine Learning We study adversarial online nonparametric regression with general convex losses and propose a parameter-free learning algorithm that achieves minimax optimal rates. Our approach leverages chaining trees to compete against H{ö}lder functions and establishes optimal regret bounds. While competing with nonparametric function classes can be challenging, they often exhibit local patterns - such as local H{ö}lder continuity - that online algorithms can exploit. Without prior knowledge, our method dynamically tracks and adapts to different H{ö}lder profiles by pruning a core chaining tree structure, aligning itself with local smoothness variations. This leads to the first computationally efficient algorithm with locally adaptive optimal rates for online regression in an adversarial setting. Finally, we discuss how these notions could be extended to a boosting framework, offering promising directions for future research. |
| title | Minimax-optimal and Locally-adaptive Online Nonparametric Regression |
| topic | Statistics Theory Machine Learning |
| url | https://arxiv.org/abs/2410.03363 |