A NO-FREE-LUNCH THEOREM FOR MULTITASK LEARNING

• 成果类型: Article
• 署名作者: Hanneke, S. T. E. V. E.; Kpotufe, Samory
• 署名单位: Purdue University System; Purdue University; Columbia University
• 刊物名称: ANNALS OF STATISTICS
• ISSN/ISSBN: 0090-5364
• DOI: 10.1214/22-AOS2189
• 发表日期: 2022
• 页码: 3119-3143
• 关键词: oracle inequalities; CLASSIFICATION; complexity; benefits; tasks

摘要

Multitask learning and related areas such as multisource domain adapta-tion address modern settings where data sets from N related distributions {Pt } are to be combined toward improving performance on any single such distri-bution D. A perplexing fact remains in the evolving theory on the subject: while we would hope for performance bounds that account for the contribu-tion from multiple tasks, the vast majority of analyses result in bounds that improve at best in the number n of samples per task, but most often do not improve in N. As such, it might seem at first that the distributional settings or aggregation procedures considered in such analyses might be somehow unfa-vorable; however, as we show, the picture happens to be more nuanced, with interestingly hard regimes that might appear otherwise favorable.In particular, we consider a seemingly favorable classification scenario where all tasks Pt share a common optimal classifier h*, and which can be shown to admit a broad range of regimes with improved oracle rates in terms of N and n. Some of our main results are:center dot We show that, even though such regimes admit minimax rates account-ing for both n and N, no adaptive algorithm exists, that is, without access to distributional information, no algorithm can guarantee rates that improve with large N for n fixed.center dot With a bit of additional information, namely, a ranking of tasks {Pt } according to their distance to a target D, a simple rank-based procedure can achieve near optimal aggregations of tasks' data sets, despite a search space exponential in N. Interestingly, the optimal aggregation might exclude certain tasks, even though they all share the same h*.