- Rating
- 1
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 1
- Soundness
- 2
Read review
Paper summary
The paper investigates Online Semi-infinite Linear Programming problem. Instead of the exact violation bound considered in the prior works, this works looks at OSILP under weaker projected bound to regulate constraint violation. For regret dependence, it transitions from dependence on the number of original/discretized constraints to the number of basis functions in our reduced dual representa- tion. Regarding horizon dependence of regret, it maintains and regret under stochastic input model, and improve fropm to under random permutation model. This work specifically highlights its use of nonnegative dual approximation as a central contribution that leads to new results that depend on 'm' instead of 'q'.
Critical strengths
- Clear mathematical formulation and presentation of theoretical guarantees.
The paper does a good job of formally presenting its assumptions, algorithms, and corresponding theoretical guarantees. I appreciate that the mathematical exposition is relatively detailed and readable rather than overly compressed. Although I have not verified every proof in detail, the mathematical development appears reasonably well organized, and the authors provide sufficient detail for readers to examine their arguments. This is a positive aspect of the paper, as it makes the proposed framework and its theoretical claims more accessible.
- Potentially useful approach to reducing the dimensionality of online LP problems.
The proposed nonnegative function-approximation framework reduces the dual representation from the original constraint dimension (m) to a basis dimension (q). This is a potentially useful direction for handling problems with a large or infinite number of constraints. The authors also establish regret guarantees under both stochastic and random-permutation input models, together with an improved stochastic regret bound under additional assumptions. These results suggest potential computational and theoretical benefits, although, as discussed below, I remain uncertain about the extent of the improvement over existing work and the practical significance of the relaxed feasibility guarantees.
Critical weaknesses
- Insufficient motivation for the problem setting and, more importantly, the relaxed constraint-violation guarantee.
The motivation in the Introduction is difficult to follow. The paper lists several potential applications, including robust resource allocation, distributionally robust optimization, and safety-constrained control, but provides neither supporting citations nor concrete examples explaining why these applications are naturally modeled as online semi-infinite linear programs. Although the abstract briefly characterizes semi-infinite constraints, the Introduction does not sufficiently connect this concept to the proposed applications. Similarly, the statement that the main challenge is "dual dimensionality" appears before the underlying difficulty has been adequately motivated.
More importantly, one of the central distinctions between this work and the prior literature, as indicated in Table 1, is the transition from controlling exact constraint violation to controlling a weaker projected constraint violation. However, the paper does not sufficiently explain why this relaxation is meaningful or desirable. While Proposition 1 establishes a connection between projected and exact violation under additional approximation conditions, the implications of these conditions and the trade-off between approximation quality, dimensionality reduction, and feasibility are not adequately discussed.
This is consequential to my assessment because the paper compares its (q)-dependent guarantees with existing (m)-dependent guarantees that control a stronger notion of feasibility. Without a clearer justification of the weaker guarantee and the circumstances under which it remains useful, it is difficult to assess whether the proposed framework constitutes a meaningful improvement or primarily addresses a different, relaxed problem.
- Insufficient explanation of technical novelty and contributions relative to prior work.
Although the paper clearly states its mathematical results, I found it difficult to identify exactly what is technically new and why the results represent a significant advance over existing literature.
The "Relation to prior work" paragraph in the Introduction provides only a broad overview and does little to explain the comparisons in Table 1. A more detailed literature review is provided in Appendix A, but the main text does not adequately distinguish the technical challenges addressed here from those addressed in prior work. In particular, given that comparable dependence on the time horizon (T) has already been achieved under other formulations, the paper should better explain the significance of replacing the dependence on (m) with (q), especially considering the simultaneous weakening of the feasibility guarantee.
The overall organization also makes the contributions difficult to follow. There is no clear roadmap explaining how the results in Sections 3–6 fit together. Furthermore, the main text provides little high-level proof intuition or discussion of the technical difficulties involved. Consequently, it is difficult to determine which arguments require genuinely new techniques and which follow from adapting existing approaches to the projected formulation.
The improved regret guarantee in Section 6 raises a related concern. The paper introduces an additional linear error-bound assumption to obtain logarithmic stochastic regret through the Accelerate-Then-Refine algorithm. However, the motivation and practical relevance of this additional condition are not sufficiently established.
I am generally open to theoretical contributions that investigate existing problems under modified assumptions or alternative performance measures, provided that these modifications are well motivated and lead to meaningful insights. Unfortunately, the current presentation does not sufficiently establish this. The lack of clarity regarding the precise technical advances, together with the limited motivation for the modified conditions, substantially weakens my assessment of the paper's significance.
Questions for authors
- What is a concrete application that motivates the semi-infinite formulation and the use of projected constraint violation?
Could the authors provide a concrete example demonstrating why the original problem requires a semi-infinite constraint system, how the proposed nonnegative basis approximation applies to it, and why controlling projected rather than exact constraint violation would be meaningful in that setting?
- How should the theoretical guarantees in Table 1 be interpreted relative to existing results?
Is the replacement of (m) by (q), together with a weaker projected feasibility guarantee, intended to represent a direct improvement over prior work or a result for a different problem formulation? In particular, how should one understand the trade-off between the basis dimension (q), the approximation error, and exact constraint violation? Under what conditions can the proposed algorithms simultaneously achieve a substantial dimensionality reduction and meaningful guarantees for the original constraints?
- What are the main technical contributions beyond applying existing online LP techniques to the projected problem?
Could the authors identify the principal technical obstacles that arise from the proposed formulation and explain which results or proof arguments require genuinely new techniques? A clearer distinction between new theoretical insights and adaptations of existing algorithms would help me assess the novelty and significance of the work.
- What motivates the additional assumption underlying the logarithmic regret result in Section 6?
Could the authors provide examples of problem settings in which the linear error-bound assumption (Assumption 4) is satisfied, and explain how restrictive this condition is? This would help clarify the scope and significance of the improved regret guarantee.