A randomized algorithm to solve reduced rank operator regression
Giacomo Turri Vladimir Kostic Pietro Novelli Massimiliano Pontil
We present and analyze an algorithm designed for addressing vector-valued
regression problems involving possibly infinite-dimensional input and output
spaces. The algorithm is a randomized adaptation of reduced rank regression, a
technique to optimally learn a low-rank vector-valued function (i.e. an
operator) between sampled data via regularized empirical risk minimization with
rank constraints. We propose Gaussian sketching techniques both for the primal
and dual optimization objectives, yielding Randomized Reduced Rank Regression
(R4) estimators that are efficient and accurate. For each of our R4 algorithms
we prove that the resulting regularized empirical risk is, in expectation
w.r.t. randomness of a sketch, arbitrarily close to the optimal value when
hyper-parameteres are properly tuned. Numerical expreriments illustrate the
tightness of our bounds and show advantages in two distinct scenarios: (i)
solving a vector-valued regression problem using synthetic and large-scale
neuroscience datasets, and (ii) regressing the Koopman operator of a nonlinear
stochastic dynamical system.