- 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
- The paper addresses a relevant problem in stochastic optimization and explores the relationship between regret and the structure of optimal decision rules.
- The authors acknowledge the limitations of the exact covariance representation and investigate the tightness of their distribution-free bound across problem sizes.
Critical weaknesses
- 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: 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.
- 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.
- 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.
- Several theoretical statements and definitions raise concerns that require clarification, as detailed in Question 1 below.
- The manuscript contains several noticeable errors and inconsistencies:
- In Example 1 (Page 6), the reported regret is incorrect. It should be rather than .
- 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
- I have the following concerns that require clarification or correction:
- Theorem 3(a) assumes that holds almost surely, but its proof also requires this relationship to hold at . This is not guaranteed even when is compact and convex. For example, let , , and . The optimal decisions agree almost surely with , yet and , yielding . Thus, the theorem requires a stronger assumption.
- Section 4.6.1 derives by minimizing , but evaluates regret using only the linear cost , 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 , with the empirical estimator . However, Section 5.1 uses . This inconsistency should be corrected, and its implications for the reported experimental results should be clarified.
- How does the proposed method reduce computational cost compared with SAA? Can the authors provide a fair comparison of solver calls and runtime ?
- Why do the LP and QP experiments exhibit substantial differences between covariance-based and empirical regret estimates?
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?