Sharp Regret Bounds and a Task-Covariance Correction for Spectral Representation Learning

Abstract

Spectral features can remain optimal under strongly uneven task preferences when they retain the directions most useful to the tasks. In a local-task model, expected probing gain depends on the task prior only through its covariance $\Lambda$: with $B$ recording dependence between views, $k$ spectral features span the leading eigenspace of $B{B}^{\top }$, while task-optimal features span that of $B\Lambda B^{\top }$. We derive alignment-dependent regret bounds, matching worst-case lower bounds for a flat leading spectrum, and bounds using the leading $2k$ directions with a spectral-tail term; a spectral gap makes the bound quadratic in small anisotropy. We also bound the imbalance from random preference patterns and from averaging independent tasks with an isotropic population covariance. With known $\Lambda$, changing one term of the spectral contrastive loss selects task-optimal features; with a labelled task bank, we propose a diagnostic and test correction without retraining. Correction reduces synthetic held-out regret from $0.858$ to $0.003$ with $2000$ tasks when less task-relevant directions dominate, and on CIFAR-100 lowers empirical regret by $0.031$--$0.053$ on held-out fine-label tasks using the same images. With a small task bank, however, correction can hurt.

53 pages, 6 figures. Comments welcome