# Constrained Online Learning with Noisy Constraint Values

arXiv: https://arxiv.org/abs/2609.06921 · HTML: https://mlsanity.com/paper/2609.06921/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 29 of its 46 references that are in the map.
- First posted on arXiv 7 Sep 2026.

## Builds on (most cited first, 29 of 29)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Bandits with Knapsacks](https://mlsanity.com/paper/1305.2545/) (2013)
- [Adaptive Online Learning in Dynamic Environments](https://mlsanity.com/paper/1810.10815/) (2018)
- [Online Convex Optimization with Stochastic Constraints](https://mlsanity.com/paper/1708.03741/) (2017)
- [Bandits with concave rewards and convex knapsacks](https://mlsanity.com/paper/1402.5758/) (2014)
- [Adversarial Bandits with Knapsacks](https://mlsanity.com/paper/1811.11881/) (2018)
- [Adaptive Algorithms for Online Convex Optimization with Long-term Constraints](https://mlsanity.com/paper/1512.07422/) (2015)
- [Online Convex Optimization with Time-Varying Constraints](https://mlsanity.com/paper/1702.04783/) (2017)
- [Online convex optimization for cumulative constraints](https://mlsanity.com/paper/1802.06472/) (2018)
- [A Unifying Framework for Online Optimization with Long-Term Constraints](https://mlsanity.com/paper/2209.07454/) (2022)
- [Regret and Cumulative Constraint Violation Analysis for Online Convex Optimization with Long Term Constraints](https://mlsanity.com/paper/2106.05135/) (2021)
- [Optimal Algorithms for Online Convex Optimization with Adversarial Constraints](https://mlsanity.com/paper/2310.18955/) (2023)
- [Online Primal-Dual Mirror Descent under Stochastic Constraints](https://mlsanity.com/paper/1908.00305/) (2019)
- [Regret and Cumulative Constraint Violation Analysis for Distributed Online Constrained Convex Optimization](https://mlsanity.com/paper/2105.00321/) (2021)
- [Chasing Convex Bodies Optimally](https://mlsanity.com/paper/1905.11968/) (2019)
- [Safe Convex Learning under Uncertain Constraints](https://mlsanity.com/paper/1903.04626/) (2019)
- [Chasing Convex Bodies with Linear Competitive Ratio](https://mlsanity.com/paper/1905.11877/) (2019)
- [Safe Online Convex Optimization with Unknown Linear Safety Constraints](https://mlsanity.com/paper/2111.07430/) (2021)
- [Simultaneously Achieving Sublinear Regret and Constraint Violations for Online Convex Optimization with Time-varying Constraints](https://mlsanity.com/paper/2111.07707/) (2021)
- [An Optimistic Algorithm for Online Convex Optimization with Adversarial Constraints](https://mlsanity.com/paper/2412.08060/) (2024)
- [BanditQ: Fair Bandits with Guaranteed Rewards](https://mlsanity.com/paper/2304.05219/) (2023)
- [No-Regret Learning Under Adversarial Resource Constraints: A Spending Plan Is All You Need!](https://mlsanity.com/paper/2506.13244/) (2025)
- [A Geometric Approach to Constrained Online Learning](https://mlsanity.com/paper/2605.21107/) (2026)
- [A Unified Framework for Analyzing Meta-algorithms in Online Convex Optimization](https://mlsanity.com/paper/2402.08621/) (2024)
- [Universal Dynamic Regret and Constraint Violation Bounds for Constrained Online Convex Optimization](https://mlsanity.com/paper/2510.01867/) (2025)
- [BAGEL: Adversarially Constrained Online Convex Optimization under Separation Oracle Access](https://mlsanity.com/paper/2502.16744/) (2025)
- [Breaking the O(√T) Cumulative Constraint Violation Barrier while Achieving O(√T) Static Regret in Constrained Online Convex Optimization](https://mlsanity.com/paper/2603.20671/) (2026)
- [Constrained Online Convex Optimization without Slater's Condition](https://mlsanity.com/paper/2606.31480/) (2026)
- [Online Convex Optimization with Dueling Feedback](https://mlsanity.com/paper/2608.15050/) (2026)

## Abstract (arXiv)

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 O(√ T) expected regret and O(√Tlog(eT)) 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 O(√ T) budget bound instead forces linear regret. In contrast, fixed positive Gaussian value noise yields a joint regret--hard-violation lower bound of Omega(minσ,1T/log2 T), 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.