Set-valued regression and cautious suboptimization: From noisy data to optimality

Jaap Eising, Jorge Cortés · 2025

Read Set-valued regression and cautious suboptimization: From noisy data to optimality by Jaap Eising, Jorge Cortés (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-07622.txt.

Introduction

Jaap Eising and Jorge Cortés seek safe near-best values from noisy data in a 2025 paper. The true curve stays hid; reads of it come with bounded noise. The curve is built from a set of base forms, which bounds its kin. Their tack: grade the worst case the data still allow, then pick the dial that lifts that floor. Closed forms and curve traits make that pick solvable.

An online form then reads, picks, and reads again in turns. Each pick stays safe by the worst-case rule. Mild terms drive the loop to the true best dial in time. The paper serves control work where a bad pick costs dear. Proof backs both the still and the loop forms.

Catalog record

CREATORJaap Eising, Jorge Cortés
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE34 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2506-07622

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Set-valued regression and cautious suboptimization: From noisy data to optimality Thanks: This work was partially funded by ONR Award N00014-23-1-2353 and SNF/FW Weave Project 200021E_20397 Jaap Eising, Jorge Cortés Abstract This paper deals with the problem of finding suboptimal values of an unknown function on the basis of measured data corrupted by bounded noise. As a prior, we assume that the unknown function is parameterized in terms of a number of basis functions. Inspired by the informativity approach, we view the problem as the suboptimization of the worst-case estimate of the function. The paper provides closed form solutions and convexity results for this function, which enables us to solve the problem. After this, an online implementation is investigated, where we iteratively measure the function and perform a suboptimization. This nets a procedure that is safe at each step, and which, under mild assumptions, converges to the true optimizer. I Introduction Optimization of unknown functions on the basis of measured data is a topic with many applications ranging from control to machine learning. For instance, cost or reward functions in modern model-predictive control methods are often partially unknown due to modeling difficulties. On the other hand, sampling the functions is often possible, giving us access to measurements. Accurately determining suboptimal values of such unknown functions is at best a major part of some control objective and at worst safety-critical. This motivates the problem: determine suboptimal points of the unknown function on the basis of noisy measurements. We will investigate this problem both in a one-shot setting, where the data are given, and in an online setting that allows for repeated measurements. Literature review: Of course this is not a new problem, and there are many solutions with various setups of which we mention the ones most relevant. In order to solve the one-shot problem, the usual approach is to first employ the data to obtain a unique or, in some sense, ‘best’ estimate of the unknown function. For this, a number of nonparametric techniques have been developed to estimate unknown functions from data. Popular are e.g. Gaussian processes [ 1 ] and methods based on Lipschitz constants [ 2 , 3 , 4 ] . However, in this paper, we will make the assumption that the unknown function can be parameterized in terms of a number of basis functions or features. Common choices of basis functions are for instance linear, polynomial, Gaussian, or sigmoidal functions. These basis functions allow us to perform regression (see e.g. [ 5 , 6 ] ) on the parameters, leading to the ‘best’ estimate. Methods differ on what is considered this best estimate: For instance least squares (minimal Frobenius norm), ridge regression (minimal L_{2} norm), sparse or Lasso regression (minimal L_{1} norm). Analogously are the similar methods that have arisen in the nonlinear system-identification literature. Methods have been developed to determine models that are sparse [ 7 ] , low rank [ 8 , 9 , 10 ] , or both [ 11 ] within a class parameterized using a basis. After obtaining an estimate of the unknown function, one can treat this estimate as the true unknown function and apply any well-studied optimization technique to obtain suboptimal values. Given the fact that the data is corrupted by noise, it is reasonable to require some robustness from the methods applied (see e.g. [ 12 , 13 ] and the references therein). Apart from these one-shot optimization problems, we are also interested in online problems, in which we iteratively measure and optimize. This is inspired by methods such as extremum-seeking control [ 14 , 15 , 16 ] , whereas our implementation is markedly different. In contrast to this paradigm of regression (or: learning) followed by optimization, this paper can be viewed as being in line with the concept of informativity (see [ 17 , 18 ] ), where system properties are investigated for all systems compatible with the measurements. This falls within a recent surge of replacing system identification with methods on the basis of Willems’ fundamental lemma [ 19 ] . While most of these works deal with linear dynamics, the paper [ 20 ] dealt with bilinear systems by embedding them into a higher dimensional linear system. Similarly, the works [ 21 , 22 ] consider systems that are linear in their basis functions. Statement of contributions: As mentioned, we take a viewpoint related to that of the informativity framework. Using the assumed basis functions, we characterize the set of all parameters compatible with a set of measurements with bounded noise. This is named set-valued regression . Clearly, a point can be guaranteed to be suboptimal for the unknown function only if it is for all functions corresponding to compatible parameters. This motivates us to introduce cautious suboptimization , that is, the problem of finding such values in a way that is robust against the worst-case realization of the parameters. In order to resolve this, we derive closed forms and investigate convexity of this realization. Combining these allows us to resolve the problem using any method from convex optimization. Importantly, this allows us to derive guaranteed upper bounds of the optimal value of the unknown functions on the basis of potentially very small data sets. In addition to this one-shot problem, we investigate an online variant consisting of the iteration of two steps: Collecting local measurements and performing cautious suboptimization. This gives rise to a procedure which given increasingly sharp upper bounds of the unknown function. Moreover, assuming that the noise is randomly generated in addition to being bounded, we prove that this procedure converges to the true optimal value. Proofs are omitted for reasons of space and will appear elsewhere. II Problem statement Let 1 1 1 Throughout the paper, we use the following notation. We denote by \mathbb{N} and \mathbb{R} the sets of nonnegative integer and real numbers, respectively. We let \mathbb{R}^{n\times m} denote the space of n\times m real matrices. For vectors v\in\mathbb{R}^{n} , we write v\geqslant 0 (resp. v>0 ) for elementwise nonnegativity (resp. positivity). The sets of such vectors are denoted \mathbb{R}^{n}_{\geqslant 0}:=\{v\in\mathbb{R}^{n}|v\geqslant 0\} and \mathbb{R}^{n}_{>0}:=\{v\in\mathbb{R}^{n}|v>0\} . On the other hand, for P\in\mathbb{R}^{n\times n} , P\geqslant 0 (resp. P>0 ) denotes that P is symmetric positive semi-definite (resp. definite). We denote the smallest singular value of M\in\mathbb{R}^{n\times m} by \sigma_{-}(M) . For a set \mathcal{S}\subseteq\mathbb{R}^{n} we denote the convex hull by \conv(\mathcal{S}) and the interior by \interior(\mathcal{S}) . \phi_{i}:\mathbb{R}^{n}\rightarrow\mathbb{R} for i=1,\ldots,k be a collection of known basis functions (or features ) and consider the set consisting of all functions \phi^{\gamma}:\mathbb{R}^{n}\rightarrow\mathbb{R} linearly parameterized by \gamma\in\mathbb{R}^{k} as \phi^{\gamma}(z)=\Sigma_{i=1}^{k}\gamma_{i}\phi_{i}(z) . By collecting the basis functions in a vector-function as b(z):=\begin{bmatrix}\phi_{1}(z)&\cdots&\phi_{k}(z)\end{bmatrix}^{\top}, we can write the shorthand \phi^{\gamma}(z)=\gamma^{\top}b(z) . Consider a function \hat{\phi}:\mathbb{R}^{n}\rightarrow\mathbb{R} which is unknown but can be expressed as a linear combination of the features, i.e., \hat{\phi}(z)=\phi^{\hat{\gamma}}(z) , for some unknown parameter \hat{\gamma} . We are interested in deducing properties of the function \hat{\phi} on the basis of measurements. Suppose we sample the function for the variables z_{i} with i=1,\ldots,T and collect noisy measurements y_{i} of the true function, that is, y_{i}=\hat{\phi}(z_{i})+w_{i} . Here, the vector w_{i} denotes an unknown noise, or disturbance, for each i . In order to reason with

Read the complete text