Optimal Multitask Linear Regression and Contextual Bandits under Sparse Heterogeneity

Large and complex datasets are often collected from several, possibly heterogeneous sources. Multitask learning methods improve efficiency by leveraging commonalities across datasets while accounting for possible differences among them. Here, we study multitask linear regression and contextual bandits under <i>sparse heterogeneity</i>, where the source/task-associated parameters are equal to a global parameter plus a sparse task-specific term. We propose a novel two-stage estimator called MOLAR that leverages this structure by first constructing a covariate-wise weighted median of the task-wise linear regression estimates and then shrinking the task-wise estimates towards the weighted median. Compared to task-wise least squares estimates, MOLAR improves the dependence of the estimation error on the data dimension. Extensions of MOLAR to generalized linear models and constructing confidence intervals are discussed in the paper. We then apply MOLAR to develop methods for sparsely heterogeneous multitask contextual bandits, obtaining improved regret guarantees over single-task bandit methods. We further show that our methods are minimax optimal by providing a number of lower bounds. Finally, we support the efficiency of our methods by performing experiments on both synthetic data and the PISA dataset on student educational outcomes from heterogeneous countries.大规模且结构复杂的数据集通常源自多个可能存在异质性的数据源。多任务学习方法通过利用不同数据集间的共性，同时兼顾数据集间可能存在的差异，从而提升学习效率。本文针对**稀疏异质性（sparse heterogeneity）**设定下的多任务线性回归与上下文老虎机（contextual bandits）展开研究，该设定中与数据源或任务相关的参数等于全局参数加上一个稀疏的任务专属项。我们提出了一种名为MOLAR的新型两阶段估计器，该估计器利用上述结构：首先对各任务的线性回归估计值计算按协变量加权的中位数，随后将各任务的估计值向该加权中位数进行收缩。相较于各任务单独的最小二乘估计，MOLAR优化了估计误差与数据维度之间的依赖关系。本文还讨论了MOLAR向广义线性模型（generalized linear models）的扩展方法，以及置信区间的构建思路。随后，我们将MOLAR应用于稀疏异质性多任务上下文老虎机的方法研发，相较于单任务老虎机方法，获得了更优的遗憾保证。此外，我们通过推导若干下界证明了所提方法具备极小极大最优（minimax optimal）性。最后，我们通过在合成数据集与源自不同国家的学生教育成果PISA数据集上开展实验，验证了所提方法的有效性。