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-\delta})$ guarantee for fixed $\delta>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}+\sigma\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.

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-\delta})$ guarantee for fixed $\delta>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}+\sigma\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.

Machine Learning (cs.LG); Artificial Intelligence (cs.AI); Optimization and Control (math.OC)

arXiv:2609.06921 [cs.LG]

(or arXiv:2609.06921v1 [cs.LG] for this version)

https://doi.org/10.48550/arXiv.2609.06921 Focus to learn more arXiv-issued DOI via DataCite (pending registration)

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.

analiza aiqbench

Constrained Online Learning with Noisy Constraint Values

Subiecte conexe