# Universal Regression with Adversarial Responses

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 40 references that are in the map.
- First posted on arXiv 9 Mar 2022.

## Builds on (most cited first, 11 of 11)

- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [Universal Bayes consistency in metric spaces](https://mlsanity.com/paper/1906.09855/) (2019)
- [Learning Whenever Learning is Possible: Universal Learning under General Stochastic Processes](https://mlsanity.com/paper/1706.01418/) (2017)
- [Universal consistency and rates of convergence of multiclass prototype algorithms in metric spaces](https://mlsanity.com/paper/2010.00636/) (2020)
- [Universal Online Learning: an Optimistically Universal Learning Rule](https://mlsanity.com/paper/2201.05947/) (2022)
- [Universal Online Learning with Bounded Loss: Reduction to Binary Classification](https://mlsanity.com/paper/2112.14638/) (2021)
- [Universal Online Learning with Unbounded Losses: Memory Is All You Need](https://mlsanity.com/paper/2201.08903/) (2022)
- [Total Variation Regularized Fr'echet Regression for Metric-Space Valued Data](https://mlsanity.com/paper/1904.09647/) (2019)
- [Open Problem: Is There an Online Learning Algorithm That Learns Whenever Online Learning Is Possible?](https://mlsanity.com/paper/2107.09542/) (2021)
- [Asymptotic Theory of Geometric and Adaptive k-Means Clustering](https://mlsanity.com/paper/2202.13423/) (2022)
- [Efficient Kirszbraun Extension with Applications to Regression](https://mlsanity.com/paper/1905.11930/) (2019)

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

- [Multiclass Learnability Beyond the PAC Framework: Universal Rates and Partial Concept Classes](https://mlsanity.com/paper/2210.02297/) (2022)
- [Adversarial Rewards in Universal Learning for Contextual Bandits](https://mlsanity.com/paper/2302.07186/) (2023)
- [Contextual Bandits and Optimistically Universal Learning](https://mlsanity.com/paper/2301.00241/) (2022)
- [A Theory of Optimistically Universal Online Learnability for General Concept Classes](https://mlsanity.com/paper/2501.08551/) (2025)
- [Characterizing Online and Private Learnability under Distributional Constraints via Generalized Smoothness](https://mlsanity.com/paper/2602.20585/) (2026)

## Abstract (arXiv)

We provide algorithms for regression with adversarial responses under large classes of non-i.i.d. instance sequences, on general separable metric spaces, with provably minimal assumptions. We also give characterizations of learnability in this regression context. We consider universal consistency which asks for strong consistency of a learner without restrictions on the value responses. Our analysis shows that such an objective is achievable for a significantly larger class of instance sequences than stationary processes, and unveils a fundamental dichotomy between value spaces: whether finite-horizon mean estimation is achievable or not. We further provide optimistically universal learning rules, i.e., such that if they fail to achieve universal consistency, any other algorithms will fail as well. For unbounded losses, we propose a mild integrability condition under which there exist algorithms for adversarial regression under large classes of non-i.i.d. instance sequences. In addition, our analysis also provides a learning rule for mean estimation in general metric spaces that is consistent under adversarial responses without any moment conditions on the sequence, a result of independent interest.