Worst-case low-rank approximations
This work addresses the problem of robust low-rank approximations for researchers and practitioners in fields like health and environmental sciences, offering incremental improvements over existing worst-case methods.
The paper tackles the unreliability of standard PCA under distributional shifts across heterogeneous domains by developing a unified framework, wcPCA, and novel estimators like norm-minPCA and norm-maxregret, proving worst-case optimality and showing marked improvements in worst-case performance with only minor average losses in simulations and real-world applications.
Real-world data in health, economics, and environmental sciences are often collected across heterogeneous domains (such as hospitals, regions, or time periods). In such settings, distributional shifts can make standard PCA unreliable, in that, for example, the leading principal components may explain substantially less variance in unseen domains than in the training domains. Existing approaches (such as FairPCA) have proposed to consider worst-case (rather than average) performance across multiple domains. This work develops a unified framework, called wcPCA, applies it to other objectives (resulting in the novel estimators such as norm-minPCA and norm-maxregret, which are better suited for applications with heterogeneous total variance) and analyzes their relationship. We prove that for all objectives, the estimators are worst-case optimal not only over the observed source domains but also over all target domains whose covariance lies in the convex hull of the (possibly normalized) source covariances. We establish consistency and asymptotic worst-case guarantees of empirical estimators. We extend our methodology to matrix completion, another problem that makes use of low-rank approximations, and prove approximate worst-case optimality for inductive matrix completion. Simulations and two real-world applications on ecosystem-atmosphere fluxes demonstrate marked improvements in worst-case performance, with only minor losses in average performance.