UNIVERSAL REGRESSION WITH ADVERSARIAL RESPONSES

• 成果类型: Article
• 署名作者: Blanchard, Moise; Jaillet, Patrick
• 署名单位: Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT)
• 刊物名称: ANNALS OF STATISTICS
• ISSN/ISSBN: 0090-5364
• DOI: 10.1214/23-AOS2299
• 发表日期: 2023
• 页码: 1401-1426
• 关键词: sequential prediction; Consistency

摘要

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 optimisti-cally universal learning rules, that is, 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.