New method controls online learning under noisy constraints reliably
Constrained Online Learning with Noisy Constraint Values
Machine LearningArtificial Intelligence
Summary
The paper looks at how to make decisions repeatedly when constraints are not perfectly known because of random noise. The authors show that accurate performance in such noisy settings is limited, so they focus instead on controlling how much the constraints are exceeded over time. They introduce a method called LEDGER that balances learning and constraint handling effectively, even without strong assumptions often needed in previous work. Their approach provides guarantees on both performance and constraint violations under common conditions.
What this means in practice
- •For network schedulers: Manage data transmission schedules with uncertain constraints to minimize delays while keeping resource overuse under control.
- •For smart grid operators: Adjust power distribution decisions in real time with noisy feedback on consumption limits to avoid overloads efficiently.
Authors
Vaneet Aggarwal
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 $σ$ yields a worst-case lower bound of $Ω(\min\{σ,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-δ})$ guarantee for fixed $δ>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}+σ\sqrt T)$ expected budget violation for $V\in[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.