{"id":"arxiv/2609.06921","url":"https://arxiv.org/abs/2609.06921","tags":["cs.LG","cs.AI","math.OC"],"score":0,"title":"Constrained Online Learning with Noisy Constraint Values","domain":"cs.LG","source":"arxiv","authors":["Vaneet Aggarwal"],"reviews":0,"subject":"cs.LG","summary":"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(\\sqrt T)$ expected regret and $O(\\sqrt{T\\log(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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-09-07","reactions":{}}