Constrained Online Learning with Noisy Constraint Values

arXiv:2609.06921v1 Announce Type: new Abstract: We study constrained online convex optimization with adversarial constraints when constraint values and gradients are observed through unbiased noise. Gaussian value noise of standard deviation sigma yields a worst-case lower bound of Omega(min{sigma,1}T/log^7T) on the maximum of expected regret and expected hard violation, even with known gradients. This rules out any jointly O(T^{1-elta}) guarantee for fixed elta>0 and fixed positive noise level. We therefore study budget violation: the largest cumulative overspend over any window within a fixed horizon. We introduce LEDGER, which tracks observed net consumption in a nonnegative balance and sets constraint weights before the current feedback noise. Under common feasibility and conditional finite-variance feedback, for fixed problem parameters, LEDGER achieves O(sqrt T/V) expected regret and O(sqrt V,T^{3/4}+sigmasqrt T) expected budget violation for Vin[T^{-1/2},1]. This gives the pair (O(sqrt T),O(T^{3/4})) at V=1 and (O(T^{2/3}),O(T^{2/3})) at V=T^{-1/6}, without a Slater condition. The budget-focused endpoint V=T^{-1/2} gives (O(T),O(sqrt T)). The same update yields O((1+E[P_T])sqrt T/V) expected dynamic regret for predictable feasible comparator paths, without common feasibility or path-length input. Its budget bound instead depends on the shortest feasible path, up to a dimension factor.

Source: arXiv cs.LG | 2026-09-09