acceptodds
Under review as a conference paper at ICLR 2027

Regret and Covariance: A Characterization for Stochastic Optimization

Abstract

Quantifying regret typically involves repeatedly re-solving a stochastic optimization problem across simulated scenarios. Such an approach is costly: the cost scales with the number of scenarios and the cost of each solve. We propose that regret can instead be measured using the joint moments of the cost vector and the optimal decision . Working with the optimal concave and Lipschitz under only a feasible region value function , we show that regret always decomposes exactly as for a residual . We further show that when is affine in , which holds for unconstrained and equality-constrained (e.g., budget-constrained Markowitz) quadratic programs and many, but not all, linear programs. For all cases, we give a distribution-free bound that depends only on the radius of the feasible region and the cost covariance. We also derive concentration and asymptotic-normality results for the empirical regret, the latter under an explicit and checkable non-degeneracy condition.

Primary area:
optimization
Keywords:
optimization, regret, machine learning

Reviews

Among:
Shape:
1234this paper, Bottom 2%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.33 over 3 reviews, above 2% of the others.
Reviewer_gsKkOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

This paper studies regret in stochastic optimization through a covariance-based decomposition. The authors derive sufficient conditions under which the residual term vanishes, establish a distribution-free regret bound, and provide concentration and asymptotic-normality results. Experiments are presented to validate the theoretical findings.

Critical strengths
  1. The paper addresses a relevant problem in stochastic optimization and explores the relationship between regret and the structure of optimal decision rules.
  2. The authors acknowledge the limitations of the exact covariance representation and investigate the tightness of their distribution-free bound across problem sizes.
Critical weaknesses
  1. Limited theoretical novelty. The main covariance decomposition in Proposition 1 is an elementary algebraic identity. The two sufficient conditions in Theorem 3 are also straightforward: E[c]=0E[c]=0 follows directly from the residual definition, while affine decision rules follow from the linearity of expectation. The regret bound and statistical results mainly apply standard Lipschitz, Jensen and Hoeffding arguments. Overall, the theoretical contribution appears incremental.
  2. The experiments do not adequately support the main theoretical or computational claims. Sections 5.2 and 5.3 merely report numerical results without a detailed analysis of the residual term or other error sources. The experiments also lack comparisons against SAA methods.
  3. The presentation is unnecessarily lengthy relative to the technical content. For example, Section 4.3 largely repeats the regret definition in Section 3.2 and presents a direct consequence of Jensen's inequality as a separate theorem. Section 4.8 similarly consists mainly of a standard concentration result with limited connection to the central covariance analysis. The manuscript would benefit from substantial consolidation and clearer emphasis on its actual contributions.
  4. Several theoretical statements and definitions raise concerns that require clarification, as detailed in Question 1 below.
  5. The manuscript contains several noticeable errors and inconsistencies:
    • In Example 1 (Page 6), the reported regret is incorrect. It should be 1/61/6 rather than 1/21/2.
    • Figure 1 (Page 9) has very small legends and insufficient explanatory labeling.
    • The reference list contains substantial errors, including incomplete author information, inconsistent quotation marks and formatting.
Questions for authors
  1. I have the following concerns that require clarification or correction:
    • Theorem 3(a) assumes that π∗(c)=Ac+b\pi^{*}(c)=Ac+b holds almost surely, but its proof also requires this relationship to hold at μ=E[c]\mu=E[c]. This is not guaranteed even when CC is compact and convex. For example, let C=[−1,2]C=[-1,2], Z=[0,1]Z=[0,1], and P(c=−1)=P(c=2)=1/2P(c=-1)=P(c=2)=1/2. The optimal decisions agree almost surely with g(c)=(2−c)/3g(c)=(2-c)/3, yet π∗(μ)=0\pi^*(\mu)=0 and E[π∗(c)]=1/2E[\pi^*(c)]=1/2, yielding R=1/4≠0R=1/4\neq0. Thus, the theorem requires a stronger assumption.
    • Section 4.6.1 derives π∗(c)\pi^*(c) by minimizing c⊤z+λ2z⊤Qzc^\top z+\frac{\lambda}{2}z^\top Qz, but evaluates regret using only the linear cost c⊤zc^\top z, following the original definition. Why is the quadratic term excluded from the regret evaluation? The authors should clarify and justify this choice.
    • Section 4 defines Regret=μ⊤π∗(μ)−E[c⊤π∗(c)]≥0\mathrm{Regret}=\mu^\top\pi^*(\mu)-\mathbb{E}[c^\top\pi^*(c)]\geq0, with the empirical estimator Regret^n=cˉ⊤π∗(cˉ)−1n∑i=1nci⊤π∗(ci)\widehat{\mathrm{Regret}} _{n}={\bar{c}}^{\top} \pi^*(\bar c)-\frac{1}{n}\sum_{i=1}^n c_i^\top\pi^*(c_i). However, Section 5.1 uses Regret^=c⊤z^(c)−c⊤z^(E[c])\widehat{\mathrm{Regret}}=c^\top\hat z(c)-c^\top\hat z(\mathbb{E}[c]). This inconsistency should be corrected, and its implications for the reported experimental results should be clarified.
  2. How does the proposed method reduce computational cost compared with SAA? Can the authors provide a fair comparison of solver calls and runtime ?
  3. Why do the LP and QP experiments exhibit substantial differences between covariance-based and empirical regret estimates?
1 comment

I appreciate the authors' efforts in addressing my technical concerns. However, the main contribution remains an integrated-covariance characterization of regret and its associated analyses, which I find relatively incremental. Could the authors clarify what insights or implications go beyond this characterization, particularly in relation to existing work on EVPI and stochastic optimization?

Reviewer_acZfOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes that regret in stochastic optimization---defined as the expected value of perfect information (EVPI), Regret=v(μ)−E[v(c)]\mathrm{Regret} = v(\mu) - \mathbb{E}[v(c)] for the single-stage program min⁡z∈Zc⊤z\min _{z\in Z} c^\top z---can be characterized through the joint moments of the cost vector cc and the optimal decision rule π⋆(c)\pi^{\star}(c). The core results are as follows: (1) an exact algebraic decomposition Regret=−Cov(c,π⋆(c))−R(c)\mathrm{Regret} = -\mathrm{Cov}(c,\pi^{\star}(c)) - R(c) for a residual term R(c)R(c) (Proposition 1); (2) sufficient conditions under which R(c)=0R(c) = 0, namely global affinity of π⋆\pi^{\star} or E[c]=0\mathbb{E}[c]=0 (distributional), with applications to unconstrained and equality-constrained QPs; (3) a distribution-free bound Regret≤Dtr(Σc)\mathrm{Regret} \le D\sqrt{\mathrm{tr}(\Sigma _c)} depending only on the radius of ZZ and the cost covariance (Theorem 2); and (4) concentration and asymptotic-normality results for the empirical regret under a checkable non-degeneracy condition (Theorems 4--5). Experiments cover a synthetic LP, a synthetic QP/portfolio problem, a real-data CRSP portfolio study, and a shortest-path tightness analysis.

Critical strengths

1. The decomposition cleanly separates what is exact from what is not, and identifies the geometric dividing line. Proposition 1 plus Theorem 3 plus Table 6 give a complete and honest map: affine π∗\pi^* ⇒\Rightarrow exact covariance formula; piecewise-affine with support straddling active-set regions ⇒\Rightarrow generimcally nonzero residual; combinatorial ⇒\Rightarrow residual can be large but the bound still applies. This is consequential because it tells a practitioner, before running any Monte Carlo, whether the cheap covariance estimate is exact or merely a bound. The equality-constrained QP/Markowitz case (Corollary 2) is a genuinely useful exact result, since the budget constraint is universal in portfolio optimization.

2. The distribution-free bound requires no regularity of π∗\pi^* and is computable without re-solving. Theorem 2's bound depends only on D=sup⁡z∈Z∥z∥D = \sup_{z\in Z}\|z\| and tr(Σc)\mathrm{tr}(\Sigma_c), both of which are available before any scenario is drawn. The worked examples in Appendix A TSP, knapsack, optimal transport, LASSO) show that DD is often immediate from the combinatorial structure of ZZ, e.g., D=5D=\sqrt{5} for the assignment problem via the Frobenius norm of a permutation matrix---which makes the bound operationally useful as a screening tool even when it is loose.

Critical weaknesses

1. The proof technique is truly basic. Although the exact regret decomposition and the distribution-free regret bound looks interesting, the proof for these theoretical results in the main text is truly elementary. The proof can be even considered as the simple application of basic tools (like Jensen inequality) and listed assumptions (e.g. like the compactness of the feasible region) to the regret bound estimation. I am not an expert in the field of regret analysis in stochastic optimization, but am a little surprised that the theoretical results shown in this work does not exist in previous literature of this field. Overall, i think the conceptual novelties of the theoretical results is not enough to reach the acceptance threshold of a top AI conference.

2. Lack enough comparisons with existing theoretical/methodological results in regret estimation of stochastic approximation. This work does not give necessary comparisons with related works of regret analysis in stochastic optimization. Even though the existing standard way to estimate regret is sample average approximation and is expensive, such estimation method is more accurate than the regret upper bound estimation shown in theorem 2. More discussions about the advantages/disadvantages of the theoretical results should be added.

3. Constrained setting. The stochastic optimization problem investigated in this paper is mainly restricted within linear model min⁡z∈Zc⊤z\min_{z \in Z}c^{\top}z, but stochastic optimization includes many much more complex problems, such as convex-concave saddle problem or its strongly-convex-strongly-concave version . This also limits the novelty and application scenarios of the proposed theoretical results.

4. Unclear application of some theoretical results. Theorem 4 gives a concentration inequality to estimate the expected value of stochastic cost function, using several i.i.d. cost function samples. However, i did not find some application scenarios/examples of such result. Besides, the proof technique for the concentration inequality and the in-distribution convergence is not that technical.

Minor problems.

1. typos in abstract: Working with the optimal concave and Lipschitz under only a feasible region value function

2. some notation lacks explanations: the SPO loss in line 68 of introduction; the PcP_c measure in PcP_{c}-almost of line 155 in Definition 1.

Questions for authors

Besides the above weaknesses, i have other two questions:

  1. Regarding Theorem 3(a): Can the authors clarify the domain assumptions needed to conclude that $\pi^*(\mathbb E[c])=A\mathbb E[c]+b) $when the affine representation is assumed only PcP_c-almost surely? Is the intended assumption that the affine representation holds throughout a domain containing both the support of (c) and its mean?

  2. Regarding the LP and QP experiments: Can the authors report the residual term separately and verify the complete identity Regret⁡=−Cov⁡(c,π∗(c))−R(c)\operatorname{Regret}=-\operatorname{Cov}(c,\pi^*(c))-R(c) numerically? This would help distinguish structural residual error from finite-sample estimation error.

Reviewer_xr6EOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

The paper claims to show that regret (suboptimality gaps) of stochastic program can be measured using the joint moments of cost coefficients and optimal decision in parameterization of the cost coefficients. Distribution-free bounds on the regret is further derived.

Critical strengths

The paper presents innovative perspective on sensitivity analysis for linear stochastic programming.

Critical weaknesses

Many issues with consistency, correctness, and rigor in derivations and numerical experiments. Below are a few examples. (a). The paper is focused on stochastic linear program in (1), but then magically applies the results to quadratic program in Sect 4.6.1. (b). Proposition 2 claims to have shown that optimizers for strongly convex quadratic program with linear constraints are discontinuous in coefficients. (c). Corollary 3, as a corollay statement, states reasoning and derivations. This seems to be either AI artifact without proofreading or lack of understanding of how to make basic math statements. (d). Theorem 4 imposes bounded support, but experiments use Gaussian, log-normal, Gamma, Poisson, and negative-binomial distributions.

Questions for authors

Q. Can the author(s) rebute the weaknesses above?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.