# Online Nonparametric Regression with General Loss Functions

arXiv: https://arxiv.org/abs/1501.06598 · HTML: https://mlsanity.com/paper/1501.06598/

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Jan 2015.

## Built on by (most cited first, 14 of 14)

- [Smoothed Online Learning is as Easy as Statistical Learning](https://mlsanity.com/paper/2202.04690/) (2022)
- [Guarantees for Epsilon-Greedy Reinforcement Learning with Function Approximation](https://mlsanity.com/paper/2206.09421/) (2022)
- [Expected Worst Case Regret via Stochastic Sequential Covering](https://mlsanity.com/paper/2209.04417/) (2022)
- [Selective Sampling and Imitation Learning via Online Regression](https://mlsanity.com/paper/2307.04998/) (2023)
- [Localization, Convexity, and Star Aggregation](https://mlsanity.com/paper/2105.08866/) (2021)
- [Second Order Path Variationals in Non-Stationary Online Learning](https://mlsanity.com/paper/2205.01921/) (2022)
- [Statistical Complexity and Optimal Algorithms for Non-linear Ridge Bandits](https://mlsanity.com/paper/2302.06025/) (2023)
- [Precise Regret Bounds for Log-loss via a Truncated Bayesian Algorithm](https://mlsanity.com/paper/2205.03728/) (2022)
- [Sequential prediction under log-loss and misspecification](https://mlsanity.com/paper/2102.00050/) (2021)
- [Nonparametric Contextual Online Bilateral Trade](https://mlsanity.com/paper/2602.12904/) (2026)
- [Minimax-optimal and Locally-adaptive Online Nonparametric Regression](https://mlsanity.com/paper/2410.03363/) (2024)
- [Minimax Adaptive Online Nonparametric Regression over Besov Spaces](https://mlsanity.com/paper/2505.19741/) (2025)
- [Online Realizable Regression and Applications for ReLU Networks](https://mlsanity.com/paper/2602.19172/) (2026)
- [Online nearest neighbor classification](https://mlsanity.com/paper/2307.01170/) (2023)

## Abstract (arXiv)

This paper establishes minimax rates for online regression with arbitrary classes of functions and general losses. We show that below a certain threshold for the complexity of the function class, the minimax rates depend on both the curvature of the loss function and the sequential complexities of the class. Above this threshold, the curvature of the loss does not affect the rates. Furthermore, for the case of square loss, our results point to the interesting phenomenon: whenever sequential and i.i.d. empirical entropies match, the rates for statistical and online learning are the same. In addition to the study of minimax regret, we derive a generic forecaster that enjoys the established optimal rates. We also provide a recipe for designing online prediction algorithms that can be computationally efficient for certain problems. We illustrate the techniques by deriving existing and new forecasters for the case of finite experts and for online linear regression.