acceptodds
Under review as a conference paper at ICLR 2027

Constrained Online Learning with Noisy Constraint Values

Abstract

We study constrained online convex optimization with adversarial constraints and conditionally unbiased, finite-variance observations of constraint values and gradients. Under common feasibility, our \LEDGER algorithm attains expected regret and expected budget violation, the largest cumulative overspend over any window. It uses a reflected exponential potential, clipped signed observations, and predictable adaptive regularization, with one feedback triple and one projection per round. Neither a Slater condition, independence between feedback channels, nor an absolute constraint-value bound is needed. A Gaussian testing lower bound proves that the budget rate has optimal horizon dependence under square-root regret at fixed positive noise, including the logarithm. The same obstruction holds for terminal violation, so the logarithm is not a cost of maximizing over windows; an budget bound instead forces linear regret. In contrast, fixed positive Gaussian value noise yields a joint regret–hard-violation lower bound of , even with exact gradients in one dimension. The hard-violation construction matches arbitrarily many moments while preserving a feasible-endpoint gap and constant endpoint probabilities. Together, the bounds separate uncertainty about hard feasibility from learnable signed budgets. Deterministic restarts remove the horizon input without changing either upper rate.

Primary area:
optimization
Keywords:
Constrained online optimization, noisy feedback, online convex optimization, budget violation, adversarial learning

Reviews

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

The paper studies online convex optimization when constraint values and first-order feedback are noisy. It assumes conditionally finite-variance observations of constraint values. It compares three ways of measuring violations: adding up the positive violation on every round, measuring the signed budget at the end, and taking the largest signed-budget violation over any time window. The comparison is against a fixed feasible action on every round.

The paper proves a near-linear lower bound for joint regret and roundwise hard violation. It also shows that square-root regret requires budget violation of at least order \sqrt{T}logT when noise is fixed and positive. Its algorithm, LEDGER, matches this horizon dependence: expected regret (O(\sqrt{T}) and expected maximum-window violation (O(\sqrt{T} logT). LEDGER combines clipping, a reflected queue, a suitable potential, and an adaptive regularizer.

Critical strengths
  1. The lower and upper bounds explain a meaningful difference between the violation measures. The hard-violation construction shows why noisy constraint values make it difficult to control positive violations on every round. Proposition 3.2 shows that terminal violation alone requires the logarithmic penalty under square-root regret. Together with Theorem 4.1, these results give a clear account of what is achievable for fixed problem parameters.

  2. The analysis handles the difficulties caused by finite-variance noise. The algorithm allows feedback components within a round to be dependent, handles the queue's reflection boundary, and avoids assuming a two-sided bound on constraint values. It also accounts explicitly for clipping, regularization, and the noise martingale when transferring the queue bound to true violation.

Critical weaknesses

Two limitations affect the significance of the result. The matching rates concern horizon dependence for fixed parameters and positive noise; they do not establish sharp dependence on all parameters at once. Also, the finite-horizon constants can be too large to be useful. Appendix C.6 gives a bound of about 61,795 while the trivial bound is 10,000. The authors acknowledge both limitations. The results should therefore be presented as asymptotic guarantees, without suggesting that they provide useful safety certificates at moderate horizons.

Questions for authors
  1. Appendix C.6 gives a bound of about 61,795 where the trivial bound is 10,000. Using the existing analysis, at roughly what horizon does the bound first improve on the trivial one for the same parameters? Which terms account for most of the gap? This would help me judge whether the result has useful finite-horizon implications in addition to its asymptotic contribution.

  2. The matching claim is stated for fixed positive noise. Could you place the lower and upper bounds side by side with their noise dependence explicit, and identify the regimes in which they match or leave a gap as noise decreases with the horizon? This would help clarify how broadly the optimality claim should be read.

  3. Could the authors identify the specific step in the maximum-window proof that cannot be obtained by directly combining the cited adaptive-regularization method with a standard reflected-queue and martingale argument? In particular, which obstacle requires the choice of potential or the treatment of clipping? A precise comparison would help me assess the depth of the technical contribution.

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

The paper studies the problem of adversarial online convex optimization with constraints. In particular it considers the case in which the learner receives conditionally unbiased, noisy observations of the loss gradient, constraint gradient, and constraint value. The noise is assumed to have bounded conditional second moments, with a known upper bound σ2\sigma^2 on the conditional variance of the constraint-value noise.

The paper defines three metrics of constraints violations, one that consider only the positive resource consumption cumulatively across alll time horizon TT that they call ICV, one that considers the violation on the maximum cumulative resource consumption over a continuous window of round WCV, and on that consider the cumulative sum over the entire time horizon, allowing for cancellation, that they call CCV.

The paper main contributions are double:

  • an upper algorithm Legder, that, with known upper bound on the Lipschitz constant G^\hat{G} and known standard deviation σ\sigma produce an expected regret of order O(T)O(\sqrt{T}) against all fixed deterministic actions that are almost surel7 feasible at each round, and expected WCV of O(Tlog⁡(T)).O(\sqrt{T\log(T)}).
  • a series of of lower bounds dependent on the constraint violation metric used:
    • a lower bound of Ω(T/log2(T))\Omega(T/log^2(T)) on the maximum between regret and ICV
    • a lower bound of $\Omega(\sqrt{T\log(T)}) $ on the maximum between regret and WCV
    • a lower bound proving trhat any algorithm that achieves worst case expect regret O(T)O(\sqrt{T}) will suffer WCV of Ω(Tlog⁡(T))\Omega(\sqrt{T\log(T)})
Critical strengths
  • The model of noisy observations in an adversarial environment is well explained and it is an interesting setting
  • The results are discussed extensively, and the paper provides both an algorithmic approach and formal lower bounds that justify the optimality of the proposed algorithm.
  • The discussion of different notions of constraints is a big strength of the paper
Critical weaknesses
  • See questions
Questions for authors
  • The algorithm requires knowledge of σ2\sigma^2. For what I understand, σ2\sigma^2 is only an upper bound on the conditional second moment of ϵt\epsilon_t. However, the guarantees depend on the chosen σ2\sigma^2, so being very conservative is costly in term of regret. Is prior knowledge of this parameter necessary? What happens if the chosen σ2\sigma^2 is too small? Is designing an algorithm that do not require prior knowledge of σ2\sigma^2 an open questions, or is such algorithm known to be impossible?
Reviewer_WL2hOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
1
Soundness
3
Read review
Paper summary

The paper studies constrained online convex optimization with adversarial constraints and noisy observations of constraint values and gradients. The paper presents LEDGER, an algorithm achieving O(T)O(\sqrt{T}) expected regret and O(Tlog⁡T)O(\sqrt{T\log T}) expected max-window constraint violation under conditional finite-variance feedback and common feasibility. The authors establish a matching budget-violation lower bound for fixed positive Gaussian value noise, as well as a nearly linear lower bound for cumulative per-round positive violation.

Critical strengths
  • The distinction between hard violation and signed budget violation under noisy constraint-value feedback is interesting. The lower bounds in Theorem 3.1 and Proposition 3.2 provide a useful characterization of what cannot be achieved.

  • Theorem 4.1 allows dependent feedback channels, bounded conditional second moments, and adversarially varying constraints without requiring a Slater condition.

  • The coupling of clipped signed observations, a reflected exponential potential, and adaptive regularization is interesting. The matching upper and lower horizon dependence for budget violation strengthens the theoretical contribution.

Critical weaknesses
  • The paper is very difficult to follow. It introduces several technical constructions in rapid succession without sufficiently developing the overarching intuition. Many paragraphs read like collections of loosely connected statements, and the overall presentation feels excessively compacted. As a result, understanding the main ideas and their connections required a lot of effort, and this paper took me nearly four times as long to review compared to other papers I received. I believe the paper would benefit a lot from a substantial rewrite, with a clearer narrative, more intuition, and a better separation between the central arguments and technical details. Some of the more technical material could be moved to the appendix to make room for these improvements.

  • The related work section is only one paragraph. The Appendix includes a much richer (and well-written!) related work section. You can use a condensed version of it in the main paper, and position and compare your work accordingly. Also, interestingly, there is work on Safe Online Learning (see, e.g., [1-2]), this could be added to the "Safe Learning" paragraph in the related work, and discussing those and contrasting with your work would make the paper richer.

  • The achievable guarantee concerns signed max-window violation rather than hard violation. Although this is introduced in other work, it is not very common. The paper would benefit from a clearer discussion of applications where compensation across rounds is appropriate.

  • the assumption requiring a fixed comparator to be feasible on every round is restrictive, particularly with time-varying constraints, and there are prior work that don't assume it. Moreover, for this reason, some work resort to dynamic regret all together, which seems more natural in this case and could alleviate the restrictive common feasibility assumption.

  • The dependence on the noise magnitude does not seem to be tight. In particular, the upper bound retains a log⁡T\sqrt{\log T} factor even as σ→0\sigma\to 0, and the analysis does not seem to establish a smooth interpolation between the noisy and noiseless regimes.

[1] Safety in the Face of Adversity: Achieving Zero Constraint Violation in Online Learning with Slowly Changing Constraints, AISTATS 2025.

[2] Safe Online Convex Optimization with First-Order Feedback, ACC 2024.

Questions for authors
  1. Can the authors provide a concrete resource-allocation (or similar) example illustrating when maximum-window budget violation is the appropriate metric, rather than hard/terminal violation?

  2. Can the analysis be extended to the dynamic regret setting (under appropriate regularity conditions like bounded comparator path-length), and can the common feasibility assumption be relaxed?

  3. Could the authors address the dependence on the noise in the bound, and whether a "noise-adaptive" guarantee is possible? Can the analysis or algorithm be refined to adapt to small constraint-value noise, particularly as σ→0\sigma\to 0?

Reviewer_4FySOpenReview ↗
Rating
1
Confidence
4
Informativeness
2
Presentation
1
Soundness
1
Read review
Paper summary

This paper studies constrained online convex optimization with adversarial losses and constraints. In each round, the learner observes one noisy sample of the loss gradient, the constraint gradient, and the constraint value. The noise is conditionally unbiased and has bounded conditional variance. The authors first show that, under Gaussian value noise, the larger of expected regret and expected hard violation is at least Ω(min⁡{σ,1} T/log⁡2T)\Omega(\min\{\sigma,1\}\,T/\log^2 T). They then consider budget violation, which is the largest cumulative violation over any time window. For this metric, they propose an algorithm called LEDGER, which is based on a virtual queue. LEDGER achieves O(T)O(\sqrt{T}) expected regret and O(Tlog⁡T)O(\sqrt{T\log T}) expected budget violation. A Gaussian testing argument shows that this budget rate is optimal in TT for fixed σ>0\sigma>0.

Critical strengths

The upper and lower bounds of the algorithm match in TT for fixed σ>0\sigma>0. The paper also shows a clear gap between hard violation and budget violation.

Critical weaknesses
  1. The paper is very hard to understand. Notation is introduced at a high rate, and the core intuition appears only in Section 4.3, mixed with technical details. The paper repeatedly lists assumptions that it does not need, and the same caveats appear in the abstract, the introduction, Section 4.5, and the appendices. The AI Use Statement says that generative AI tools were used in revision, and much of the text reads as machine-polished rather than written to explain ideas. The paper needs a substantial rewrite for clarity.

  2. The motivation for the problem setting is weak. The paper does not give a concrete application where (i) the constraints change adversarially, (ii) the constraint values are observed only through one unbiased, finite-variance sample per round, and (iii) one fixed action is feasible in every round. The paper also has no experiments. It is therefore unclear whether this setting is practically relevant or mainly technically convenient.

  3. The choice of violation metric appears to be a fallback. The paper first proves that hard violation cannot be controlled, and then switches to budget violation, where underspending can offset overspending. As a result, the positive result is for a weaker metric that seems chosen because it is tractable, not because an application needs it. This metric is also not new (Sinha and Vaze, 2024, Sec. 3). The paper does not explain why it is the right measure of constraint satisfaction.

  4. The dependence on the noise level σ\sigma is not tight. The upper bound scales with Bv=L2+σ2B_v=\sqrt{L^2+\sigma^2}, which does not go to zero as σ→0\sigma\to 0. With exact feedback, O(T)O(\sqrt{T}) violation is achievable (Sarkar and Sinha, 2026). However, LEDGER still gives O(Tlog⁡T)O(\sqrt{T\log T}) in this limit, and its constants do not decrease. The lower bound, on the other hand, scales with σ\sigma. So the claimed optimality holds only for fixed σ>0\sigma>0, and the algorithm does not adapt between the noisy and exact settings.

  5. The algorithm requires prior knowledge of σ\sigma. The step size α\alpha and the regularizer rtr_t depend on BvB_v, so the algorithm must know σ\sigma, G^\hat{G}, and DD in advance. The doubling trick only removes the need to know TT. The paper does not give a variant that adapts to σ\sigma, and it does not study what happens when σ\sigma is misspecified. For example, if σ\sigma is underestimated, the clipping-bias bound in Lemma C.1 no longer holds.

Questions for authors

None

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.