Universal regression with adversarial responses

DOI10.1214/23-AOS2299arXiv2203.05067MaRDI QIDQ6136596FDOQ6136596

Patrick Jaillet, Moïse Blanchard

Publication date: 31 August 2023

Published in: The Annals of Statistics (Search for Journal in Brave)

Abstract: 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.

Full work available at URL: https://arxiv.org/abs/2203.05067

zbMATH Keywords

consistencynonparametric estimationstochastic processesmetric spacesonline learninggeneralizationstatistical learning theory

Mathematics Subject Classification ID

General nonlinear regression (62J02) General considerations in statistical decision theory (62C05) Generalized stochastic processes (60G20) Probabilistic metric spaces (54E70) Applied statistics (educational aspects) (97K80)

Cites Work

• A decision-theoretic generalization of on-line learning and an application to boosting
• Title not available (Why is that?)
• Prediction, Learning, and Games
• Consistent nonparametric regression. Discussion
• Geodesic regression and the theory of least squares on Riemannian manifolds
• Title not available (Why is that?)
• Spherical regression with errors in variables
• A distribution-free theory of nonparametric regression
• Total variation regularized Fréchet regression for metric-space valued data
• The weighted majority algorithm
• How to use expert advice
• Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems
• On the strong universal consistency of nearest neighbor regression function estimates
• Nonparametric inference for ergodic, stationary time series
• Learning from dependent observations
• Probability, Random Processes, and Ergodic Properties
• Sequential Prediction of Unbounded Stationary Time Series
• A simple randomized algorithm for sequential prediction of ergodic time series
• Title not available (Why is that?)
• Introduction to Multi-Armed Bandits
• Regression Estimation from an Individual Stable Sequence
• Universal Bayes consistency in metric spaces
• Title not available (Why is that?)
• Strong laws of large numbers for generalizations of Fréchet mean sets
• Title not available (Why is that?)
• Universal regression with adversarial responses

Cited In (1)

• Universal regression with adversarial responses

This page was built for publication: Universal regression with adversarial responses

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6136596)