Constrained Gradient Equilibrium: Approachability under Locally Constrained Adversaries
Abstract
Gradient 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. We first show that constrained GEQ (CGEQ) can be impossible even under simple and slowly varying constraints, motivating imposing local temporal structure on the adversary. We then develop an approachability framework for CGEQ under locally constrained adversaries, and obtain necessary and sufficient characterizations in the spirit of classical Blackwell approachability. Beyond these theoretical characterizations, we provide an algorithmic principle that converts window-wise no-regret learners into CGEQ algorithms under a local feasibility condition with margin. Experiments on synthetic and real data demonstrate that the resulting algorithms perform strongly in both achieving GEQ and respecting the constraints.
Related
- Unit commitment constrained Nash equilibrium in power markets
- A Safeguarded Projected-Gradient Framework for Complementarity Constrained Least Squares Problems
- A Stochastic Proximal-Gradient Method for Regularized Generally Constrained Continuous Optimization
- How to Make the Gradient Mapping Small for Constrained Stochastic Min-Max Problems and Beyond
- Budget-Constrained Multi-Consensus Decentralized Gradient Descent
BibTeX
@misc{zhang2026constrained,
title = {{Constrained Gradient Equilibrium: Approachability under Locally Constrained Adversaries}},
author = {Kaicheng Zhang and Lujing Zhang and Yifei Pang and Yuxiao Wen and Zhun Deng and Yanjun Han},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.33985},
eprint = {2610.33985},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.33985},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Constrained Gradient Equilibrium: Approachability under Locally Constrained Adversaries
AU - Kaicheng Zhang
AU - Lujing Zhang
AU - Yifei Pang
AU - Yuxiao Wen
AU - Zhun Deng
AU - Yanjun Han
PY - 2026
DA - 2026/10/25
PB - arXiv
DO - 10.48550/arxiv.2610.33985
UR - https://arxiv.org/abs/2610.33985
AB - Gradient 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. We first show that constrained GEQ (CGEQ) can be impossible even under simple and slowly varying constraints, motivating imposing local temporal structure on the adversary. We then develop an approachability framework for CGEQ under locally constrained adversaries, and obtain necessary and sufficient characterizations in the spirit of classical Blackwell approachability. Beyond these theoretical characterizations, we provide an algorithmic principle that converts window-wise no-regret learners into CGEQ algorithms under a local feasibility condition with margin. Experiments on synthetic and real data demonstrate that the resulting algorithms perform strongly in both achieving GEQ and respecting the constraints.
ER -