  Learning a smooth graph signal from partially observed data is a well-studied
task in graph-based machine learning. We consider this task from the
perspective of optimal recovery, a mathematical framework for learning a
function from observational data that adopts a worst-case perspective tied to
model assumptions on the function to be learned. Earlier work in the optimal
recovery literature has shown that minimizing a regularized objective produces
optimal solutions for a general class of problems, but did not fully identify
the regularization parameter. Our main contribution provides a way to compute
regularization parameters that are optimal or near-optimal (depending on the
setting), specifically for graph signal processing problems. Our results offer
a new interpretation for classical optimization techniques in graph-based
learning and also come with new insights for hyperparameter selection. We
illustrate the potential of our methods in numerical experiments on several
semi-synthetic graph signal processing datasets.
