Paper characterizes constrained gradient equilibrium under local adversaries
Original title: Constrained Gradient Equilibrium: Approachability under Locally Constrained Adversaries
Constrained gradient equilibrium can fail under simple constraints unless the adversary is locally restricted.
The paper studies when time-averaged gradients can vanish for a constrained online learner facing an adversary. It shows constrained gradient equilibrium can be impossible even with simple, slowly varying constraints, then gives necessary and sufficient approachability conditions under locally constrained adversaries. An algorithmic principle converts window-wise no-regret learners into such algorithms when a local feasibility condition with margin holds. Experiments on synthetic and real data are reported to achieve equilibrium while respecting constraints.
- Gradient equilibrium requires time-averaged gradients along the learner's path to vanish.
- Characterizations follow the spirit of classical Blackwell approachability.
- The conversion needs a local feasibility condition with margin.
- Reported experiments use both synthetic and real data.
From the original article
1 min read at arxiv.orgGradient equilibrium (GEQ) is a recent framework in online learning that requires the time-averaged gradients along the learner's trajectory to vanish. We study GEQ when the learner is constrained and ask when such an equilibrium remains achievable in an adversarial environment.
By Kaicheng Zhang · arxiv.org
A short excerpt; the article and its images belong to the publisher. Summary, key facts and assessment above are AI-written from the article and can be wrong.