提出首个自适应局部光滑性的在线非参数回归算法，实现最优误差率。
Minimax-optimal and Locally-adaptive Online Nonparametric Regression
- 用分层树结构动态追踪局部光滑性变化
- 在对抗环境中达到最小最大最优误差率
- 无需先验知识，适合复杂非平稳数据
我们研究带有通用凸损失的对抗性在线非参数回归问题，提出一种无参数学习算法，可实现最小最大最优速率。该方法利用分层树（chaining trees）与霍尔德（Hölder）函数类竞争，并建立最优遗憾界。尽管非参数函数类难以处理，但通常呈现局部模式（如局部霍尔德连续性），在线算法可加以利用。本方法无需先验知识，通过修剪核心分层树结构，动态追踪并适应不同霍尔德特征，与局部光滑性变化保持一致。这使得本算法成为首个在对抗设定下具有局部自适应最优速率且计算高效的在线回归方法。最后，我们讨论了将这些思想扩展至提升框架的可能性，为未来研究提供新方向。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。