  This paper deals with the problem of accurately determining guaranteed
suboptimal values of an unknown cost function on the basis of noisy
measurements. We consider a set-valued variant to regression where, instead of
finding a best estimate of the cost function, we reason over all functions
compatible with the measurements and apply robust methods explicitly in terms
of the data. Our treatment provides data-based conditions under which
closed-forms expressions of upper bounds of the unknown function can be
obtained, and regularity properties like convexity and Lipschitzness can be
established. These results allow us to provide tests for point- and set-wise
verification of suboptimality, and tackle the cautious optimization of the
unknown function in both one-shot and online scenarios. We showcase the
versatility of the proposed methods in two control-relevant problems:
data-driven contraction analysis of unknown nonlinear systems and suboptimal
regulation with unknown dynamics and cost. Simulations illustrate our results.
