Sharper Risk Bound for Multi-Task Learning with Multi-Graph Dependent Data
This work addresses a foundational theoretical bottleneck in multi-task learning with graph-structured data, offering improved generalization guarantees for applications like Macro-AUC optimization.
The paper tackles the sub-optimal risk bound of O(1/√n) in multi-task learning with graph-dependent data by developing a new Bennett-type inequality, achieving a sharper bound of O(log n/n). This theoretical advancement is applied to Macro-AUC optimization, showing superiority over prior work in experiments.
In multi-task learning (MTL) with each task involving graph-dependent data, existing generalization analyses yield a \emph{sub-optimal} risk bound of $O(\frac{1}{\sqrt{n}})$, where $n$ is the number of training samples of each task. However, to improve the risk bound is technically challenging, which is attributed to the lack of a foundational sharper concentration inequality for multi-graph dependent random variables. To fill up this gap, this paper proposes a new Bennett-type inequality, enabling the derivation of a sharper risk bound of $O(\frac{\log n}{n})$. Technically, building on the proposed Bennett-type inequality, we propose a new Talagrand-type inequality for the empirical process, and further develop a new analytical framework of the local fractional Rademacher complexity to enhance generalization analyses in MTL with multi-graph dependent data. Finally, we apply the theoretical advancements to applications such as Macro-AUC optimization, illustrating the superiority of our theoretical results over prior work, which is also verified by experimental results.