A Randomized Algorithm to Solve Reduced Rank Operator Regression
Giacomo Turri, Vladimir Kostić, Pietro Novelli, Massimiliano Pontil · SIAM Journal on Mathematics of Data Science · 2026
Abstract. We present and analyze an algorithm for solving vector-valued regression problems over possibly infinite-dimensional input and output spaces. The algorithm is a randomized adaptation of the well-established reduced rank regression, designed to optimally learn a low-rank operator between feature representations of sampled data. We handle both finite and infinite-dimensional feature spaces and propose Gaussian sketching techniques, resulting in randomized reduced rank regression (R[Formula: see text]) estimators. We show that these estimators are both computationally efficient and statistically accurate, a crucial aspect in recent applications involving dynamical systems and conditional mean embeddings. We establish that the regularized empirical risk of our R[Formula: see text] estimators is, in expectation with respect to the randomness of a sketch, arbitrarily close to the optimal value when hyperparameters are properly chosen. Numerical experiments illustrate the tightness of our bounds and showcase advantages in two distinct scenarios: (i) solving a vector-valued regression problem using synthetic and large-scale neuroscience datasets, and (ii) regressing the Koopman or transfer operator of a nonlinear dynamical system.