acceptodds
Under review as a conference paper at ICLR 2027

Online Semi-Infinite Linear Programming via Nonnegative Function Approximation

Abstract

We study online semi-infinite linear programming, a sequential resource-allocation problem in which the decision space is finite dimensional but the constraints are indexed by a large, possibly infinite, set. This setting captures online allocation problems with continuously indexed safety, robustness, coverage, or moment constraints. Classical online linear-programming algorithms maintain one dual variable per constraint, and their regret guarantees typically scale with the number of constraints; this dependence becomes prohibitive in semi-infinite regimes. We propose a nonnegative function-approximation approach that represents the dual measure using \(q\) nonnegative basis functions. This yields a tractable projected problem whose regret bounds depend on the basis dimension \(q\), rather than on the number of original constraints. We develop first-order primal–dual algorithms for stochastic and random-permutation input models. Under stochastic arrivals, our algorithms achieve \(O(qT)\) regret, together with sublinear projected constraint violation. Under random permutation arrivals, we obtain a \(\widetilde O(qT)\)-type regret bound. We further give an accelerate-then-refine algorithm that improves the stochastic regret to \(O(q\log T)\) under additional conditions. Experiments on large-scale instances show that the proposed basis-based methods remain stable as the number of constraints grows, while standard online LP methods degrade substantially.

Primary area:
optimization
Keywords:
Online Linear Programming

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_9xWeOpenReview ↗
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 TT dependence of regret, it maintains log⁡T\log T and T\sqrt{T} regret under stochastic input model, and improve fropm log⁡TT\log T \sqrt{T} to T\sqrt{T} 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
  1. 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.

  1. 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
  1. 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.

  1. 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
  1. 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?

  1. 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?

  1. 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.

  1. 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.

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

The paper studies online semi-infinite linear programming through nonnegative basis approximations of dual variables. It develops low-dimensional primal-dual algorithms with regret and projected-feasibility guarantees, plus a conditional transfer to the original constraints.

Critical strengths

S1. Reducing the number of maintained dual variables is a natural approach to handling large constraint families. The nonnegative basis construction is easy to understand, and Lemma 1 clearly explains why the projected problem upper-bounds the original offline optimum.

S2. The paper explains why the regularizer stabilizes the dual iterates and makes the exact infinite-dimensional dual strongly convex, leading to a unique and continuous optimizer. Lemma 2 is a nice technical contribution.

S3. The proposed methods appear more stable than the discretized Simple-GD baseline as the number of constraints grows.

Critical weaknesses

W1. The paper combines standard online LP dual-price ideas with nonnegative basis approximation of the dual. The technical tools,projected subgradient, mirror descent, and regularized duals, are standard. The main novelty is the reduced-dual SILP formulation, which is interesting but incremental. The authors should better illustrate which proof techniques are new.

W2. The guarantees mainly concern projected feasibility. Proposition 1 transfers them to original constraints, but the paper does not quantify how its approximation error depends on basis dimension. Without a q−ϵtest−Tq-\epsilon_{test}-T trade-off for concrete coefficient classes, it remains unclear whether accurate original feasibility preserves the advertised regret and dimensional advantages.

W3. The O(qlog⁡T)O(q\log T) result relies on a linear error bound (sharpness/weak sharp minima) for the regularized projected dual. This is stronger than standard strong convexity and is not shown to hold for the paper's hinge-type objective. The authors need to provide meaningful examples satisfying such an assumption, explain whether the distributions used in experiments qualify, and clarify how its constant is obtained and whether it remains uniform as the regularization parameter changes with TT.

W4. Table 1 compares different feasibility metrics, where prior work controls original finite-system constraints, whereas the proposed bounds are on projected constraints. Although this distinction is disclosed, the authors should emphasize that original SILP feasibility requires additional approximation assumptions, limiting direct comparisons of the reported rates and dimension dependence.

W5. The projected problem has a larger feasible set, so it may allow higher rewards through violations of original constraints. The experiments should report original maximum constraint violation alongside projected violation, using the same original offline benchmark for every method. Otherwise, the practical significance of lower regret is difficult to assess.

W6. The paper does not give a principled way for selecting the basis family and dimension qq, or for bounding the resulting approximation error ϵtext\epsilon_{text}. Since the original feasibility guarantees depend critically on these values, a concrete construction with an explicit approximation bound would clarify the theory's practical applicability.

Questions for authors

Please refer to W1-W6.

Reviewer_R8JCOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies online semi-infinite linear programming by approximating the infinite-dimensional dual space using a finite number of nonnegative basis functions. The authors then establish a connection between the approximated problem and the original semi-infinite problem and develop online algorithms with regret and constraint violation guarantees for the approximated problem.

Critical strengths

The problem of online optimization with infinitely many constraints is interesting and potentially important. It would be great if the authors could elaborate more on the applications.

The proposed first-order method is computationally appealing, especially given that the number of constraints is infinite.

Critical weaknesses

My main concern is the novelty of the paper. Once the semi-infinite LP is approximated by a finite-dimensional LP, the proposed algorithms and their analyses appear to largely follow existing online LP methods. The main contribution therefore seems to lie in the approximation itself.

However, the usefulness of this approximation heavily relies on Assumption 2, particularly part (b), which appears to be very strong and potentially unrealistic for general function classes. The paper does not provide sufficient justification for when this assumption holds or how large (q) needs to be to achieve a desired approximation accuracy. Without such guarantees, it is unclear whether the proposed approach offers a meaningful improvement for the original semi-infinite problem.

Questions for authors
  1. It seems the inner part of (2) is not necessarily equivalent to the maximum constraint violation. I guess the authors might need S to be a subset of the support of \sigma, right?

  2. I wonder whether Assumption 2 is necessary. It seems very strong, but the necessity is not justified. Can the authors elaborate more on the necessity? Alternatively, could the authors show some upper bound of q to let Assumption 2 hold?

Some minor points:

a. The definition of the <u,Ax(\pi) - b> is used on parge 3 but defined on page 4. b. By optimizer, do you mean the optimal solution?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.