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 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 Ω(min{σ,1}T/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.
Related
- Chance-Constrained Personalized LLM Routing with Online Preference Learning
- Online Optimization with Unknown Time-Varying Parameters Using Noisy Gradient Measurements
- Energy-constrained two-way capacity bounds for noisy Gaussian channels
- Observability as a constraint qualification for a nonsmooth bilevel PDE-constrained problem
- A constraint dissolving method for generally constrained optimization over a nonconvex set
BibTeX
@misc{aggarwal2026constrained,
title = {{Constrained Online Learning with Noisy Constraint Values}},
author = {Vaneet Aggarwal},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.06921},
eprint = {2609.06921},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.06921},
}
RIS
TY - UNPB
TI - Constrained Online Learning with Noisy Constraint Values
AU - Vaneet Aggarwal
PY - 2026
DA - 2026/09/13
PB - arXiv
DO - 10.48550/arxiv.2609.06921
UR - https://arxiv.org/abs/2609.06921
AB - 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 Ω(min{σ,1}T/log^2 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.
ER -