Pith. sign in

REVIEW 4 major objections 4 minor 23 references

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

T0 review · 4 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash

Pith's one-line read The paper proves a closed-form worst-case upper bound for functions that are linear in known basis functions, and an online procedure whose certified optimality gap converges to zero when the noise is uniformly distributed.

desk verdict Useful framework and a genuinely monotone certified bound, but every major theorem is unproved and the convergence claim leans on exact uniform noise plus a missing argument about the moving iterate. read the letter →

arxiv 2506.07622 v1 pith:7EF4FWXG submitted 2025-06-09 math.OC

classification math.OC MSC 90C2590C4793B30
keywords set-valuedregressioncautioussuboptimizationboundednoiseworst-caseboundsconvexoptimizationonlinedatainformativityuncertaintyquantification
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper asks what can be guaranteed about the minimum of an unknown function when the only information is a finite set of noisy samples and the prior that the function is a linear combination of known basis functions. Rather than commit to a single regression estimate, it keeps every parameter vector consistent with the bounded-noise measurements and optimizes the worst-case upper bound, a stance it calls cautious suboptimization. It derives a closed-form expression for that upper bound, gives data-dependent conditions under which the bound is convex, and builds an online procedure that measures locally around the current candidate and updates the set of consistent parameters. The procedure provides certified upper bounds on the true minimum that never increase, and under uniformly distributed noise the expected uncertainty goes to zero, so the iterates converge to the true optimizer.

What carries the argument

The load-bearing object is the consistent parameter set $\Gamma$, represented as the quadratic set $\Gamma=Z(N)=\{\gamma\in\mathbb{R}^k : [1\ \gamma^{\top}] N [1\ \gamma^{\top}]^{\top} \ge 0\}$, where $N$ is the data matrix built from the measurements and the noise model's matrix $\Pi$. Because $\Pi_{22}<0$ and $N_{22}<0$ exactly when the basis measurements are sufficiently rich, each $\Gamma_k$ is a bounded convex set, and the intersection $\Gamma_0\cap\cdots\cap\Gamma_{k-1}$ is the set of parameters still compatible with all measurements so far. The online algorithm is driven by a finite local sampling pattern $F$ with $0\in\operatorname{int}\operatorname{conv} F$: at each step it measures the function at $z_k+f$ for $f\in F$, builds $N_k$, and recomputes $z_k$ as the minimizer of $\phi_+(\cdot;\Gamma_0\cap\cdots\cap\Gamma_{k-1})$ over $z_{k-1}+\operatorname{conv} F$. The strict convexity of these subproblems and the monotone decrease of the $\phi_+$ values are what make every iterate safe: each step yields a certified upper bound on the unknown function's true minimum.

What would settle it

Run the paper's quadratic example with the same measurement pattern $F$ and with noise sampled uniformly from $Z(\Pi)$, and estimate the expected uncertainty $U(z;\Gamma_0\cap\cdots\cap\Gamma_k)$ at a fixed point $z$ for growing $k$. Theorem IV.3 predicts a monotone decrease to zero; if for any $z$ the empirical mean levels off above zero, the convergence claim as stated is false.

Watch

Extended reading notes

Core claim

On its own terms, the paper establishes that cautious suboptimization is tractable because the worst-case upper bound has a closed algebraic form. With $\Pi_{22}<0$ and full-rank measurements $\Phi$, the consistent parameter set is $\Gamma=Z(N)$, where $N$ is the data matrix of equation (3); Theorem III.1 states that $\phi_{+}(z;\Gamma)=\sup_{\gamma\in\Gamma}\gamma^{\top}b(z) = -N_{12}N_{22}^{-1}b(z) + \sqrt{(N\mid N_{22})\,b(z)^{\top}(-N_{22}^{-1})b(z)}$. The linear term is the least-squares estimate and the square-root term is the worst-case correction from the remaining uncertainty. In the online setting the paper shows that intersecting the new compatible-parameter sets keeps each subproblem strictly convex, produces monotonically nonincreasing upper bounds on the true minimum, and, when the noise is uniformly distributed on the bounded noise set, drives the expected uncertainty at every point to zero.

Load-bearing premise

The online convergence result relies on the noise vectors being uniformly distributed over the bounded noise set, not merely bounded, together with a uniform lower bound on the smallest singular value of the local measurement matrix; the paper's own constant-noise experiment shows that without the distributional assumption the iterates stall at a suboptimal point.

Editorial extensions

If this is right

  • A user who knows the basis functions and has only a small noisy data set can compute a guaranteed value $\delta$ for any query point $z$ such that the true function satisfies $\hat{\phi}(z)\le\delta$, directly from the closed form.
  • If the basis functions are convex and the data satisfy the paper's nonnegativity criteria, the one-shot cautious problem $\min_{z\in S}\phi_+(z;\Gamma)$ is a convex program solvable by gradient descent with the closed-form gradient.
  • The online algorithm gives a stopping certificate at every iteration: the gap between the certified upper bound and the true minimum is at most the maximum uncertainty over the search region.
  • When noise is uniformly distributed on the noise set, the expected uncertainty vanishes, so the expected gap between the algorithm's upper bound and the true optimal value goes to zero.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The closed-form upper bound and its gradient could be used directly as an acquisition rule for choosing where to measure next, although the paper only analyzes a fixed local pattern $F$.
  • Because each new measurement only shrinks $\Gamma$ by adding a quadratic constraint, a practical implementation for large $k$ would need a representation or outer approximation of the intersection; the paper leaves this computational question open.
  • The uniform-noise assumption in Theorem IV.3 is strong: for other bounded zero-mean noise distributions the proof does not apply, so a practitioner should test the stopping criterion against adversarial constant noise before relying on convergence.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 4 minor

Summary. The paper develops a set-valued regression framework for linearly parameterized unknown functions from measurements corrupted by bounded noise. It defines the set Gamma of parameters compatible with the data as the ellipsoid Z(N), derives closed-form worst-case upper and lower envelopes and gradients, gives convexity criteria, and introduces an online procedure that samples near the current candidate minimizer and maintains certified upper bounds on the true minimum. The central convergence claim is that, under uniformly distributed noise, the expected uncertainty goes to zero and the online bounds approach the true optimal value. All proofs are deferred to a later publication.

Significance. If the deferred proofs are valid, the paper would contribute a clean bridge between data informativity and robust optimization: the closed-form expressions for phi_plus and phi_minus give certified suboptimality bounds from small data sets without fitted parameters, and the convexity criteria make the one-shot problem tractable by standard convex optimization. The simulation setup is described in enough detail to be reproducible, and the constant-noise experiment in Figure 3 is honest about the limitations of the bounded-noise setting. However, the absence of derivations makes the main theorems unverifiable in the current manuscript, and the online convergence argument has a gap between pointwise uncertainty decay and convergence of the moving iterates.

major comments (4)
  1. [Section I] The manuscript states 'Proofs are omitted for reasons of space and will appear elsewhere' and then states Theorem III.1, Lemma III.4, Theorem IV.1, and Theorem IV.3 without derivations. Since Theorem IV.3 is the only result that drives the convergence claim, and since the closed form in Theorem III.1 is the basis for the whole method, the submission is not self-contained. I recommend including complete proofs in an appendix or in the main text before the paper can be evaluated for a journal.
  2. [Section IV, after Theorem IV.3] Theorem IV.3 establishes for each fixed z that E[U(z; Gamma0 cap ... cap Gamma_k)] converges to 0. The paragraph following it concludes that the expected difference between min_{z in S} phi_+(z; Gamma0 cap ... cap Gamma_k) and the true minimum converges to zero. This step needs uniform convergence of the uncertainty over S, or an additional argument controlling the moving iterates z_k; pointwise convergence alone does not imply convergence at the sequence of points generated by the algorithm. This is load-bearing for the abstract's promise that the online procedure converges to the true optimizer.
  3. [Section IV, Eqs. (8)-(9)] The online update in (9) requires minimizing phi_+(z; Gamma0 cap ... cap Gamma_{k-1}), but the closed forms in Theorem III.1 and Lemma III.3 apply only when Gamma is a single ellipsoid Z(N). An intersection of ellipsoids is not generally representable as Z(N), and no extension of the closed form to intersections is provided. If the intended implementation instead uses a joint-data ellipsoid, such as the set obtained from a block-diagonal noise model, that replacement must be stated explicitly and the monotonicity and convergence results must be re-examined for the larger set. As written, the online algorithm is not computable from the formulas in the paper.
  4. [Section IV, Theorem IV.3, and Section V, Figure 3] The convergence guarantee rests on the exact assumptions W_k^T ~ Uni(Z(Pi)) for k >= 1 and sigma_-(Phi_F(z)) >= a for all z. These are substantial hypotheses, not merely mild regularity conditions: Section V's own constant-noise experiment shows that with merely bounded adversarial noise the iterates converge to the strictly suboptimal point (0.1519, 0.1519) and the bound does not approach the true minimum. The abstract's phrase 'under mild assumptions' therefore understates the scope of the result, and the proof must address the uniform singular-value bound over the domain or over the reachable set of iterates.
minor comments (4)
  1. [Section II, Eq. (1)] There is a dimension mismatch: the text writes Phi in R^{T x k}, but the displayed matrix and the relation Y = gamma^T Phi + W require Phi in R^{k x T}.
  2. [Section IV, Theorem IV.1] The name 'online gradient descent' is misleading because the update in (9) is a full re-optimization over S(z_{k-1}), not a gradient step; a name such as 'online cautious re-optimization' would match the procedure better.
  3. [Section V, Figure 3 paragraph] The text contains a duplicated word ('the origin origin') and the figure caption says 'nonrandom noise' while the text describes a constant noise sample applied after k=1; these should be harmonized.
  4. [Section V and Theorem IV.3] The simulation does not verify the assumption sigma_-(Phi_F(z)) >= a for all z used in Theorem IV.3; since the domain is unbounded, this requires a proof or an explicit check, and the paper should state how the assumption is satisfied in the example.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the central worst-case bounds are derived from the data and noise model by convex analysis, not assumed or fitted; the self-citations are motivational, not load-bearing.

full rationale

The paper's central claim is the closed-form expression for phi_plus and phi_minus in Theorem III.1, obtained by maximizing and minimizing the linear function gamma^T b(z) over the ellipsoidal set Gamma = Z(N). This is a genuine derivation from Assumption 1 and the definition of N in (3): the quadric inequality [1; gamma]^T N [1; gamma] >= 0, with N22 < 0, is exactly the consistency set, and the displayed formula is the standard explicit solution of that quadratically constrained linear problem. It is not equivalent to its input by construction, because the input is the set Gamma and the output is its support function in direction b(z); the formula contains the Schur complement and the least-squares term, which are computed, not postulated. No fitted parameter is later renamed as a prediction: the online upper bound in Theorem IV.1 follows because the true parameter gamma_hat lies in every Gamma_k, so minimizing the upper bound over the intersection yields a certified bound. The citations to the informativity framework [17], [18], which include one of the authors, are used for vocabulary and motivation, not as the load-bearing argument for any theorem; the convex-analysis derivation does not reduce to those works. The paper explicitly states 'Proofs are omitted for reasons of space and will appear elsewhere.' That is a completeness and verifiability limitation, but an omitted proof is not circularity. Similarly, Theorem IV.3's reliance on uniformly distributed noise and on sigma_-(Phi_F(z)) >= a is a substantive distributional assumption; Section V's constant-noise simulation shows that without randomness the iterates stall, which is a correctness caveat, not a circular reduction. No step in the paper's derivation chain equates a fitted constant with a prediction or imports an unverified uniqueness result from the authors' prior work. The result stands or falls on the (currently omitted) proofs and on the stated noise assumptions, not on circular reasoning.

Assumptions & free parameters 1 free parameters · 6 assumptions · 0 invented entities

The central claim rests on the exact basis-function parameterization, an accurate bounded-noise model, persistence-of-excitation in online sampling, and, for the convergence theorem, uniformly distributed noise. These are stated assumptions rather than fitted parameters. The optional lambda is a user-chosen trade-off. No invented entities are introduced.

free parameters (1)
  • lambda = not specified (lambda >= 0)
    User-chosen weight in the generalized objective (6) balancing upper bound and uncertainty; the core cautious suboptimization problem is recovered at lambda = 0, so it is not a fitted constant for the central claim.
assumptions (6)
  • domain assumption Unknown function is an exact linear combination of known basis functions, phi_hat = gamma_hat^T b(.).
    Introduced in Section II; if the true function is outside the span, Gamma may not contain the true parameter and the certified bounds are void.
  • domain assumption Noise is bounded by a known quadratic inequality W^T in Z(Pi) with Pi22 < 0 and nonnegative Schur complement.
    Assumption 1 in Section II; an incorrect or too-small Pi can make Gamma empty or exclude the true parameter.
  • domain assumption For the online theorem, the finite set F satisfies 0 in int(conv F) and Phi_F(z) has full row rank for all z.
    Assumptions before Theorem IV.1; this persistence-of-excitation condition keeps Gamma bounded and lets local measurements shrink the parameter set.
  • domain assumption For the convergence theorem, noise samples are uniformly distributed on Z(Pi) and sigma_minus(Phi_F(z)) >= a for all z.
    Assumptions of Theorem IV.3; the constant-noise simulation in Section V shows convergence can fail without the random-noise assumption.
  • domain assumption Convexity criteria require convex basis functions and parameter sets contained in the nonnegative orthant.
    Corollaries III.5 and III.6; these conditions are needed to make the cautious suboptimization problem convex.
  • standard math Standard Schur complement and convex analysis facts for quadratic sets are used without proof.
    Used throughout Section III, e.g., the characterization Gamma = Z(N) and the closed-form support function expressions.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Set-valued regression and cautious suboptimization: From noisy data to optimality." pith.science (2026). https://pith.science/paper/7EF4FWXG

@misc{pith2026250607622,
  author       = {Pith},
  title        = {Pith review of: Set-valued regression and cautious suboptimization: From noisy data to optimality},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/7EF4FWXG}},
  note         = {Machine review of arXiv:2506.07622}
}
read the original 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.

Figures

Figures reproduced from arXiv: 2506.07622 by the authors.

Figure 1
Figure 1. The simulation results for the initial condition [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. The simulation results for eight different initial conditions. In [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗
Figure 3
Figure 3. The simulation results for the initial condition [PITH_FULL_IMAGE:figures/full_fig_p006_3.png] view at source ↗

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

23 extracted references · 20 canonical work pages

  1. [1]

    C. E. Rasmussen and C. K. I. Williams, Gaussian Processes for Machine Learning. Cambridge, MA: MIT Press, 2005

  2. [2]

    Optimal estimation theory for dynamic systems with set membership uncertainty: An overview,

    M. Milanese and A. Vicino, “Optimal estimation theory for dynamic systems with set membership uncertainty: An overview,” Automatica, vol. 27, no. 6, pp. 997–1009, 1991

  3. [3]

    Set membership estimation of nonlinear regressions,

    M. Milanese and C. Novara, “Set membership estimation of nonlinear regressions,” in IFAC World Congress, vol. 35, Barcelona, Spain, 2002, pp. 7–12

  4. [4]

    Lazily adapted constant kinky inference for nonparametric regression and model-reference adaptive control,

    J. Calliess, S. J. Roberts, C. E. Rasmussen, and J. Maciejowski, “Lazily adapted constant kinky inference for nonparametric regression and model-reference adaptive control,” Automatica, vol. 122, p. 109216, 2020

  5. [5]

    Hastie, R

    T. Hastie, R. Tibshirani, and J. Friedman, The Elements of Statistical Learning: Data Mining, Inference, and Prediction , 2nd ed., ser. Springer Series in Statistics. New York: Springer, 2013

  6. [6]

    Regression shrinkage and selection via the Lasso,

    R. Tibshirani, “Regression shrinkage and selection via the Lasso,” Journal of the Royal Statistical Society. Series B , vol. 58, no. 1, pp. 267–288, 1996

  7. [7]

    Discovering governing equations from data by sparse identification of nonlinear dynamical systems,

    S. L. Brunton, J. L. Proctor, and J. N. Kutz, “Discovering governing equations from data by sparse identification of nonlinear dynamical systems,” Proceedings of the National Academy of Sciences , vol. 113, no. 15, pp. 3932–3937, 2016

  8. [8]

    Dynamic mode decomposition of numerical and exper- imental data,

    P. J. Schmid, “Dynamic mode decomposition of numerical and exper- imental data,” Journal of Fluid Mechanics , vol. 656, pp. 5–28, 2010

Show all 23 references
  1. [9]

    Dynamic mode decomposition and its variants,

    ——, “Dynamic mode decomposition and its variants,” Annual Review of Fluid Mechanics , vol. 54, no. 1, pp. 225–254, 2022

  2. [10]

    J. N. Kutz, S. L. Brunton, B. W. Brunton, and J. L. Proctor, Dynamic Mode Decomposition: Data-Driven Modeling of Complex Systems, ser. Other Titles in Applied Mathematics. Philadelphia, PA: SIAM, 2016, vol. 149

  3. [11]

    Sparsity-promoting dynamic mode decomposition,

    M. R. Jovanovi ´c, P. J. Schmid, and J. W. Nichols, “Sparsity-promoting dynamic mode decomposition,” Physics of Fluids , vol. 26, no. 2, p. 024103, 2014

  4. [12]

    Ben-Tal, L

    A. Ben-Tal, L. E. Ghaoui, and A. Nemirovski, Robust Optimization, ser. Applied Mathematics Series. Princeton, NJ: Princeton University Press, 2009

  5. [13]

    Theory and applica- tions of robust optimization,

    D. Bertsimas, D. B. Brown, and C. Caramanis, “Theory and applica- tions of robust optimization,” SIAM Review, vol. 53, no. 3, pp. 464– 501, 2011

  6. [14]

    Stability of extremum seeking feedback for general nonlinear dynamic systems,

    M. Krsti ´c and H.-H. Wang, “Stability of extremum seeking feedback for general nonlinear dynamic systems,” Automatica, vol. 36, no. 4, pp. 595–601, 2000

  7. [15]

    K. B. Ariyur and M. Krsti ´c, Real-Time Optimization by Extremum- Seeking Control. New York: Wiley, 2003

  8. [16]

    Solving smooth and nonsmooth multivariable extremum seeking problems by the methods of nonlinear program- ming,

    A. Teel and D. Popovic, “Solving smooth and nonsmooth multivariable extremum seeking problems by the methods of nonlinear program- ming,” in American Control Conference , Arlington, V A, 2001, pp. 2394–2399

  9. [17]

    Data informativity: a new perspective on data-driven analysis and control,

    H. J. van Waarde, J. Eising, H. L. Trentelman, and M. K. Camlibel, “Data informativity: a new perspective on data-driven analysis and control,” IEEE Transactions on Automatic Control , vol. 65, no. 11, pp. 4753–4768, 2020

  10. [18]

    Quadratic matrix inequalities with applications to data-based control,

    H. J. van Waarde, M. K. Camlibel, J. Eising, and H. L. Trentelman, “Quadratic matrix inequalities with applications to data-based control,” SIAM Journal on Control and Optimization , vol. 61, no. 4, pp. 2251– 2281, 2023

  11. [19]

    A note on persistency of excitation,

    J. C. Willems, P. Rapisarda, I. Markovsky, and B. L. M. De Moor, “A note on persistency of excitation,” Systems & Control Letters, vol. 54, no. 4, pp. 325–329, 2005

  12. [20]

    Data-driven simulation of generalized bilinear systems via linear time-invariant embedding,

    I. Markovsky, “Data-driven simulation of generalized bilinear systems via linear time-invariant embedding,” IEEE Transactions on Automatic Control, vol. 68, no. 2, pp. 1101–1106, 2022

  13. [21]

    Data-driven stabilization of nonlinear polynomial systems with noisy data,

    M. Guo, C. D. Persis, and P. Tesi, “Data-driven stabilization of nonlinear polynomial systems with noisy data,” IEEE Transactions on Automatic Control , vol. 67, no. 8, pp. 4210–4217, 2021

  14. [22]

    Learning controllers from data via approximate nonlinearity cancellation,

    C. De Persis, M. Rotulo, and P. Tesi, “Learning controllers from data via approximate nonlinearity cancellation,” IEEE Transactions on Automatic Control , vol. 68, no. 10, pp. 6082–6097, 2023

  15. [23]

    Boyd and L

    S. Boyd and L. Vandenberghe, Convex Optimization . Cambridge, UK: Cambridge University Press, 2009

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.